839. Maps and sets missing splice operation

Section: 23.4 [associative], 23.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 lists.

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_types 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