Container mit den Eigenschaften std :: vector und std :: set?

Question

Gibt es in der C++ - Welt einen Container mit diesen Eigenschaften?

• Elemente sind einzigartig und mit Hilfe einer anpassbaren Komparator bestellt
• einen Direktzugriffs Betreiber bereitzustellen.

bin Sammeln ich zur Zeit meine Daten in ein std::set<C,COMPARATOR> und danach eine std::copy(_set.begin(),_set.end(),std::back_inserter(_vec)) tun Direktzugriff auf die geordnete Sammlung haben zu können. Die Größe könnte jedoch in Hunderte von Millionen gehen.

Answer 1

Wenn Boost eine Option ist, werfen Sie einen Blick auf flat_set in the Containers library.

Die Schnittstelle für flat_set dem von std::set identisch ist, aber es bietet Random Access-Iteratoren, wie 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]; 

Wenn Sie mit der Standardbibliothek stecken geblieben sind, können Sie eine sortierte vector für diesen Zweck verwenden können. Die Standardbibliothek bietet tatsächlich eine Menge von Algorithmen im Header <algorithm>, mit denen Sie so ziemlich alles tun können, was Sie mit einem set mit einem sortierten Iterator-Bereich tun können.

Answer 2

Keine, die ich kenne. Bei Hunderten von Millionen Elementen und einigen geordneten Zugriffen ist es jedoch möglich, dass die Speicherdarstellung kompakt und konsekutiv ist. Dies sind noch mehr Anforderungen für Ihre Containerklasse.

Ich würde mit std::vector gehen und den von Ihnen beschriebenen Ansatz oder einen anderen Sortieralgorithmus verwenden. Sie werden wahrscheinlich Ihre std::set danach nicht brauchen, damit Sie den Speicher freigeben können.

Answer 3

Nicht in der C++ - Standardbibliothek, nein. Sie haben entweder set/priority_queue für die Bestellung oder vector/deque für den wahlfreien Zugriff.

Aber nichts hält Sie davon ab, Ihren eigenen Wrapper um vector zu schreiben, der einfach die Bestellung erzwingt. Es ist nicht so viel Code. Einige Beispielfunktionen:

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); 
    } 
};