Должны ли элементы с дублирующимися ключами в unordered_multimap храниться в порядке их вставки?

Question

В одной книге упоминается, что для 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

Answer 1

Вот что говорит стандарт об упорядочении [unord.req] / §6:

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

Итак, чтобы ответить на вопрос:

Должны ли элементы с дублирующимися ключами в unordered_multimap храниться в порядке их вставки?

Нет, такого требования или гарантии нет. Если в книге такое утверждение о стандарте, то это не правильно. Если книга описывает конкретную реализацию std::unordered_multimap, тогда описание может быть верным для этой реализации.

---

Требования стандарта делают реализацию с использованием открытой адресации нецелесообразной. Следовательно, совместимые реализации обычно используют отдельную цепочку хеш-коллизий, см. Как C++ STL unordered_map разрешает коллизии?

Поскольку эквивалентные ключи - которые обязательно сталкиваются - на практике (на практике это явно не требуется) хранятся в отдельном связанном списке, наиболее эффективный способ их вставки - в порядке вставки (push_back) или наоборот (push_front). Только последний эффективен, если отдельная цепочка является односвязной.