This article intends to examine how to utilize the container adapter std::flat_map, new to the C++23 Standard Library. You’re probably familiar with std::map and std::unordered_map (and their “multi” variants), and may be curious as to why we need another associative container type. The reason, as usual for C++, is performance: in some cases, operations on a std::flat_map can outperform those on a std::map or a (sorted) std::vector.
Going back to std::map for a moment, the ability to access elements in O(log(n)) (logarithmic time) stems from the fact that keys must have operator< defined (or operator<=> = default), and store their (key, value) pairs with strict, weak ordering. The following program populates and then outputs a std::map:
#include <map>
#include <string>
#include <string_view>
#include <iostream>
#include <cctype>
using namespace std;
class Person {
string lastname, firstname;
static string toUpper(string_view);
public:
Person(string_view firstname, string_view lastname) : lastname{ lastname }, firstname{ firstname } {}
friend bool operator<(const Person&, const Person&);
friend ostream& operator<<(ostream&, const Person&);
};
bool operator<(const Person& lhs, const Person& rhs) {
if (lhs.lastname != rhs.lastname) {
return Person::toUpper(lhs.lastname) < Person::toUpper(rhs.lastname);
}
else {
return Person::toUpper(lhs.firstname) < Person::toUpper(rhs.firstname);
}
}
ostream& operator<<(ostream& os, const Person& p) {
return os << p.firstname << ' ' << p.lastname;
}
string Person::toUpper(string_view s) {
string upper;
for (auto c : s) {
if (isalpha(c)) {
upper.push_back(toupper(c));
}
}
return upper;
}
int main() {
map<Person,int> Presidents{
{ { "George HW", "Bush" }, 1988 },
{ { "Bill", "Clinton" }, 1992 },
{ { "George W", "Bush" }, 2000 },
{ { "Barack", "Obama" }, 2008 },
{ { "Donald", "Trump" }, 2016 },
{ { "Joe", "Biden" }, 2020 }
};
for (const auto& p : Presidents) {
cout << p.first << " elected in " << p.second << '\n';
}
}
The expected output from the program is names in (surname, first name) alphabetical order:
Joe Biden elected in 2020
George HW Bush elected in 1988
George W Bush elected in 2000
Bill Clinton elected in 1992
Barack Obama elected in 2008
Donald Trump elected in 2016
By contrast to std::map, std::unordered_map stores its (key, value) pairs in seemingly random order in exchange for O(1) (constant) lookup time, and requires operator== and a hash function to be defined, for example:
#include <unordered_map>
#include <string>
#include <string_view>
#include <iostream>
#include <cctype>
using namespace std;
class Person {
string lastname, firstname;
static string toUpper(string_view);
public:
Person(string_view firstname, string_view lastname) : lastname{ lastname }, firstname{ firstname } {}
friend bool operator==(const Person&, const Person&);
friend ostream& operator<<(ostream&, const Person&);
friend class hash<Person>;
};
bool operator==(const Person& lhs, const Person& rhs) {
return Person::toUpper(lhs.lastname + ',' + lhs.firstname)
== Person::toUpper(rhs.lastname + ',' + rhs.firstname);
}
ostream& operator<<(ostream& os, const Person& p) {
return os << p.firstname << ' ' << p.lastname;
}
string Person::toUpper(string_view s) {
string upper;
for (auto c : s) {
if (isalpha(c)) {
upper.push_back(toupper(c));
}
}
return upper;
}
namespace std {
template <>
struct hash<Person> {
size_t operator()(const Person& p) const {
return hash<string>()(p.firstname + p.lastname);
}
};
}
int main() {
unordered_map<Person,int> Presidents{
{ { "George HW", "Bush" }, 1988 },
{ { "Bill", "Clinton" }, 1992 },
{ { "George W", "Bush" }, 2000 },
{ { "Barack", "Obama" }, 2008 },
{ { "Donald", "Trump" }, 2016 },
{ { "Joe", "Biden" }, 2020 }
};
for (const auto& p : Presidents) {
cout << p.first << " elected in " << p.second << '\n';
}
}
This gives the possible output (may vary dependent upon Standard Library implementation):
Barack Obama elected in 2008
George W Bush elected in 2000
George HW Bush elected in 1988
Bill Clinton elected in 1992
Joe Biden elected in 2020
Donald Trump elected in 2016
It is possible to adapt the first version of this program to use std::flat_map although the header <flat_map> doesn’t seem to be widely available at the time of writing, even in “experimental”. I used the code from this GitHub repo which compiled with Visual Studio C++ 17.8 using /std:c++latest:
#include <stdexcept>
#include "flat_map"
// ...
int main() {
flat_map<Person,int> Presidents{
// ...
The output is identical to using std::map; with this in mind, the question remains as to how std::flat_map operates “under the hood”. In fact, just as std::stack<T> is a wrapper (adapter) around (usually) a std::vector<T>, std::flat_map<K,V> is a wrapper around std::vector<K> and a std::vector<V>, with the guarantee that the elements always remain in sorted order (as for a std::map<K,V>). This may be what you want, and means that manually calling std::sort() is never necessary as it would be to maintain two std::vectors in order.
Only two of the Standard Containers can be used as the underlying container type for std::flat_map, they are std::vector (the default) and std::deque. These containers are accessed directly by the member functions keys() and values() and all of their respective member functions are then available, such as values().data() for a std::vector which is guaranteed to be held contiguously in memory. Other member functions for std::flat_map include insert(), erase() and emplace() as for other associative containers (at() and operator[] can also be used).
In summary, if you’ve ever needed to manually convert a std::map<K,V> into a temporary std::vector<std::pair<K,V>> (or two std::vectors) in order to use it for a particular operation, consider using std::flat_map instead. Also available are std::flat_set, std::flat_multimap and std::flat_multiset, the last two allow multiple data with the same keys, the *set variants being defined in header <flat_set>.
Learn Modern C++ 