This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Resolved status.

### 839. Maps and sets missing splice operation

Section: 24.4 [associative], 24.5 [unord] Status: Resolved Submitter: Alan Talbot Opened: 2008-05-18 Last modified: 2020-09-06

Priority: Not Prioritized

View all other issues in [associative].

View all issues with Resolved status.

Discussion:

Splice is a very useful feature of `list`. This functionality is also very useful for any other node based container, and I frequently wish it were available for maps and sets. It seems like an omission that these containers lack this capability. Although the complexity for a splice is the same as for an insert, the actual time can be much less since the objects need not be reallocated and copied. When the element objects are heavy and the compare operations are fast (say a `map<int, huge_thingy>`) this can be a big win.

Suggested resolution:

Add the following signatures to map, set, multimap, multiset, and the unordered associative containers:

>     void splice(list<T,Allocator>&& x);
>     void splice(list<T,Allocator>&& x, const_iterator i);
>     void splice(list<T,Allocator>&& x, const_iterator first, const_iterator last);

Hint versions of these are also useful to the extent hint is useful. (I'm looking for guidance about whether hints are in fact useful.)

>     void splice(const_iterator position, list<T,Allocator>&& x);
>     void splice(const_iterator position, list<T,Allocator>&& x, const_iterator i);
>     void splice(const_iterator position, list<T,Allocator>&& x, const_iterator first, const_iterator last);

[ Sophia Antipolis: ]

> Don't try to `splice "list"` into the other containers, it should be container-type.

> `forward_list` already has `splice_after`.

> Would "`splice`" make sense for an `unordered_map`?

> Jens, Robert: "`splice`" is not the right term, it implies maintaining ordering in `list`s.

> Howard: `adopt`?

> Jens: `absorb`?

> Alan: `subsume`?

> Robert: `recycle`?

> Howard: `transfer`? (but no direction)

> Jens: `transfer_from`. No.

> Alisdair: Can we give a nothrow guarantee? If your `compare()` and `hash()` doesn't throw, yes.

> Daniel: For `unordered_map`, we can't guarantee nothrow.

[ San Francisco: ]

> Martin: this would possibly outlaw an implementation technique that is currently in use; caching nodes in containers.

> Alan: if you cache in the allocator, rather than the individual container, this proposal doesn't interfere with that.

> Martin: I'm not opposed to this, but I'd like to see an implementation that demonstrates that it works.

[ 2009-07 Frankfurt: ]

> NAD Future.

[ 2009-09-19 Howard adds: ]

> I'm not disagreeing with the NAD Future resolution. But when the future gets here, here is a possibility worth exploring:

> > Add to the "unique" associative containers:

> > >     typedef details      node_ptr;

> > >     node_ptr             remove(const_iterator p);
> > >     pair<iterator, bool> insert(node_ptr&& nd);
> > >     iterator             insert(const_iterator p, node_ptr&& nd);

> > And add to the "multi" associative containers:

> > >     typedef details node_ptr;

> > >     node_ptr remove(const_iterator p);
> > >     iterator insert(node_ptr&& nd);
> > >     iterator insert(const_iterator p, node_ptr&& nd);

> > `Container::node_ptr` is a smart pointer much like `unique_ptr`. It owns a node obtained from the container it was removed from. It maintains a reference to the allocator in the container so that it can properly deallocate the node if asked to, even if the allocator is stateful. This being said, the `node_ptr` can not outlive the container for this reason.

> > The `node_ptr` offers "`const`-free" access to the node's `value_type`.

> > With this interface, clients have a great deal of flexibility:

> > - A client can remove a node from one container, and insert it into another (without any heap allocation). This is the splice functionality this issue asks for.
> > - A client can remove a node from a container, change its key or value, and insert it back into the same container, or another container, all without the cost of allocating a node.
> > - If the Compare function is nothrow (which is very common), then this functionality is nothrow unless modifying the value throws. And if this does throw, it does so outside of the containers involved.
> > - If the Compare function does throw, the `insert` function will have the argument `nd` retain ownership of the node.
> > - The `node_ptr` should be independent of the `Compare` parameter so that a node can be transferred from `set<T, C1, A>` to `set<T, C2, A>` (for example).

> > Here is how the customer might use this functionality:

> > - Splice a node from one container to another:

> >   >     m2.insert(m1.remove(i));

> > - Change the "key" in a `std::map` without the cost of node reallocation:

> >   >     auto p = m.remove(i);
> >   >     p->first = new_key;
> >   >     m.insert(std::move(p));

> > - Change the "value" in a `std::set` without the cost of node reallocation:

> >   >     auto p = s.remove(i);
> >   >     *p = new_value;
> >   >     s.insert(std::move(p));

> > - Move a move-only or heavy object out of an associative container (as opposed to the proposal in 1041):

> >   >     MoveOnly x = std::move(*s.remove(i));

> >   1. `remove(i)` transfers ownership of the node from the set to a temporary `node_ptr`.
> >   2. The `node_ptr` is dereferenced, and that non-const reference is sent to `move` to cast it to an rvalue.
> >   3. The rvalue `MoveOnly` is move constructed into `x` from the `node_ptr`.
> >   4. `~node_ptr()` destructs the moved-from `MoveOnly` and deallocates the node.

> >   Contrast this with the 1041 solution:

> >   >     MoveOnly x = std::move(s.extract(i).first);

> >   The former requires one move construction for `x` while the latter requires two (one into the `pair` and then one into `x`). Either of these constructions can throw (say if there is only a copy constructor for `x`). With the former, the point of throw is outside of the container `s`, after the element has been removed from the container. With the latter, one throwing construction takes place prior to the removal of the element, and the second takes place after the element is removed.

> > The "node insertion" API maintains the API associated with inserting `value_type`s so the customer can use familiar techniques for getting an iterator to the inserted node, or finding out whether it was inserted or not for the "unique" containers.

> > Lightly prototyped. No implementation problems. Appears to work great for the client.

[08-2016, Post-Chicago]

Move to Tentatively Resolved

Proposed resolution:

This functionality is provided by P0083R3