Должны ли элементы с дублирующимися ключами в unordered_multimap храниться в порядке их вставки?
В одной книге упоминается, что для std::unordered_multimap:
Порядок элементов не определен. Единственная гарантия заключается в том, что
дубликаты, которые возможны из-за использования мультимножества, сгруппированы
вместе в порядке их вставки.
Но из вывода приведенного ниже примера мы видим, что порядок печати обратен их вставке.
#include <string>
#include <unordered_map>
int main()
{
std::unordered_multimap<int, std::string> um;
um.insert( {1,"hello1.1"} );
um.insert( {1,"hello1.2"} );
um.insert( {1,"hello1.3"} );
for (auto &a: um){
cout << a.first << '\t' << a.second << endl;
}
}
Который при компиляции и запуске выдает такой вывод (g ++ 5.4.0):
1 hello1.3
1 hello1.2
1 hello1.1
обновлено: unordered_multiset имеет ту же проблему:
auto cmp = [](const pair<int,string> &p1, const pair<int,string> &p2)
{return p1.first == p2.first;};
auto hs = [](const pair<int,string> &p1){return std::hash<int>()(p1.first);};
unordered_multiset<pair<int, string>, decltype(hs), decltype(cmp)> us(0, hs, cmp);
us.insert({1,"hello1.1"});
us.insert({1,"hello1.2"});
us.insert({1,"hello1.3"});
for(auto &a:us){
cout<<a.first<<"\t"<<a.second<<endl;
}
выход:
1 hello1.3
1 hello1.2
1 hello1.1
Решение
Вот что стандарт говорит о порядке [unord.req] / §6:
… В контейнерах, которые поддерживают эквивалентные ключи, элементы с эквивалентными ключами соседствуют друг с другом в порядке итерации контейнера. Таким образом, хотя абсолютный порядок элементов в неупорядоченном контейнере не указан, его элементы сгруппированы в группы эквивалентных ключей, так что все элементы каждой группы имеют эквивалентные ключи. Мутирующие операции с неупорядоченными контейнерами должны сохранять относительный порядок элементов в каждой группе эквивалентных ключей, если не указано иное.
Итак, чтобы ответить на вопрос:
Должны ли элементы с дублирующимися ключами в unordered_multimap храниться в порядке их вставки?
Нет, такого требования или гарантии нет. Если в книге такое утверждение о стандарте, то это не правильно. Если книга описывает конкретную реализацию std::unordered_multimap, тогда описание может быть верным для этой реализации.
Требования стандарта делают реализацию с использованием открытой адресации нецелесообразной. Следовательно, совместимые реализации обычно используют отдельную цепочку хеш-коллизий, см. Как C ++ STL unordered_map разрешает коллизии?
Поскольку эквивалентные ключи — которые обязательно сталкиваются — на практике (на практике это явно не требуется) хранятся в отдельном связанном списке, наиболее эффективный способ их вставки — в порядке вставки (push_back) или наоборот (push_front). Только последний эффективен, если отдельная цепочка является односвязной.
Другие решения
Других решений пока нет …