Следует ли хранить элементы с повторяющимися ключами в 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

c++ c++11 c++-standard-library unordered-multimap
person camino    schedule 16.07.2016    source источник
comment
The order of the elements is undefined. Думаю, вам нужно понять, что Стандарт имеет в виду, когда говорит, что не определено: может случиться что угодно, но не важно, что произойдет, и никто не должен полагаться на то, что может произойти во вторник, с ветром, дующим на восток. Реализации могут определять порядок, если они хотят - вероятно, как побочный эффект непреднамеренного византизма - но Стандарт этого не делает. Это все. Сказав это, если бы вы вставили больше элементов, вы, вероятно, обнаружили бы, что «предсказуемый» порядок начал разрушаться. Но опять же, это совершенно неважно. Это unordered_map.   -  person underscore_d    schedule 17.07.2016
comment
@underscore_d: Нет, это unordered_multimap, для которого черновик C++ от 14 ноября 2014 года (по крайней мере) требует, чтобы элементы с эквивалентными ключами располагались рядом друг с другом в порядке итерации контейнера, и чтобы перефразирование сохраняло относительный порядок эквивалентных элементы (23.2.5). Я ничего не могу найти об относительном порядке, определяемом в соответствии с порядком вставки, но это стоит знать.   -  person Ry-♦    schedule 17.07.2016
comment
@RyanO'Hara Спасибо за информацию. Я не обработал это полностью, потому что в 1-й строке отсутствует multi. Теперь нам нужно знать, в какой книге это сказано, а не в том, что она будет надежнее Стандарта!   -  person underscore_d    schedule 17.07.2016
comment
@underscore_d Утверждение взято из стандартной библиотеки C++. Учебное пособие и справочник по контейнерам главы 6.2, в начале страницы 183: Теперь, если мы напечатаем все элементы, порядок может быть другим, поскольку порядок не определен. Единственная гарантия состоит в том, что дубликаты, которые возможны из-за использования мультимножества, группируются вместе в порядке их вставки.   -  person camino    schedule 17.07.2016
comment
@camino Спасибо за цитату и дополнительную цитату. Я не думаю, что его заявление имеет какой-либо смысл. Порядок undefined напрямую конфликтует с сгруппированными в порядке их вставки. Они просто сгруппированы вместе в неопределенном (хотя обычно неизменном) порядке.   -  person underscore_d    schedule 17.07.2016
comment
@underscore_d Спасибо за разъяснение   -  person camino    schedule 17.07.2016

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

person eerorika    schedule 17.07.2016
comment
Разработчик не обязан сохранять это поведение в будущих версиях своей библиотеки. - person kfsone; 17.07.2016