The KeyEqual Template Parameter

Like a map, set, and other standard containers, a hash_map allows the client to specify the comparison type as a template parameter and to pass a specific comparison object of that type in the constructor. Unlike a map and set, a hash_map does not sort elements by key, but must still compare keys for equality. Thus, instead of using less as the default comparator, it uses the transparent equal_to<> comparator. The comparison object is used only to detect attempts to insert duplicate keys into the container.

The Hash Template Parameter

You should be able to change the hashing function to make it better suit the type of elements you want to store in the hash map. Thus, the hash_map template takes four template parameters: the key type, the value type, the comparator type, and the hash type.

The Type Aliases

The hash_map class template defines three type aliases:

using key_type = Key;
using mapped_type = T;
using value_type = std::pair<const Key, T>;

The value_type, in particular, is useful for referring to the more cumbersome pair<const Key, T> type. As you will see, these type aliases are required to satisfy the Standard Library container requirements.

The Constructor

The constructor initializes all the fields. It constructs mBuckets with the correct number of buckets. Unfortunately, the template syntax is somewhat dense. If the syntax confuses you, consult Chapter 12 for details on writing class templates.

// Construct mBuckets with the correct number of buckets.
template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>::hash_map(
    const KeyEqual& equal, size_t numBuckets, const Hash& hash)
    : mBuckets(numBuckets), mEqual(equal), mHash(hash)
{
    if (numBuckets == 0) {
        throw std::invalid_argument("Number of buckets must be positive");
    }
}

The implementation requires at least one bucket, so the constructor enforces that restriction.

Searching Elements

Each of the three major operations (lookup, insertion, and deletion) requires code to find an element with a given key. Thus, it is helpful to have a private helper method that performs that task. findElement() first uses the hash object to calculate the hash of the key and limits the calculated hash value to the number of hash buckets by taking the modulo of the calculated value. Then, it searches all the elements in that bucket for an element with a key matching the given key. The elements stored are key/value pairs, so the actual comparison must be done on the first field of the element. The comparison function object specified in the constructor is used to perform the comparison.

template <typename Key, typename T, typename KeyEqual, typename Hash>
std::pair<
    typename hash_map<Key, T, KeyEqual, Hash>::ListType::iterator, size_t>
        hash_map<Key, T, KeyEqual, Hash>::findElement(const key_type& k)
{

    // Hash the key to get the bucket.
    size_t bucket = mHash(k) % mBuckets.size();

    // Search for the key in the bucket.
    auto iter = find_if(begin(mBuckets[bucket]), end(mBuckets[bucket]),
        [this, &k](const auto& element) { return mEqual(element.first, k); });

    // Return a pair of the iterator and the bucket index.
    return std::make_pair(iter, bucket);
}

findElement() returns a pair containing an iterator and a bucket index. The bucket index is the index of the bucket to which the given key maps, independent of whether or not the given key is actually in the container. The returned iterator refers to an element in the bucket list, the list representing the bucket to which the key mapped. If the element is found, the iterator refers to that element; otherwise, it is the end iterator for that list.

The syntax in the function header of this method is somewhat confusing, particularly the use of the typename keyword. You must use the typename keyword whenever you are using a type that is dependent on a template parameter. Specifically, the type ListType::iterator , which is list<pair<const Key, T>>::iterator , is dependent on both the Key and T template parameters.

You can implement the find() method as a simple wrapper for findElement():

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::value_type*
    hash_map<Key, T, KeyEqual, Hash>::find(const key_type& k)
{
    // Use the findElement() helper, and C++17 structured bindings.
    auto[it, bucket] = findElement(k);
    if (it == end(mBuckets[bucket])) {
        // Element not found -- return nullptr.
        return nullptr;
    }
    // Element found -- return a pointer to it.
    return &(*it);
}

The const version of find() uses a const_cast to forward the request to the non-const version to avoid code duplication:

template <typename Key, typename T, typename KeyEqual, typename Hash>
const typename hash_map<Key, T, KeyEqual, Hash>::value_type*
    hash_map<Key, T, KeyEqual, Hash>::find(const key_type& k) const
{
    return const_cast<hash_map<Key, T, KeyEqual, Hash>*>(this)->find(k);
}

The operator[] implementation uses findElement() and if it does not find the element, it inserts it as follows:

template <typename Key, typename T, typename KeyEqual, typename Hash>
T& hash_map<Key, T, KeyEqual, Hash>::operator[] (const key_type& k)
{
    // Try to find the element. If it doesn't exist, add a new element.
    auto[it, bucket] = findElement(k);
    if (it == end(mBuckets[bucket])) {
        mSize++;
        mBuckets[bucket].push_back(std::make_pair(k, T()));
        return mBuckets[bucket].back().second;
    } else {
        return it->second;
    }
}

