Функция std::unordered_multiset::find возвращает первый вставленный элемент между двумя значениями с одинаковым хеш-значением

Question

Сказать, что у нас есть std::unordered_multiset с двумя значениями, отображающими одно и то же хеш-значение, есть ли гарантии по стандарту C++, что find вернет первый вставленный элемент?

Answer 1

Я предполагаю, что ваш вопрос касается двух ключей, которые не только генерируют одно и то же значение хеш-функции, но и сравнивают его с помощью предиката равенства, предоставленного unordered_multiset, unordered_multiset::find будет использовать только значение хеша, чтобы сначала найти область, в которой нужно искать, но после этого поиск будет выполнен с использованием предиката равенства.

§23.2.5 [unord.req] Таблица 103 - Неупорядоченные требования к ассоциативным контейнерам

b.find(k)

Возвращает итератор, указывающий на элемент с ключом, эквивалентным k, или же b.end() если такого элемента не существует.

Никаких дополнительных требований для find() размещены на unordered_multi* контейнеры. Это означает, что реализации не требуют, чтобы unordered_multiset::find вернуть итератор к первому вставленному элементу. Но с другой стороны, если эти два (или более) ключа действительно эквивалентны, что вас волнует?

Answer 2

Интересный вопрос. Я не часто использовал неупорядоченные ассоциативные контейнеры, поэтому я воспользовался возможностью поиска в стандарте. Вот моя интерпретация: 23.2.5.6 говорит

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

Но затем продолжается

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

23.2.5.9 тогда говорится

"Для unordered_multiset и unordered_multimap перефразировка сохраняет относительный порядок эквивалентных элементов".

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

"Возвращает итератор, указывающий на элемент с ключом, эквивалентным k, или b.end(), если такого элемента не существует."

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

Возвращает диапазон, содержащий все элементы с ключами, эквивалентными k.

*equal_range(k).first мог сделать работу и вернуть первый элемент, вставленный с ключом k.