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

Section: 23.2.7 [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 23.2.7 [associative.reqmts], paragraph 8, it is specified that that insert does not invalidate any iterators. As per 23.2.2 [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 23.2.7 [associative.reqmts], par. 8, since both modify the container. For the sake of consistency, in 23.2.7 [associative.reqmts], par. 8: either reference to insert should be removed (i.e. count on 23.2.2 [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 23.2.8 [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 23.2.2 [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:

  2. Modify 23.2.7 [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 23.2.7 [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 23.2.7 [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 23.2.7.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 23.2.8 [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 23.2.8.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.