Chapter 20 - Code Examples

Instantiating

To instantiate an std::map or std::multimap you need to specify the key type and the value type.

std::map<int, std::string> intToStringMap;
std::map<std::string, std::string> stringToStringMap;

Most functions in map and multimap work in a similar fashion - they accept similar parameters and return similar value types.

Knowing how to use one will give you an intuitive sense of how to use the other, much like set and multiset.

Inserting

Using the insert member function

std::map<int, std::string> intToStringMap;
intToStringMap.insert(std::make_pair(-1, "Minus One"));

The std::make_pair function creates a key-value pair, the first parameter being the key and the second the value - this returns an std::pair type.

Alternatively you can also directly supply an std::pair object to be inserted:

intToStringMap.insert(std::pair<int, std::string>(10, "Ten"));

Using array-like syntax

intToStringMap[100] = "Hundred";

This is the most user friendly and generally most popular approach.

Finding and Lookups

The .find() member method

All associative containers (std::map, std::map, etc) feature a member function called .find() that allows you to search for a given key.

The result for .find() is always an iterator:

std::map<int, std::string>::const_iterator result = mapIntToString.find(key);

If the key was not found in the container, it will return container.end(); therefore you should always check for this before using the returned iterator to access the underlying value.

if (result != mapIntToString.end()) {
    std::cout << "Key: " << result->first 
              << " has value: " << result->second << std::endl;
} else {
    std::cout << "Key was not found" << std::endl;
}

Finding in a multimap

An std::multimap opens the possibility of storing multiple pairs with the same key.

The .find() member method returns an iterator to the first pair for the given key.

Incrementing this iterator gives access to consequently placed values, possibly with the same key.

Use the .count() member function to determine how many times to increment the iterator to enumerate over all keys of a particular value.

auto pairFound = mmapIntToStr.find(key);

// Check if find() succeeded
if (pairFound != mmapIntToStr.end()) {
    // Find the number of pairs that have the same supplied key
    int numPairsInMap = mmapIntToStr.count(1000);
    
    // Stay within bounds
    for (int counter = 0; counter < numPairsInMap; counter++) 
    {
        cout << "Key: " << pairFound->first; // key
        cout << ", Value [" << counter << "] = ";
        cout << pairFound->second << endl; // value
        
        pairFound++;
    }
}
else {
   cout << "Element not found in the multimap";
}

Erasing

Using the .erase() member function

The .erase() member function can be invoked with either:

• A key value

• An iterator pointing to an element in the std::map

• A range of elements described by two iterators

Conclusion

Sequential Containers

• Store elements in the order they were inserted

• Not necessarily contiguously in memory (this is only for std::vector)

• std::vector, std::deque, std::list

• Dynamic array, chunks of dynamic arrays, linked lists

Associative Containers

• They are not stored sequentially in the order they were inserted

• std::set, std::map, std::unordered_set, std::unordered_map

• Binary search trees, hash sets/hash maps.

Ordered Containers

std::set and std::map are represented by binary search trees internally, which implicitly means that the elements are sorted in some order.

While much quicker than std::vector or std::list when it comes to searching, its performance still scales with the number of inputs, although logarithmically as opposed to linearly.

Unordered Containers

std::unordered_set and std::unordered_map are represented by hash sets (or hash tables) internally.

Such containers generally promise constant-time insertions and searches, independent of the size of the container.

As a result, these containers are optimised only for search performance, and are suitable in situations where the order of elements does not matter.