--- title: "node-handles for lists" document: P3049R2 date: 2026-06-15 audience: LWG reply-to: - "Michael Florian Hava " --- **Before** **Proposed** :::wording-add //given: template void splice_if(list & from, list & to, T val) { const auto it{ranges::find(from, val)}; if(it != from.end()) to.splice(to.begin(), from, it); } //usage: list & l1 = …; //filled with random ints //both lists must be available here to move an element list & l2 = …; splice_if(l1, l2, 42); //given: template list::node_type extract_if(list & from, T val) { const auto it{ranges::find(from, val)}; if(it != from.end()) return from.extract(it); return {}; } //usage: list & l1 = …; //filled with random ints auto nh{extract_if(l1, 42)}; //nh can be passed around independently! // => extraction and insertion can be separated list & l2 = …; if(nh) l2.insert(l2.end(), move(nh)); //given: template void splice_if(forward_list & from, forward_list & to, T val) { //assume there is a ranges::find_before returning // the iterator before val or end() const auto it{ranges::find_before(from, val)}; if(it != from.end()) to.splice_after(to.before_begin(), from, it); } //usage: forward_list & l1 = …; //filled with random ints //both lists must be available here to move an element forward_list & l2 = …; splice_if(l1, l2, 42); //given: template auto extract_if(forward_list & from, T val) { //assume there is a ranges::find_before returning // the iterator before val or end() const auto it{ranges::find_before(from, val)}; if(it != from.end()) return from.extract_after(it); return forward_list::node_type{}; } //usage: forward_list & l1 = …; //filled with random ints auto nh{extract_if(l1, 42)}; //nh can be passed around independently! // => extraction and insertion can be separated forward_list & l2 = …; if(nh) l2.insert_after(l2.before_begin(), move(nh)); ::: [RISC Software GmbH, Softwarepark 32a, 4232 Hagenberg, Austria, michael.hava@risc-software.at](mailto:michael.hava@risc-software.at) 1 **R1:** Changes after LEWG Mailing List Review in June 2024: * Rewrote subsection on cross container `node-handle` compatibility. * Added subsection on why `list` isn't a valid `node-handle` type. **R2:** Updates after LEWG review in Brno on 2026-06-12: * Expanded motivation in paper to match all the motivation presented during the discussion. * Added references to `forward_list::before_begin` to make API more comprehensible. * Minor fixes to the wording. * Referencing more up to date working draft. ## Motivation Node handles are an over-specified solution to the relatively simple problem of moving nodes between associative containers, which can be done with a more conservative interface similar to std::list::splice. There is a lack of consistency with std::list, where splicing and merging can be done but there is no node handle-based interface, yet lists are indeed node based, too. P00832 acknowledges the simpler solution (by Talbot) but dismisses it as it offered “no further advantages”: however, the further advantages or use cases node handles allegedly provide are not clear at all. We agree with the criticism that there is a lack of consistency with other node-based sequences, but think the advantages of this new API are very clear: * Separation of extraction and insertion (compared to the traditional splice-API), thereby enabling: * Modifications of the otherwise immutable key. * Adding custom logic running between extraction and insertion. * Transferability between compatible containers. * Isolation of source- and target-container. * Transfer of expensive-to-move or outright immovable objects. As several of these are equally relevant for lists, we propose adding a suitable subset of the `nodehandle` API to the remaining node-based sequence containers, namely `list` and `forward_list`. ### Design Space ```cpp using node_type = implementation defined specialization of node_handle; 0⃣ node_type extract(const_iterator pos); 1⃣ node_type extract(const key_type & key); 2⃣ template node_type extract(Key && key); 3⃣ struct insert_return_type { 4⃣ iterator position; bool inserted; node_type node; }; insert_return_type insert(node_type && handle); 5⃣ iterator insert(const_iterator pos, node_type && handle); 6⃣ ``` Removing aspects related to key lookups (2⃣�, �3⃣, �5⃣) and for handling key collisions (�4⃣), we arrive at the following API subset for node-based sequence containers, proposed verbatim for `list`: ```cpp using node_type = implementation defined specialization of node_handle; node_type extract(const_iterator pos); iterator insert(const_iterator pos, node_type && handle); ``` Note that whilst this API is syntactically consistent across all classes, the iterator parameter of `insert` has varying meanings: * Ordered, associative: A location to insert as close as possible to. * Unordered, associative: A hint for where search for an insertion point could start. * Sequence: The actual insertion point. As `forward_list` is singly-linked it cannot efficiently support the same API as other sequence containers. Therefore its API has been adapted in name and semantics, resulting in member functions like `erase_after` instead of `erase`. We follow this design principle and propose the following API : 2 `using` `node_type` `=` `implementation defined specialization of node_handle``;` `node_type` `extract_after``(``const_iterator` `pos``);` `iterator` `insert_after``(``const_iterator` `pos``,` `node_type` `&&` `handle``);` **On cross container** `node-handle` **compatibility** An advanced feature of the `node-handle` API is the ability to transfer nodes between compatible containers of the same category. Compatibility is only dependent on matching allocators and element types, other attributes (key comparison, hashing strategy and key uniqueness) are ignored. For `forward_list` and `list` this doesn’t apply as there are no attributes to ignore. Nonetheless there is group of lists we in theory could provide additional compatibility with: the bucket lists of an `unordered_[multi_]set`. As the requirements on elements of unordered sets are a strict superset of those in lists, it could be possible to move nodes between those two. [However, reviewing [unord.req.general] casts doubt mandating such a compatibility is possible](https://eel.is/c++draft/unord.req.general) after all. As only forward iterators are required, there is sufficient leeway for implementation divergence: MS-STL uses doubly-linked bucket lists whereas libstdc++ uses a singly-linked 3 4 ones. Therefore we don’t propose additional node-type compatibilities. **Extracting multiple nodes at once** One could imagine an extension to the `node-handle` API that only makes sense for node-based sequence containers: extracting several consecutive nodes at once and later batch inserting them. While we can foresee clever `node-handle` implementation strategies to support this transparently for doubly-linked lists, we expect different handle types to be necessary for singly-linked lists if O(1) range inserts are to be maintained. On first glance this API does not support removing the first element nor inserting before the first element. 2 But this is in fact supported by the use of the special iterator produced by `before_begin` [([forward.list.iter]).](https://eel.is/c++draft/forward.list.iter) [https://github.com/microsoft/STL/blob/d6efe9416e4ad7d6e245ae9e96023d413794d1eb/stl/inc/](https://github.com/microsoft/STL/blob/d6efe9416e4ad7d6e245ae9e96023d413794d1eb/stl/inc/xhash#L332-L335) 3 [xhash#L332-L335](https://github.com/microsoft/STL/blob/d6efe9416e4ad7d6e245ae9e96023d413794d1eb/stl/inc/xhash#L332-L335) [https://github.com/gcc-mirror/gcc/blob/cebbaa2a84586a7345837f74a53b7a0263bf29ee/](https://github.com/gcc-mirror/gcc/blob/cebbaa2a84586a7345837f74a53b7a0263bf29ee/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L317) 4 [libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L317](https://github.com/gcc-mirror/gcc/blob/cebbaa2a84586a7345837f74a53b7a0263bf29ee/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L317) As we can’t come up with a convincing use-case for such a facility, we don’t propose them and suggest future proposals on this topic to introduce a dedicated `multi-node-handle` instead of changing the conceptual design of `node-handle`. **Why** `list` **shouldn't be used as** `node-handle` It has been suggested that `list` doesn't need a dedicated `node-handle` type as the type itself can already act as a `multi-node-handle`. Apart from the issue of API inconsistency, we don’t agree with this suggestion as `list` in general does not provide the same guarantees. A `node-handle` is designed as a lightweight, move-only(!) „container“ for up to one node in [transit. Accordingly, per [container.node.overview] it has to be both](https://eel.is/c++draft/container.node.overview) `nothrow-defaultconstructible` as well as `nothrow-move-constructible`. Neither of which is mandated for `list` per the standard and at east one implementation does not provide said guarantees due to the usage of sentinel nodes . Therefore we maintain a dedicated `node-handle` type is necessary 5 for portable code. ## Impact on the Standard ## Implementation Experience ## Proposed Wording ### [version.syn] ### [container.node] :::wording #define __cpp_lib_node_extract 201606YYYYMML //also in , , , , , ::: **[DRAFTING NOTE: Adjust the placeholder value as needed to denote the proposal’s date of adoption.]** **??.?.?.? Overview** **[container.node.overview]** :::wording-add 1 A node handle is an object that accepts ownership of a single element from a list [list], a forward_list [forward.list], an associative container ([associative.reqmts]), or an unordered associative container ([unord.req]). It may be used to transfer that ownership to another container with compatible nodes. Containers with compatible nodes have the same node handle type. Elements may be transferred in either direction between container types in the same row of [tab:container.node.compat]. ::: **[DRAFTING NOTE: Even though theoretically possible, we can’t mandate additional compatibilities for various reasons.]** … 4 If a user-defined specialization of pair exists for `pair` or `pair`, where `Key` is the container’s `key_type` and `T` is the container’s `mapped_type`, the behavior of operations involving node handles is undefined. :::wording template class node-handle { public: // These type declarations are described in [container.requirements.general], [associative.reqmts], and [unord.req]. using value_type = see below; // not present for map containers using key_type = see below; // notonly present for setmap containers using mapped_type = see below; // notonly present for setmap containers using allocator_type = see below; … // [container.node.observers], observers value_type& value() const; // not present for map containers key_type& key() const; // notonly present for setmap containers mapped_type& mapped() const; // notonly present for setmap containers https://github.com/microsoft/STL/blob/926d458f82ae1711d4e92c0341f541a520ef6198/stl/inc/list#L802- 5 L908 ::: ### [forward.list] **??.?.?.? Overview** **[forward.list.overview]** :::wording-add … namespace std { template> class forward_list { … using const_iterator = implementation-defined; // see [container.requirements] using node_type = see below; ::: ```cpp // [forward.list.cons], construct/copy/destroy … // [forward.list.modifiers], modifiers … template R> iterator insert_range_after(const_iterator position, R&& rg); node_type extract_after(const_iterator position); iterator insert_after(const_iterator position, node_type&& nh); [DRAFTING NOTE: forward_list provides before_begin to enable removal/insertion at begin.] iterator erase_after(const_iterator position); … }; } ``` 4 An incomplete type `T` may be used when instantiating `forward_list` if the allocator meets the allocator completeness requirements (***[allocator.requirements.completeness]).*** `T` shall be complete before any member of the resulting specialization of `forward_list` is referenced. :::wording-add 5 node_type is a specialization of a node-handle class template ([container.node]), such that the public nested types are the same types as the corresponding types in forward_list. ::: … **??.?.?.? Modifiers** **[forward.list.modifiers]** … 20 *Returns:* An iterator pointing to the last inserted element, or `position` if `rg` is empty. :::wording-add node_type extract_after(const_iterator position); ::: :::wording-add 21 Preconditions: The iterator following position is dereferenceable. ::: :::wording-add 22 Effects: Removes the element pointed to by the iterator following position. ::: :::wording-add 23 Returns: A node_type owning the removed element. ::: :::wording-add 24 Throws: Nothing. ::: :::wording-add 25 Complexity: Constant. ::: :::wording-add iterator insert_after(const_iterator position, node_type&& nh); ::: :::wording-add 26 Preconditions: nh is empty or get_allocator() == nh.get_allocator() is true. ::: :::wording-add 27 Effects: If nh is empty, has no effect and returns end(). Otherwise, inserts the element owned by nh after position and returns an iterator pointing to the newly inserted element. ::: :::wording-add 28 Postconditions: nh is empty, ::: :::wording-add 29 Throws: Nothing. ::: :::wording-add 30 Complexity: Constant. ::: ```cpp iterator insert_after(const_iterator position, initializer_list il); ``` ### [list] ## Acknowledgements **??.?.?.? Overview** **[list.overview]** :::wording-add … namespace std { template> class list { … using const_reverse_iterator = std::reverse_iterator; using node_type = see below; ::: :::wording-add // [list.cons], construct/copy/destroy … // [list.modifiers], modifiers … iterator insert(const_iterator position, initializer_list il); node_type extract(const_iterator position); iterator insert(const_iterator position, node_type&& nh); iterator erase(const_iterator position); … }; } ::: 3 An incomplete type `T` may be used when instantiating `list` if the allocator meets the allocator completeness requirements (***[allocator.requirements.completeness]).*** `T` shall be complete before any member of the resulting specialization of `list` is referenced. :::wording-add 4 node_type is a specialization of a node-handle class template ([container.node]), such that the public nested types are the same types as the corresponding types in list. ::: … **??.?.?.? Modifiers** **[list.modifiers]** :::wording-add … iterator insert(const_iterator position, initializer_list); node_type extract(const_iterator position); ::: :::wording-add 1 Preconditions: position is dereferenceable. ::: :::wording-add 2 Effects: Removes the element pointed to by position. ::: :::wording-add 3 Returns: A node_type owning the removed element. ::: :::wording-add 4 Throws: Nothing. ::: :::wording-add 5 Complexity: Constant. ::: :::wording-add iterator insert(const_iterator position, node_type&& nh); ::: :::wording-add 6 Preconditions: nh is empty or get_allocator() == nh.get_allocator() is true. ::: :::wording-add 7 Effects: If nh is empty, has no effect and returns end(). Otherwise, inserts the element owned by nh before position and returns an iterator pointing to the newly inserted element. ::: :::wording-add 8 Postconditions: nh is empty, ::: :::wording-add 9 Throws: Nothing. ::: :::wording-add 10 Complexity: Constant. ::: ```cpp template reference emplace_front(Args&&... args); ```