Возвращает ли функция std :: unordered_multiset :: find первый вставленный элемент между двумя значениями с одинаковым хеш-значением
Сказать, что у нас есть std::unordered_multiset с двумя значениями, отображающими одно и то же значение хеша, есть ли гарантии по стандарту c ++, что find вернет первый вставленный элемент?
Решение
Я предполагаю, что ваш вопрос касается двух ключей, которые не только генерируют одно и то же значение хеш-функции, но и сравнивают его с помощью предиката равенства, предоставленного unordered_multiset, unordered_multiset::find будет использовать только значение хеша, чтобы сначала найти область, в которой искать, но после этого поиск будет выполнен с использованием предиката равенства.
§23.2.5 [Unord.req] Таблица 103 — Неупорядоченные требования к ассоциативным контейнерам
b.find(k)Возвращает итератор, указывающий на элемент с ключом, эквивалентным
k,
или жеb.end()если такого элемента не существует.
Никаких дополнительных требований для find() размещены на unordered_multi* контейнеры. Это означает, что реализации не требуют, чтобы unordered_multiset::find вернуть итератор к первому вставленному элементу. Но с другой стороны, если эти два (или более) ключа действительно эквивалентны, что вас волнует?
Другие решения
Интересный вопрос. Я не часто использовал неупорядоченные ассоциативные контейнеры, поэтому я воспользовался возможностью поиска по стандарту. Вот моя интерпретация: 23.2.5.6 говорит
«В контейнерах, которые поддерживают эквивалентные ключи, элементы с эквивалентными
ключи расположены рядом друг с другом в порядке итерации
контейнер. Таким образом, хотя абсолютный порядок элементов в
неупорядоченный контейнер не указан, его элементы сгруппированы в
группы эквивалентных ключей, так что все элементы каждой группы имеют
эквивалентные ключи. «
Но затем продолжается
«Мутирующие операции с неупорядоченными контейнерами должны сохранять
относительный порядок элементов в каждой группе эквивалентных ключей, если только
иначе указано. «
23.2.5.9 тогда говорится
«Для unordered_multiset и unordered_multimap перефразирование консервов
относительное упорядочение эквивалентных элементов. «
Таким образом, порядок, кажется, сохраняется, потому что insert не говорит о том, что он может изменить порядок эквивалентных ключей. Но тогда найти указан как
«Возвращает итератор, указывающий на элемент с ключом, эквивалентным k,
или b.end (), если такого элемента не существует. «
Таким образом, он не определяет, какой элемент из эквивалентных ключей он возвращает. Строго говоря, это может вернуть случайный элемент с заданным ключом и при этом соответствовать спецификации. Учитывая, что equal_range определяется как
Возвращает диапазон, содержащий все элементы с ключами, эквивалентными k.
*equal_range(k).first мог сделать работу и вернуть первый элемент, вставленный с ключом k.