Гарантирует ли std :: multiset порядок вставки? - PullRequest
Новая
       27

Гарантирует ли std :: multiset порядок вставки?

12 голосов
/ 15 апреля 2010

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

Ответы [ 3 ]

21 голосов
/ 15 апреля 2010

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

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

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

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

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

3 голосов
/ 15 апреля 2010

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

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

1 голос
/ 15 апреля 2010

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