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

### 1253. invalidation of iterators and `emplace` vs. `insert` inconsistence in assoc. containers

Section: 22.2.6 [associative.reqmts] Status: C++11 Submitter: Boris Dušek Opened: 2009-10-24 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 C++11 status.

Discussion:

In the latest published draft N2960, section 22.2.6 [associative.reqmts], paragraph 8, it is specified that that `insert` does not invalidate any iterators. As per 22.2.1 [container.requirements.general], paragraph 12, this holds true not only for `insert`, but `emplace` as well. This gives the `insert` member a special treatment w.r.t. `emplace` member in 22.2.6 [associative.reqmts], par. 8, since both modify the container. For the sake of consistency, in 22.2.6 [associative.reqmts], par. 8: either reference to `insert` should be removed (i.e. count on 22.2.1 [container.requirements.general], par. 12), or reference to `emplace` be added (i.e. mention all members of assoc. containers that modify it).

[ 2009-11-18 Chris provided wording. ]

> This suggested wording covers both the issue discussed, and a number of other identical issues (namely `insert` being discussed without `emplace`). I'm happy to go back and split and introduce a new issue if appropriate, but I think the changes are fairly mechanical and obvious.

[ 2010-01-23 Daniel Krügler and J. Daniel García updated wording to make the use of `hint` consistent with `insert`. ]

[ 2011-02-23 Daniel Krügler adapts wording to numbering changes to match the N3225 draft. During this action it was found that 22.2.7 [unord.req] had been changed considerably due to acceptance of N3068 during the Pittsburgh meeting, such that the suggested wording change to p. 6 can no longer be applied. The new wording is more general and should now include `insert()` and `emplace()` calls as well ("mutating operations"). ]

[2011-03-06 Daniel Krügler adapts wording to numbering changes to match the N3242 draft]

Proposed resolution:

1. Modify bullet 1 of 22.2.1 [container.requirements.general], p. 10:

   10 Unless otherwise specified (see [associative.reqmts.except], [unord.req.except], [deque.modifiers], and [vector.modifiers]) all container types defined in this Clause meet the following additional requirements:

   - if an exception is thrown by an `insert()` or `emplace()` function while inserting a single element, that function has no effects.
   - ...

2. Modify 22.2.6 [associative.reqmts], p. 4:

   > 4 An associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys. The `set` and `map` classes support unique keys; the `multiset` and `multimap` classes support equivalent keys. For `multiset` and `multimap`, `insert`, `emplace`, and `erase` preserve the relative ordering of equivalent elements.

3. Modify Table 102 — Associative container requirements in 22.2.6 [associative.reqmts]:

   > Table 102 — Associative container requirements (in addition to container)
   > Expression | Return type | Assertion/note pre-/post-condition | Complexity
   > --- | --- | --- | ---
   > […]
   > `a_eq.emplace(args)` | `iterator` | […] Effects: Inserts a `T` object `t` constructed with `std::forward<Args>(args)...` and returns the iterator pointing to the newly inserted element. If a range containing elements equivalent to `t` exists in `a_eq`, `t` is inserted at the end of that range. | logarithmic
   > `a.emplace_hint(p, args)` | `iterator` | equivalent to `a.emplace(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. The element is inserted as close as possible to the position just prior to `p`. Implementations are permitted to ignore the hint. | logarithmic in general, but amortized constant if the element is inserted right after before `p`
   > […]

4. Modify 22.2.6 [associative.reqmts], p. 9:

   > 9 The `insert` and `emplace` members shall not affect the validity of iterators and references to the container, and the `erase` members shall invalidate only iterators and references to the erased elements.

5. Modify 22.2.6.2 [associative.reqmts.except], p. 2:

   > 2 For associative containers, if an exception is thrown by any operation from within an `insert()` or `emplace()` function inserting a single element, the `insert()` function insertion has no effect.

6. Modify 22.2.7 [unord.req], p. 13 and p. 14:

   > 6 An unordered associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys. `unordered_set` and `unordered_map` support unique keys. `unordered_multiset` and `unordered_multimap` support equivalent keys. In containers that support equivalent keys, elements with equivalent keys are adjacent to each other in the iteration order of the container. Thus, although the absolute order of elements in an unordered container is not specified, its elements are grouped into equivalent-key groups such that all elements of each group have equivalent keys. Mutating operations on unordered containers shall preserve the relative order of elements within each equivalent-key group unless otherwise specified.

   > […]

   > 13 The `insert` and `emplace` members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. The erase members shall invalidate only iterators and references to the erased elements.

   > 14 The `insert` and `emplace` members shall not affect the validity of iterators if `(N+n) < z * B`, where `N` is the number of elements in the container prior to the insert operation, `n` is the number of elements inserted, `B` is the container's bucket count, and `z` is the container's maximum load factor.

7. Modify 22.2.7.2 [unord.req.except], p. 2:

   > 2 For unordered associative containers, if an exception is thrown by any operation other than the container's hash function from within an `insert()` or `emplace()` function inserting a single element, the `insert()` insertion function has no effect.