{"id":110823,"date":"2025-01-31T07:00:00","date_gmt":"2025-01-31T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=110823"},"modified":"2025-01-31T23:05:57","modified_gmt":"2025-02-01T07:05:57","slug":"20250131-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20250131-00\/?p=110823","title":{"rendered":"Creating a generic insertion iterator, part 2"},"content":{"rendered":"

Last time, we tried to create a generic insertion iterator<\/a> but ran into trouble because our iterator failed to satisfy the iterator requirements of default constructibility and assignability.<\/p>\n

We ran into this problem because we stored the lambda as a member of the iterator.<\/p>\n

So let’s not do that!<\/p>\n

Instead of saving the lambda, we’ll just save a pointer to the lambda.<\/p>\n

template<typename Lambda>\r\nstruct generic_output_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    generic_output_iterator(Lambda&& lambda) noexcept :\r\n        insert(std::addressof(lambda)<\/span>) {}\r\n\r\n    generic_output_iterator& operator*() noexcept\r\n        { return *this; }\r\n    generic_output_iterator& operator++() noexcept\r\n        { return *this; }\r\n    generic_output_iterator& operator++(int) noexcept\r\n        { return *this; }\r\n\r\n    template<typename Value>\r\n    generic_output_iterator& operator=(\r\n        Value&& value)\r\n    {\r\n        (*insert)<\/span>(std::forward<Value>(value));\r\n        return *this;\r\n    }\r\n\r\nprotected:\r\n    Lambda* insert;<\/span>\r\n\r\n};\r\n\r\ntemplate<typename Lambda>\r\ngeneric_output_iterator<Lambda>\r\ngeneric_output_inserter(Lambda&& lambda) noexcept {\r\n    return generic_output_iterator<Lambda>(\r\n        std::forward<Lambda>(lambda));\r\n}\r\n\r\ntemplate<typename Lambda>\r\ngeneric_output_iterator(Lambda&&) ->\r\n    generic_output_iterator<Lambda>;\r\n<\/pre>\n
This requires that the lambda remain valid for the lifetime of the iterator, but that may not a significant burden. Other iterators also retain references that are expected to remain valid for the lifetime of the iterator. For example, std::back_inserter(v)<\/code> requires that v<\/code> remain valid for as long as you use the inserter. And if you use the iterator immediately, then the requirement will be satisfied:<\/p>\n
auto sample(std::vector<int>& v)\r\n{\r\n    std::map<int> m;\r\n    std::copy(v.begin(), v.end(),\r\n        generic_output_iterator(\r\n            [&m, hint = m.begin()](int v) mutable {<\/span>\r\n            hint = m.insert(hint, { v, 0 });       <\/span>\r\n        }));\r\n}\r\n<\/pre>\n
This lambda is used to produce the generic_output_iterator<\/code>, and the resulting iterator is consumed by std::copy<\/code> before the lambda destructs at the end of the full statement.<\/p>\n
It does become a problem if you want to save the iterator:<\/p>\n
auto sample(std::vector<int>& v1, std::vector<int>& v2)\r\n{\r\n    std::map<int> m;\r\n    \/\/ Don't do this\r\n    auto output =\r\n        generic_output_iterator(\r\n            [&m, hint = m.begin()](int v) mutable {\r\n            hint = m.insert(hint, { v, 0 });\r\n        }));\r\n    std::copy(v1.begin(), v1.begin(), output);\r\n    std::copy(v2.begin(), v2.begin(), output);\r\n}\r\n<\/pre>\n
In the above example, the resulting iterator is saved in output<\/code>, and then the lambda destructs, leaving output<\/code> pointing to an already-destroyed lambda.<\/p>\n
If you need to do this, you should store the lambda in a variable whose lifetime is at least as long as the iterator.<\/p>\n
auto sample(std::vector<int>& v1, std::vector<int>& v2)\r\n{\r\n    std::map<int> m;\r\n    auto lambda = [&m, hint = m.begin()](int v) mutable {\r\n        hint = m.insert(hint, { v, 0 });\r\n    };\r\n\r\n    auto output = generic_output_iterator(lambda);\r\n    std::copy(v1.begin(), v1.begin(), output);\r\n    std::copy(v2.begin(), v2.begin(), output);\r\n}\r\n<\/pre>\n
Bonus chatter<\/b>: If we really wanted to, we could teach the generic_output_iterator<\/code> to make a copy of the lambda, though we would have to work around the inability to default-construct a lambda, and also deal with the possibility that the lambda is move-only.<\/p>\n
We can simulate copy-assigning a lambda by destructing the old lambda and then copy-constructing the incoming lambda into the space occupied by the old lambda. If the lambda is noexcept copy-constructible, then we can just construct the new lambda in the space occupied by the old lambda. But if the copy constructor is potentially-throwing, we cannot contain the lambda directly but instead have to use a unique_ptr<\/code> to the lambda that we swap in after successfully copying the incoming one.<\/p>\n
If the lambda itself is not even copyable (for example, if it captures a unique_ptr<\/code>), we’ll have to emplace it into a shared_ptr<\/code>.<\/p>\n
Doing all of this is a lot of annoying typing and SFINAE, so I’ll leave it as an exercise that nobody will do.<\/p>\n","protected":false},"excerpt":{"rendered":"
Satisfying the iterator requirements, perhaps with a little cheating.<\/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-110823","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Satisfying the iterator requirements, perhaps with a little cheating.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110823","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=110823"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110823\/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=110823"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=110823"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=110823"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}