std :: vectorとstd :: setプロパティを持つコンテナ？

Question

これらのプロパティを持つC++世界のコンテナはありますか？

• 要素がユニークで、カスタマイズ可能なコンパレータ
• の助けを借りて注文したランダムアクセス演算子を提供します。

私は現在、注文したコレクションへのランダムアクセスを持つことができるようにstd::copy(_set.begin(),_set.end(),std::back_inserter(_vec))を行い、その後std::set<C,COMPARATOR>に自分のデータを収集しています。しかし、サイズは数億になるかもしれません。

Answer 1

ブーストがオプションの場合は、flat_set in the Containers libraryをご覧ください。

flat_setためのインタフェースはstd::setのものと同じであるが、それは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]; 

あなたが標準ライブラリで立ち往生している場合は、この目的のためにソートvectorを使用することができます。標準ライブラリーは実際に<algorithm>ヘッダーに多くのアルゴリズムを提供しています。このアルゴリズムを使用すると、ソートされたイテレーターの範囲でsetを使用してできることはほとんどできます。

Answer 2

私が知っていることはありません。しかし、何億もの要素といくつかの順序付けられたアクセスによって、メモリ表現がコンパクトで連続的であることが望まれるかもしれません。これは、コンテナクラスのためのさらに多くの要件です。

私はstd::vectorに行き、あなたが説明したアプローチまたは他のソートアルゴリズムを使用します。後であなたのstd::setは必要ないので、メモリを解放することができます。

Answer 3

標準のC++ライブラリにはありません。ご注文の場合はset/priority_queue、ランダムアクセスの場合はvector/dequeとなります。

しかし、単に注文を強制するvectorの周りに独自のラッパーを書くことを止めるものは何もありません。それほど多くのコードではありません。いくつかの例機能：

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