type of container

[rmxhaha]

Hi
I need help with which type of container should I use...

I need the data in the array to be :
- sorted
- Quick for insert and delete as well ( cause the program tend to do that alot )
- The program iterate always from the index 0 to some point in array usually not until the end


Which container should I use ?

[coder777]

list:

http://www.cplusplus.com/reference/list/list/

[rmxhaha]

Seems that <list> is not sorted
so should I build my own insert sort or just build my own linked list ?

By The way, doubly linked list is just a waste of memory since I only iterate from the front not the back....

[Imadatobanisa]

Hey guys, I have a question about C++ standard containers...
The basic difference : vector,map and list????? And usage of map (if possible)??

[coder777]

list has a sort function:

http://www.cplusplus.com/reference/list/list/sort/

By The way, doubly linked list is just a waste of memory since I only iterate from the front not the back....

This one more pointer rather doesn't matter. it improves the speed when it comes to sorting.

But you may introduce your own singly linked list and sort on insert. It's sure not that hard

[ne555]

> list has a sort function:
I'm not sure what are you suggesting.
Merge sort is O(n lg n), it's a little costly for an insertion operation.

> so should I build my own insert sort
That'll be O(n), still too much.

I suggest you to use std::set for O(lg n) insert and erase.
I can't assure you that the iteration will be O(n), but it could not be higher than O(n lg n)


> (double linked list) improves the speed when it comes to sorting.
¿how so?

[coder777]

The basic difference : vector,map and list????? And usage of map (if possible)??

vector mimics an array. it's designed for fast access of the single element. insert/delete of a particular element is rather slow.

list is desinged for fast insert/delete of an element. accessing a particular element is not as fast as vector.

map is somehow a combination of vector and list. It's designed to access a particular element via a key. The key can be of any type (if the key was an index it would appear like a vector (not time wise of course)). It is sorted according to the key, hence the key needs to be comparabel with <

[TheIdeasMan]

I agree with ne555, set is sorted by default, and uses an AVL tree which gives efficient performance.

map also uses an AVL tree, and is not a combination of vector & list, in any way.

[Imadatobanisa]

What is AVL tree, TheIdeasMan?

[TheIdeasMan]

I did a google search of wiki AVL tree and came up with this:

http://en.wikipedia.org/wiki/AVL_tree

Also STL set - C++ set example is found here funnily enough LOL:

http://www.cplusplus.com/reference/set/set/

And STL map :

http://www.cplusplus.com/reference/map/map/

Also on wiki.

Part of learning programming should include the ability to do basic research with Google.