Inserting Elements

insert() must first check if an element with that key is already in the hash_map. If not, it can add the element to the list in the appropriate bucket. Note that findElement() returns the bucket index to which a key hashes, even if an element with that key is not found:

template <typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::insert(const value_type& x)
{
    // Try to find the element.
    auto[it, bucket] = findElement(x.first);
    if (it != end(mBuckets[bucket])) {
        // The element already exists.
        return;
    } else {
        // We didn't find the element, so insert a new one.
        mSize++;
        mBuckets[bucket].push_back(x);
    }
}

Note that this implementation of insert() returns void, so the caller does not know whether the element was inserted or if it was already in the hash_map. This shortcoming is resolved later in this chapter, once iterators have been implemented for hash_map.

Deleting Elements

erase() follows the same pattern as insert(): It first attempts to find the element by calling findElement(). If the element exists, it erases it from the list in the appropriate bucket. Otherwise, it does nothing.

template <typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::erase(const key_type& k)
{
    // First, try to find the element.
    auto[it, bucket] = findElement(k);
    if (it != end(mBuckets[bucket])) {
        // The element exists -- erase it.
        mBuckets[bucket].erase(it);
        mSize--;
    }
}

Removing All Elements

clear() simply clears each bucket, and sets the size of the hash_map to zero:

template <typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::clear() noexcept
{
    // Call clear on each bucket.
    for (auto& bucket : mBuckets) {
        bucket.clear();
    }
    mSize = 0;
}

Swapping

The swap() method just swaps all data members using std::swap():

template <typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::swap(
    hash_map<Key, T, KeyEqual, Hash>& other) noexcept
{
    using std::swap;

    swap(mBuckets, other.mBuckets);
    swap(mSize, other.mSize);
    swap(mEqual, other.mEqual);
    swap(mHash, other.mHash);
}

The following standalone swap() function is also provided, which simply forwards to the swap() method:

template <typename Key, typename T, typename KeyEqual, typename Hash>
void swap(hash_map<Key, T, KeyEqual, Hash>& first,
          hash_map<Key, T, KeyEqual, Hash>& second) noexcept
{
    first.swap(second);
}

Assignment Operators

Here are the implementations of the copy and move assignment operators. See Chapter 9 for a discussion of the copy-and-swap idiom.

template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>&
    hash_map<Key, T, KeyEqual, Hash>::operator=(
        const hash_map<Key, T, KeyEqual, Hash>& rhs)
{
    // check for self-assignment
    if (this == &rhs) {
        return *this;
    }

    // Copy-and-swap idiom
    auto copy = rhs;  // Do all the work in a temporary instance
    swap(copy);       // Commit the work with only non-throwing operations
    return *this;
}

template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>&
    hash_map<Key, T, KeyEqual, Hash>::operator=(
        hash_map<Key, T, KeyEqual, Hash>&& rhs) noexcept
{
    swap(rhs);
    return *this;
}

The const_hash_map_iterator Class

Given the decisions made in the previous section, it’s time to define the const_hash_map_iterator class. The first thing to note is that each const_hash_map_iterator object is an iterator for a specific instantiation of the hash_map class. In order to provide this one-to-one mapping, the const_hash_map_iterator must also be a class template with the hash map type as a template parameter called HashMap.

The main question in the class definition is how to conform to the bidirectional iterator requirements. Recall that anything that behaves like an iterator is an iterator. Your class is not required to derive from another class in order to qualify as a bidirectional iterator. However, if you want your iterator to be usable in the generic algorithms functions, you must specify its traits. The discussion earlier in this chapter explains that iterator_traits is a class template that defines, for each iterator type, five type aliases: value_type, difference_type, iterator_category, pointer, and reference. The iterator_traits class template coud be partially specialized for your new iterator type if you want. Alternatively, the default implementation of the iterator_traits class template just grabs the five type aliases out of the iterator class itself. Thus, you can simply define those type aliases directly in your iterator class. The const_hash_map_iterator is a bidirectional iterator, so you specify bidirectional_iterator_tag as the iterator category. Other legal iterator categories are input_iterator_tag, output_iterator_tag, forward_iterator_tag, and random_access_iterator_tag. For the const_hash_map_iterator, the element type is typename HashMap::value_type.

Here is the basic const_hash_map_iterator class definition:

