{"id":8173,"date":"2023-09-04T06:51:38","date_gmt":"2023-09-04T06:51:38","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=8173"},"modified":"2023-09-04T06:57:28","modified_gmt":"2023-09-04T06:57:28","slug":"c23-four-new-associative-containers","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/c23-four-new-associative-containers\/","title":{"rendered":"C++23: Four new Associative Containers"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">The four associative containers <code>std::flat_map<\/code>, <code>std::flat_multimap<\/code>, <code>std::flat_set<\/code>, and <code>std::flat_multiset<\/code> in C++23 are a drop-in replacement for the ordered associative containers <code>std::map<\/code>,<code> std::multimap<\/code>, <code>std::set<\/code>, and <code>std::multiset<\/code>. We have them for two reasons in C++23: memory consumption and performance.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1030\" height=\"579\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/Cpp23-3-1030x579.png\" alt=\"\" class=\"wp-image-8177\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/Cpp23-3-1030x579.png 1030w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/Cpp23-3-300x169.png 300w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/Cpp23-3-768x432.png 768w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/Cpp23-3-705x397.png 705w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/Cpp23-3.png 1280w\" sizes=\"auto, (max-width: 1030px) 100vw, 1030px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">With C++23, we have 12 associative Containers. Twelve? Right! <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>C++98<\/strong>: <code>std::map, std::set, std::multimap<\/code>, and <code>std::multiset<\/code><\/li>\n\n\n\n<li><strong>C++11<\/strong>: <code>std::unordered_map, std::unordered_set, std::unordered_multimap<\/code>, and <code>std::unordered_multiset<\/code><\/li>\n\n\n\n<li><strong>C++23<\/strong>: <code>std::flat_map, std::flat_set, std::flat_multimap<\/code>, and <code>std::flat_multiset<\/code><\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Now,  I need a systematic and start with the C++98 and C++11 associative containers.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Associative Container<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">All associative containers have in common that they associate a key with a value. Therefore, you can get the value by using the key. The C++98 associative containers are called ordered associative containers; the C++11 ones are unordered associative containers. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To classify the associative containers, you have to answer three simple questions:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Are the keys sorted?<\/li>\n\n\n\n<li>Does the key have an associated value?<\/li>\n\n\n\n<li>Can a key appear more than once?<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">The following table with 2^3= 8 rows answers the three questions. I answered a fourth question in the table. How fast is the access time in the average case?<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"955\" height=\"407\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/OrderedVersusUnorderedContainers.png\" alt=\"\" class=\"wp-image-8187\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/OrderedVersusUnorderedContainers.png 955w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/OrderedVersusUnorderedContainers-300x128.png 300w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/OrderedVersusUnorderedContainers-768x327.png 768w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/OrderedVersusUnorderedContainers-705x300.png 705w\" sizes=\"auto, (max-width: 955px) 100vw, 955px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">I&#8217;d like to give you more information about the associative containers to understand their performance characteristics.cs. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Ordered Associative Containers<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">The keys of the ordered associative containers are ordered. The smaller relation (&lt;) is used by default, and the containers are sorted in increasing order.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This ordering has interesting consequences.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The key has to support an ordering relation.<\/li>\n\n\n\n<li>Associative containers are typically implemented as <a href=\"https:\/\/en.wikipedia.org\/wiki\/Red%E2%80%93black_tree\" data-type=\"link\" data-id=\"https:\/\/en.wikipedia.org\/wiki\/Red%E2%80%93black_tree\">red-black trees.<\/a> These are balanced binary search trees.<\/li>\n\n\n\n<li>The access time to the key and, therefore, to the value is logarithmic.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">The most often used ordered associative container is <code>std::map<\/code>:<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;gray;border-width:.1em .1em .1em .8em\"><pre style=\"margin: 0; line-height: 125%\">std<span style=\"color: #555555\">::<\/span>map<span style=\"color: #555555\">&lt;<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span>, std<span style=\"color: #555555\">::<\/span>string<span style=\"color: #555555\">&gt;<\/span> int2String{ {<span style=\"color: #FF6600\">3<\/span>, <span style=\"color: #CC3300\">&quot;three&quot;<\/span>}, {<span style=\"color: #FF6600\">2<\/span>, <span style=\"color: #CC3300\">&quot;two&quot;<\/span>}, {<span style=\"color: #FF6600\">1<\/span>, <span style=\"color: #CC3300\">&quot;one&quot;<\/span>},\n                                       {<span style=\"color: #FF6600\">5<\/span>, <span style=\"color: #CC3300\">&quot;five&quot;<\/span>}, {<span style=\"color: #FF6600\">6<\/span>, <span style=\"color: #CC3300\">&quot;six&quot;<\/span>}, {<span style=\"color: #FF6600\">4<\/span>, <span style=\"color: #CC3300\">&quot;four&quot;<\/span>}, {<span style=\"color: #FF6600\">7<\/span>, <span style=\"color: #CC3300\">&quot;seven&quot;<\/span>} };\n<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">The balanced binary search tree may have the following structure:<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"475\" height=\"265\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/geordneteAssoziativeArrays.png\" alt=\"\" class=\"wp-image-8180\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/geordneteAssoziativeArrays.png 475w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/08\/geordneteAssoziativeArrays-300x167.png 300w\" sizes=\"auto, (max-width: 475px) 100vw, 475px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Unordered Associative Containers<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The crucial idea of the unordered associative containers is that the key is mapped onto the bucket with the help of the hash function. The value is just attached to the key.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The unordered associative containers store their keys in buckets. Which bucket the key goes to is due to the hash function, which maps the key to a unique number. This number is modulo-divided by the number of buckets. If different keys are mapped to the same bucket, it\u2019s called a collision. The good hash function equally distributes the keys. The value is just associated with the key.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The usage of the hash function has very important consequences for the unordered associative container.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The hash function for the key must be available.<\/li>\n\n\n\n<li>The keys must support equality comparison to deal with collisions.<\/li>\n\n\n\n<li>The execution time of a hash function is a constant. Therefore, the access time to the keys of an unordered associative container is constant if the keys are equally distributed.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">According to<code> std::map<\/code>, <code>std::unordered_map<\/code> is the most often used unordered associative container.<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;gray;border-width:.1em .1em .1em .8em\"><pre style=\"margin: 0; line-height: 125%\">std<span style=\"color: #555555\">::<\/span>unordered_map<span style=\"color: #555555\">&lt;<\/span>std<span style=\"color: #555555\">::<\/span>string, <span style=\"color: #007788; font-weight: bold\">int<\/span><span style=\"color: #555555\">&gt;<\/span> str2Int{ {<span style=\"color: #CC3300\">&quot;Grimm&quot;<\/span>,<span style=\"color: #FF6600\">491634333356<\/span>}, {<span style=\"color: #CC3300\">&quot;Grimm-Jaud&quot;<\/span>, <span style=\"color: #FF6600\">49160123335<\/span>}, \n                                              {<span style=\"color: #CC3300\">&quot;Schmidt&quot;<\/span>,<span style=\"color: #FF6600\">4913333318<\/span>},{<span style=\"color: #CC3300\">&quot;Huber&quot;<\/span>,<span style=\"color: #FF6600\">490001326<\/span>} };\n<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">The graphic shows the mapping of the keys to their bucket using the hash function.<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"387\" height=\"342\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/09\/UngeordnetesAssoziativesArrayEng.png\" alt=\"\" class=\"wp-image-8196\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/09\/UngeordnetesAssoziativesArrayEng.png 387w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2023\/09\/UngeordnetesAssoziativesArrayEng-300x265.png 300w\" sizes=\"auto, (max-width: 387px) 100vw, 387px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">The four associative containers <code>std::flat_map<\/code>, <code>std::flat_multimap<\/code>, <code>std::flat_set<\/code>, and <code>std::flat_multiset<\/code> in C++23 are a drop-in replacement for the ordered associative containers <code>std::map<\/code>,<code> std::multimap<\/code>, <code>std::set<\/code>, and <code>std::multiset<\/code>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Container Adaptors<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The flat-ordered associative containers in C++23 have the same interface as their C++98 pendants. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The flat-ordered associative containers are called container adaptors because they require separate sequence containers for their keys and values. This sequence container must support a random access iterator. By default, a <code>std::vector <\/code>is used, but a<code> std::array<\/code>, or a <code>std::deque<\/code> is also valid.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The following code snippet shows the declaration of <code>std::flat_map<\/code>, and <code>std::flat_set<\/code>:<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;gray;border-width:.1em .1em .1em .8em\"><pre style=\"margin: 0; line-height: 125%\"><span style=\"color: #006699; font-weight: bold\">template<\/span><span style=\"color: #555555\">&lt;<\/span><span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">Key<\/span>, <span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">T<\/span>, \n        <span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">Compare<\/span> <span style=\"color: #555555\">=<\/span> less<span style=\"color: #555555\">&lt;<\/span>Key<span style=\"color: #555555\">&gt;<\/span>,\n        <span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">KeyContainer<\/span> <span style=\"color: #555555\">=<\/span> vector<span style=\"color: #555555\">&lt;<\/span>Key<span style=\"color: #555555\">&gt;<\/span>, <span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">MappedContainer<\/span> <span style=\"color: #555555\">=<\/span> vector<span style=\"color: #555555\">&lt;<\/span>T<span style=\"color: #555555\">&gt;&gt;<\/span>\n<span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">flat_map<\/span>;\n\n<span style=\"color: #006699; font-weight: bold\">template<\/span><span style=\"color: #555555\">&lt;<\/span><span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">Key<\/span>, \n         <span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">Compare<\/span> <span style=\"color: #555555\">=<\/span> less<span style=\"color: #555555\">&lt;<\/span>Key<span style=\"color: #555555\">&gt;<\/span>, \n         <span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">KeyContainer<\/span> <span style=\"color: #555555\">=<\/span> vector<span style=\"color: #555555\">&lt;<\/span>Key<span style=\"color: #555555\">&gt;&gt;<\/span>\n<span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">flat_set<\/span>;\n<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">The reason for the flat-ordered associative containers is performance.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Comparison of the Flat-Ordered Containers and their Non-Flat Pendants<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The <strong>flat-ordered associative containers<\/strong> provide different time and space complexities than the ordered ones. They require less memory and are faster to read than their non-flat-ordered pendants. They support a random access iterator. &nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The <strong>non-flat-ordered associative containers<\/strong> improve writing performance if you insert or delete elements. Additionally, they guarantee that the iterators stay valid after inserting or deleting an element and support a bidirectional iterator.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">So far, I cannot show you numbers about the flat-ordered associative containers because no compiler supports them. I will update my performance test &#8220;<a href=\"https:\/\/www.modernescpp.com\/index.php\/more-special-friends-with-std-map-and-std-unordered-map\/\" data-type=\"link\" data-id=\"https:\/\/www.modernescpp.com\/index.php\/more-special-friends-with-std-map-and-std-unordered-map\/\">More special Friends with <code>std::map<\/code> and <code>std::unordered_map<\/code><\/a>&#8221; if <code>std::flat_map<\/code> is available.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">What&#8217;s Next? <\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">A <code>std::mdspan<\/code> is a non-owning multidimensional view of a contiguous sequence of objects. The contiguous sequence of objects can be a plain C-array, a pointer with a size, a <code>std::array<\/code>, a <code>std::vector<\/code>, or a <code>std::string<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The four associative containers std::flat_map, std::flat_multimap, std::flat_set, and std::flat_multiset in C++23 are a drop-in replacement for the ordered associative containers std::map, std::multimap, std::set, and std::multiset. We have them for two reasons in C++23: memory consumption and performance. With C++23, we have 12 associative Containers. Twelve? Right! Now, I need a systematic and start with the [&hellip;]<\/p>\n","protected":false},"author":21,"featured_media":8175,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[378],"tags":[472],"class_list":["post-8173","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c-23","tag-associative-containers"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8173","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=8173"}],"version-history":[{"count":23,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8173\/revisions"}],"predecessor-version":[{"id":8206,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8173\/revisions\/8206"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/8175"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=8173"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=8173"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=8173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}