C++ Node Handles: Moving Elements Without Allocation

Introduced in C++17, the node handle API enables developers to extract individual nodes directly from associative containers—such as std::set, std::map, std::unordered_set, and std::unordered_map—and transfer them to another container without allocating or deallocating memory. By decoupling an internal node from the container's balancing or hashing structure while preserving its allocated memory block, the node handle allows zero-copy, zero-allocation splicing of elements, significantly optimizing performance-critical workflows.

The Traditional Relocation Problem

Prior to C++17, moving an element from one associative container to another required two distinct operations: inserting the element into the target container and erasing it from the source container.

Even when using move semantics, associative containers are node-based structures where each entry requires a wrapper node containing bookkeeping metadata (such as red-black tree pointers or hash bucket links). Consequently, insertion always forced a dynamic allocation for a new node in the destination container, while the subsequent erasure deallocated the source node. This created unnecessary memory overhead and allocation latency, even if the payload itself was moved efficiently.

Mechanics of Node Extraction

The node handle API resolves this by exposing the container's internal node directly. Using the .extract() member function, a node is unlinked from the source container's tree or bucket array without invoking its destructor or freeing its memory:

auto node = source_map.extract(key);

The resulting node_type object is a move-only wrapper that takes full ownership of the extracted node. While held in a node handle, the element is not part of any container, but its underlying value remains fully constructed in place.

Zero-Allocation Insertion

Once a node handle is obtained, it can be inserted into a compatible destination container using an overload of the .insert() method:

destination_map.insert(std::move(node));

During this operation, the destination container adopts the existing memory block instead of requesting new memory from its allocator. It recalculates the necessary balancing pointers (for trees) or bucket positions (for hash tables) and links the node directly into its internal structure. If an insertion fails—such as when a key collision occurs in a unique associative container—the node handle remains valid and retains ownership of the uninserted node, preventing data loss and still avoiding deallocation.

Container Splicing with merge

For bulk operations, C++17 introduced the .merge() member function, which operationalizes the node handle mechanism automatically across entire containers:

destination_map.merge(source_map);

The .merge() function iterates through the source container, extracting each node and relinking it into the destination container without any heap allocation. Any elements that cannot be inserted due to key collisions remain in the source container.

In-Place Key Modification

Beyond inter-container transfers, node handles allow modifying keys within unique associative containers without reallocating. Normally, elements in containers like std::set or keys in std::map are immutable (const) to prevent corrupting the internal ordering. By extracting the node via a node handle, developers gain mutable access to the key through node.key(). The key can be altered safely while the node is detached, and reinserting the handle prompts the container to position the existing node into its new correct location with zero memory allocations.

Requirements and Compatibility

To transfer nodes without allocation, containers must be compatible:

  • Both containers must share the exact same node layout and element types.
  • Both containers must use equivalent allocator types; if the allocators do not compare equal, the transfer cannot reuse the existing memory allocation.
  • Transfers are permitted between equivalent unique and non-unique variants, such as moving a node directly from a std::set into a std::multiset.