template <typename HashMap>
class const_hash_map_iterator
{
    public:
        using value_type = typename HashMap::value_type;
        using difference_type = ptrdiff_t;
        using iterator_category = std::bidirectional_iterator_tag;
        using pointer = value_type*;
        using reference = value_type&;
        using list_iterator_type = typename HashMap::ListType::const_iterator;

        // Bidirectional iterators must supply a default constructor.
        // Using an iterator constructed with the default constructor
        // is undefined, so it doesn't matter how it's initialized.
        const_hash_map_iterator() = default;

        const_hash_map_iterator(size_t bucket, list_iterator_type listIt,
            const HashMap* hashmap);

        // Don't need to define a copy constructor or operator= because the
        // default behavior is what we want.

        // Don't need destructor because the default behavior
        // (not deleting mHashmap) is what we want!

        const value_type& operator*() const;

        // Return type must be something to which -> can be applied.
        // Return a pointer to a pair<const Key, T>, to which the compiler
        // will apply -> again.
        const value_type* operator->() const;

        const_hash_map_iterator<HashMap>& operator++();
        const_hash_map_iterator<HashMap> operator++(int);

        const_hash_map_iterator<HashMap>& operator--();
        const_hash_map_iterator<HashMap> operator--(int);

        // The following are ok as member functions because we don't
        // support comparisons of different types to this one.
        bool operator==(const const_hash_map_iterator<HashMap>& rhs) const;
        bool operator!=(const const_hash_map_iterator<HashMap>& rhs) const;
    protected:
        size_t mBucketIndex = 0;
        list_iterator_type mListIterator;
        const HashMap* mHashmap = nullptr;

        // Helper methods for operator++ and operator--
        void increment();
        void decrement();
};

Consult Chapter 15 for details on operator overloading if the definitions and implementations (shown in the next section) of the overloaded operators confuse you.

The const_hash_map_iterator Method Implementations

The const_hash_map_iterator constructor initializes the three member variables:

template<typename HashMap>
const_hash_map_iterator<HashMap>::const_hash_map_iterator(size_t bucket,
    list_iterator_type listIt, const HashMap* hashmap)
    : mBucketIndex(bucket), mListIterator(listIt), mHashmap(hashmap)
{
}

The default constructor is defaulted so that clients can declare const_hash_map_iterator variables without initializing them. An iterator constructed with the default constructor does not need to refer to any value, and attempting any operations on it is allowed to have undefined results.

The implementations of the dereferencing operators are concise, but can be tricky. Chapter 15 explains that operator* and operator-> are asymmetric; operator* returns a reference to the actual underlying value, which in this case is the element to which the iterator refers, while operator-> must return something to which the arrow operator can be applied again. Thus, it returns a pointer to the element. The compiler then applies -> to the pointer, which results in accessing a field of the element.

// Return a reference to the actual element.
template<typename HashMap>
const typename const_hash_map_iterator<HashMap>::value_type&
    const_hash_map_iterator<HashMap>::operator*() const
{
    return *mListIterator;
}

// Return a pointer to the actual element, so the compiler can
// apply -> to it to access the actual desired field.
template<typename HashMap>
const typename const_hash_map_iterator<HashMap>::value_type*
    const_hash_map_iterator<HashMap>::operator->() const
{
    return &(*mListIterator);
}

The increment and decrement operators are implemented as follows. They defer the actual incrementing and decrementing to the private increment() and decrement() helper methods.

// Defer the details to the increment() helper.
template<typename HashMap>
const_hash_map_iterator<HashMap>&
    const_hash_map_iterator<HashMap>::operator++()
{
    increment();
    return *this;
}

// Defer the details to the increment() helper.
template<typename HashMap>
const_hash_map_iterator<HashMap>
    const_hash_map_iterator<HashMap>::operator++(int)
{
    auto oldIt = *this;
    increment();
    return oldIt;
}

// Defer the details to the decrement() helper.
template<typename HashMap>
const_hash_map_iterator<HashMap>&
    const_hash_map_iterator<HashMap>::operator--()
{
    decrement();
    return *this;
}

// Defer the details to the decrement() helper.
template<typename HashMap>
const_hash_map_iterator<HashMap>
    const_hash_map_iterator<HashMap>::operator--(int)
{
    auto oldIt = *this;
    decrement();
    return oldIt;
}

Incrementing a const_hash_map_iterator tells it to refer to the “next” element in the container. This method first increments the list iterator, then checks if it has reached the end of its bucket. If so, it finds the next non-empty bucket in the hash_map and sets the list iterator equal to the start element in that bucket. Note that it can’t simply move to the next bucket, because there might not be any elements in it. If there are no more non-empty buckets, mListIterator is set, by the convention chosen for this example, to the end iterator of the last bucket in the hash_map, which is the special “end” position of the const_hash_map_iterator. Iterators are not required to be any safer than dumb pointers, so error-checking for things like incrementing an iterator already at the end is not required.

