This ordering has exciting consequences for the ordered associative containers.<\/p>\n
- \n
- The key has to support an ordering relation.<\/li>\n
- Associative containers are typically implemented in balanced binary search trees<\/a>.<\/li>\n
- The access time to the key and, therefore, to the value is logarithmic.<\/li>\n<\/ul>\n
The most often used ordered associative container is std::map:<\/span><\/p>\n
<\/p>\n
\nmap<int<\/span>, string> int2String{ {3,\"three\"<\/span>},{2,\"two\"<\/span>},{1,\"one\"<\/span>},{5,\"five\"<\/span>},{6,\"six\"<\/span>},{4,\"four\"<\/span>},{7,\"seven\"<\/span>} };\r\n<\/pre>\n<\/div>\n<\/p>\n
The balanced binary search tree may have the following structure.<\/p>\n
<\/p>\n
![\"geordneteAssoziativeArrays\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2016\/11\/geordneteAssoziativeArrays.png\")
<\/p>\n<\/p>\nUnordered associative containers<\/h2>\n
The key idea of the unordered associative containers is that the key is mapped with the help of the hash function onto the bucket. You can find the key\/value pair in the bucket.<\/p>\n
I have to introduce a few terms before I describe the characteristics of unordered associative containers.<\/p>\n
- \n
- Hash value<\/strong>: The value you will get if you apply the hash function to the key.<\/li>\n
- Collision<\/strong>: We will collide if different keys are mapped to the same hash value. The unordered associative containers have to deal with this situation.<\/li>\n<\/ul>\n
The usage of the hash function has very important consequences for the unordered associative container.<\/p>\n
- \n
- The keys have to support equal comparison to deal with collisions.<\/li>\n
- The hash value of a key has to be available.<\/li>\n
- The execution of a hash function is a constant. Therefore, the access time to the keys of an unordered associative container is constant. For simplicity reasons I ignored collisions.<\/li>\n<\/ul>\n
<\/p>\n
According to std::map<\/span> is the most often used ordered associative container std::unordered_map<\/span> will become the most often used unordered associative container.<\/p>\n
<\/p>\n
\nunordered_map<string,int<\/span>> str2Int{ {\"Grimm<\/span>\"<\/span>,491634333356},{\"Grimm-Jaud<\/span><\/span>\",49160123335<\/span>}, {\"<\/span>Schmid<\/span>t\",4913333318<\/span>},{\"<\/span>Huber<\/span>\",490001326<\/span>} };<\/span>\r\n <\/pre>\n<\/div>\nThe graphic shows the mapping of the keys to their bucket by using the hash function.<\/p>\n
![\"UngeordnetesAssoziativesArrayEng\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2016\/11\/UngeordnetesAssoziativesArrayEng.png\")
<\/h2>\nThe similarities<\/h2>\n
The similar names of std::map<\/span> and std::unordered_map<\/span> are not by accident. Both have a similar interface. To be more precise. The interface of std::map<\/span> is a subset of the interface of std::unorederd_map.<\/span> Have a look:<\/p>\n
<\/p>\n
<\/p>\n
\n\n\n
\n \n 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40<\/pre>\n<\/td>\n
\n \/\/ mapHashCompare.cpp<\/span>\r\n\r\n#include <iostream><\/span>\r\n#include <map><\/span>\r\n#include <unordered_map><\/span>\r\n\r\nint<\/span> main(){\r\n\r\n std::cout << std::endl;\r\n\r\n std::cout << \"C++ map: \"<\/span> << std::endl;\r\n std::map<std::string,int<\/span>> m { {\"Dijkstra\"<\/span>,1972},{\"Scott\"<\/span>,1976} };\r\n m[\"Ritchie\"<\/span>] = 1983;\r\n std::cout << \" m[Ritchie]: \"<\/span> << m[\"Ritchie\"<\/span>] << \"\\n \"<\/span>;\r\n for<\/span>(auto<\/span> p : m) std::cout << '{'<\/span> << p.first << ','<\/span> << p.second << '}'<\/span>;\r\n m.erase(\"Scott\"<\/span>);\r\n std::cout << \"\\n \"<\/span>;\r\n for<\/span>(auto<\/span> p : m) std::cout << '{'<\/span> << p.first << ','<\/span> << p.second << '}'<\/span>;\r\n m.clear();\r\n std::cout << std::endl;\r\n std::cout << \" m.size(): \"<\/span> << m.size() << std::endl;\r\n\r\n\r\n std::cout << std::endl;\r\n\r\n std::cout << \"C++11 unordered_map: \"<\/span> << std::endl;\r\n std::unordered_map<std::string,int<\/span>> um { {\"Dijkstra\"<\/span>,1972},{\"Scott\"<\/span>,1976} };\r\n um[\"Ritchie\"<\/span>] = 1983;\r\n std::cout << \" um[Ritchie]: \"<\/span> << um[\"Ritchie\"<\/span>] << \"\\n \"<\/span>;\r\n for<\/span>(auto<\/span> p : um) std::cout << '{'<\/span> << p.first << ','<\/span> << p.second << '}'<\/span>;\r\n um.erase(\"Scott\"<\/span>);\r\n std::cout << \"\\n \"<\/span>;\r\n for<\/span>(auto<\/span> p : um) std::cout << '{'<\/span> << p.first << ','<\/span> << p.second << '}'<\/span>;\r\n um.clear();\r\n std::cout << std::endl;\r\n std::cout << \" um.size(): \"<\/span> << um.size() << std::endl;\r\n\r\n std::cout << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\nA typical case of copy and paste<\/em>. The difference between lines 11 – 21 and 26 – 36 is only that I used in the first case std::map<\/span>; that I used in the second case std::unordered_map. <\/span>Therefore, I will only explain the second case. I initialized in line 27 the std::unordered_map<\/span> with the help of an initializer list. Then I update the value of the key “Richie”<\/span> <\/span>and return the associated value. In lines 30 and 33, I display the key\/values pairs by using a range-based for-loop. p.first<\/span> is the first, p.second<\/span> is the second element of the pair. By using um.clear() <\/span>I can clear the unordered associative container by using um.size()<\/span> I can determine its size.<\/div>\n<\/div>\nA second glance reveals a small difference.<\/div>\n.<\/div>\n![\"mapHashCompare\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2016\/11\/mapHashCompare.png\")
<\/div>\n<\/p>\n
The keys of the std::maps are ordered and, therefore, the pairs. Surprised? Of course not! That is the visible difference between the ordered and unordered associative containers.<\/p>\n
The eight variations<\/h2>\n
I start with the classically ordered associative containers to get an ordering into the eight variations. You can easily apply the ordering to the unordered associative containers.<\/p>\n
The answers to two questions are the key to getting systematic into ordered associative containers:<\/p>\n
- \n
- Does the key have an associated value?<\/li>\n
- Are several identical keys possible?<\/li>\n<\/ul>\n
You get the four ordered associative containers std::set, std::multiset, std::map, and std::multimap by answering the two questions.<\/span><\/p>\n
Of course, you can apply the two questions to the unordered associative containers. Now you get the containers std::unordered_set, std::unordered_multiset, std::unordered_map<\/span>, and std::unordered_multimap.<\/span><\/p>\n
All that is left is to write down the systematic. If the container’s name has the component<\/p>\n
- \n
- map, <\/strong>it has an associated value.<\/li>\n
- multi<\/strong>, it can have more than one identical key. <\/li>\n
- unordered<\/strong>, its keys are non-sorted.<\/li>\n<\/ul>\n
But the analogy goes on. If two container names only differ in the name component unordered,<\/strong> they will have a similar interface. The container without the name component unordered supports an interface that is a subset of the unordered container. You saw it already in the listing mapHashCompare.cpp.<\/span><\/p>\n
The table shows once more the entire system. The systematic includes the access time for the ordered containers (logarithmic) and the unordered container (constant).<\/p>\n
![\"OrderedVersusUnorderedContainers\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2016\/11\/OrderedVersusUnorderedContainers.png\")
<\/h2>\nWhat’s next?<\/h2>\n
My first plan was to show you the performance difference between ordered and unordered containers. So, I will do it in the next post.<\/a><\/span><\/p>\n
<\/p>\n
- multi<\/strong>, it can have more than one identical key. <\/li>\n
- map, <\/strong>it has an associated value.<\/li>\n
- Collision<\/strong>: We will collide if different keys are mapped to the same hash value. The unordered associative containers have to deal with this situation.<\/li>\n<\/ul>\n
- The access time to the key and, therefore, to the value is logarithmic.<\/li>\n<\/ul>\n