c++11 containers
sorted_vector use when doing lots of unsorted insertions and maintaining constant sort would be expensive
map sorted binary search tree; always sorted by key; you can walk through in sorted order
multimap same as map but allows dupe keys; need for this should be pretty rare
unordered_map hashmap; always sorted by key; additional bucket required for hash collisions; no defined order when walking through
unordered_multimap same as map but allows dupe keys; dupes are obviously in the same bucket, and you can walk just the dupes if needed
sets are just like maps, except the key is embedded in the object, great idea
but… they are ruined by the constraint that contained items must be const
but… then redeemed by mutable
You can use mutable on the variable that are not part of the key to remove the const!
This changes the constness of the object from binary (completely const) to logical (constness is defined by the developer)
so… set is an excellent way to achieve both encapsulation and logical const

Final note: using object pointers is the ultimate solution.
The entire object can be dereferenced and accessed then without const issues.
Two requirements: you must make sure yourself that you do not change the key values;
you must create sort functors that dereference the pointers to sort using object contents if needed
(the default sorting will be by pointer address).
The arguably biggest advantage, as a result, is that you can create multiple sets
to reference the same group of objects with different sort funtors to create multiple indices.

Here is my published reusable c++ code, which includes a version of a sorted vector that I’ve been using for years. It may not be academically sterile C++, I’m more interested in getting things done, and I had to crank out some new functionality needed for my upcoming media manager. But it should be solid production code. It glues together std::vector with std::sort, std::lower_bound, etc., which is a pretty fscking logical thing to do – who wants to redo that every time you have data to manage? :> My favorite part is the find_it_or_fail() function, the only real extension of functionality. Basically, it extends lower_bound() in a logical way, so you either get a hit, or failure (indicated by returning vector::end()). There are also versions of member functions with predicate function parameters, to help you use it with vectors of object pointers, which isn’t exactly straightforward in C++. Let me know if it seems useful or sucky. :>

Reusable STLContainers code
old wiki copy of sorted_vector

Just a quick note: I feel like I’ve accomplished a lot today just because I READ this article. Nice bomb drop. We’ll see what I do with it… I think it’s a bit too crunchy to put into use – I don’t feel like dealing with any gotchas on all the versions of all the compilers I’m using, as there are a LOT these days. But it has lead me to research other progress in the C++ standard. The boost function library, which has been accepted into TR1, is already available in some compiler spaces, whoop.

I started down this path because I wanted to store a predicate function in my sorted_vector class. For now I can get by without this stuff, always passing in a functor to the function calls that need it, but that’s not as elegant.

Meanwhile, it’s upwards and onwards with QT slots and signals – QT is getting the job done for me in a major way. There are boost::signal and boost::bind as alternatives to that, but I’m really kicking out the jams with QT, so I’m not stopping now. More to come soon, hopefully.

UPDATE: C++0x is hopefully coming soon. Wikipedia, as usual, gives a nice overview and some nice guidance. In particular, I need to avoid std::auto_ptr and function object base classes (std::unary_function, std::binary_function) which are slated for removal(!). Sounds like I need to keep my eye out for polymorphic wrappers for function objects, they may be just the ticket I need. Check out the whole standard, it’s juicy! :>

UPDATE 2: Here is a nice rundown of options for the sort predicate function, leading into the C++0x solution.