Learn How to Pick the Correct Dictionary in C++ With Ordered Containers

When it comes to picking an associative container (like a hash map), modern C++ has a lot to offer. Sometimes, it is hard to select the most efficient dictionary data structure even for a professional engineer. Let's see what the C++23 standard library and the most prominent third-party libraries (such as boost, folly, abseil) provide, and how to pick the most suitable associative container. At the end of this series, I'll share a diagram to help you choose the best container for various purposes. Associative container types and characteristics There are two major types of associative containers in C++: maps and sets. Maps allow you to store some value along with the key, and search for the value by its key. Sets only store keys but not values, and are useful when it is necessary to check if the key is present, but not retrieve the associated value. In general, all maps and sets allow adding a key to the container, erasing it, checking if some key is present, and changing the associated value for the existing key (maps only). Once the key is added to the map or set, it becomes constant and can no longer be changed. Another way to categorize associative containers is key ordering. There are ordered and unordered containers. In the first category, keys are sorted according to some comparison criteria and maintain their order at all times. In unordered containers, there is no defined order to the keys, and it can change at any time. Looking at the internal structure, there are node-based containers, and ones not based on separate key/key-value nodes (often called flat). Node-based ones provide stricter reference and iterator stability guarantees. Such containers often allow manipulating separate nodes (for example, moving a node from one container to another). However, node-based containers are usually less efficient than their flat counterparts. Finally, containers can provide different thread safety guarantees. Most containers only allow concurrent reads when no modification happens, but some special containers provide wider capabilities. Let's look at the above container categories in more detail. In this first part, I will only cover ordered containers. Ordered containers Some containers are ordered by keys according to the comparison criteria you specify. By default, it's std::less (link), which means, keys are compared with the operator #include int main() { std::map map{ {1, "string 1"}, {5, "string 5"}, {0, "string 0"}, {3, "string 3"} }; if (auto it = map.lower_bound(2); it != map.end()) { std::cout first " second string 3, because the key 2 is absent in the map, and the next existing key in order after 2 is 3. When you iterate over an ordered container, you will visit keys in order, too: #include #include int main() { std::set set{0, 1, 4, -10, 5}; set.insert(3); for (int value : set) { std::cout << value << ' '; } } This program prints: -10 0 1 3 4 5 (ordered from the smallest to the largest key). Node-based containers There are several ordered associative containers in the C++ STL: std::map (link), std::multimap (link), and their value-less variants std::set (link) and std::multiset (link). Multi containers allow to store more than one key with equivalent values. These containers are almost always implemented using some form of a binary search tree, such as a red-black or an AVL tree. They are node-based, which means, they allocate a separate node for each new key (or a new key-value pair), which is somewhat inefficient and is not CPU cache-friendly. On the other hand, this makes map and set iterators and references stable. Even if some element is added or removed, iterators and references to the existing elements do not change. This makes the following code valid: #include #include int main() { std::map map{ {"test", 123} }; auto& value = map["test"]; auto valueIt = map.find("test"); // Map is modified: map.emplace("test2", 456); // References and iterators to the existing elements // remain valid. This line prints "123, 123": std::cout second << "\n"; } Insertion, deletion, key search, and upper/lower bound operations time complexity is always O(logN). Here is how the map from the first example may look like in memory: Each rectangle is a separate node, which contains both the key and the value. Nodes are connected using left and right pointers, and the tree always maintains the properties of the binary search tree. The library keeps the tree balanced, so that all branches are approximately the same depth, which guarantees the O(logN) time complexity for all search/insertion/deletion operations. Flat ordered containers A "flat" (not based on nodes) alternatives to node-based containers are C++23 std::flat_map (link), std::flat_set (link), std::flat_multimap (link) and std::flat_multiset (link). If C++23 is not available in your compiler yet, you can use boost flat containers, which provide compatible interfaces. Flat ordered containers are useful in cases when there are not too many elements, or when insertions and deletions are rare. These containers store everything in a contiguous block of memory (or a few contiguous blocks). This makes insertion and deletion time complexity O(N), which is much worse than in binary search tree node-based containers. Key search time complexity is still O(logN). These containers do not provide reference and iterator stability, but use less memory, do fewer allocations, and are more CPU cache-friendly. There are third-party flat ordered containers such as folly::sorted_vector_map and folly::sorted_vector_set (link). They do not allow duplicate keys (just like std::flat_map and std::flat_set). Here is how std::flat_map may look like in memory: There are two contiguous blocks of memory, one containing keys in sorted order, and another containing the corresponding values. Order statistic trees None of the above containers provide all possible operations you might need. For example, it is impossible to get the number of keys that precede the given key (this operation is called rank). It is also not possible to get the i-th key (or the corresponding value) in order (this is the select operation). However, both operations can be supported by a binary search tree with O(logN) time complexity. A tree that allows such operations is called an order statistic tree. The only container I am aware of, which allows such operations is boost::multi_index_container. Boost Multi Index library provides much more than that, but let's focus on rank and select for now. Here is an example showing one way to create and use an order statistic tree: #include #include #include #include #include struct KeyValue { std::string key; int value{}; }; using OrderStatisticTree = boost::multi_index_container > > >; int main() { OrderStatisticTree tree; tree.insert(KeyValue{ .key = "abc", .value = 5 }); tree.insert(KeyValue{ .key = "zkey", .value = 10 }); tree.insert(KeyValue{ .key = "def", .value = 20 }); tree.insert(KeyValue{ .key = "aaaa", .value = 50 }); auto defIt = tree.find("def"); std::cout key << "\n"; } First, we define the KeyValue structure, which has both the key and the value for our container. Then, we define the OrderStatisticTree type, and we ask the Multi Index library to index the tree by KeyValue::key using the ranked_unique index type. Then, we create the tree, and add a few elements to it by calling insert. The rank call returns the def key rank. The next line will output def rank: 2, because there are two keys that are positioned before the def in order (aaaa, abc, def). The nth call is the "select" operation, and it returns an iterator to the key with index 2 in order (which will be def again: the next line will output Key with index 2: def). The ranked_unique index type corresponds to std::map. There is also the ranked_non_unique index type, which corresponds to std::multimap. Of course, classic ordered container operations are also available: you can call insert, emplace, find, upper_bound and lower_bound, erase, contains, etc. Time complexity of all the above operations is always O(logN). Multi Index guarantees iterator and reference stability, just as C++ standard maps and sets. Containers with ranked indexes will use more memory than the plain std::map, because they need to store additional data related to key ranks. There are more rank/select methods provided by the ranked index types, which may be useful in your use case. Boost Multi Index container memory layout is more complex than the classic node-based or flat containers, as it allows multiple indexes into the same set of values: Which one do I use? If you need the key order or upper/lower bound operations, pick one of the above containers. If you need to associate values with the keys, pick map containers, otherwise, choose set ones. If the number of elements in the container is very small, or if container modifications are rare, take one of the flat options. If you never modify a container after inserting some initial elements, use std::vector (link) or std::array (link), sort them once, and use algorithms like std::binary_search (link) or std::equal_range (link) to find the key. Otherwise, go with the std::map / std::set ones. If you need to store duplicate keys, pick "multi" containers (they also have an additional equal_range operation which returns iterators to the range of keys equivalent to the one you are looking for). If you need statistics operations like rank and select, there is no other choice but boost::multi_index_container. Remember that all of the above containers are only thread-safe when no modification is happening. If in your case one thread may modify the container while other threads access it, you will need to implement manual synchronization (for example, using mutexes). I will cover the thread safety aspect in more detail in the next article. When it comes to picking an associative container (like a hash map), modern C++ has a lot to offer. Sometimes, it is hard to select the most efficient dictionary data structure even for a professional engineer. Let's see what the C++23 standard library and the most prominent third-party libraries (such as boost , folly , abseil ) provide, and how to pick the most suitable associative container. At the end of this series, I'll share a diagram to help you choose the best container for various purposes. boost folly abseil Associative container types and characteristics There are two major types of associative containers in C++: maps and sets . Maps allow you to store some value along with the key, and search for the value by its key. Sets only store keys but not values, and are useful when it is necessary to check if the key is present, but not retrieve the associated value. In general, all maps and sets allow adding a key to the container, erasing it, checking if some key is present, and changing the associated value for the existing key (maps only). Once the key is added to the map or set, it becomes constant and can no longer be changed. maps sets Maps Sets Another way to categorize associative containers is key ordering. There are ordered and unordered containers. In the first category, keys are sorted according to some comparison criteria and maintain their order at all times. In unordered containers, there is no defined order to the keys, and it can change at any time. ordered unordered Looking at the internal structure, there are node-based containers, and ones not based on separate key/key-value nodes (often called flat ). Node-based ones provide stricter reference and iterator stability guarantees. Such containers often allow manipulating separate nodes (for example, moving a node from one container to another). However, node-based containers are usually less efficient than their flat counterparts. node-based flat Finally, containers can provide different thread safety guarantees. Most containers only allow concurrent reads when no modification happens, but some special containers provide wider capabilities. Let's look at the above container categories in more detail. In this first part, I will only cover ordered containers . ordered containers Ordered containers Some containers are ordered by keys according to the comparison criteria you specify. By default, it's std::less ( link ), which means, keys are compared with the operator #include int main() { std::map map{ {1, "string 1"}, {5, "string 5"}, {0, "string 0"}, {3, "string 3"} }; if (auto it = map.lower_bound(2); it != map.end()) { std::cout first " second #include int main() { std::map map{ {1, "string 1"}, {5, "string 5"}, {0, "string 0"}, {3, "string 3"} }; if (auto it = map.lower_bound(2); it != map.end()) { std::cout first " second string 3 , because the key 2 is absent in the map, and the next existing key in order after 2 is 3 . 3 -> string 3 2 2 3 When you iterate over an ordered container, you will visit keys in order, too: #include #include int main() { std::set set{0, 1, 4, -10, 5}; set.insert(3); for (int value : set) { std::cout #include int main() { std::set set{0, 1, 4, -10, 5}; set.insert(3); for (int value : set) { std::cout << value << ' '; } } This program prints: -10 0 1 3 4 5 (ordered from the smallest to the largest key). -10 0 1 3 4 5 Node-based containers There are several ordered associative containers in the C++ STL: std::map ( link ), std::multimap ( link ), and their value-less variants std::set ( link ) and std::multiset ( link ). Multi containers allow to store more than one key with equivalent values. These containers are almost always implemented using some form of a binary search tree , such as a red-black or an AVL tree. They are node-based, which means, they allocate a separate node for each new key (or a new key-value pair), which is somewhat inefficient and is not CPU cache-friendly. On the other hand, this makes map and set iterators and references stable. Even if some element is added or removed, iterators and references to the existing elements do not change. This makes the following code valid: std::map link std::multimap link std::set link std::multiset link binary search tree red-black AVL #include #include int main() { std::map map{ {"test", 123} }; auto& value = map["test"]; auto valueIt = map.find("test"); // Map is modified: map.emplace("test2", 456); // References and iterators to the existing elements // remain valid. This line prints "123, 123": std::cout second #include int main() { std::map map{ {"test", 123} }; auto& value = map["test"]; auto valueIt = map.find("test"); // Map is modified: map.emplace("test2", 456); // References and iterators to the existing elements // remain valid. This line prints "123, 123": std::cout second << "\n"; } Insertion, deletion, key search, and upper/lower bound operations time complexity is always O(logN) . O(logN) Here is how the map from the first example may look like in memory: Each rectangle is a separate node, which contains both the key and the value. Nodes are connected using left and right pointers, and the tree always maintains the properties of the binary search tree . The library keeps the tree balanced, so that all branches are approximately the same depth, which guarantees the O(logN) time complexity for all search/insertion/deletion operations. left right binary search tree O(logN) Flat ordered containers A " flat " (not based on nodes) alternatives to node-based containers are C++23 std::flat_map ( link ), std::flat_set ( link ), std::flat_multimap ( link ) and std::flat_multiset ( link ). If C++23 is not available in your compiler yet, you can use boost flat containers , which provide compatible interfaces. Flat ordered containers are useful in cases when there are not too many elements, or when insertions and deletions are rare. These containers store everything in a contiguous block of memory (or a few contiguous blocks). This makes insertion and deletion time complexity O(N) , which is much worse than in binary search tree node-based containers. Key search time complexity is still O(logN) . These containers do not provide reference and iterator stability, but use less memory, do fewer allocations, and are more CPU cache-friendly. There are third-party flat ordered containers such as folly::sorted_vector_map and folly::sorted_vector_set ( link ). They do not allow duplicate keys (just like std::flat_map and std::flat_set ). flat std::flat_map link std::flat_set link std::flat_multimap link std::flat_multiset link boost flat containers O(N) O(logN) folly::sorted_vector_map folly::sorted_vector_set link std::flat_map std::flat_set Here is how std::flat_map may look like in memory: std::flat_map There are two contiguous blocks of memory, one containing keys in sorted order, and another containing the corresponding values. Order statistic trees None of the above containers provide all possible operations you might need. For example, it is impossible to get the number of keys that precede the given key (this operation is called rank ). It is also not possible to get the i -th key (or the corresponding value) in order (this is the select operation). However, both operations can be supported by a binary search tree with O(logN) time complexity. A tree that allows such operations is called an order statistic tree . rank i select O(logN) order statistic tree order statistic tree The only container I am aware of, which allows such operations is boost::multi_index_container . Boost Multi Index library provides much more than that, but let's focus on rank and select for now. Here is an example showing one way to create and use an order statistic tree: boost::multi_index_container Boost Multi Index Boost Multi Index library rank select #include #include #include #include #include struct KeyValue { std::string key; int value{}; }; using OrderStatisticTree = boost::multi_index_container > > >; int main() { OrderStatisticTree tree; tree.insert(KeyValue{ .key = "abc", .value = 5 }); tree.insert(KeyValue{ .key = "zkey", .value = 10 }); tree.insert(KeyValue{ .key = "def", .value = 20 }); tree.insert(KeyValue{ .key = "aaaa", .value = 50 }); auto defIt = tree.find("def"); std::cout key #include #include #include #include struct KeyValue { std::string key; int value{}; }; using OrderStatisticTree = boost::multi_index_container > > >; int main() { OrderStatisticTree tree; tree.insert(KeyValue{ .key = "abc", .value = 5 }); tree.insert(KeyValue{ .key = "zkey", .value = 10 }); tree.insert(KeyValue{ .key = "def", .value = 20 }); tree.insert(KeyValue{ .key = "aaaa", .value = 50 }); auto defIt = tree.find("def"); std::cout key << "\n"; } First, we define the KeyValue structure, which has both the key and the value for our container. Then, we define the OrderStatisticTree type, and we ask the Multi Index library to index the tree by KeyValue::key using the ranked_unique index type. Then, we create the tree, and add a few elements to it by calling insert. The rank call returns the def key rank. The next line will output def rank: 2, because there are two keys that are positioned before the def in order (aaaa, abc, def). The nth call is the "select" operation, and it returns an iterator to the key with index 2 in order (which will be def again: the next line will output Key with index 2: def). First, we define the KeyValue structure, which has both the key and the value for our container. KeyValue Then, we define the OrderStatisticTree type, and we ask the Multi Index library to index the tree by KeyValue::key using the ranked_unique index type. OrderStatisticTree KeyValue::key ranked_unique Then, we create the tree , and add a few elements to it by calling insert . tree insert The rank call returns the def key rank. The next line will output def rank: 2 , because there are two keys that are positioned before the def in order ( aaaa , abc , def ). rank def def rank: 2 def aaaa abc def The nth call is the " select " operation, and it returns an iterator to the key with index 2 in order (which will be def again: the next line will output Key with index 2: def ). nth select 2 def Key with index 2: def The ranked_unique index type corresponds to std::map . There is also the ranked_non_unique index type, which corresponds to std::multimap . Of course, classic ordered container operations are also available: you can call insert , emplace , find , upper_bound and lower_bound , erase , contains , etc. Time complexity of all the above operations is always O(logN) . Multi Index guarantees iterator and reference stability, just as C++ standard maps and sets. Containers with ranked indexes will use more memory than the plain std::map , because they need to store additional data related to key ranks. ranked_unique std::map ranked_non_unique std::multimap insert emplace find upper_bound lower_bound erase contains O(logN) std::map There are more rank/select methods provided by the ranked index types, which may be useful in your use case. more rank/select methods Boost Multi Index container memory layout is more complex than the classic node-based or flat containers, as it allows multiple indexes into the same set of values: Which one do I use? If you need the key order or upper/lower bound operations, pick one of the above containers. If you need to associate values with the keys, pick map containers, otherwise, choose set ones. If the number of elements in the container is very small, or if container modifications are rare, take one of the flat options. If you never modify a container after inserting some initial elements, use std::vector (link) or std::array (link), sort them once, and use algorithms like std::binary_search (link) or std::equal_range (link) to find the key. Otherwise, go with the std::map / std::set ones. If you need to store duplicate keys, pick "multi" containers (they also have an additional equal_range operation which returns iterators to the range of keys equivalent to the one you are looking for). If you need statistics operations like rank and select, there is no other choice but boost::multi_index_container. If you need the key order or upper/lower bound operations, pick one of the above containers. If you need to associate values with the keys, pick map containers, otherwise, choose set ones. map set If the number of elements in the container is very small, or if container modifications are rare, take one of the flat options. If you never modify a container after inserting some initial elements, use std::vector ( link ) or std::array ( link ), sort them once, and use algorithms like std::binary_search ( link ) or std::equal_range ( link ) to find the key. Otherwise, go with the std::map / std::set ones. flat std::vector link std::array link std::binary_search link std::equal_range link std::map std::set If you need to store duplicate keys, pick " multi " containers (they also have an additional equal_range operation which returns iterators to the range of keys equivalent to the one you are looking for). multi equal_range If you need statistics operations like rank and select , there is no other choice but boost::multi_index_container . rank select boost::multi_index_container Remember that all of the above containers are only thread-safe when no modification is happening. If in your case one thread may modify the container while other threads access it, you will need to implement manual synchronization (for example, using mutexes). I will cover the thread safety aspect in more detail in the next article.