• Choose a category
• All
• Classic-Fiction

const hashmap& rhs);

hashmap& operator=(

hashmap&& rhs); // C++11

// Size methods

bool empty() const;

size_type size() const;

size_type max_size() const;

// Other modifying utilities

void swap(hashmap& hashIn);

// Other methods omitted for brevity

};

Code snippet from Hashmap\FinalHashmap\hashmap.h

The implementations of the constructor, destructor, copy constructor, move constructor, assignment operator, and move assignment operator are identical to those shown earlier for the basic hashmap implementation.

The implementations of size() and empty() are easy because the hashmap implementation tracks its size in the mSize data member. Note that size_type is one of the typedefs that is defined in the class. Since it is a member of the class, such a return type in the implementation must be fully qualified with typename hashmap.

template

bool hashmap::empty() const

{

return mSize == 0;

}

template

typename hashmap::size_type

hashmap::size() const

{

return mSize;

}

Code snippet from Hashmap\FinalHashmap\hashmap.cpp

max_size() is a little trickier. At first, you might think the maximum size of the hashmap container is the sum of the maximum size of all the lists. However, the worst-case scenario is that all the elements hash to the same bucket. Thus, the maximum size it can claim to support is the maximum size of a single list:

template

typename hashmap::size_type

hashmap::max_size() const

{

// In the worst case, all the elements hash to the same

// list, so the max_size is the max_size of a single list.

// This code assumes that all the lists have the same max_size.

return (*mElems)[0].max_size();

}

Code snippet from Hashmap\FinalHashmap\hashmap.cpp

Finally, the implementation of swap()uses the std::swap() utility function to swap each of the four data members. Note that the vector pointers are swapped, which is a constant-time operation:

// Just swap the four data members. Use the generic swap template.

template

void hashmap::swap(

hashmap& hashIn)

{

// Explicitly qualify with std:: so the compiler doesn't think

// it's a recursive call.

std::swap(*this, hashIn);

}

Code snippet from Hashmap\FinalHashmap\hashmap.cpp

Writing an Iterator

The most important container requirement is the iterator. In order to work with the generic algorithms, every container must provide an iterator for accessing the elements in the container. Your iterator should generally provide overloaded operator* and operator->, plus some other operations depending on its specific behavior. As long as your iterator provides the basic iteration operations, everything should be fine.

The first decision to make about your iterator is what kind it will be: forward, bidirectional, or random access. Random access iterators don’t make much sense for associative containers, so bidirectional seems like the logical choice for the hashmap iterator. That means you must also provide operator++, operator--, operator==, and operator!=. Consult Chapter 12 for more details on the requirements for the different iterators.

The second decision is how to order the elements of your container. The hashmap is unsorted, so iterating in a sorted order is probably too difficult. Instead, your iterator can just step through the buckets, starting with the elements in the first bucket and progressing to those in the last bucket. This order will appear random to the client, but will be consistent and repeatable.

The third decision is how to represent your iterator internally. The implementation is usually quite