2356. Stability of erasure in unordered associative containers

Section: 23.2.8 [unord.req] Status: C++14 Submitter: Joaquín M López Muñoz Opened: 2014-01-21 Last modified: 2016-01-28

Priority: 2

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with C++14 status.

Discussion:

Issue 518 resolution for unordered associative containers, modelled after that of issue 371, which is related to associative containers, states that insertion, erasure and rehashing preserve the relative ordering of equivalent elements. Unfortunately, this is not sufficient to guarantee the validity of code such as this:

std::unordered_multimap<int, int> m;
auto i = m.begin();
while (i != m.end()) {
  if (pred(i))
    m.erase(i++);
  else
    ++i;
}

(which is a direct translation from multimap to unordered_multimap of the motivating example in 371), or even this:

std::unordered_multimap<int, int> m;
auto p = m.equal_range(k);
while (p.first != p.second) {
  if (pred(p.first))
    m.erase((p.first)++);
  else
    ++(p.first);
}

because the relative ordering of non-equivalent elements elements could potentially change after erasure (not that any actual implementation does that, anyway). Such an underspecification does not happen for regular associative containers, where the relative ordering of non-equivalent elements is kept by design.

[2014-02-13 Issaquah: Move to Immediate]

Proposed resolution:

This wording is relative to N3797.

1. Modify 23.2.8 [unord.req], p14 as indicated:

   -14- 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, and preserve the relative order of the elements that are not erased.