c++ - std :: multisetは挿入順序を保証しますか？

Question

std::multisetの要素を格納するがありますclass A。operator<このクラスに独自の実装を提供しました。私の質問は、このマルチセットに2つの同等のオブジェクトを挿入した場合、それらの順序は保証されますか？たとえば、最初にオブジェクトa1をセットに挿入し、次に同等のオブジェクトa2をこのセットに挿入します。セットを反復するときにa1、が前に来ることを期待できますか？a2いいえの場合、マルチセットを使用してこれを実現する方法はありますか？

Answer 1

C ++ 03では、それが保証されておらずinsert、相対的な順序eraseが保持されます。ただし、これはC++0xで変更されています。

n3092、§23.2.4/ 4：連想コンテナは、キーごとに最大1つの要素を含む可能性がある場合、一意のキーをサポートします。それ以外の場合は、同等のキーをサポートします。setクラスとmapクラスは、一意のキーをサポートしています。マルチセットクラスとマルチマップクラスは同等のキーをサポートします。マルチセットおよびマルチマップの場合、挿入および消去は、同等の要素の相対的な順序を保持します。 _{強調鉱山。}

これについては、この欠陥レポートで説明しています。このページはこの問題に関するコメントのコレクションであり、よく書かれていて、かなり具体化されています。（前の「概要」リンクよりもこれを読むことを強くお勧めします。）

そのコメントページから、現在の実装の比較を見つけることができるので、使用する予定の実装が期待どおりであるかどうかを確認できます。

私はあなたが望む注文を頭のてっぺんから強制する方法を考えることができません。：/

Answer 2

それを考慮に入れるa1とa2、あなたの例では同等に比較され、実際にに格納されているのはとのstd::multisetコピーです。どちらがどれであるかをどうやって知るのか、私にはよくわかりません。a1a2

違いがわかるとしたら、class Aそもそもうまく設計されていなかったのかもしれません。したがって、そのstd::multisetようなことを保証するものではありません。

Answer 3

std::multimapはこれを保証しません。operator<たとえば、関数を介して整数を使用して表現できる場合int A::orderingInt()は、

std::multiset<MyCustom> myset;

と

class MyCustom : public std::vector<A> {}

過負荷で

bool operator<(const MyCustom& a, const MyCustom& b) {
   // theoretically empty MyCustom should not occure
   return a[0].orderingInt() < b[0].orderingInt();
}

もちろん、追加と反復は今では異なります。

A a;
myset[a.orderingInt()].push_back(a);

// groups with "small" elements first
for(std::multiset<MyCustom>::iterator it=myset.begin(); it!=myset.end(); it++) {
    // those elements are "equal"
    for(std::vector<A>::iterator jt=it->begin(); jt->end(); jt++) { 
         // use A& a = *jt;
    }
}