Container with std::vector and std::set properties ?

Question

Is there a container in the C++ world that has these properties ?

• Elements are unique and ordered with the help of a customizable comparator
• provide an random access operator.

I'm currently collecting my data into a std::set<C,COMPARATOR> and afterwards do a std::copy(_set.begin(),_set.end(),std::back_inserter(_vec)) to be able to have random access to the ordered collection. The size however might go into hundreds of millions.

Answer 1

If Boost is an option, have a look at flat_set in the Containers library.

The interface for flat_set is identical to that of std::set but it provides random access iterators, like std::vector:

#include <boost/container/flat_set.hpp>

[...]

boost::container::flat_set<int> c;
c.insert(1);
c.insert(2);
c.insert(3);
c.insert(4);

// unfortunately, no operator[] on the container itself,
// but the iterator is random access
int third_element = c.begin()[2];

If you are stuck with the standard library, you can use a sorted vector for this purpose. The standard library actually offers a lot of algorithms in the <algorithm> header that allow you to do pretty much anything that you can do with a set with a sorted iterator range.