Add support for `merge`?

[yilongli]

Thanks for making this library!

I am hoping to use unordered_dense::map as a drop-in replacement for std::unordered_map in some performance-critical sections of my code. However, I currently rely on the merge method, which is not yet implemented. It also appears to be the only method missing in the standard API. Would be great if you could include it as well. Thanks in advance!

[martinus]

merge() is not possible because unordered_dense is not node based, so data has to be moved when you want to move stuff from another unordered_dense map.

I'd say the fastest way move stuff from e.g. map2 into map1 with unordered_dense is this:

auto data = std::move(map2).extract();
map1.insert(std::make_move_iterator(data.begin()), std::make_move_iterator(data.end()));

Note that the extract() method does something complete different in unordered_dense than in std::unordered_map.

[Philippe91]

BTW, the result of extract() is clear, and there is a comment that says that the map is emptied. However, the extract() implementation makes me question: what about the internal state of the map afterward since m_buckets / m_num_buckets are preserved? For instance, is it safe to insert into the map (or to actually call any method) after an extract() was executed? Since this is a non-standard API, a bit of documentation about it would be welcome 😉

[yilongli]

Cool; thanks for your suggestion! A bit of warning about extract & merge would be nice in README.

[yilongli]

Actually, my code doesn't depend on the guarantee of merge that no elements are moved, and your solution just works out of the box for me. Thus, I think it would be beneficial for users to have a non-standard api that does exactly this.

Further, to avoid confusion, I suggest using a different name for extract(). For example, what about renaming extract to drain (it kinda implies that the container will be emptied) and provide a new method absorb for the merge-like operation?

Thanks again for your library!

[martinus]

I've named extract() after the proposed std::flat_map which does basically the same; move out the internally used container: https://wg21.link/p0429r9 There's also replace() like in that paper. So at least there will be a container with an API that does practically the same thing. I think std::flat_map was supposed to come for C++23 but didn't make it

[yilongli]

Good to know! Anyway, feel free to close this issue.