C++ Reference ยท Containers
C++ node handles: extract and merge
Move nodes between map, set and unordered containers without copying: node_type, extract, insert(node), merge, and changing a map key in place.
Associative containers (set, map, multiset, multimap and their unordered_ versions) store each element in its own heap node. Since C++17 you can detach a node from one container with extract(), which gives you a node handle (node_type), and then insert that handle into another container. No element is copied or moved, no allocation happens, and pointers and references to the element stay valid.
Node handles solve a long-standing gap: the keys of a std::map are const, so you could not rename a key. With extract you take the node out, change its key through the handle, and insert it again. The related merge() member moves every node that fits from one container into another.
auto node = m.extract("old"); // detach the node node.key() = "new"; // keys are writable through a handle m.insert(std::move(node)); // reattach
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
node_type extract(const_iterator position); node_type extract(const key_type& key); insert_return_type insert(node_type&& nh); // set, map, unordered_* iterator insert(node_type&& nh); // multiset, multimap iterator insert(const_iterator hint, node_type&& nh); template<class C2> void merge(C2& source); template<class C2> void merge(C2&& source); // rvalue sources are accepted too
| Name | Description |
|---|---|
position, key |
Selects the element to detach. |
nh |
A node handle obtained from extract of a compatible container. |
source |
A container with the same key, value and allocator types, but possibly different comparator or hash. |
Node handle members: empty(), explicit operator bool, get_allocator(), swap, and value() (sets), key() and mapped() (maps).
Returns: extract returns the handle (empty if the key is absent). insert(node_type&&) into a unique-key container returns a struct with position, inserted and node; if the key already existed, inserted is false and node gets the handle back. For multi-containers it returns an iterator.
Errors / undefined behavior: inserting a non-empty handle whose allocator differs from the container's allocator is undefined. Reading key(), mapped() or value() of an empty handle is undefined.
Usage notes
- No copies, no allocation. Extract and insert only relink nodes, so they are cheap for large or non-movable elements.
- Iterators to the extracted element are invalidated; pointers and references to it remain valid and are usable again after insertion into another container.
mergeis all-or-nothing per element. A node with a key that already exists in the target stays in the source. If a comparison throws, some nodes may have been moved already.- Handles are move-only. A non-empty handle that is destroyed frees the element, so you do not leak.
- Complexity.
extractby iterator is amortized O(1); by key it is a lookup (O(log n) ordered, O(1) average unordered).mergeis O(n log size) for ordered sources. - Sequence containers have no node handles.
vector,dequeandlistdo not supportextract;list::spliceis their equivalent for moving nodes. - Added in C++17.
Related
std::map,std::set, map operations,std::unordered_map, Iterator invalidation- Lessons: Map, Set