{"id":5691,"date":"2019-05-29T05:58:16","date_gmt":"2019-05-29T05:58:16","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/more-special-friends-with-std-map-and-std-unordered-map\/"},"modified":"2023-08-20T14:24:33","modified_gmt":"2023-08-20T14:24:33","slug":"more-special-friends-with-std-map-and-std-unordered-map","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/more-special-friends-with-std-map-and-std-unordered-map\/","title":{"rendered":"More special Friends with std::map and std::unordered_map"},"content":{"rendered":"

Modern C++ has eight associative containers, but your special friends should be std::map<\/span> and std::unordered_map<\/span>. Why? Let me explain it in this post.<\/p>\n

<\/p>\n

 <\/p>\n

\"book<\/p>\n

In my last post, C++ Core Guidelines:  std::array<\/span> and std::vector <\/span><\/a>are your friends; I stated: In 99 % of your use-cases, you are lovely with a std::array<\/span> or a std::vector. <\/span>A similar statement exists for associative containers: In 95 % of your use cases, you are lovely with a std::map<\/span> or std::unordered_map<\/span>.  In seldom cases, you don’t need the value associated with the key. These are the missing 5 %. Before I begin this post and give an overview and numbers to both associative containers, here is my rule of thumb for today: If you want a container with a key\/value association and the keys should be ordered, use std::map<\/span>; if not, use a std::unordered_map<\/span>.<\/strong><\/p>\n

Here is the first overview. For more details, please read my previous posts about associative containers<\/a>.<\/p>\n

The eight Variations<\/h2>\n

\"OrderedVersusUnorderedContainers\"<\/h2>\n

To get an ordering into the eight variations of associative containers, you have to answer three questions. Each question can be answered by yes or no. 2 ^ 3 == 8.<\/span> Here are the three questions:<\/p>\n

    \n
  1. Is the container ordered?<\/li>\n
  2. Does the key have an associated value?<\/li>\n
  3. Are several identical keys possible?<\/li>\n<\/ol>\n

    And here are the answers.<\/p>\n

      \n
    1. When the container is not ordered, it’s called unordered<\/span>.<\/li>\n
    2. When the key does have a value associated, it’s called map<\/span>; if not set<\/span>.<\/li>\n
    3. When the container can have more than one identical key, it’s called multi<\/span>.<\/li>\n<\/ol>\n

      When I speak of the ordered container, I mean the ordering of the keys.<\/p>\n

      Maybe this taxonomy was too complicated. Let me give you a more straightforward picture.<\/p>\n

      A Phone Book<\/h3>\n

      The eight variations are just different versions of a phone book. What is a phone book? A phone book is a sequence of key\/value pairs. You use the keys (family names) to get the values (phone numbers).<\/p>\n

      The family names of a phone book can be ordered or unordered; the phone book can have a phone number associated with the family name or not and can have only one or more identical family names. If you want to store your mobile and landline numbers in a phone book, you are pretty happy that you can use two identical keys.<\/p>\n

      The reason for this post is not to explain the associative containers: The reason is a different one. The access time to an ordered associative container is logarithmic, but the access time to an unordered associative container is amortized constant. <\/p>\n<\/p>\n

      Performance of a std::map<\/span> and a std::unordered::map<\/span><\/h2>\n

      What does amortized constant access time mean for an unordered associative container such as std::unordered_map<\/span>? It means that your query for a phone number is independent of the size of the phone book. Don’t you believe me? Let me show you a performance test.<\/p>\n

      I have a phone book with roughly 89,000 entries. I will increase its size successively by ten until it has almost 89,000,000 entries. After each step, I will ask for all its phone numbers. This means I randomly use all family names. <\/p>\n

      The following image shows you a part of the initial phone book. You can see the name\/number pairs separated by a colon and the name separated from the number by a comma.<\/p>\n

      \"telebook\"<\/p>\n

       The program should be pretty easy to read.<\/p>\n

       <\/p>\n

      \n
      \/\/ telephoneBook.cpp<\/span>\r\n\r\n#include <chrono><\/span>\r\n#include <fstream><\/span>\r\n#include <iostream><\/span>\r\n#include <map><\/span>\r\n#include <random><\/span>\r\n#include <regex><\/span>\r\n#include <sstream><\/span>\r\n#include <string><\/span>\r\n#include <unordered_map><\/span>\r\n#include <vector><\/span>\r\n\r\nusing<\/span> map =<\/span> std::<\/span>unordered_map<<\/span>std::<\/span>string, int<\/span>><\/span>;                   \/\/ (1)<\/span>\r\n\r\nstd::<\/span>ifstream openFile(const<\/span> std::<\/span>string&<\/span> myFile){                  \r\n\r\n  std::<\/span>ifstream file(myFile, std::<\/span>ios::<\/span>in);\r\n  if<\/span> ( !<\/span>file ){\r\n    std::<\/span>cerr <<<\/span> \"Can't open file \"<\/span>+<\/span> myFile +<\/span> \"!\"<\/span> <<<\/span> std::<\/span>endl;\r\n    exit(EXIT_FAILURE);\r\n  }\r\n  return<\/span> file;\r\n  \r\n}\r\n\r\nstd::<\/span>string readFile(std::<\/span>ifstream file){                        \r\n    \r\n    std::<\/span>stringstream buffer;\r\n    buffer <<<\/span> file.rdbuf();\r\n    \r\n    return<\/span> buffer.str();\r\n    \r\n}\r\n\r\nmap createTeleBook(const<\/span> std::<\/span>string&<\/span> fileCont){                 \r\n    \r\n    map teleBook; \r\n    \r\n    std::<\/span>regex regColon(\":\"<\/span>);\r\n    \r\n    std::<\/span>sregex_token_iterator fileContIt(fileCont.begin(), fileCont.end(), regColon, -<\/span>1<\/span>);\r\n    const<\/span> std::<\/span>sregex_token_iterator fileContEndIt;\r\n    \r\n    std::<\/span>string entry;\r\n    std::<\/span>string key;\r\n    int<\/span> value;\r\n    while<\/span> (fileContIt !=<\/span> fileContEndIt){                               \/\/ (2)<\/span>\r\n        entry =<\/span> *<\/span>fileContIt++<\/span>;\r\n        auto<\/span> comma =<\/span> entry.find(\",\"<\/span>);                                  \/\/ (3)<\/span>\r\n        key =<\/span> entry.substr(0<\/span>, comma);\r\n        value =<\/span> std::<\/span>stoi(entry.substr(comma +<\/span> 1<\/span>, entry.length() -<\/span>1<\/span>));\r\n        teleBook[key] =<\/span> value;                                         \/\/ (4)<\/span>\r\n    }\r\n    return<\/span> teleBook;\r\n    \r\n}\r\n\r\nstd::<\/span>vector<<\/span>std::<\/span>string><\/span> getRandomNames(const<\/span> map&<\/span> teleBook){    \r\n    \r\n    std::<\/span>vector<<\/span>std::<\/span>string><\/span> allNames;\r\n    for<\/span> (const<\/span> auto<\/span>&<\/span> pair:<\/span> teleBook) allNames.push_back(pair.first);   \/\/ (5)<\/span>\r\n    \r\n    std::<\/span>random_device randDev;\r\n    std::<\/span>mt19937 generator(randDev());\r\n \r\n    std::<\/span>shuffle(allNames.begin(), allNames.end(), generator);         \/\/ (6)<\/span> \r\n    \r\n    return<\/span> allNames;\r\n}\r\n    \r\nvoid<\/span> measurePerformance(const<\/span> std::<\/span>vector<<\/span>std::<\/span>string>&<\/span> names, map&<\/span> m){   \r\n        \r\n    auto<\/span> start =<\/span> std::<\/span>chrono::<\/span>steady_clock::<\/span>now();\r\n    for<\/span> (const<\/span> auto<\/span>&<\/span> name:<\/span> names) m[name];                              \/\/ (7)<\/span>\r\n    std::<\/span>chrono::<\/span>duration<<\/span>double<\/span>><\/span> dur=<\/span> std::<\/span>chrono::<\/span>steady_clock::<\/span>now() -<\/span> start;\r\n    std::<\/span>cout <<<\/span> \"Access time: \"<\/span> <<<\/span> dur.count() <<<\/span> \" seconds\"<\/span> <<<\/span> std::<\/span>endl;\r\n    \r\n}\r\n    \r\nint<\/span> main(int<\/span> argc, char<\/span>*<\/span> argv[]){\r\n\r\n    std::<\/span>cout <<<\/span> std::<\/span>endl;\r\n  \r\n    \/\/ get the filename<\/span>\r\n    std::<\/span>string myFile;\r\n    if<\/span> ( argc ==<\/span> 2<\/span> ){\r\n        myFile=<\/span> {argv[1<\/span>]};\r\n    }\r\n    else<\/span>{\r\n        std::<\/span>cerr <<<\/span> \"Filename missing !\"<\/span> <<<\/span> std::<\/span>endl;\r\n        exit(EXIT_FAILURE);\r\n    } \r\n  \r\n    std::<\/span>ifstream file =<\/span> openFile(myFile);\r\n  \r\n    std::<\/span>string fileContent =<\/span> readFile(std::<\/span>move(file));\r\n  \r\n    map teleBook =<\/span> createTeleBook(fileContent);\r\n  \r\n    std::<\/span>cout <<<\/span> \"teleBook.size(): \"<\/span> <<<\/span>  teleBook.size() <<<\/span> std::<\/span>endl;\r\n  \r\n    std::<\/span>vector<<\/span>std::<\/span>string><\/span> randomNames =<\/span> getRandomNames(teleBook);\r\n  \r\n    measurePerformance(randomNames, teleBook); \r\n    \r\n    std::<\/span>cout <<<\/span> std::<\/span>endl;\r\n    \r\n}\r\n<\/pre>\n<\/div>\n
       <\/p>\n
      Let me start with the main program. I open the file, read the content, create a phone book (std::map<\/span> or std::unordered_map<\/span>), get an arbitrary permutation of the family names, and make the performance test finally. Okay, this was too concise.<\/p>\n
      Line 1 is the most interesting one. A std::unordered_map<\/span> supports a superset of the interface of a std::map<\/span>. This makes it quite convenient for me to make my performance test. I first did it by using map = std::map<std::string, int>;<\/span> and then changed the line to using map = std::unordered_map<std::string, int>;<\/span>.  The according to relations holds for the pairs (std::set\/std::unordered_set<\/span>),(std::mulitset, std::unordered_multiset<\/span>), and (std::multimap, std::unordered_multimap<\/span>). I assume the following functions are also quite interesting for you:<\/p>\n