[c++] In which scenario do I use a particular STL container?
Here is a flowchart inspired by David Moore's version (see above) that I created, which is up-to-date (mostly) with the new standard (C++11). This is only my personal take on it, it's not indisputable, but I figured it could be valuable to this discussion:
I've been reading up on STL containers in my book on C++, specifically the section on the STL and its containers. Now I do understand each and every one of them have their own specific properties, and I'm close to memorizing all of them... But what I do not yet grasp is in which scenario each of them is used.
What is the explanation? Example code is much prefered.
I expanded on Mikael Persson's fantastic flowchart. I added some container categories, the array container, and some notes. If you'd like your own copy, here is the Google Drawing. Thanks, Mikael for doing the groundwork! C++ Container Picker
An important point only briefly mentioned so far, is that if you require contiguous memory (like a C array gives), then you can only use
array if the size is known at compile time.
string if you only need to work with character types and need a string, not just a general-purpose container.
vector in all other cases (
vector should be the default choice of container in most cases anyway).
With all three of these you can use the
data() member function to get a pointer to the first element of the container.
Look at Effective STL by Scott Meyers. It's good at explaining how to use the STL.
If you want to store a determined/undetermined number of objects and you're never going to delete any, then a vector is what you want. It's the default replacement for a C array, and it works like one, but doesn't overflow. You can set its size beforehand as well with reserve().
If you want to store an undetermined number of objects, but you'll be adding them and deleting them, then you probably want a list...because you can delete an element without moving any following elements - unlike vector. It takes more memory than a vector, though, and you can't sequentially access an element.
If you want to take a bunch of elements and find only the unique values of those elements, reading them all into a set will do it, and it will sort them for you as well.
If you have a lot of key-value pairs, and you want to sort them by key, then a map is useful...but it will only hold one value per key. If you need more than one value per key, you could have a vector/list as your value in the map, or use a multimap.
It's not in the STL, but it is in the TR1 update to the STL: if you have a lot of key-value pairs that you're going to look up by key, and you don't care about their order, you might want to use a hash - which is tr1::unordered_map. I've used it with Visual C++ 7.1, where it was called stdext::hash_map. It has a lookup of O(1) instead of a lookup of O(log n) for map.