ISO/IEC JTC1 SC22 WG21 N4279

Date: 2014-11-07

Thomas Köppe <tkoeppe@google.com>

Improved insertion interface for unique-key maps (Revision 2.3)

Revision history

Contents

  1. Background
  2. Summary
  3. Impact on the standard
  4. Technical specifications
  5. Notes
  6. Questions for the WG

Background

The existing interface of unique-keyed map containers (std::map, std::unordered_map) is slightly underspecified, which makes certain container mutations more complicated to write and error-prone than necessary. This paper describes new member function templates to fill this gap.

The justification and rationale for the new interface are given in N3873. The initial reaction to N3873 in Issaquah was that the existing map interfaces should be fixed rather than adding new interfaces. We explored this idea in N4006 in Rapperswil and decided that the original proposal was preferable (with some name changes). This paper only summarises the proposed extension without repeating the original discussion. We only restate the motivating code snippet here for motivation:

std::map<std::string, std::unique_ptr<Foo>> m; m["foo"] = nullptr; auto ptr = std::make_unique_ptr<Foo>; auto res = m.emplace("foo", std::move(ptr)); assert(ptr);    // ??? (may or may not fire)

Summary

To each of the unique-keyed map container templates std::map and std::unordered_map, we propose to add the following new, specialised algorithms:

The utility of these two algorithms lies in the fact that they make mutations possible that would be verbose to spell out, error-prone, surprising and hard to teach with the existing interface. Moreover, the algorithms can perform their actions as efficiently as possible, since they are able to take advantage of the internal structure of the container, thus filling a gap where users might previously have felt that they “could do it better by hand”. Briefly:

Finally, since both new algorithms separate parameters into key and mapped type components, they are somewhat more intuitive than the generic container mutators that are expressed in terms of value_type (which is a std::pair). This point is often confusing or annoying to users and hard to teach.

Impact on the standard

This is purely an extension of the standard library. Eight new function templates have to be added to [map.modifiers] and to [unord.maps.modifiers]. There is no interference with existing code.

Technical specifications

Add the following to [maps.modifiers] and to [unord.maps.modifiers]:

template <class... Args> pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); template <class... Args> pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); template <class... Args> iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); template <class... Args> iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);

Effects: If the key k already exists in the map, there is no effect. Otherwise, inserts an element into the map. In the first and third forms, the element is constructed from the arguments as value_type(k, std::forward<Args>(args)...). In the second and fourth forms, the element is constructed from the arguments as value_type(std::move(k), std::forward<Args>(args)...). In the first two overloads, the bool component of the returned pair is true if and only if the insertion took place. The returned iterator points to the element of the map whose key is equivalent to k.

Complexity: The same as emplace and emplace_hint, respectively.

template <class M> pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); template <class M> pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); template <class M> iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); template <class M> iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);

Effects: If the key k does not exist in the map, inserts an element into the map. In the first and third forms, the element is constructed from the arguments as value_type(k, std::forward<Args>(args)...). In the second and fourth forms, the element is constructed from the arguments as value_type(std::move(k), std::forward<Args>(args)...). If the key already exists, std::forward<M>(obj) is assigned to the mapped_type corresponding to the key. In the first two overloads, the bool component of the returned value is true if and only if the insertion took place. The returned iterator points to the element that was inserted or updated.

Complexity: The same as emplace and emplace_hint, respectively.

Also add the function declarations to the synopses. In [map.overview]/2, add:

// 23.4.4.4, modifiers [...] template <class... Args> pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); template <class... Args> pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); template <class... Args> iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); template <class... Args> iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); template <class M> pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); template <class M> pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); template <class M> iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); template <class M> iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);

Similarly, add to [unord.map.overview]/3:

// modifiers [...] template <class... Args> pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); template <class... Args> pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); template <class... Args> iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); template <class... Args> iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); template <class M> pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); template <class M> pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); template <class M> iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); template <class M> iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);

Notes

The original names in N3873 were “emplace_stable” and “emplace_or_update”, and both took only a single second parameter M && obj. In Rapperswil, the names try_emplace and emplace_or_assign were proposed, and the question arose whether the signatures could be variadic.

Making try_emplace variadic seems to pose no further obstacle, and this is how it appears in this paper. As for emplace_or_assign, we agreed that a variadic signature would not fit well with assignment (we never have variadic assignment operations in the standard), so we retained the single-parameter form here. However, with a single argument the function feels less like an “emplace” and more like an “insert”, which is why we are tentatively proposing the name insert_or_update here. Naturally, this is up to debate.

In Rapperswil and subsequent discussions it was also suggested to include overloads in which the key parameter is taken by mutable rvalue reference. These overloads were added in revision v2.1, which was presented to LEWG, for the reason that without them, the new interface would be worse than the existing insert/emplace interface in certain cases.

We are not considering templated key parameters and support for transparent comparators; transparent comparators are currently only considered for look-up functions, not for mutators.

Questions for the WG

Questions in poll form.