{"id":110817,"date":"2025-01-29T07:00:00","date_gmt":"2025-01-29T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=110817"},"modified":"2025-01-29T07:36:06","modified_gmt":"2025-01-29T15:36:06","slug":"20250129-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20250129-00\/?p=110817","title":{"rendered":"How do I create an inserter iterator that does unhinted insertion into an associative container like <CODE>std::map<\/CODE>?"},"content":{"rendered":"<p>The C++ standard library contains various types of inserters:<\/p>\n<ul>\n<li><code>back_inserter(c)<\/code> which uses <code>c.push_back(v)<\/code>.<\/li>\n<li><code>front_inserter(c)<\/code> which uses <code>c.push_front(v)<\/code>.<\/li>\n<li><code>inserter(c, it)<\/code> which uses <code>c.insert(it, v)<\/code>.<\/li>\n<\/ul>\n<p>C++ standard library associative containers do not have <code>push_back<\/code> or <code>push_front<\/code> methods; your only option is to use the <code>inserter<\/code>. But we also learned that the <a title=\"Speeding up the insertion of a sorted (or mostly-sorted) key list into a std::map or other ordered associative container\" href=\"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230522-00\/?p=108226\"> hinted insertion can speed up the operation if the hint is correct, or slow it down if the hint is wrong<\/a>. (<a title=\"How useful is the hint passed to the std::unordered_... collections?\" href=\"https:\/\/devblogs.microsoft.com\/oldnewthing\/20241028-00\/?p=110428\">Or it might not have any effect at all<\/a>.)<\/p>\n<p>What if you know that the items are arriving in an unpredictable order? You don&#8217;t want to provide a hint, because that&#8217;s a pessimization. The <code>inserter<\/code> requires you to pass a hint. What do you do if you don&#8217;t want to provide a hint?<\/p>\n<p>It looks like you&#8217;ll have to write your own inserter. Fortunately, it&#8217;s not hard.<\/p>\n<pre>template&lt;typename Container&gt;\r\nstruct default_insert_iterator\r\n{\r\n    using iterator_category = std::output_iterator_tag;\r\n    using value_type = void;\r\n    using pointer = void;\r\n    using reference = void;\r\n    using difference_type = void;\r\n\r\n    default_insert_iterator(Container&amp; c) noexcept :\r\n        container(std::addressof(c)) {}\r\n\r\n    default_insert_iterator&amp; operator*() noexcept\r\n        { return *this; }\r\n    default_insert_iterator&amp; operator++() noexcept\r\n        { return *this; }\r\n    default_insert_iterator&amp; operator++(int) noexcept\r\n        { return *this; }\r\n\r\n    default_insert_iterator&amp; operator=(\r\n        typename Container::value_type const&amp; value)\r\n    {\r\n        container-&gt;insert(value);\r\n        return *this;\r\n    }\r\n\r\n    default_insert_iterator&amp; operator=(\r\n        typename Container::value_type &amp;&amp; value)\r\n    {\r\n        container-&gt;insert(std::move(value));\r\n        return *this;\r\n    }\r\n\r\nprotected:\r\n    Container* container;\r\n\r\n};\r\n\r\ntemplate&lt;typename Container&gt;\r\ndefault_insert_iterator&lt;Container&gt;\r\ndefault_inserter(Container&amp; cont) noexcept {\r\n    return default_insert_iterator&lt;Container&gt;(cont);\r\n}\r\n<\/pre>\n<p>The iterator type itself doesn&#8217;t have much in it. It declares some member types to satisfy iterator requirements, and it has dummy <code>*<\/code> and <code>++<\/code> operators. The actual interesting thing is the assignment operator, which inserts the value into the container using an unhinted <code>insert<\/code>.<\/p>\n<p>There is a subtlety: Iterators must be default-constructible, so we have to store the container as a pointer rather than a reference, since there is no default constructor for a reference. (Although iterators must be default-constructible, a default-constructed iterator is not dereferenceable, so it&#8217;s okay that the pointer is uninitialized.)<\/p>\n<p>But wait, there are other ways to insert into a container. Maybe we know that the items are mostly-ordered, so you want to hint the insertion with the result of the previous insertion.<\/p>\n<p>We&#8217;ll generalize our inserter next time.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Curiously missing from the standard library.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-110817","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>Curiously missing from the standard library.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110817","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=110817"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110817\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=110817"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=110817"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=110817"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}