• Choose a category
• All
• Classic-Fiction

hashmap::find(const key_type& x)

{

size_t bucket;

// Use the findElement() helper.

auto it = findElement(x, bucket);

if (it == (*mElems)[bucket].end()) {

// We didn't find the element--return nullptr.

return nullptr;

}

// We found the element. Return a pointer to it.

return &(*it);

}

Code snippet from Hashmap\BasicHashmap\hashmap.cpp

The operator[] method uses the find() method, and if it does not find the element, it inserts it:

template

T& hashmap::operator[] (const key_type& x)

{

// Try to find the element. If it doesn't exist, add a new element.

value_type* found = find(x);

if (found == nullptr) {

insert(make_pair(x, T()));

found = find(x);

}

return found->second;

}

Code snippet from Hashmap\BasicHashmap\hashmap.cpp

This method is somewhat inefficient, because in the worst case it calls find() twice and insert() once. However, each of these operations runs in constant time with respect to the number of elements in the hashmap, so the overhead is not too significant.

Element Insert

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

template

void hashmap::insert(const value_type& x)

{

size_t bucket;

// Try to find the element.

auto it = findElement(x.first, bucket);

if (it != (*mElems)[bucket].end()) {

// The element already exists.

return;

} else {

// We didn't find the element, so insert a new one.

mSize++;

(*mElems)[bucket].insert((*mElems)[bucket].end(), x);

}

}

Code snippet from Hashmap\BasicHashmap\hashmap.cpp

Element Delete

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

void hashmap::erase(const key_type& x)

{

size_t bucket;

// First, try to find the element.

auto it = findElement(x, bucket);

if (it != (*mElems)[bucket].end()) {

// The element exists--erase it.

(*mElems)[bucket].erase(it);

mSize--;

}

}

Code snippet from Hashmap\BasicHashmap\hashmap.cpp

Using the Basic Hashmap

Here is a small test program demonstrating the basic hashmap class template:

hashmap myHash;

myHash.insert(make_pair(4, 40));

myHash.insert(make_pair(6, 60));

// x will have type hashmap::value_type*

auto x = myHash.find(4);

if (x != nullptr) {

cout << "4 maps to " << x->second << endl;

} else {

cout << "cannot find 4 in map" << endl;

}

myHash.erase(4);

auto x2 = myHash.find(4);

if (x2 != nullptr) {

cout << "4 maps to " << x2->second << endl;

} else {

cout << "cannot find 4 in map" << endl;

}

myHash[4] = 35;

myHash[4] = 60;

auto x3 = myHash.find(4);

if (x3 != nullptr) {

cout << "4 maps to " << x3->second << endl;

} else {

cout << "cannot find 4 in map" << endl;

}

Code snippet from Hashmap\BasicHashmap\TestHashmap.cpp

The output is:

4 maps to 40

cannot find 4 in map

4 maps to 60

With the Microsoft Visual C++ compiler, at least through Visual Studio 2010, you may see a warning “warning C4290: C++ exception specification ignored except to indicate a function is not __declspec(nothrow),” because it doesn’t support exception throw lists. You can ignore these warnings for this example.

Making the Hashmap an STL Container

The basic hashmap shown in the previous section follows the spirit, but not the letter, of the STL. For most purposes, the preceding implementation is good enough. However, if you want to use the STL algorithms on your hashmap, you must do a bit more work. The C++ standard specifies specific methods and typedefs