ISO/IEC JTC1 SC22 WG21 N4006

Date: 2014-05-26

Thomas Köppe <tkoeppe@google.com>

An improved emplace() for unique-key maps

Contents

  1. Motivation
  2. Impact on the standard
  3. Design Decisions
  4. Proposed wording
  5. Notes
  6. Criticism
  7. Acknowledgements

Motivation

A new problem has surfaced with the existing interface of unique-keyed map containers (std::map, std::unordered_map) when those containers are used with movable types. The following snippet is representative:

std::map<std::string, std::unique_ptr<Foo>> m; m["foo"] = nullptr; std::unique_ptr<Foo> p(new Foo); auto res = m.emplace("foo", std::move(p)); assert(p);    // ???

What is the value of p? It is currently unspecified whether p has been moved-from. It would certainly be desirable to have deterministic, standardised semantics for this operation. For example, a user may wish to attempt adding a given unique pointer to a number of containers until an insertion succeeds; having the object destroyed by a failed insertion seems surprising and rarely helpful.

The author had initially proposed in N3873 to add new specialised algorithms to unique-key maps, emplace_stable and emplace_or_update, which would make the appropriate guarantees, and which would be able to do so by virtue of separate key and mapped element parameters, as opposed to the variadic parameters of emplace that are passed through to a pair constructor. When that paper was presented in Issaquah in February 2014, Jeffrey Yasskin created LWG 2362 to track the core problem, namely the lack of specification of whether moving-from happens. At the meeting, there seems to have been a strong consensus that emplace should “just work”, but that no progress could be made until a concrete proposal had been worked out. At the same time, new algorithms should not be added, and a fixed emplace would provide the desired functionality. It was also recognized that fixing emplace would not be trivial and that there would need to be a way to extract the key from the arguments.

Impact on the standard

This is purely modification of the standard library, specifically to the headers of std::map [map.overview] and std::unordered_map [unord.map.overview]. The containers continue to meet their respective container requirements.

Design Decisions

Recall the current signature of emplace inside a map<K, T> or unordered_map<K, T>:

template <typename ...Args> pair<iterator, bool> emplace(Args &&... args);

Also recall the container requirements [associative.reqmts, unord.req]:

Effects: 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.

This implies that the fundamental requirement is that the following construction is valid:

value_type(std::forward<Args>(args)...)    // std::pair<const K, T>(std::forward<Args>(args)...)

The only value_type constructors that can possibly be used are the pair constructors [pairs.pair], which are:

  1. pair(const pair &)
  2. pair(pair &&)
  3. pair(const T1 &, const T2 &)
  4. template <typename U, typename V> pair(U &&, V &&)
  5. template <typename U, typename V> pair(const pair<U, V> &)
  6. template <typename U, typename V> pair(pair<U, V> &&)
  7. template <typename ...Args1, typename ...Args2> pair(piecewise_construct_t, tuple<Args1...>, tuple<Args2...>)

Constructors 4, 5 and 6 only participate in overload resolution if U and V are implicitly convertible to T1 and T2, respectively (but see N3680 for an open issue).

Observe that only constructor calls with one, two or three arguments can possibly be valid. It is therefore feasible to replace the single, variadic function template for emplace by three separate overloads with respectively one, two and three parameters. We propose to augment two of these three overloads with an appropriate non-construction guarantee.

Proposed wording

From [map.overview] and [unord.map.overview], remove the lines:

template <class... Args> pair<iterator, bool> emplace(Args&&... args); template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);

Instead, add the following:

template <class W> pair<iterator, bool> emplace(W&& w); template <class U, class V> pair<iterator, bool> emplace(U&& u, V&& v); template <class U, class V> pair<iterator, bool> emplace(piecewise_construct_t, U&& u, V&& v); template <class W> iterator emplace_hint(const_iterator position, W&& w); template <class U, class V> iterator emplace_hint(const_iterator position, U&& u, V&& v); template <class U, class V> iterator emplace_hint(const_iterator position, piecewise_construct_t, U&& u, V&& v);

Furthermore, add the following to [map.modifiers] and [unord.map.modifiers]:

template <class U, class V> pair<iterator, bool> emplace(U&& u, V&& v); template <class U, class V> pair<iterator, bool> emplace(piecewise_construct_t, U&& u, V&& v);

Effects: If the key equivalent to the provided key already exists, does nothing. In the first form, the provided key is u if u is a reference to key_type, and key_type(std::forward<U>(u)) otherwise. In the second form, u and v shall be references to tuples, and the provided key is a key_type object constructed from the forwarded tuple elements. It is unspecified whether a temporary key_type is actually constructed.

Remarks: No mapped element is constructed if the key already exists. In particular, even if the mapped element comes from an rvalue reference argument, the argument will not be moved-from.

Notes

We only provide non-construction guarantees for those overloads where the key is explicitly visible. The one-parameter overload allows for arguments which have conversions to pairs, and a non-construction guarantee cannot be given in general. (For instance, if the conversion of w to value_type produces a temporary, it may not be possible to obtain the key without constructing the temporary.)

It is also not whether a key object must be constructed in the other cases. In the two-parameter overload, it seems sufficient that u is a reference to a key_type to not require a temporary, but even if u has a different type, a transparent comparator may still be able to perform the key look-up without requiring an actual key object. (This applies only to the ordered map. For the unordered map, there are no “transparent hash functors”, and thus a key object must always be available.) The three-parameter overload may not require a key object construction if the second argument has a type like tuple<key_type &>.

In light of these difficulties, we chose to simply leave it unspecified whether a temporary key object is constructed. It seems less important to specify this for keys than it does for mapped elements. An alternative would be to add further, explicit overloads with first parameter const key_type & (mimicking the pair constructors), but this seems unnecessary.

Criticism

The author’s main argument in N3873 against fixing emplace and rather introduce new member functions is still pertinent and worth bearing in mind:

If emplace is fixed to behave in a well-defined fashion with regard to moving from its arguments if the key already exists, this fix is unobservable. From within the language, a user cannot tell whether her platform conforms to the fixed semantics. When moving to a different platform that is lacking the fix, the code would continue to compile, but silently behave differently. This is surprising, hard to catch, and against the spirit of providing clean transition paths. Conversely, a user eager to rely on this fix would find himself hard-pressed to guarantee that it will work as intended on all deployed platforms. (One could take this to a pathological extreme and have a conforming C++11 implementation randomly either move-from or not, so that any unit test designed to catch this would be flaky. This is contrived, but hopefully illustrates the potential reluctance to rely on this fix.)

The author considers this argument to bear considerable weight. A technical solution to the transitioning problem could be to define another preprocessor macro such as STD_EMPLACE_DOES_NOT_MOVE, but that seems gratuitous. On the other hand, a new set of functions with new names sidesteps this problem and makes it immediately obvious whether this new feature is available, and it also avoids the different treatment of the various overloads of emplace that we are forced to include in the present proposal.

Acknowledgements

Many thanks once again to Geoffrey Romer, Jeffrey Yasskin and Stuart Taylor for providing invaluable feedback and discussion.