std :: unordered_set :: equal_range итератор вопрос

Question

std::unordered_set::equal_range возвращает пару итераторов, описывающих диапазон значений в наборе, где ключи для значений сравниваются как равные. Дано:

auto iteratorFromEqualRange = someUnorderedSet.equal_range(key).first;
auto iteratoFromFind = someUnorderedSet.find(key);

Стандарт гарантирует, что:

++iteratorFromEqualRange == ++iteratorFromFind;

как они оба определены в терминах std::unordered_set::iterator? Другими словами, может ли другая реализация std::unordered_set хранить «скрытую» информацию о контексте того, что мы итерируем, или это не очень тонкое применение интерфейса корзины (что ограничивает наши варианты реализации)?

Я ожидаю, что это действительно гарантия, учитывая требования LegacyForwardIterator , я просто прошу подтверждение (или лучшую новость, которая включает в себя какой-то аварийный люк)

Answer 1

Итератор unordered_set является прямым итератором (теперь он называется LegacyForwardIterator ).

Стандарт C ++ 14 (окончательный проект n4140) утверждает это в отношении прямых итераторов:

24.2.5 Прямые итераторы [forward.iterators]

1 Класс или тип указателя X удовлетворяет требованиям прямого итератора, если
...
(1.5) - объекты типа X предлагают многопроходную гарантию , описанную ниже.
...

3 Два с разыменованием итераторы a и b типа X предлагают многопроходную гарантию, если:

(3,1) - a == b подразумевает ++a == ++b и
(3.2) - X является типом указателя или выражение (void)++X(a), *a эквивалентно выражению *a.

Объединение (1.5) и (3.1) в этом случае будет означать, что ++iteratorFromEqualRange == ++iteratorFromFind; гарантируется стандартом при условии, что оба эти итератора могут быть разыменованы.