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.
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 hassplice_after
.Would "
splice
" make sense for anunordered_map
?Jens, Robert: "
splice
" is not the right term, it implies maintaining ordering inlist
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()
andhash()
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 likeunique_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, thenode_ptr
can not outlive the container for this reason.The
node_ptr
offers "const
-free" access to the node'svalue_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 argumentnd
retain ownership of the node.- The
node_ptr
should be independent of theCompare
parameter so that a node can be transferred fromset<T, C1, A>
toset<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(i)):
MoveOnly x = std::move(*s.remove(i));
remove(i)
transfers ownership of the node from the set to a temporarynode_ptr
.- The
node_ptr
is dereferenced, and that non-const reference is sent tomove
to cast it to an rvalue.- The rvalue
MoveOnly
is move constructed intox
from thenode_ptr
.~node_ptr()
destructs the moved-fromMoveOnly
and deallocates the node.Contrast this with the 1041(i) solution:
MoveOnly x = std::move(s.extract(i).first);The former requires one move construction for
x
while the latter requires two (one into thepair
and then one intox
). Either of these constructions can throw (say if there is only a copy constructor forx
). With the former, the point of throw is outside of the containers
, 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