C++ std::map Types of Maps


Example

Regular Map

A map is an associative container, containing key-value pairs.

#include <string>
#include <map>
std::map<std::string, size_t> fruits_count;

In the above example, std::string is the key type, and size_t is a value.

The key acts as an index in the map. Each key must be unique, and must be ordered.

  • If you need mutliple elements with the same key, consider using multimap (explained below)

  • If your value type does not specify any ordering, or you want to override the default ordering, you may provide one:

    #include <string>
    #include <map>
    #include <cstring>
    struct StrLess {
        bool operator()(const std::string& a, const std::string& b) {
            return strncmp(a.c_str(), b.c_str(), 8)<0;
                   //compare only up to 8 first characters
        }
    }
    std::map<std::string, size_t, StrLess> fruits_count2;
    

    If StrLess comparator returns false for two keys, they are considered the same even if their actual contents differ.

Multi-Map

Multimap allows multiple key-value pairs with the same key to be stored in the map. Otherwise, its interface and creation is very similar to the regular map.

 #include <string>
 #include <map>
 std::multimap<std::string, size_t> fruits_count;
 std::multimap<std::string, size_t, StrLess> fruits_count2;

Hash-Map (Unordered Map)

A hash map stores key-value pairs similar to a regular map. It does not order the elements with respect to the key though. Instead, a hash value for the key is used to quickly access the needed key-value pairs.

#include <string>
#include <unordered_map>
std::unordered_map<std::string, size_t> fruits_count;

Unordered maps are usually faster, but the elements are not stored in any predictable order. For example, iterating over all elements in an unordered_map gives the elements in a seemingly random order.