// Behavior is undefined if mListIterator already refers to the past-the-end
// element, or is otherwise invalid.
template<typename HashMap>
void const_hash_map_iterator<HashMap>::increment()
{
    // mListIterator is an iterator into a single bucket. Increment it.
    ++mListIterator;

    // If we're at the end of the current bucket,
    // find the next bucket with elements.
    auto& buckets = mHashmap->mBuckets;
    if (mListIterator == end(buckets[mBucketIndex])) {
        for (size_t i = mBucketIndex + 1; i < buckets.size(); i++) {
            if (!buckets[i].empty()) {
                // We found a non-empty bucket.
                // Make mListIterator refer to the first element in it.
                mListIterator = begin(buckets[i]);
                mBucketIndex = i;
                return;
            }
        }
        // No more non-empty buckets. Set mListIterator to refer to the
        // end iterator of the last list.
        mBucketIndex = buckets.size() - 1;
        mListIterator = end(buckets[mBucketIndex]);
    }
}

Decrement is the inverse of increment: it makes the iterator refer to the “previous” element in the container. However, there is an asymmetry because of the asymmetry between the way the start and end positions are represented: start is the first element, but end is “one past” the last element. The algorithm for decrement first checks if the underlying list iterator is at the start of its current bucket. If not, it can just be decremented. Otherwise, the code needs to check for the first non-empty bucket before the current one. If one is found, the list iterator must be set to refer to the last element in that bucket, which is the end iterator decremented by one. If no non-empty buckets are found, the decrement is invalid, so the code can do anything it wants (behavior is undefined). Note that the for loop needs to use a signed integer type for its loop variable and not an unsigned type such as size_t because the loop uses --i:

// Behavior is undefined if mListIterator already refers to the first
// element, or is otherwise invalid.
template<typename HashMap>
void const_hash_map_iterator<HashMap>::decrement()
{
    // mListIterator is an iterator into a single bucket.
    // If it's at the beginning of the current bucket, don't decrement it.
    // Instead, try to find a non-empty bucket before the current one.
    auto& buckets = mHashmap->mBuckets;
    if (mListIterator == begin(buckets[mBucketIndex])) {
        for (int i = mBucketIndex - 1; i >= 0; --i) {
            if (!buckets[i].empty()) {
                mListIterator = --end(buckets[i]);
                mBucketIndex = i;
                return;
            }
        }
        // No more non-empty buckets. This is an invalid decrement.
        // Set mListIterator to refer to the end iterator of the last list.
        mBucketIndex = buckets.size() - 1;
        mListIterator = end(buckets[mBucketIndex]);
    } else {
        // We're not at the beginning of the bucket, so just move down.
        --mListIterator;
    }
}

Note that both increment() and decrement() access private members of the hash_map class. Thus, the hash_map class must declare const_hash_map_iterator to be a friend class.

After increment() and decrement(), operator== and operator!= are positively simple. They just compare each of the three data members of the objects:

template<typename HashMap>
bool const_hash_map_iterator<HashMap>::operator==(
    const const_hash_map_iterator<HashMap>& rhs) const
{
    // All fields, including the hash_map to which the iterators refer,
    // must be equal.
    return (mHashmap == rhs.mHashmap &&
        mBucketIndex == rhs.mBucketIndex &&
        mListIterator == rhs.mListIterator);
}

template<typename HashMap>
bool const_hash_map_iterator<HashMap>::operator!=(
    const const_hash_map_iterator<HashMap>& rhs) const
{
    return !(*this == rhs);
}

The hash_map_iterator Class

The hash_map_iterator class derives from const_hash_map_iterator. It does not need to override operator==, operator!=, increment(), and decrement() because the base class versions are just fine:

template <typename HashMap>
class hash_map_iterator : public const_hash_map_iterator<HashMap>
{
    public:
        using value_type =
            typename const_hash_map_iterator<HashMap>::value_type;
        using difference_type = ptrdiff_t;
        using iterator_category = std::bidirectional_iterator_tag;
        using pointer = value_type*;
        using reference = value_type&;
        using list_iterator_type = typename HashMap::ListType::iterator;

        hash_map_iterator() = default;
        hash_map_iterator(size_t bucket, list_iterator_type listIt,
            HashMap* hashmap);

        value_type& operator*();
        value_type* operator->();

