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

Question

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

• Elements are unique and ordered using a custom comparator.
• provides a random access operator.

I am currently collecting my data in std::set<C,COMPARATOR> and then std::copy(_set.begin(),_set.end(),std::back_inserter(_vec)) to have random access to an ordered collection. However, the size can be hundreds of millions.

Answer 1

If the Boost option is an option, see flat_set in the container library .

The interface for flat_set is identical to the std::set interface, but it provides random access iterators such as 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 many algorithms in the <algorithm> header, which allow you to do almost anything you can do with set with a sorted iterator range.

Answer 2

No, that I know. However, with hundreds of millions of elements and some sort of ordered access, you might want your memory representation to be compact and consistent, which even more requires a container class for you.

I would go with std::vector and use the approach you described or any other sorting algorithm. You probably won't need your std::set , so you can free up memory.

Answer 3

Not in the C ++ standard library, no. You either have set / priority_queue for ordering, or vector / deque for random access.

But you have nothing to stop writing your own wrapper around vector , which simply forcibly arranges. This is not much code. Some sample functions:

 template <typename T, typename COMP = std::less<T>> class sorted_vec { std::vector<T> vec_; public: // random access using iterator = typename std::vector<T>::iterator; T& operator[](size_t idx) { return vec_[idx]; } iterator begin() { return vec_.begin(); } iterator end() { return vec_.end(); } // insertion void push(const T& val) { vec_.insert(std::lower_bound(vec_.begin(), vec_.end(), COMP{}), val); } };