Ordered Map

c++17 containers intermediate

Related: Ordered Set

std::map is a key-value container that maintains its keys in sorted order at all times. Generally std::map is implemented as a tree of key-value pairs, and not a hash map. This means when iterating the key-value pairs of a std::map the order will always be known but that insertion or lookup (search) is slower than std::unordered_map.

#include <map>
#include <string>
#include <iostream>

int main() {
  std::map<std::string, int> persons{
    {"Maria", 42},
    {"Nushi", 12},
    {"Mohammed", 25},
    {"Jose", 64}
  };

  for (const auto& [name, age] : persons) {
    std::cout << name << " is " << age << " years old.\n";
  }
}

Jose is 64 years old.
Maria is 42 years old.
Mohammed is 25 years old.
Nushi is 12 years old.

Changing the Sort Order of std::map

By default std::map uses the comparator function object std::less<Key> to determine the sort order of its keys. This means if “a” is less than “b” (a < b) then “a” sorts before “b”. The std library also provides std::greater<Key> for a convenient way to reverse the default sort order.

To change the sort order of std::map you provide a third template parameter which is a sort function object. The sort function object should implement a function call operator(()) that takes two const Key& elements and returns true if the first argument sorts before the second argument. That means the sort function’s signature is usually bool operator()(const Key& a, const Key& b) const where Key is the type of the keys in your map. Here’s an example of a custom sort function:

#include <map>
#include <string>
#include <iostream>

using std::string;

struct ShorterString {
  bool operator()(const string& a, const string& b) const {
    return a.size() <= b.size();
  }
};

int main() {
  std::map<string, int, ShorterString> persons{
    {"Maria", 42},
    {"Nushi", 12},
    {"Mohammed", 25},
    {"Jose", 64}
  };

  for (const auto& [name, age] : persons) {
    std::cout << name << " is " << age << " years old.\n";
  }
}

Jose is 64 years old.
Maria is 42 years old.
Nushi is 12 years old.
Mohammed is 25 years old.