CODEWITHSUNDEEP
c++c++11stl
Nemanja Trifunovic
Nemanja Trifunovic

Reputation: 24561

equal_range and std::unordered_multiset

My understanding is that we can't make any assumptions about the order of the elements within unordered... containers (even though they are implemented via hash tables). If that is correct, how can std::unordered_multiset::equal_range() return a range of equal values?

For instance:

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

Upvotes: 2

Views: 675

Answers (2)

Columbo
Columbo

Reputation: 60989

The standard specifies how equal elements lie in the range in [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.

Upvotes: 6

CoffeDeveloper
CoffeDeveloper

Reputation: 8315

From cplusplus.com

Elements with equivalent values are grouped together in the same bucket and in such a way that an iterator (see equal_range) can iterate through all of them.

From standard:

unordered_multiset::equal_range: The member function returns a range that contains all of the elements with the specified key. It returns make_pair(end(), end()) if no such elements exist

to understand see also equal_range:

Thus, the function determines the largest range of positions over which val can be inserted in the sequence and still preserve its ordering.

There is no mandate about HOW this ordering is preserved.

It is not specified anywhere that equal elements need to be contiguos if they have same key and value. Same key may mean that elements with same hash could be grouped togheter (equivalent means same hash), infact the following test provide a example in wich different elements are grouped by key (all have key 1 because of overrided hash_function), but the code is still working correctly.

#include <iostream>
#include <unordered_set>
using namespace std;

template <typename T>
struct my_hash
{
    size_t operator()(const T k) const
    {
    // Compute individual hash values for two data members and combine them using XOR and bit shifting
    return 1;
    }
};

int main() {
    typedef std::unordered_multiset<int,my_hash<int> > int_set;
    typedef int_set::iterator int_set_iterator;

    int_set set;
    set.insert(1);
    set.insert(2);
    set.insert(1);
    set.insert(2);
    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);
    std::cout<<range_size<<std::endl; // print 3

    range = set.equal_range(2);
    range_size = std::distance(range.first, range.second);
    std::cout<<range_size<<std::endl; //print 2

    range = set.equal_range(3);
    range_size = std::distance(range.first, range.second);
    std::cout<<range_size<<std::endl; //print 1

    return 0;
}

In short words, equal_range on unordered_multiset, generate a "list" of values that are first selected by key (hash value), then, those values are "filtered" so that they are equivalent and (according to equal_range spec) ordered by operator <=

This is all based on specifications, implementation still open. Since the question is "HOW", a possible way would be

  1. Take elements in the bucket with a given hash_code
  2. start filtering elements discarding unneeded elements with operator <=

A smart implementation of the unordered_multiset would "pre_filter" in some way the elements so that calling "equal_range" is cheap. but a implementation's is not required to be so smart and could as well incurr a performance penality when calling "range_equals" (assuming you have a not very smart hash_function)

Upvotes: 5

Related Questions