Issue 2772: Inconsistency in the insert(node) interface

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

2772. Inconsistency in the `insert(node)` interface

Section: 23.2.7 [associative.reqmts], 23.2.8 [unord.req], 23.4.2 [associative.map.syn], 23.5.2 [unord.map.syn] Status: NAD Submitter: Tomasz Kamiński Opened: 2016-09-06 Last modified: 2018-01-28

Priority: 2

View other active issues in [associative.reqmts].

View all other issues in [associative.reqmts].

View all issues with NAD status.

Discussion:

In C++17 the interface of the unique map was extended to include following function:

pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); //and move version
iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); //and move version
iterator insert(const_iterator hint, node_type&& nh)
insert_return_type insert(node_type&& nh);

All of the functions share a common property, that they are performing basically no-operation in case when element with given key (part of node) is already stored in the map. However there is major difference in their interface. The first three functions:

pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); //and copy version
iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); //and copy version
iterator insert(const_iterator hint, node_type&& nh)

are guaranteeing that the value of the arguments (k, nh, args...) will not be changed if the map already contains a key with given value, so the programmer is free to reuse it for their own purpose.

However, the interface of the fourth function is a bit different:

insert_return_type insert(node_type&& nh);

The insert_return_type is an unspecified type that contains:

bool inserted;
X::iterator position;
X::node_type node;

As we can see, the insert function is returning a node. This difference is actually misleading, as the programmer may start to wonder, why the function returns a node handle, instead of being guaranteed that the argument will not be modified (as other functions do). Most reasonable explanation is that, this function actually return a handle to a different node, that one passed as the argument, i.e. this function replaces an existing node with the nh argument and returns the handle to the old node. However, this function actually has the same semantics as the other insert function and returns a node that was passed as argument.

In addition, this design makes the interface of the insert function for the map inconsistent. Value inserting functions are returning pair<iterator, bool> while node inserting function is returning an unspecified type with guaranteed set of members.

The only potential benefit of this signature is that it could potentially allow programmer to use decomposition declaration, so instead of:

auto nh = node_provider();
if (map.insert(std::move(nh)).second)
  handle_node_in_other_way(std::move(nh));

The user would be able to write:

if (auto [it, ins, nh] = map.insert(node_provider); ins)
   handle_node_in_other_way(std::move(nh));

However, the insert_return_type is not currently required to work with decomposition declaration, so this is only "potential" benefit that could be added in future.

Furthermore, this change is preventing a user to use structured binding with combination with insert in generic code:

template<typename UniqMap, typename Elem>
void log_duplicate_insertion(UniqMap& map, Elem&& elem)
{
  if (auto [it, ins] = map.insert(std::forward<Elem>(elem)); !ins)
    std::cout << "attempt to insert duplicate for " << *it;
}

Currently, log_duplicate_insertion will not work with node_handle_type.

So, I am proposing to change the interface of the insert(node_handle) function for associative containers with unique keys, to be consistent with the other insert operation and try_emplace function. I.e. change the signature to:

std::pair<iterator, bool> insert(node_type&& nh);

and provide the guarantee that nh will be unchanged if an element was not inserted.

[2016-09-06, Howard comments]

This is related to LWG 839⁽ⁱ⁾.

[2018-1-26 issues processing telecon]

Status to 'NAD'; this is "specified as designed". This was considered during the design, but not accepted.

Proposed resolution:

2772. Inconsistency in the insert(node) interface

2772. Inconsistency in the `insert(node)` interface