Is there a sorted_vector class, which supports insert() etc.?

Question

Often, it is more efficient to use a sorted std::vector instead of a std::set. Does anyone know a library class sorted_vector, which basically has a similar interface to std::set, but inserts elements into the sorted vector (so that there are no duplicates), uses binary search to find elements, etc.?

I know it's not hard to write, but probably better not to waste time and use an existing implementation anyway.

Update: The reason to use a sorted vector instead of a set is: If you have hundreds of thousands of little sets that contain only 10 or so members each, it is more memory-efficient to just use sorted vectors instead.

Answer 1

I think there's not 'sorted container' adapter in the STL because there are already the appropriate associative containers for keeping things sorted that would be appropriate to use in nearly all cases. To be honest, about the only reason I can think of off the top of my head for having a sorted vector<> container might be to interoperate with C functions that expect a sorted array. Of course, I may be missing something.

If you feel that a sorted vector<> would be more appropriate for your needs (being aware of the shortcomings of inserting elements into a vector), here's an implementation on Code Project:

• An STL compliant sorted vector By Martin Holzherr

I've never used it, so I can't vouch for it (or its license - if any is specified). But a quick read of the article and it looks like the author at least made a good effort for the container adapter to have an appropriate STL interface.

It seems to be worth a closer look.

Answer 2

The reason such a container is not part of the standard library is that it would be inefficient. Using a vector for storage means objects have to be moved if something is inserted in the middle of the vector. Doing this on every insertion gets needlessly expensive. (On average, half the objects will have to be moved for each insertion. That's pretty costly)

If you want a sorted vector, it is likely better to insert all the elements, and then call std::sort() once, after the insertions.

Answer 3

Alexandresu's Loki has a sorted vector implementation, if you dont want to go through the relativley insignicant effort of rolling you own.

Answer 4

If you decide to roll your own, you might also want to check out boost:ublas. Specifically:

#include <boost/numeric/ublas/vector_sparse.hpp>

and look at coordinate_vector, which implements a vector of values and indexes. This data structure supports O(1) insertion (violating the sort), but then sorts on-demand Omega(n log n). Of course, once it's sorted, lookups are O(logn). If part of the array is sorted, the algorithm recognizes this and sorts only the newly added elements, then does an inplace merge. If you care about efficiency, this is probably the best you can do.