Dynamically sorted STL containers

Question

I'm fairly new to the STL, so I was wondering whether there are any dynamically sortable containers? At the moment my current thinking is to use a vector in conjunction with the various sort algorithms, but I'm not sure whether there's a more appropriate selection given the (presumably) linear complexity of inserting entries into a sorted vector.

To clarify "dynamically", I am looking for a container that I can modify the sorting order at runtime - e.g. sort it in an ascending order, then later re-sort in a descending order.

Answer 1

You'll want to look at std::map

std::map<keyType, valueType>

The map is sorted based on the < operator provided for keyType.

Or

std::set<valueType>

Also sorted on the < operator of the template argument, but does not allow duplicate elements.

There's

std::multiset<valueType>

which does the same thing as std::set but allows identical elements.

I highly reccomend "The C++ Standard Library" by Josuttis for more information. It is the most comprehensive overview of the std library, very readable, and chock full of obscure and not-so-obscure information.

Also, as mentioned by 17 of 26, Effective Stl by Meyers is worth a read.