C++17: Improved Associative Containers and Uniform Container Access

C++11 has eight associative containers. With C++17, you can more comfortably insert new elements into them, merge existing associative containers, or move elements from one container into another if they are similar. But that is not all. The access to the associative and sequential containers was unified.

Before I dive into the details, let me first answer the question: What do I mean by similar associative containers? We have eight associative containers. Here are they.

By similar, I mean their elements have the same structure and data types. The elements of std::set and std::multiset, std::unordered_set and std::unordered_multiset, std::map and std::multimap, and std::unordered_map and std::unordered_multimap have the same structure. 

Of course, that was only a high-level overview of the eight associative containers. That is for two reasons. First, I want to write about the improved interface. Second, you can read the details in my previous post: Hash Tables

Now to something completely new.

 

Rainer D 6 P2 500x500Modernes C++ Mentoring

Be part of my mentoring programs:

  • "Fundamentals for C++ Professionals" (open)
  • "Design Patterns and Architectural Patterns with C++" (open)
  • "C++20: Get the Details" (open)
  • "Concurrency with Modern C++" (starts March 2024)
  • Do you want to stay informed: Subscribe.

     

    The improved interface of the associative containers

    Let me show you the improved interface with an exhaustive example.

    // accociativeContainers.cpp
    
    #include <iostream>
    #include <map>
    #include <string>
    #include <utility>
     
    using namespace std::literals;                                     // 1
    
    template <typename Cont>
    void printContainer(const Cont& cont, const std::string& mess){    // 2
      std::cout << mess;
      for (const auto& pa: cont){
        std::cout << "(" << pa.first << ": " << pa.second << ") ";
      }
      std::cout << std::endl;
    }
    
    int main(){
      
      std::map<int, std::string> ordMap{{1, "a"s}, {2, "b"}};          // 3
      ordMap.try_emplace(3, 3, 'C');
      ordMap.try_emplace(3, 3, 'c');
     
      printContainer(ordMap, "try_emplace: ");
      
      std::cout << std::endl;
      
      std::map<int, std::string> ordMap2{{3, std::string(3, 'C')},     // 4
                                          {4, std::string(3, 'D')}};
      ordMap2.insert_or_assign(5, std::string(3, 'e'));
      ordMap2.insert_or_assign(5, std::string(3, 'E'));
      
      printContainer(ordMap2, "insert_or_assign: ");                   // 5
      
      std::cout << std::endl;
      
      ordMap.merge(ordMap2);                                           // 6
      
      std::cout<< "ordMap.merge(ordMap2)" << std::endl;
      
      printContainer(ordMap, "  ordMap: ");
      printContainer(ordMap2, "  ordMap2: ");
      
      std::cout << std::endl;  
      
      std::cout << "extract and insert: " << std::endl;
                                                                               
      std::multimap<int, std::string> multiMap{{2017, std::string(3, 'F')}};  
      
      auto nodeHandle = multiMap.extract(2017);                        // 7
      nodeHandle.key() = 6;                                           
      ordMap.insert(std::move(nodeHandle));                         
    
      printContainer(ordMap, "   ordMap: ");
      printContainer(multiMap, "   multiMap: ");
      
    }
    

     

    I use in the example a std::map because, most of the time, a std::map is your first choice for an associative container. If your associative container is big and performance is critical, think about a std::unordered_map. In the post Associative Containers – A simple Performance Comparison are a few performance numbers.

    To simplify my life, I wrote the function template printContainer (2) to display the associative container with a short message. The same argument holds for using namespace std::literals expression (1). Now, I can use the new built-in literal for a C++ string. You see its usage in the key/value pair {1, “a”s} in (3). “a”s is the C++ string literal that has been available since C++14. You must add the character s to the C string literal “a” to get a C++ string literal.

    Now, I will explain the program in detail. To get a better idea of it, peek at the output.

    accociativeContainers

    There are two new ways to add elements to an associative container: try_emplace and insert_or_assign. ordMap.try_emplace(3, 3, ‘C’) (3) tries to add a new element to ordMap. The first 3 is the key of the element, and the following 3 and ‘C’ directly go to the constructor of the value, which is, in this case, a std::string. It’s called try. Therefore, if the key is already in the std::map, nothing happens. ordMap2.insert_or_assign(5, std::string(3, ‘e’)) (4) behaves different. The first call (4) inserts the key/value pair 5, std::string(“eee”), and the second call assigns the std::string(“EEE”) to the key 5.

    With C++17, you can merge associative Containers (6). ordMap.merge(ordMap2) will merge the associative container ordMap2 into ordMap. Formally this process is called “splice”. That means each node consisting of the key/value pair will be extracted from ordMap2 and inserted into ordMap if the key is unavailable in ordMap. If the key is already in ordMap, nothing will happen. There is no copy or move operation involved. All pointers and references to the transferred node remain valid.  You can merge nodes between similar containers. Associative containers must have the same structure and the same data types.

    The extracting and inserting goes on (7). As mentioned, each associative container has a new subtype: node_type. I implicitly used it by merging one container into another (6). You can even use the node_type to change a key of a key/value pair. Have a look here. auto nodeHandle multiMap.extract(2017) extracts the node with the key 2017 from the std::multimap<int, std::string>. In the following lines, I change the key to 6: nodeHandle.key() = 6 and insert it into ordMap. I have to move the node, and copying is not possible.

    Of course, I also can insert the node into the same associative container (A) from which I extracted it or insert the node into the ordMap without changing the key (B). You can also change the value of node (C).

     

    auto nodeHandle = multiMap.extract(2017);   // A                      
    nodeHandle.key() = 6;
    multiMap.insert(std::move(nodeHandle));
      
    
    auto nodeHandle = multiMap.extract(2017);   // B                     
    ordMap.insert(std::move(nodeHandle)); 
    
    
    auto nodeHandle = multiMap.extract(2017);   // C
    nodeHandle.key() = 6;
    ordMap.insert(std::move(nodeHandle));   
    ordMap[6] = std::string("ZZZ");
    

     

    If you extract a node from an associative container (A) having a value such as std::map, std::unordered_map, std::multimap, or std::unordered_multimap, you get a node nodeHandleMap, on which you can invoke nodeHandleMap.key(). There is no method nodeHandleMap.value() to change the node’s value. Curiously enough, if you extract a node nodeHandleSet from a std::set or one of its three siblings, you can change the key by invoking nodeHandleSet.value().

     C++17 get three new global functions for accessing a container.

    Uniform container access

    The three new functions are named std::size, std::empty, and std::data.

    • std::size: Returns the size of a STL container, a C++ string, or a C array.
    • std::empty: Returns whether a given STL container, a C++ string, o a C array is empty.
    • std::data: Returns a pointer to the block of memory containing the elements of a container. The container has to have method data. This holds true for a std::vector, a std::string, and a std::array

    What’s next?

    I have written about 10 posts on C++17. Here are they: category C++17. Therefore, I’m done. I have written the last two years a lot of posts about multithreading. These posts were about the theory, the practice, concurrency with C++17 and C++20, and the memory model. As you might guess, I have a few new posts in mind for wrapping up my previous posts. Therefore, I will write my next posts about multithreading in existing and concurrency in the upcoming C++ standards. First, I have to define a few terms. So I will write about data race versus race conditions. In German, we use the term “kritischer Wettlauf” for two different phenomena. That is extremely bad. Because in concurrency, concise terminology is critical.

     

     

     

    Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, moon, and Philipp Lenk.

    Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.

    My special thanks to Embarcadero
    My special thanks to PVS-Studio
    My special thanks to Tipi.build 
    My special thanks to Take Up Code
    My special thanks to SHAVEDYAKS

    Seminars

    I’m happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

    Standard Seminars (English/German)

    Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

    • C++ – The Core Language
    • C++ – The Standard Library
    • C++ – Compact
    • C++11 and C++14
    • Concurrency with Modern C++
    • Design Pattern and Architectural Pattern with C++
    • Embedded Programming with Modern C++
    • Generic Programming (Templates) with C++
    • Clean Code with Modern C++
    • C++20

    Online Seminars (German)

    Contact Me

    Modernes C++ Mentoring,

     

     

    0 replies

    Leave a Reply

    Want to join the discussion?
    Feel free to contribute!

    Leave a Reply

    Your email address will not be published. Required fields are marked *