Types of maps

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.