        hash_map_iterator<HashMap>& operator++();
        hash_map_iterator<HashMap> operator++(int);

        hash_map_iterator<HashMap>& operator--();
        hash_map_iterator<HashMap> operator--(int);
};

The hash_map_iterator Method Implementations

The implementations of the hash_map_iterator methods are rather straightforward. The constructor just calls the base class constructor. The operator* and operator-> use const_cast to return a non-const type. operator++ and operator-- just use the increment() and decrement() from the base class, but return a hash_map_iterator instead of a const_hash_map_iterator. Note that the C++ name lookup rules require you to explicitly use the this pointer to refer to data members and methods in a base class template:

template<typename HashMap>
hash_map_iterator<HashMap>::hash_map_iterator(size_t bucket,
    list_iterator_type listIt, HashMap* hashmap)
    : const_hash_map_iterator<HashMap>(bucket, listIt, hashmap)
{
}

// Return a reference to the actual element.
template<typename HashMap>
typename hash_map_iterator<HashMap>::value_type&
    hash_map_iterator<HashMap>::operator*()
{
    return const_cast<value_type&>(*this->mListIterator);
}

// Return a pointer to the actual element, so the compiler can
// apply -> to it to access the actual desired field.
template<typename HashMap>
typename hash_map_iterator<HashMap>::value_type*
    hash_map_iterator<HashMap>::operator->()
{
    return const_cast<value_type*>(&(*this->mListIterator));
}

// Defer the details to the increment() helper in the base class.
template<typename HashMap>
hash_map_iterator<HashMap>& hash_map_iterator<HashMap>::operator++()
{
    this->increment();
    return *this;
}

// Defer the details to the increment() helper in the base class.
template<typename HashMap>
hash_map_iterator<HashMap> hash_map_iterator<HashMap>::operator++(int)
{
    auto oldIt = *this;
    this->increment();
    return oldIt;
}

// Defer the details to the decrement() helper in the base class.
template<typename HashMap>
hash_map_iterator<HashMap>& hash_map_iterator<HashMap>::operator--()
{
    this->decrement();
    return *this;
}

// Defer the details to the decrement() helper in the base class.
template<typename HashMap>
hash_map_iterator<HashMap> hash_map_iterator<HashMap>::operator--(int)
{
    auto oldIt = *this;
    this->decrement();
    return oldIt;
}

Iterator Type Aliases and Access Methods

The final piece involved in providing iterator support for hash_map is to supply the necessary type aliases in the hash_map class template, and to write the begin(), end(), cbegin(), and cend() methods. The type aliases and method prototypes look like this:

template <typename Key, typename T, typename KeyEqual = std::equal_to<>,
    typename Hash = hash<Key>>
class hash_map
{
    public:
        // Other type aliases omitted for brevity
        using iterator = hash_map_iterator<hash_map_type>;
        using const_iterator = const_hash_map_iterator<hash_map_type>;

        // Iterator methods
        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;
        const_iterator cbegin() const;
        const_iterator cend() const;
        // Remainder of class definition omitted for brevity
};

The implementation of begin() includes an optimization for the case when there are no elements in the hash_map, in which case the end iterator is returned. Here is the code:

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
    hash_map<Key, T, KeyEqual, Hash>::begin()
{
    if (mSize == 0) {
        // Special case: there are no elements, so return the end iterator.
        return end();
    }

    // We know there is at least one element. Find the first element.
    for (size_t i = 0; i < mBuckets.size(); ++i) {
        if (!mBuckets[i].empty()) {
            return hash_map_iterator<hash_map_type>(i,
                std::begin(mBuckets[i]), this);
        }
    }
    // Should never reach here, but if we do, return the end iterator.
    return end();
}

end() creates a hash_map_iterator referring to the end iterator of the last bucket:

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
    hash_map<Key, T, KeyEqual, Hash>::end()
{
    // The end iterator is the end iterator of the list of the last bucket.
    size_t bucket = mBuckets.size() - 1;
    return hash_map_iterator<hash_map_type>(bucket,
        std::end(mBuckets[bucket]), this);
}

The implementations of the const versions of begin() and end() use const_cast to call the non-const versions. These non-const versions return a hash_map_iterator, which is convertible to a const_hash_map_iterator:

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::const_iterator
    hash_map<Key, T, KeyEqual, Hash>::begin() const
{
    return const_cast<hash_map_type*>(this)->begin();
}

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::const_iterator
    hash_map<Key, T, KeyEqual, Hash>::end() const
{
    return const_cast<hash_map_type*>(this)->end();
}

