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:
To each of the unique-keyed map container templates std::map and
std::unordered_map, we propose to add the following new, specialised
algorithms:
try_emplace(): if the key already exists, does not
insert anything and does not modify the arguments.insert_or_assign(): inserts the mapped element or
assigns it to the current element if the key already exists.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:
try_emplace does not steal from the arguments if the insertion does not
happen, unlike insert
or emplace. Using insert or emplace, the user would
have to perform a separate find call to prevent stealing from the argument.
As the motivating code snippet demonstrates, it might not even show as an error if the user
forgot to do this and wrote erroneous code.insert_or_assign returns more information than operator[] and does
not require
default-constructibility of the mapped type. To achieve the same result with the current interface,
one would need find, followed by a separate insertion if the
key did not already exist.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.
This is purely an extension of the standard library. Four new function templates have to be added to [map.special], and also to a new section “specialised algorithms” [unord.maps.special] for unordered maps. There is no interference with existing code.
Add the following to [maps.special], and to a new subsection under [unord.maps], named
“unordered_map specialised algorithms [unord.maps.special]”:
Effects: If the key k already exists in the map, there is no effect, no
dynamic allocations are performed and no exceptions are thrown. Otherwise, inserts the element
constructed from the arguments as value_type(k, forward<Args>(args)...) into
the map. The bool part of the return value is true if and only if the insertion
took place, and the iterator part points to the element of the map whose key
is equivalent to k. The hint iterator provides an insertion hint.
Complexity: The same as emplace and emplace_hint,
respectively.
Effects. If the key comparing equal to k does not exist in the map,
inserts the element constructed as value_type(k, forward<M>(obj)).
If the key already exists, the mapped part of the value is assigned forward<M>(obj).
The bool part of the return value is true if and only if the insertion took place,
and the iterator part points to the inserted or updated
element. The hint iterator provides an insertion hint.
Complexity: The same as emplace and emplace_hint,
respectively.
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 there were also questions as to whether there should be overloads in which the key parameter is taken by mutable (rvalue) reference. This was deemed a less common use case so that we are not pursuing it here, but the proposed design is amenable to future extensions should a desire for further generality arise. This also includes considerations like templated key parameters and support for transparent comparators; transparent comparators are currently only considered for look-up functions, not for mutators.
Questions in poll form.
try_emplace(const key_type &, Args &&...) rather than
the originally proposed try_emplace(const key_type &, M &&).
emplace_or_assign to insert_or_assign is appropriate.const key_type &
suffices for now.