Uhh well, I guess this is gonna be a banal question...
I'd have a question about STLPort containers; namely, which is good for what. I was searching online for a while, but there were times I found some contradicting sites and that puzzled me...
I'm somewhat positive that Vectors are good unless you are adding/removing values a lot, in which case they can be slow. List, queue and double queue is perhaps a bit faster but also cost more memory than Vector.
That leaves maps or hash_maps for storing things that can change (relatively) a lot, right? Somewhere I read that hash_maps can look up data quicker than maps. Is that so? And is something correct from all these things written here?
Hope is the first step on the road to disappointment.
There's a great explanation in Bruce Eckel's free C++ book Volume 2 (http://64.78.49.204/). I quote:
From a design standpoint, all you really want is a sequence that can be manipulated to solve your problem. If a single type of sequence satisfied all your needs, there would be no reason to have different types. You need a choice of containers for two reasons. First, containers provide different types of interfaces and external behavior. A stack has an interface and a behavior that is different from that of a queue, which is different from that of a set or a list. One of these might provide a more flexible solution to your problem than the other, or it might provide a clearer abstraction that conveys your design intent. Second, different containers have different efficiencies for certain operations. Compare a vector to a list, for example. Both are simple sequences that can have nearly identical interfaces and external behaviors. But certain operations can have radically different costs. Randomly accessing elements in a vector is a constant-time operation; it takes the same amount of time regardless of the element you select. However, it is expensive to move through a linked list to randomly access an element, and it takes longer to find an element if it is farther down the list. On the other hand, if you want to insert an element in the middle of a sequence, it’s cheaper with a list than with a vector. The efficiencies of these and other operations depend on the underlying structure of the sequence. In the design phase, you might start with a list and, when tuning for performance, change to a vector, or vice-versa. Because of iterators, code that merely traverses sequences is insulated from changes in the underlying sequence implementation.
This is only a small part but it says the basics. Download his book and check out the whole chapter to discover more .
Last edited by bal on Mon Jan 03, 2005 10:54 am, edited 1 time in total.
I'll definitely echo Sinbad on Effective STL. It's a great read and has some handy charts on the covers to help with some quick decisions. Well worth the money.
It's really a matter of choosing what fits your situation. Vectors have constant time retrieval, but because you're copying an array insertion and removal are expensive (adding to the end is not necessarily as expensive, as vectors try to keep a little bit of extra allocated array space). So if you have a list that won't often change, vectors will offer fast iteration and retrieval.
Lists dont have expensive manipulation, but their retrieval is slower (retrieving in vectors is the equivelant of a pointer dereference, but lists have to iterate over every item before the one you're looking for).
Sets are sorted lists, with the benefit that they won't hold duplicates. If you need every item to be unique, then this is a good choice. Because it's sorted, performance for actions that involve searching for data (removing) can be faster.
Maps are associative, and you should use them if you need indexed data (they won't offer you any performance benefits over the lists for non-associative data). A good example is allowing the lookup of an item by a string for it's name. Hashmaps hash keys (indexes) before inserting a key-value pair, which makes retrieval much faster than a regular map. Both of these items only allow one value per key. A Multimap is a map that allows many values with the same key.
List and vector are interchangeable, as are map and hashmap (assuming you have a hash function for the key). The only distinction between them are the performance benefits they offer, some situations you'll pick one and some the other.
.
