• Choose a category
• All
• Classic-Fiction

}

// Print elements using C++11 range-based for loop

for (auto& p : myHash)

cout << p.first << " maps to " << p.second << endl;

// Create a map with all the elements in the hashmap.

map myMap(myHash.begin(), myHash.end());

for (auto it = myMap.begin(); it != myMap.end(); ++it) {

cout << it->first << " maps to " << (*it).second << endl;

}

Code snippet from Hashmap\FinalHashmap\TestHashmap.cpp

Note on Allocators

As described earlier in this chapter, all the STL containers allow you to specify a custom memory allocator. A “good citizen” hashmap implementation should do the same. However, we omit those details because they obscure the main points of this implementation.

Note on Reversible Containers

If your container supplies a bidirectional or random access iterator, it is considered reversible. Reversible containers are supposed to supply two additional typedefs:

TYPE NAME DESCRIPTION

reverse_iterator The type for iterating over elements of the container in reverse order.

const_reverse_iterator A version of reverse_iterator for iterating over const elements of the container in reverse order.

Additionally, the container should provide rbegin() and rend() which are symmetric with begin() and end(); and should provide the C++11 crbegin() and crend() which are symmetric with cbegin() and cend(). The usual implementations just use the reverse_iterator adapter described earlier in this chapter. We leave them as an exercise for the reader.

Making the Hashmap an Associative Container

In addition to the basic container requirements shown already, you can also make your container adhere to additional requirements for associative, unordered associative, or sequential containers. This example makes the hashmap an associative container, so it should conform to the following typedefs and methods.

Associative Container typedef Requirements

Associative containers require three additional typedefs:

TYPE NAME DESCRIPTION

key_type The key type with which the container is instantiated

key_compare The comparison class or function pointer type with which the container is instantiated

value_compare Class for comparing two value_type elements

This example implementation also throws in a mapped_type typedef, because that’s what the map does. The value_compare is implemented not as a typedef, but as a nested class definition. Alternatively, the class could be a friend class of the hashmap, but this definition follows the map definition found in the standard. The purpose of the value_compare class is to call the comparison function on the keys of two elements:

template ,

typename Hash = DefaultHash>

class hashmap

{

public:

typedef Key key_type;

typedef T mapped_type;

typedef pair value_type;

typedef Compare key_compare;

typedef pair& reference;

typedef const pair& const_reference;

typedef HashIterator iterator;

typedef HashIterator const_iterator;

typedef size_t size_type;

typedef ptrdiff_t difference_type;

// Required class definition for associative containers

class value_compare :

public std::binary_function

{

friend class hashmap;

public:

bool operator() (const value_type& x, const value_type& y) const

{

return comp(x.first, y.first);

}

protected:

Compare comp;

value_compare(Compare c) : comp(c) {}

};

// Remainder of hashmap class definition omitted for brevity

};

Code snippet from Hashmap\FinalHashmap\hashmap.h

Associative Container Method Requirements

The standard prescribes quite a few additional method requirements for associative containers:

METHOD DESCRIPTION WORST CASE COMPLEXITY

Constructor taking an iterator range. Constructs the container and inserts elements in the iterator range. The iterator range need not refer into another container of the same type.

Note that all constructors of associative containers must take a comparison