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

Contents[Show]

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 container was unified.

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

eightAssociativeContainers

By similar, I mean that their elements have the same structure and the same 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 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.

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 of most of the times a std::map is your first choice for an associative container. If your associative container is big and performance is key, think about a std::unordered_map. In the post Associative Containers - A simple Performance Comparison are a few performance numbers.

To make my life easy I wrote the function template printContainer (2) to display the associative container together with a short message. The same argument holds for the using namespace std::literals expression (1). Now, I can use the new builtin-literal for a C++ string. You see its usage it in the key/value pair {1, "a"s} in (3). "a"s is the C++ string literal that is available since C++14. You have just to 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

They are two new ways to add new elements to an associative container: try_emplace and insert_or_assign. ordMap.try_emplace(3, 3, 'C') (3) tries to add an new element to ordMap. The first 3 is the key of the element and the following 3 and 'C' directly goes 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"), the second call assign 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 not available in ordMap. If the key is already in ordMap, nothing will happen. There is no copy or move operation involved. All pointer and references to the transferred node remain valid.  You can merge nodes between similar containers. Associative containers must have to have the same structure and the same data types.

The extracting and inserting goes on (7). As I already mentioned it, each associative containers has a new subtype: a so-called node_type. I used it implicitly by merging one container into the other (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, 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 the 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 value of the node. 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 a 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 to C++17. Here are they: category C++17. Therefore, I'm done. I have written in 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 my 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. At first, I have to define a few terms. So I will write about data race versus race condition. In German, we use the same term "kritischer Wettlauf" for two different phenomena. That is extremely bad. Because in concurrency, a concise terminology is key.

 

 

 

Thanks a lot to my Patreon Supporter: Eric Pederson.

 

 

title page smalltitle page small Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Get your e-book. Support my blog.

 

Tags: C++17

Add comment


My Newest E-Book

Latest comments

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 354

All 329888

Currently are 165 guests and no members online