The cbegin() and cend() methods forward the request to the const versions of begin() and end():

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::const_iterator
    hash_map<Key, T, KeyEqual, Hash>::cbegin() const
{
    return begin();
}

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::const_iterator
    hash_map<Key, T, KeyEqual, Hash>::cend() const
{
    return end();
}

Using the hash_map Iterators

Now that hash_map supports iteration, you can iterate over its elements just as you would on any Standard Library container, and you can pass the iterators to methods and functions. Here are some examples:

hash_map<string, int> myHash;
myHash.insert(make_pair("KeyOne", 100));
myHash.insert(make_pair("KeyTwo", 200));
myHash.insert(make_pair("KeyThree", 300));

for (auto it = myHash.cbegin(); it != myHash.cend(); ++it) {
    // Use both -> and * to test the operations.
    cout << it->first << " maps to " << (*it).second << endl;
}

// Print elements using a range-based for loop
for (auto& p : myHash) {
    cout << p.first << " maps to " << p.second << endl;
}

// Print elements using a range-based for loop and C++17 structured bindings
for (auto&[key, value] : myHash) {
    cout << key << " maps to " << value << endl;
}

// Create an std::map with all the elements in the hash_map.
map<string, int> myMap(cbegin(myHash), cend(myHash));
for (auto& p : myMap) {
    cout << p.first << " maps to " << p.second << endl;
}

The last piece of code also shows that the non-member functions such as std::cbegin() and std::cend() are working as expected.

hash_map Iterator Range Constructor

The constructor accepting an iterator range is a method template so that it can take an iterator range from any container, not just other hash_maps. If it were not a method template, it would need to specify the InputIterator type explicitly as hash_map_iterator, limiting it to iterators from hash_maps. Despite the syntax, the implementation is uncomplicated: it delegates the construction to the explicit constructor to initialize all the data members, then calls insert() to actually insert all the elements in the specified range.

// Make a call to insert() to actually insert the elements.
template <typename Key, typename T, typename KeyEqual, typename Hash>
template <typename InputIterator>
hash_map<Key, T, KeyEqual, Hash>::hash_map(
    InputIterator first, InputIterator last, const KeyEqual& equal,
    size_type numBuckets, const Hash& hash)
    : hash_map(equal, numBuckets, hash)
{
    insert(first, last);
} 

hash_map Initializer List Constructor

Initializer lists are discussed in Chapter 1. Following is the implementation of the hash_map constructor that takes an initializer list, which is very similar to the implementation of the constructor accepting an iterator range:

template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>::hash_map(
    std::initializer_list<value_type> il,
    const KeyEqual& equal, size_type numBuckets, const Hash& hash)
    : hash_map(equal, numBuckets, hash) 
{
    insert(std::begin(il), std::end(il));
}

With this initializer list constructor, a hash_map can be constructed as follows:

hash_map<string, int> myHash {
    { "KeyOne", 100 },
    { "KeyTwo", 200 },
    { "KeyThree", 300 } };

hash_map Initializer List Assignment Operator

Assignment operators can also accept an initializer list on the right-hand side. Following is an implementation of an initializer list assignment operator for hash_map. It uses a copy-and-swap-like algorithm to guarantee strong exception safety.

template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>& hash_map<Key, T, KeyEqual, Hash>::operator=(
    std::initializer_list<value_type> il)
{
    // Do all the work in a temporary instance
    hash_map_type newHashMap(il, mEqual, mBuckets.size(), mHash);
    swap(newHashMap);  // Commit the work with only non-throwing operations
    return *this;
}

With this assignment operator, you can write code as follows:

myHash = {
    { "KeyOne", 100 },
    { "KeyTwo", 200 },
    { "KeyThree", 300 } };

hash_map Insertion Operations

In the earlier section, “Using the Basic Hash Map,” a simple insert() method is given. In this version, four insert() methods are provided with additional features:

• The simple insert() operation returns a pair<iterator, bool>, which indicates both where the item is inserted and whether or not it was newly created.
• The version of insert() that takes a hint is useless for a hash_map, but it is provided for symmetry with other kinds of collections. The hint is ignored, and it merely calls the first version.
• The third form of insert() is a method template, so ranges of elements from arbitrary containers can be inserted into the hash_map.
• The last form of insert() accepts an initializer_list<value_type>.

Note that technically, the following versions of insert() can also be provided. These accept rvalue references.

std::pair<iterator, bool> insert(value_type&& x);
iterator insert(const_iterator hint, value_type&& x);

The hash_map does not provide these. Additionally, there are two versions of insert() related to handling nodes. Nodes are discussed in Chapter 17. The hash_map omits these as well.

