Поддерживает ли std:: multiset порядок вставки?

У меня есть std::multiset, в котором хранятся элементы class A. Я предоставил свою собственную реализацию operator< для этого класса. Мой вопрос: если я вставляю два эквивалентных объекта в этот мультимножество, гарантируется ли их заказ? Например, сначала я вставляю объект a1 в набор, а затем вставляю в этот эквивалентный объект a2. Могу ли я ожидать, чтобы a1 появился раньше a2, когда я повторяю набор? Если нет, есть ли способ достичь этого с помощью мультимножества?

Ответ 1

В С++ 03 вам не гарантируется сохранение insert и erase относительного упорядочения. Однако это изменяется в С++ 0x:

n3092, §23.2.4/4: Ассоциативный контейнер поддерживает уникальные ключи, если он может содержать не более одного элемента для каждого ключа. В противном случае он поддерживает эквивалентные ключи. Классы набора и карты поддерживают уникальные ключи; классы мультимножества и multimap поддерживают эквивалентные ключи. Для мультимножества и multimap, вставки и стирания сохраняют относительный порядок эквивалентных элементов. _{Выделите мой.}

Это обсуждается в отчете . Эта страница представляет собой сборник комментариев по этой проблеме, она хорошо написана и довольно сглажена. (Я очень рекомендую прочитать это по предыдущей ссылке "Обзор".)

На этой странице комментариев вы найдете сравнение текущих реализаций, чтобы вы могли проверить, соответствуют ли реализации, которые вы собираетесь использовать, за то, что вы ожидаете.

Я не могу придумать способ заставить заказ, который вы хотите, с моей головы.:/

Ответ 2

Учитывая, что a1 и a2 будут сравниваться в вашем примере равными, а то, что на самом деле хранится в std::multiset, - это копии a1 и a2, я действительно не знаю, как вы знаете, что есть.

Если вы можете сказать разницу, возможно, class A не был хорошо спроектирован в первую очередь. Поэтому std::multiset не гарантирует такую вещь.

Ответ 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;
    }
}