CODEWITHSUNDEEP
c++c++11containers
Oncaphillis
Oncaphillis

Reputation: 1908

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

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

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.

Upvotes: 6

Views: 961

Answers (3)

ComicSansMS
ComicSansMS

Reputation: 54777

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.

Upvotes: 8

Barry
Barry

Reputation: 304122

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

But there's nothing to stop you from writing your own wrapper around vector which simply enforces ordering. It's not that much code at all. Some example 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);
    }
};

Upvotes: 1

Daerst
Daerst

Reputation: 973

None that I am aware of. However, with hundreds of millions of elements and some ordered access you might want your memory representation to be compact and consecutive, which are even more requirements for your container class.

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

Upvotes: 1

Related Questions