Делает станд.:: порядок вставки гарантии мультимножества?
У меня есть a std::multiset который хранит элементы class A. Я обеспечил свою собственную реализацию operator< для этого класса. Мой вопрос состоит в том, если я вставляю два эквивалентных объекта в это мультимножество, их гарантируемый порядок? Например, сначала я вставляю объект a1 в набор и затем я вставляю эквивалентный объект a2 в этот набор. Я могу ожидать a1 прибыть прежде a2 когда я выполняю итерации через набор? Если не, там какой-либо способ достигнуть этого мультимножества использования?
3 ответа
В C ++ 03 не гарантируется, что insert и erase сохраняют относительный порядок . Однако это изменено в C ++ 0x:
n3092, §23.2.4 / 4: ассоциативный контейнер поддерживает уникальные ключи, если он может содержать не более одного элемента для каждого ключа. В противном случае он поддерживает эквивалентные ключи. Классы set и map поддерживают уникальные ключи; классы мультимножества и нескольких карт поддерживают эквивалентные ключи. Для мультимножества и нескольких карт при вставке и стирании сохраняется относительный порядок эквивалентных элементов. Акцент мой.
Это обсуждается в отчете о дефекте . Эта страница представляет собой сборник комментариев по проблеме, она хорошо написана и довольно подробно изложена. (Я очень рекомендую прочитать это вместо предыдущей ссылки «Обзор».)
На этой странице комментариев вы найдете сравнение текущих реализаций, так что вы можете проверить, соответствуют ли реализации, которые вы собираетесь использовать, тому, что вы ожидаете.
Я не могу придумать, как заставить приказ, который вы хотите, слететь с моей головы. : /
std :: multimap не гарантирует этого.
Если вы можете выразить свой оператор <, используя целое число через функция например 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;
}
}
Принимая во внимание, что a1 и a2 в вашем примере будут сравниваться как равные, а то, что фактически хранится в std :: multiset , является копиями a1 и a2 , я действительно не знаю, как вы узнаете, что есть что.
Если вы заметите разницу, возможно, класс A изначально не был хорошо спроектирован. Так что std :: multiset не гарантирует этого.