The first two insert() methods are implemented as follows:

template <typename Key, typename T, typename KeyEqual, typename Hash>
std::pair<typename hash_map<Key, T, KeyEqual, Hash>::iterator, bool>
    hash_map<Key, T, KeyEqual, Hash>::insert(const value_type& x)
{
    // Try to find the element.
    auto[it, bucket] = findElement(x.first);
    bool inserted = false;
    if (it == std::end(mBuckets[bucket])) {
        // We didn't find the element, so insert a new one.
        it = mBuckets[bucket].insert(it, x);
        inserted = true;
        mSize++;
    }
    return std::make_pair(
        hash_map_iterator<hash_map_type>(bucket, it, this), inserted);
}

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
    hash_map<Key, T, KeyEqual, Hash>::insert(
        const_iterator /*hint*/, const value_type& x)
{
    // Completely ignore position.
    return insert(x).first;
}

The third form of insert() is a method template for the same reason as the constructor shown earlier: it should be able to insert elements by using iterators from containers of any type. The actual implementation uses an insert_iterator, described earlier in this chapter.

template <typename Key, typename T, typename KeyEqual, typename Hash>
template <typename InputIterator>
void hash_map<Key, T, KeyEqual, Hash>::insert(
    InputIterator first, InputIterator last)
{
    // Copy each element in the range by using an insert_iterator adaptor.
    // Give begin() as a dummy position -- insert ignores it anyway.
    std::insert_iterator<hash_map_type> inserter(*this, begin());
    std::copy(first, last, inserter);
}

The last insert operation accepts an initializer list. The implementation for hash_map simply forwards the work to the insert() method accepting an iterator range:

template <typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::insert(
    std::initializer_list<value_type> il)
{
    insert(std::begin(il), std::end(il));
}

With this insert() method, you can write code as follows:

myHash.insert({
    { "KeyFour", 400 },
    { "KeyFive", 500 } });

hash_map Emplace Operations

Emplace operations construct objects in-place. They are discussed in Chapter 17. The emplace methods for hash_map look as follows :

template <typename... Args>
std::pair<iterator, bool> emplace(Args&&... args);

template <typename... Args>
iterator emplace_hint(const_iterator hint, Args&&... args);

The ... in these lines are not typos. These are so-called variadic templates, that is, templates with a variable number of template type parameters and a variable number of function parameters. Variadic templates are discussed in Chapter 22. This hash_map implementation omits emplace operations.

hash_map Erase Operations

The version of erase() in the earlier section, “A Basic Hash Map,” is not compliant with Standard Library requirements. You need to implement the following versions:

• A version that takes as a parameter a key_type and returns a size_type for the number of elements removed from the collection (for hash_map there are only two possible return values, 0 and 1).
• A version that erases a value at a specific iterator position, and returns an iterator to the element following the erased element.
• A version that erases a range of elements based on two iterators, and returns an iterator to the element following the last erased element.

The first version is implemented as follows:

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
    hash_map<Key, T, KeyEqual, Hash>::erase(const key_type& k)
{
    // First, try to find the element.
    auto[it, bucket] = findElement(k);
    if (it != std::end(mBuckets[bucket])) {
        // The element exists -- erase it.
        mBuckets[bucket].erase(it);
        mSize--;
        return 1;
    } else {
        return 0;
    }
}

The second version of erase() must remove the element at a specific iterator position. The iterator given is, of course, a hash_map_iterator. Thus, hash_map must have some ability to obtain the underlying bucket and list iterator from the hash_map_iterator. The approach taken here is to make the hash_map class a friend of the hash_map_iterator (not shown in the earlier class definition). Here is the implementation of this version of erase():

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
    hash_map<Key, T, KeyEqual, Hash>::erase(iterator position)
{
    iterator next = position;
    ++next;
    // Erase the element from its bucket.
    mBuckets[position.mBucketIndex].erase(position.mListIterator);
    mSize--;
    return next;
}

The final version of erase() removes a range of elements. It iterates from first to last, calling erase() on each element, thus letting the previous version of erase() do all the work:

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
    hash_map<Key, T, KeyEqual, Hash>::erase(iterator first, iterator last)
{
    // Erase all the elements in the range.
    for (iterator next = first; next != last;) {
        next = erase(next);
    }
    return last;
}

hash_map Accessor Operations

The standard requires methods called key_eq() and hash_function() to retrieve the equality predicate and the hash function respectively:

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::key_equal
    hash_map<Key, T, KeyEqual, Hash>::key_eq() const
{
    return mEqual;
}

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::hasher
    hash_map<Key, T, KeyEqual, Hash>::hash_function() const
{
    return mHash;
}

