したがって、私のアプリケーションには、1億以上の要素を含むコンテナーがあります。
私は、コンテナ全体での頻繁な挿入と削除に関して、std :: deque（std :: vectorは言うまでもなく）よりも時間的に優れた動作をするコンテナを探しています...中央付近を含みます。n番目の要素へのアクセス時間は、ベクトルほど高速である必要はありませんが、std :: list（とにかく要素ごとに膨大なメモリオーバーヘッドがあります）のように完全なトラバーサルよりも明らかに優れている必要があります。
要素はインデックス順に並べて処理する必要があるため（vector、deque、listなど）、std::setまたはstd::unordered_setも適切に機能しません。
私が座ってそのようなコンテナを自分でコーディングする前に：誰かがそのような獣を見たことがありますか？STLにはこのようなものはないと確信しています。ブーストを探していると、使用できるものが見つかりませんでしたが、間違っている可能性があります。
ヒントはありますか？
アプリがビッグデータを中心としている場合は、ビッグデータをSTLで完全に置き換えることができます。
編集：私は実際に答えるのが少し速かった。1億は実際には多くはありません。たとえば、各要素が1バイトの場合、96MiB配列に保存できます。したがって、STXXLが有用であるかどうかにかかわらず、要素のサイズは大幅に大きくする必要があります。
スキップリストを使用すると、必要なパフォーマンス特性を得ることができると思います。
https://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist
もちろん、これは「索引付け可能な」部分です。実際には、アイテムを並べ替える必要はありません。したがって、演習として残すいくつかの変更が必要です。
1億個のリストノードが32ビットのアドレス空間に負担をかけ始めていることに気付くかもしれませんが、64ビットではおそらく問題にはなりません。
1）データが非常にスパースである場合、つまりゼロがたくさんあるか、そのように表現できる場合は、それを利用するデータ構造を強くお勧めします。
2）ハッシュマップは、説明するすべての操作に対してO（1）を実行する必要があり、前述のスパースハッシュの実装は特にスペース効率が高くなります。sparsetableまた、もう少し低レベルで、配列の代わりに使用できるタイプも含まれています。
3）厳密な順序がそれほど重要でない場合（要素はインデックス順に処理する必要があると述べたため）、swapベクトルの最後まで消去してからresizeO（1）で削除することができます。 ）。挿入はただですpush_back。
ハッシュマップを試してください。STLにはいくつかあり、すべてunordered_mapなどの順序付けられていない名前付けプレフィックスが付いています。優れたハッシュアルゴリズムがあれば、一定時間の挿入と検索が行われます。「巨大な」データセットを使用すると、ハッシュマップがニーズをカバーする可能性が高くなります。インターフェイスの違いをカバーするためにアプリケーションにわずかな変更を加えるのは簡単です。