{"id":62,"date":"2022-05-15T18:56:43","date_gmt":"2022-05-15T18:56:43","guid":{"rendered":"https:\/\/blogs.oregonstate.edu\/codeblock\/?p=62"},"modified":"2022-05-15T18:56:43","modified_gmt":"2022-05-15T18:56:43","slug":"all-maps-are-not-created-equally","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/codeblock\/2022\/05\/15\/all-maps-are-not-created-equally\/","title":{"rendered":"All Maps Are Not Created Equally"},"content":{"rendered":"\n<p>For this, the final blog post of the Capstone project, I\u2019ve decided to utilize this space and time to gain a deeper understanding of maps and, more specifically, the boost container called flat_map.&nbsp;<\/p>\n\n\n\n<p>Recently in the Mahjong codebase I\u2019ve been working with nested maps and accessing data stored in a nested map structure. Although maps were obviously a topic covered throughout my CS coursework, I honestly didn\u2019t reach for them too often in my own projects and it took a fair amount of brainpower to unpack both what was in the nested map structure I was looking at and how to get the data from it that I needed.<\/p>\n\n\n\n<p>Fast-forward through conversations with engineers, cppreference reading, and a <a href=\"https:\/\/www.youtube.com\/watch?v=KiB0vRi2wlc\" target=\"_blank\" rel=\"noreferrer noopener\">supremely helpful video about maps in C++ from the Cherno<\/a> and I succeeded in strengthening my understanding of maps, how to use them, and when to reach for them. But then, as often happens, my mentor\/sensei asked me, \u201cwhy do you think we\u2019re using a boost container flat_map instead of just std::map?\u201d to which, in the moment, I could only make assumptions and guesses around optimization, but nothing concrete. Back to the books for me!<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/media.giphy.com\/media\/ncve7z4oPPURO\/giphy.gif\" alt=\"\" \/><\/figure>\n\n\n\n<p>First off, what the heck is a boost container flat_map? A flat_map is \u201can associative container that supports unique keys and provides fast retrieval of values of another type T based on the keys\u201d (<a href=\"https:\/\/www.boost.org\/doc\/libs\/1_65_1\/doc\/html\/boost\/container\/flat_map.html\" target=\"_blank\" rel=\"noreferrer noopener\">source<\/a>). That sure sounds like a map\u2026 \ud83e\uddd0 Like std::map, flat_map also supports random access iterators.<\/p>\n\n\n\n<p>Where I started to uncover some differences is in the following:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>flat_map &lt;Key, T&gt; has a value_type of std::pair&lt;Key, T&gt; whereas std::map&lt;Key,T&gt; has a value_type of std::pair&lt;<strong>const<\/strong> Key, T&gt;<\/li><li>flat_map is implemented like an ordered vector, which means that insertion of new elements will invalidate previous iterators and references<\/li><li>Random insertion into a std::map is faster than random insertion into flat_map (<a href=\"https:\/\/stackoverflow.com\/a\/25027750\" target=\"_blank\" rel=\"noreferrer noopener\">source<\/a>)<\/li><li>Random search between the two containers is comparable, though there is some debate that flat_map can be made faster and std::map cannot (<a href=\"https:\/\/stackoverflow.com\/a\/25027750\" target=\"_blank\" rel=\"noreferrer noopener\">source<\/a>)<\/li><\/ul>\n\n\n\n<p>None of this necessarily answered my sensei\u2019s question of why use a flat_map vs. a map. Thankfully though, a thorough and multiply cited above Stack Overflow post uncovered the answer to my query!<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/media.giphy.com\/media\/ugOMVsKh9pMWxji7w4\/giphy.gif\" alt=\"\" \/><\/figure>\n\n\n\n<p>One very important, significant advantage of a boost container flat_map over std::map is the speed with which a flat_map can be iterated over. Although a std::map would work for the specific use case in our Mahjong game where we use a flat_map, the fact that our nested map structure needs to be iterated over in a couple of different places in the game to get the data we need, a flat_map is a much better choice because that iteration can be optimized.<\/p>\n\n\n\n<p>Of course this is part of the job of a software engineer, however it\u2019s still amazing to me that someone knew to or at least took the time to look into making that design decision. I am such a novice and constantly humbled by the intelligence and experience of my colleagues. It\u2019s an incredible honor to work and learn from them, and I am eternally eager to continue growing in this field.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>For this, the final blog post of the Capstone project, I\u2019ve decided to utilize this space and time to gain a deeper understanding of maps and, more specifically, the boost container called flat_map.&nbsp; Recently in the Mahjong codebase I\u2019ve been working with nested maps and accessing data stored in a nested map structure. Although maps &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/blogs.oregonstate.edu\/codeblock\/2022\/05\/15\/all-maps-are-not-created-equally\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;All Maps Are Not Created Equally&#8221;<\/span><\/a><\/p>\n","protected":false},"author":12173,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[25,26,6,17,7,11,27],"class_list":["post-62","post","type-post","status-publish","format-standard","hentry","category-mahjong-board-editor","tag-blog-8","tag-boost-container-flat_map","tag-brainium-mahjong","tag-c","tag-capstone","tag-mahjong-board-editor","tag-stdmap"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/posts\/62","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/users\/12173"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/comments?post=62"}],"version-history":[{"count":1,"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/posts\/62\/revisions"}],"predecessor-version":[{"id":63,"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/posts\/62\/revisions\/63"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/media?parent=62"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/categories?post=62"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/codeblock\/wp-json\/wp\/v2\/tags?post=62"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}