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

stl::set is basically a sorted container.

Answer 2

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.

Answer 3

STL maps and sets are both sorted containers.

I second Doug T's book recommendation - the Josuttis STL book is the best I've ever seen as both a learning and reference book.

Effective STL is also an excellent book for learning the inner details of STL and what you should and shouldn't do.

Answer 4

For "STL compatible" sorted vector see A. Alexandrescu's AssocVector from Loki.

Answer 5

You should definitely use a set/map. Like hazzen says, you get O(log n) insert/find. You won't get this with a sorted vector; you can get O(log n) find using binary search, but insertion is O(n) because inserting (or deleting) an item may cause all existing items in the vector to be shifted.

Answer 6

It's not that simple. In my experience insert/delete is used less often than find. Advantage of sorted vector is that it takes less memory and is more cache-friendly. If happen to have version that is compatible with STL maps (like the one I linked before) it's easy to switch back and forth and use optimal container for every situation.

Answer 7

in theory an associative container (set, multiset, map, multimap) should be your best solution.

In practice it depends by the average number of the elements you are putting in. for less than 100 elements a vector is probably the best solution due to: - avoiding continuous allocation-deallocation - cache friendly due to data locality these advantages probably will outperform nevertheless continuous sorting. Obviously it also depends on how many insertion-deletation you have to do. Are you going to do per-frame insertion/deletation?

More generally: are you talking about a performance-critical application?

remember to not prematurely optimize...

Answer 8

The stl provides no such container. You can define your own, backed by either a set/multiset or a vector, but you are going to have to re-sort every time the sorting function changes by either calling sort (for a vector) or by creating a new collection (for set/multiset).

If you just want to change from increasing sort order to decreasing sort order, you can use the reverse iterator on your container by calling rbegin() and rend() instead of begin() and end(). Both vector and set/multiset are reversible containers, so this would work for either.

Answer 9

If you know you're going to be sorting on a single value ascending and descending, then set is your friend. Use a reverse iterator when you want to "sort" in the opposite direction.

If your objects are complex and you're going to be sorting in many different ways based on the member fields within the objects, then you're probably better off with using a vector and sort. Try to do your inserts all at once, and then call sort once. If that isn't feasible, then deque may be a better option than the vector for large collections of objects.

I think that if you're interested in that level of optimization, you had better be profiling your code using actual data. (Which is probably the best advice anyone here can give: it may not matter that you call sort after each insert if you're only doing it once in a blue moon.)

Answer 10

The answer is as always it depends.

set and multiset are appropriate for keeping items sorted but are generally optimised for a balanced set of add, remove and fetch. If you have manly lookup operations then a sorted vector may be more appropriate and then use lower_bound to lookup the element.

Also your second requirement of resorting in a different order at runtime will actually mean that set and multiset are not appropriate because the predicate cannot be modified a run time.

I would therefore recommend a sorted vector. But remember to pass the same predicate to lower_bound that you passed to the previous sort as the results will be undefined and most likely wrong if you pass the wrong predicate.

Answer 11

It sounds like you want a multi-index container. This allows you to create a container and tell that container the various ways you may want to traverse the items in it. The container then keeps multiple lists of the items, and those lists are updated on each insert/delete.

If you really want to re-sort the container, you can call the std::sort function on any std::deque, std::vector, or even a simple C-style array. That function takes an optional third argument to determine how to sort the contents.

If you don't like the syntax for std::sort/std::stable_sort, each of the STL containers (std::list, std::vector and std::deque) have a sort() method that takes an optional argument on how to sort the contents.