What are some uses of local iterator for STL unordered containers?

Question

In §23.2.7 Unordered associative containers [unord.req] of the C++ standard table 91 describes the additional requirements a STL unordered associative container must meet. In this table the standard dictates that the STL unordered containers (i.e., unordered_set, unordered_map, unordered_multiset and unordered_multimap) must provide as member types local_iterator and const_local_iterator.

• local_iterator is an iterator type whose category, value, difference, pointer and reference types are the same as the unordered container's iterator. This iterator can be used to iterate through a single bucket but not across buckets.
• const_local_iterator is an iterator type whose category, value, difference, pointer and reference types are the same as the unordered container's const_iterator. This iterator can be used to iterate through a single bucket but not across buckets.

Q

What are some uses for these iterators?

Swinton

Answer 1

The main thing I can see it being used for is to check how many collisions you have. Using bucket you can get what bucket a key is stored in. You can then pass that bucket value to begin which will return a local_iterator to the items in that bucket. Now you can iterate that bucket and see if you collide with any other elements and if you do, what those elements are. This, in turn, allows you to tune your hashing function.

Adage

Answer 2

This feature is quite useful, when you want to efficiently get a random element from an unordered_map.

With a vector, we can generate a random index, and get a random elements with that index in O(1). However, this does work with an unordered_map.

Instead, we can generate a random bucket index, and call unordered_map::begin(index) to get a random bucket in O(1). Then we can generate a random local index, i.e. index of elements in the bucket, and iterate elements with the local_iterator to get a random element (this step is NOT O(1), however, normally number of elements in a bucket is small).

unordered_map<int, int>::const_local_iterator random_element(const unordered_map<int, int> &m) {
    if (m.bucket_count() == 0)
        throw runtime_error("empty map");
    while (true) {
        auto bucket_index = gen_random_num() % m.bucket_count();
        auto bucket_size = m.bucket_size(bucket_index);
        if (bucket_size == 0)
            continue;
        auto element_index = gen_random_num() % bucket_size;
        return std::next(m.cbegin(bucket_index), element_index);
    }
}

Samuele

Wouldn’t that bias the distribution towards elements in less-populated buckets? – Beisel

Yes. So this method depends on a good hash function evenly distributing keys in buckets. – Samuele

Even the best hash function won’t reliably do that. – Beisel