Merging an (unordered) associative container with itself
Joaquín M López Muñoz

Created on 2021-08-04.00:00:00 last changed 1 month ago


Date: 2021-08-15.00:00:00

[ 2021-08-20; Reflector poll ]

Set priority to 3 after reflector poll. Tim Song commented: "I think the current PR of LWG bans this code, but we might want to have consistency with list::merge instead."

Date: 2021-08-08.11:34:27

For the expression a.merge(a2), it is not explicitly stated whether a2 can be the same object as a. libstdc++-v3 and libc++ seemingly assume this is not allowed, as the following code produces an infinite loop with both standard library implementations:

#include <set>

int main()
  std::multiset<int> c={0, 0};

A strict reading of postconditions seems to ban the case where a and a2 are the same:

  • [associative.reqmts.general]: "Iterators referring to the transferred elements […] now behave as iterators into a, not into a2": if a and a2 are the same, a transferred iterator can't be both an iterator to a and not an iterator to a2.

  • [unord.req.general]: "Iterators referring to the transferred elements and all iterators referring to a will be invalidated, but iterators to elements remaining in a2 will remain valid": if a and a2 are the same, an iterator can't both be invalidated and remain valid.

Even if a provision is made that, when a and a2 are the same, no elements are transferred by convention, [unord.req.general] would still implicitly ban the case, as all iterators would be invalidated but the iterators to the remaining elements (again, all iterators) would remain valid, which is contradictory.

For context, analogous operations for std::list take inconsistent approaches:

  • splice(const_iterator position, list& x) requires that source and destination be not the same.

  • splice(const_iterator position, list& x, const_iterator i) implicitly allows addressof(x) == this, as the case position == i is taken care of.

  • std::list::merge explicitly allows the case addressof(x) == this (resulting in a no-op).

Date User Action Args
2021-08-20 17:17:04adminsetmessages: + msg12006
2021-08-04 00:00:00admincreate