839. Maps and sets missing splice operation

Section: 26.4 [associative], 26.5 [unord] Status: Resolved Submitter: Alan Talbot Opened: 2008-05-18 Last modified: 2017-03-13

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:

Here is how the customer might use this functionality:

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