CODEWITHSUNDEEP
c++c++11iteratorc++14language-lawyer
frasnian
frasnian

Reputation: 2003

std::unordered_set::equal_range iterator question

std::unordered_set::equal_range returns a pair of iterators describing the range of values in the set where the keys for the values compare as equal. Given:

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

is it guaranteed by the Standard that:

++iteratorFromEqualRange == ++iteratorFromFind;

as they are both defined in terms of std::unordered_set::iterator? In other words, can a different implementation of std::unordered_set keep "hidden" information about the context of what we're iterating, or is this a not-very-subtle enforcement of the bucket interface (which limits our implementation options)?

I expect that this is indeed a guarantee, given the requirements of LegacyForwardIterator, I'm just asking for confirmation (or better news that includes some kind of escape hatch)

Upvotes: 3

Views: 113

Answers (1)

P.W
P.W

Reputation: 26800

The iterator of unordered_set is a Forward Iterator (now named LegacyForwardIterator).

The C++14 standard (final draft n4140) states this regarding Forward Iterators:

24.2.5 Forward iterators [forward.iterators]

1 A class or pointer type X satisfies the requirements of a forward iterator if
...
(1.5) — objects of type X offer the multi-pass guarantee, described below.
...

3 Two dereferenceable iterators a and b of type X offer the multi-pass guarantee if:

(3.1) — a == b implies ++a == ++b and
(3.2) — X is a pointer type or the expression (void)++X(a), *a is equivalent to the expression *a.

Combining (1.5) and (3.1) in this case would mean that ++iteratorFromEqualRange == ++iteratorFromFind; is guaranteed by the standard, provided both these iterators can be dereferenced.

Upvotes: 2

Related Questions