Professional C__ - Marc Gregoire [298]
hashmap const hashmap mSize(src.mSize), mComp(src.mComp), mHash(src.mHash) { // Don't need to bother checking if numBuckets is positive, because // we know src checked. Use the vector copy constructor. mElems = new vector } // C++11 move constructor template hashmap { // move ownership mElems = src.mElems; src.mElems = nullptr; mSize = src.mSize; src.mSize = 0; mComp = src.mComp; mHash = src.mHash; } // Assignment operator template hashmap const hashmap { // Check for self-assignment. if (this != &rhs) { delete mElems; mSize = rhs.mSize; mComp = rhs.mComp; mHash = rhs.mHash; // Don't need to bother checking if numBuckets is positive, because // we know rhs checked. Use the vector copy constructor. mElems = new vector } return *this; } // C++11 move assignment operator template hashmap hashmap { // check for self-assignment if (this != &rhs) { delete mElems; // move ownership mElems = rhs.mElems; rhs.mElems = nullptr; mSize = rhs.mSize; rhs.mSize = 0; mComp = rhs.mComp; mHash = rhs.mHash; } return *this; } Code snippet from Hashmap\BasicHashmap\hashmap.cpp Note that the copy constructor and assignment operator both construct the new vector by using its copy constructor with the vector from the source hashmap as the source. Element Lookup 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 protected helper method that performs that task. findElement() first uses the hash object to hash the key to a specific bucket. Then, it looks 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. lists require a linear search to find matching elements, but you could use the find() algorithm instead of an explicit for loop. template typename list hashmap size_t& bucket) const { // Hash the key to get the bucket. bucket = mHash.hash(x); // Look for the key in the bucket. for (auto it = (*mElems)[bucket].begin(); it != (*mElems)[bucket].end(); ++it) { if (mComp(it->first, x)) { return it; } } return (*mElems)[bucket].end(); } Code snippet from Hashmap\BasicHashmap\hashmap.cpp Note that findElement() returns an iterator referring to an element in the list representing the bucket to which the key hashed. If the element is found, the iterator refers to that element; otherwise, it is the end iterator for that list. The bucket is returned by reference in the bucket argument. The syntax in 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 list Another note on the syntax: mElems is a pointer, so it must be dereferenced before you can apply operator[] to it to obtain a specific element. Hence the somewhat ugly: (*mElems)[bucket]. You can implement the find() method as a simple wrapper for findElement(): template typename hashmap