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

3578. Iterator SCARYness in the context of associative container merging

Section: 23.2.7.1 [associative.reqmts.general] Status: Tentatively Ready Submitter: Joaquín M López Muñoz Opened: 2021-08-04 Last modified: 2024-12-09

Priority: 3

View other active issues in [associative.reqmts.general].

View all other issues in [associative.reqmts.general].

View all issues with Tentatively Ready status.

Discussion:

For the expression a.merge(a2), postconditions say that "iterators referring to the transferred elements […] now behave as iterators into a […]". When a and a2 are of different types, this seems to imply, under the widest interpretation for "behaving as", that a-iterators and a2-iterators are actually of the same type, that is, that associative containers have SCARY iterators, which is, to the best of my knowledge, not currently mandated by the standard.

There are (at least) three possible resolutions to this ambiguity, ordered by intrusiveness:

• Indicate that "behaving as" only applies to the case where a and a2 are of the same type.

• Clarify what "behaving as" means. A non-SCARY interpretation is that an a2-iterator to a transferred element can still be dereferenced, incremented (if not past the last element of a) and decremented (if not pointing to the first element of a), while comparison with a-iterators and use in the interface of a is not guaranteed.

• Mandate SCARY iterators by, for instance, requiring that associative containers with compatible nodes (23.2.5.1 [container.node.overview]/1) have the same iterator types.

Note that this issue does not extend to unordered associative containers, as there (23.2.8.1 [unord.req.general]) iterators to transferred elements are invalidated, which makes the point of SCARYness irrelevant. That said, if SCARY iterators are finally required for associative containers, it makes much sense to extend the requirement to unordered associative containers as well.

[2021-08-20; Reflector poll]

Set priority to 3 after reflector poll.

[2024-12-04; Jonathan provides wording]

If we want to require SCARY iterators then that should be a proposal that goes through LEWG design review. I propose an almost minimal change to make the spec consistent without imposing any new requirements on implementations.

The minimal change would be to say that iterators remain valid if a and a2 have the same type, which is the minimum portable guarantee that always holds. However what matters in practice is whether the iterator types are the same. That would not be a portable guarantee, because it depends on whether the implementation uses SCARY iterators for its maps and sets, so users could write code that works on one implementation and fails to compile when moved to a different implementation. But that portability trap would be present even if we only say iterators remain valid when a and a2 are the same type. If the code compiles and works on an implementation with SCARY iterators, then users will rely on that, even if unintentionally. Leaving that case unspecified or undefined in the standard doesn't prevent users from relying on it. It doesn't seem to serve any benefit to pretend it doesn't work when it actually does on some implementations.

N.B. Libstdc++ associative container iterators are SCARY by default, but non-SCARY when -D_GLIBCXX_DEBUG is used to enable Debug Mode (see Bug 62169). I believe libc++ iterators are SCARY even when -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG is used, and MSVC STL iterators are SCARY even when /D_ITERATOR_DEBUG_LEVEL is used.

[2024-12-09; Reflector poll]

Set status to Tentatively Ready after eight votes in favour during reflector poll.

Proposed resolution:

This wording is relative to N4993.

1. Modify 23.2.7.1 [associative.reqmts.general] as indicated:

   a.merge(a2)

   -112- Result: void

   -113- Preconditions: a.get_allocator() == a2.get_allocator() is true.

   -114- Effects: Attempts to extract each element in a2 and insert it into a using the comparison object of a. In containers with unique keys, if there is an element in a with key equivalent to the key of an element from a2, then that element is not extracted from a2.

   -115- Postconditions: Pointers and references to the transferred elements of a2 refer to those same elements but as members of a. If a.begin() and a2.begin() have the same type, iterators Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into a, not into a2.

   -116- Throws: Nothing unless the comparison objects throws.

   -117- Complexity: N log(a.size()+N), where N has the value a2.size().