Issue 1302: different emplace semantics for sequence and associated containers

1302. different `emplace` semantics for sequence and associated containers

Section: 23.2.7 [associative.reqmts], 23.2.8 [unord.req] Status: NAD Submitter: Nicolai Josuttis Opened: 2010-01-03 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [associative.reqmts].

View all other issues in [associative.reqmts].

View all issues with NAD status.

Discussion:

According to the new naming scheme introduced with N2680

vector<T> v;
v.emplace(v.begin(),x,y,z)

now has a different semantics than

set<T> s;
s.emplace(s.begin(),x,y,z);

While the version for vectors takes the first argument as position and the remaining for construction, the version for sets takes all arguments for construction.

IMO, this is a serious design mistake for a couple of reasons:

First, in principle, all STL member functions should have the same behavior with the same member function to avoid confusion and allow to write proper generic code.

In fact, when I write the following simple function template:
```
template <typename T>
void doEmplace (T& cont)
{
   cont.emplace(cont.begin(),"nico","josuttis",42);
}
```
the semantics depends on the type of the container.
In addition, I also guess using the name emplace_hint() instead of emplace() for associative containers is a design mistake. According to my knowledge, it was a design goal of the original STL to provide ONE insert function, which works for ALL containers. This was insert(pos,val).

The trick to declare pos as a hint, allowed that we could implement a generic insert for all containers. Now, with the new emplace naming scheme, this trick is gone for the new kind of insertion.

I consider this to be a serious design penalty because once this is specified we can't fix that without breaking backward compatibility.

However, we have two choices for a fix:

rename emplace_hint(pos,val) for associative containers back to emplace(pos,val). However to avoid the overloading problems, we also have to rename the existing emplace(val) functions to something else (I don't have a good name here at hand).
Keep emplace(val) for associative containers as it is, but rename emplace(pos,val) for sequence containers and emplace_hint(pos,val) to something like emplace_at(pos,val), declaring that pos is a hint for associative containers.

[ 2010 Pittsburgh: Moved to NAD, rationale added below. ]

Rationale:

There was no consensus to make this change.

Proposed resolution:

In 23.2.8 [unord.req], change:

Table 96 — Associative container requirements (in addition to container)
expression Return type Assertion/note pre-/post-condition Post-condition

...

a_uniq.emplace_value(args) pair<iterator, bool> inserts a T object t constructed with std::forward<Args>(args)...
if and only if there is no element in the container with key equivalent to the key of t.
The bool component of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t. logarithmic

a_eq.emplace_value(args) iterator inserts a T object t constructed with std::forward<Args>(args)... and returns the iterator pointing to the newly inserted element. logarithmic

a.emplace_hint(p,args) iterator equivalent to a.emplace_value(std::forward<Args>(args)...). Return value is an iterator pointing to the element with the key equivalent to the newly inserted element. The const_iterator p is a hint pointing to where the search should start. Implementations are permitted to ignore the hint. logarithmic in general, but amortized constant if the element is inserted right after p

...

Table 96 — Associative container requirements (in addition to container)
expression	Return type	Assertion/note pre-/post-condition	Post-condition
...
`a_uniq.emplace_value(args)`	`pair<iterator, bool>`	inserts a T object t constructed with std::forward<Args>(args)... if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t.	logarithmic
`a_eq.emplace_value(args)`	`iterator`	inserts a T object t constructed with std::forward<Args>(args)... and returns the iterator pointing to the newly inserted element.	logarithmic
`a.emplace_hint(p,args)`	`iterator`	equivalent to `a.emplace_value(std::forward<Args>(args)...)`. Return value is an iterator pointing to the element with the key equivalent to the newly inserted element. The const_iterator p is a hint pointing to where the search should start. Implementations are permitted to ignore the hint.	logarithmic in general, but amortized constant if the element is inserted right after p
...

In 23.2.8 [unord.req], change:

Table 98 — Unordered associative container requirements (in addition to container)
expression Return type Assertion/note pre-/post-condition Post-condition

...

a_uniq.emplace_value(args) pair<iterator, bool> inserts a T object t constructed with std::forward<Args>(args)... if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t. Average case O(1), worst case O(a_uniq.size()).

a_eq.emplace_value(args) iterator inserts a T object t constructed with std::forward<Args>(args)... and returns the iterator pointing to the newly inserted element. Average case O(1), worst case O(a_eq.size()).

a.emplace_hint(p,args) iterator equivalent to a.emplace_value(std::forward<Args>(args)...). Return value is an iterator pointing to the element with the key equivalent to the newly inserted element. The const_iterator p is a hint pointing to where the search should start. Implementations are permitted to ignore the hint. Average case O(1), worst case O(a.size()).

...

Table 98 — Unordered associative container requirements (in addition to container)
expression	Return type	Assertion/note pre-/post-condition	Post-condition
...
`a_uniq.emplace_value(args)`	`pair<iterator, bool>`	inserts a `T` object `t` constructed with `std::forward<Args>(args)...` if and only if there is no element in the container with key equivalent to the key of `t`. The bool component of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t.	Average case O(1), worst case O(a_uniq.size()).
`a_eq.emplace_value(args)`	`iterator`	inserts a T object t constructed with std::forward<Args>(args)... and returns the iterator pointing to the newly inserted element.	Average case O(1), worst case O(a_eq.size()).
`a.emplace_hint(p,args)`	`iterator`	equivalent to `a.emplace_value(std::forward<Args>(args)...)`. Return value is an iterator pointing to the element with the key equivalent to the newly inserted element. The const_iterator p is a hint pointing to where the search should start. Implementations are permitted to ignore the hint.	Average case O(1), worst case O(a.size()).
...

In 23.4.3 [map], 23.4.6 [set], 23.5.3 [unord.map], 23.5.6 [unord.set], change:

// modifiers:
template <class... Args> pair<iterator, bool> emplace_value(Args&&... args); template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);

In 23.4.4 [multimap], 23.4.7 [multiset], 23.5.4 [unord.multimap], 23.5.7 [unord.multiset], change:

// modifiers:
template <class... Args> iterator emplace_value(Args&&... args); template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);

1302. different emplace semantics for sequence and associated containers

1302. different `emplace` semantics for sequence and associated containers