22

整数インデックスが付いたデータがあります。私が持っているデータのコレクションに追加する必要がある新しいデータを継続的に生成し、そのインデックスで並べ替えながら、データの先頭に簡単に移動して反復できるようにしたいと考えています。これは std::multimap がまさに私が必要としているもののように思えます。

ただし、挿入された順序で保持される同じインデックスを持つデータも必要です。この場合、データを反復すると、後のデータの前に前のデータが取得されます。

マルチマップはこれを行いますか?

これが事実であるという保証は見つかりませんでした。sgi のマニュアルでは、そのかどうかについての言及は見当たりませんでした。gcc 4.3.4 の実装で試してみたところ、いくつかの限られたテスト ケースには当てはまるように見えましたが、もちろん、標準でこれが要求されているかどうか、またこの事実を信頼できるかどうか疑問に思っていました。

編集:いくつかの回答に応じて明確にするために、最初に(一意ではない)インデックスで、次に挿入時間でデータを並べ替えたいと思いました。第二部がマルチマップで無料になるのではないかと期待していたのですが、そうではないようです。

4

7 に答える 7

43

新しい標準（C++ 11）がこれを変更したようです：

キーが同等であると比較されるキーと値のペアの順序は、挿入の順序であり、変更されません。[cppリファレンス]

これは、標準ライブラリを C++11 準拠に変更するときに見落とされがちな詳細のように思われ、コンパイラのライブラリが適切に実装されなかった場合にエラーを黙って引き起こすような詳細であるため、私はそれを使用することをためらっています。

于 2012-11-12T02:23:56.330 に答える
8

私が何かを見逃していない限り、標準はそのような保証を提供しません。

最も明白な回避策は、シーケンス番号を 2 次キーとして含めることです。たとえば、クラスに static unsigned long を含め、マルチマップに挿入するオブジェクトを作成するたびに、その現在の値をオブジェクトに入れ、それをインクリメントします。オブジェクトの比較関数では、現在キーとして使用しているデータが等しい場合、そのカウンターを順序付けの決定要因として使用します。この場合、各キーは一意になるため、マルチマップの代わりにマップを使用できることに注意してください。

于 2009-10-20T15:12:02.800 に答える
4

Boost multi_indexは、 Jerry Coffinによって提供された回避策を取りたくない場合、あなたがやろうとしていることをサポートします。

于 2009-10-20T15:28:18.220 に答える
3

私が正しければ、何らかのキーでソートされたデータが必要です。同じキーで 2 つのものを挿入するたびに、挿入された順序でそれらを取得する必要があります。

その場合は、マルチマップの実装を確認する必要があります。同じキーを持つ複数の挿入のケースをどのように処理するかによって、この保証がある場合とない場合があります。非常に特殊なケースの実装を制限するため、標準はこの種の保証を提供していないと思います。

もう 1 つのアプローチは、(Multi ではなく) Map を使用して複合キーを作成することです。キーは、選択した通常のキーと常に増加するカウンターで構成されます。比較すると、等しいキーでは、挿入番号によってキーが一意になります。このようにして、一意のキーと順序を同じ「通常の」キーに強制します (これが理解できたことを願っています)。

最後のアプローチが最も実装しやすいと思います。

オプション: (好ましくない)

この保証により、いつでも自作のデータ構造を使用できます。挿入されたデータを保持するためのベクトルを持つツリー (たとえば、赤黒または AVL) を使用します。反復では、ノードを見つけて、ベクトルに移動し、その内容を反復する必要があります。ベクトルを終了するたびに、次のノードに進みます。

于 2009-10-20T15:31:36.653 に答える
1

同じキーに属する要素は、情報を取得するときにlower_boundおよびupper_bound関数によって順序付けられるため、要素が挿入された順序で( equal_rangeによって) アクセスできるという保証はありません。

于 2009-10-20T15:19:21.663 に答える
1

いいえ、そうではありません。それが必要な場合は、ベクターのような「シーケンス コンテナー」を使用する必要があります。たとえば、std::pairs でベクトルをロードできますか?

于 2009-10-20T15:12:41.043 に答える
1

マルチマップが必要なようです...

ただし、挿入された順序で保持される同じインデックスを持つデータも必要です。この場合、データを反復すると、後のデータの前に前のデータが取得されます。

インデックス順になります。より多くのアイテムを挿入するにつれてインデックスが時間とともに増加する場合、インデックスの性質上、「以前の」データが最初に表示されます。

そうでなければ、いいえ。2 つのマルチマップを同じデータに保持できます。1 つはインデックス順、もう 1 つは挿入時間順です。

std::multimap<index, T*> orderedByIndex;
std::multimap<time, T*> orderedByInsertionTime;

両方の方法でマップを反復する機能を提供します。

(編集私はこれを読んで、インデックスごとに反復したり、挿入時間ごとに反復したりすることもありますが、最初のインデックス、次に挿入時間を意味する場合は上記の回答を参照してください。)

于 2009-10-20T15:13:01.403 に答える