c++ - equal_range 和 std::unordered_multiset

Question

我的理解是，我们不能对无序...容器中元素的顺序做出任何假设(即使它们是通过哈希表实现的)。如果那是正确的，那么 std::unordered_multiset::equal_range() 如何返回一系列相等的值？

例如:

typedef std::unordered_multiset<int> int_set;
typedef int_set::iterator int_set_iterator;

int_set set;
set.insert(1);
set.insert(2);
set.insert(1);
set.insert(3);
set.insert(1);

// equal_range seems to assume all 1s are located next to each other
std::pair<int_set_iterator, int_set_iterator> range = set.equal_range(1);

size_t range_size = std::distance(range.first, range.second); // the value is 3

Answer 1

标准规定了 [unord.req]/6 中相等元素如何位于范围内:

In containers that support equivalent keys, elements with equivalent keys are adjacent to each other in the iteration order of the container. Thus, although the absolute order of elements in an unordered container is not specified, its elements are grouped into equivalent-key groups such that all elements of each group have equivalent keys. Mutating operations on unordered containers shall preserve the relative order of elements within each equivalent-key group unless otherwise specified.