Online Book Reader

Home Category

Professional C__ - Marc Gregoire [297]

By Root 1570 0
that type in the constructor. Unlike the map and set, the hashmap does not sort elements by key, but must still compare keys for equality. Thus, instead of using less as the default comparison, it uses equal_to. The comparison object is used only to detect attempts to insert duplicate keys into the container.

The Template Argument Hash

When you allow clients to define their own classes, from which they construct objects to pass in the constructor, you must figure out how to specify the type of parameter in the constructor. There are several ways to do it. The STL way, which is on the complicated end of the spectrum, takes the class type as a template parameter, and uses that templatized type as the type in the constructor. We follow that approach for the hash class, as you can see above. Thus, the hashmap template takes four template parameters: the key type, the value type, the comparison type, and the hash type.

The typedefs

The hashmap class template defines three typedefs:

typedef Key key_type;

typedef T mapped_type;

typedef pair value_type;

The value_type, in particular, is useful for referring to the more cumbersome pair. As you will see, these typedefs are also required for STL containers by the standard.

The Implementation

After you finalize the hashmap interface, you need to choose the implementation model. The basic hash table structure generally consists of a fixed number of buckets, each of which can store one or more elements. The buckets should be accessible in constant time based on a bucket-id (the result of hashing a key). Thus, a vector is the most appropriate container for the buckets. Each bucket must store a list of elements, so the STL list can be used as the bucket type. Thus, the final structure is a vector of lists of pair elements. Here are the protected members of the hashmap class:

protected:

typedef list ListType;

// In this first implementation, it would be easier to use a vector

// instead of a pointer to a vector, which requires dynamic allocation.

// However, a pointer to a vector is used so that, in the final

// implementation, swap() can be implemented in constant time.

vector* mElems;

size_t mSize;

Compare mComp;

Hash mHash;

Code snippet from Hashmap\BasicHashmap\hashmap.h

Without the typedefs for value_type and ListType, the line declaring mElems would look like this:

vector>>* mElems;

The mComp and mHash members store the comparison and hashing objects, respectively, and mSize stores the number of elements currently in the container.

The Constructor

The constructor initializes all the fields and allocates a new vector. Unfortunately, the template syntax is somewhat dense. As mentioned in the beginning of this chapter, if the syntax confuses you, consult Chapter 19 for details on writing class templates.

// Construct mElems with the number of buckets.

template

hashmap::hashmap(

const Compare& comp, const Hash& hash) throw(invalid_argument) :

mSize(0), mComp(comp), mHash(hash)

{

if (mHash.numBuckets() <= 0) {

throw invalid_argument("Number of buckets must be positive");

}

mElems = new vector(mHash.numBuckets());

}

Code snippet from Hashmap\BasicHashmap\hashmap.cpp

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

Destructor, Copy Constructor, Move Constructor, Copy Assignment Operator, and Move Assignment Operator

Here are the implementations of the destructor, copy constructor, move constructor, copy assignment operator, and move assignment operator. Their implementations are straightforward. Consult Chapter 9 for more details on how move constructors and move assignment operators work.

template

hashmap::~hashmap()

{

delete mElems;

mElems = nullptr;

mSize = 0;

}

// Copy constructor

template

®Online Book Reader