The find() method is identical to the version shown earlier for the basic hash_map, except for the return code. Instead of returning a pointer to the element, it constructs a hash_map_iterator referring to it:

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
    hash_map<Key, T, KeyEqual, Hash>::find(const key_type& k)
{
    // Use the findElement() helper, and C++17 structured bindings.
    auto[it, bucket] = findElement(k);
    if (it == std::end(mBuckets[bucket])) {
        // Element not found -- return the end iterator.
        return end();
    }
    // Element found -- convert the bucket/iterator to a hash_map_iterator.
    return hash_map_iterator<hash_map_type>(bucket, it, this);
}

The const version of find() returns a const_hash_map_iterator. It uses const_cast to call the non-const version of find() to avoid code duplication. Note that the non-const find() returns a hash_map_iterator, which is convertible to a const_hash_map_iterator.

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::const_iterator
    hash_map<Key, T, KeyEqual, Hash>::find(const key_type& k) const
{
    return const_cast<hash_map_type*>(this)->find(k);
}

The implementations of both versions of equal_range() are identical, except that one returns a pair of hash_map_iterators while the other returns a pair of const_hash_map_iterators. They both simply forward the request to find(). A hash_map cannot have elements with duplicate keys, so the result of equal_range() for hash_map is always a pair of identical iterators.

template <typename Key, typename T, typename KeyEqual, typename Hash>
std::pair<
    typename hash_map<Key, T, KeyEqual, Hash>::iterator,
    typename hash_map<Key, T, KeyEqual, Hash>::iterator>
    hash_map<Key, T, KeyEqual, Hash>::equal_range(const key_type& k)
{
    auto it = find(k);
    return std::make_pair(it, it);
}

Because hash_map does not allow duplicate keys, count() can only return 1 or 0: 1 if it finds the element, and 0 if it doesn’t. The implementation just wraps a call to find(). The find() method returns the end iterator if it can’t find the element. count() retrieves an end iterator by calling end() in order to compare it.

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
    hash_map<Key, T, KeyEqual, Hash>::count(const key_type& k) const
{
    // There are either 1 or 0 elements matching key k.
    // If we can find a match, return 1, otherwise return 0.
    if (find(k) == end()) {
        return 0;
    } else {
        return 1;
    }
}

The final method, operator[], is not required by the standard, but is provided for convenience of the programmer, and to be symmetric with std::map. The prototype is identical to the one for std::map. The comments explain the potentially confusing one-line implementation.

template <typename Key, typename T, typename KeyEqual, typename Hash>
T& hash_map<Key, T, KeyEqual, Hash>::operator[] (const key_type& k)
{
    // It's a bit cryptic, but it basically attempts to insert
    // a new key/value pair of k and a zero-initialized value. Regardless
    // of whether the insert succeeds or fails, insert() returns a pair of
    // an iterator/bool. The iterator refers to a key/value pair, the
    // second element of which is the value we want to return.
    return ((insert(std::make_pair(k, T()))).first)->second;
}

hash_map Bucket Operations

Unordered associative containers should also provide a number of bucket-related methods:

• bucket_count() returns the number of buckets in the container.
• max_bucket_count() returns the maximum number of buckets that are supported.
• bucket(key) returns the index of the bucket to which the given key maps.
• bucket_size(n) returns the number of elements in the bucket with given index.
• begin(n), end(n), cbegin(n), cend(n) return local begin and end iterators to the bucket with given index.

Here are the implementations for the hash_map:

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
    hash_map<Key, T, KeyEqual, Hash>::bucket_count() const
{
    return mBuckets.size();
}

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
    hash_map<Key, T, KeyEqual, Hash>::max_bucket_count() const
{
    return mBuckets.max_size();
}

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
    hash_map<Key, T, KeyEqual, Hash>::bucket(const Key& k) const
{
    return const_cast<hash_map_type*>(this)->findElement(k).second;
}

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
    hash_map<Key, T, KeyEqual, Hash>::bucket_size(size_type n) const
{
    return mBuckets[n].size();
}

template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::local_iterator
    hash_map<Key, T, KeyEqual, Hash>::begin(size_type n)
{
    return mBuckets[n].begin();
}

The implementations for the other begin(n), end(n), cbegin(n), and cend(n) methods are similar; they simply forward the call to the correct bucket list based on the given index.

Finally, an unordered associative container should also provide load_factor(), max_load_ factor(), rehash(), and reserve() methods. These are omitted for hash_map.