2263. Comparing iterators and allocator pointers with different const-character

Section: 16.4.4.6 [allocator.requirements], 23.2 [container.requirements] Status: C++14 Submitter: Howard Hinnant Opened: 2013-06-25 Last modified: 2016-01-28

Priority: 1

View other active issues in [allocator.requirements].

View all other issues in [allocator.requirements].

View all issues with C++14 status.

Discussion:

This ancient issue 179 says one ought to be able to compare iterators with const_iterators from any given container. I'm having trouble finding words that guarantee this in C++11. This impacts not only a container's iterators, but also the allocator requirements in [llocator.requirements] surrounding pointer, const_pointer, void_pointer and const_void_pointer. E.g. can one compare a pointer with a const_pointer?

Since allocator::pointer and const_pointer are required to be random access iterators, one could expect that the 179 guarantees apply for them as well.

[ Daniel comments: ]

The wording for 179 was part of several working drafts (e.g. also in N3092) over some time and suddenly got lost in N3242, presumably by accident. Whatever we decide for allocator pointers, I expect that we need to restore the 179 wording as part of the overall resolution:

Reinsert after 23.2 [container.requirements] p6:

-6- begin() returns an iterator referring to the first element in the container. end() returns an iterator which is the past-the-end value for the container. If the container is empty, then begin() == end();

-?- In the expressions 

i == j
i != j
i < j
i <= j
i >= j
i > j
i - j

where i and j denote objects of a container's iterator type, either or both may be replaced by an object of the container's const_iterator type referring to the same element with no change in semantics.

[2014-02-13 Issaquah, Daniel comments and suggests wording]

First, I didn't originally move the seemingly lost wording to the resolution section because I wanted to ensure that the committee double-checks the reason of this loss.

Second, albeit restoring this wording will restore the comparability of const_iterator and iterator of containers specified in Clause 23, but this alone would not imply that this guarantee automatically extends to all other iterators, simply because there is no fundamental relation between a mutable iterator and a constant iterator by itself. This relation only exists under specific conditions, for example for containers which provide two such typedefs of that kind. Thus the wording restoration would not ensure that allocator pointer and const_pointer would be comparable with each other. To realize that, we would need additional guarantees added to the allocator requirements. In fact, it is crucial to separate these things, because allocators are not restricted to be used within containers, they have their own legitimate use for other places as well (albeit containers presumably belong to the most important use-cases), and this is also stated in the introduction of 16.4.4.6 [allocator.requirements], where it says:

All of the string types (Clause 21), containers (Clause 23) (except array), string buffers and string streams (Clause 27), and match_results (Clause 28) are parameterized in terms of allocators.

[2014-02-12 Issaquah meeting]

Move a Immediate.

Proposed resolution:

  1. Insert after 16.4.4.6 [allocator.requirements] p4 as indicated:

    -4- An allocator type X shall satisfy the requirements of CopyConstructible (17.6.3.1). The X::pointer, X::const_pointer, X::void_pointer, and X::const_void_pointer types shall satisfy the requirements of NullablePointer (17.6.3.3). No constructor, comparison operator, copy operation, move operation, or swap operation on these types shall exit via an exception. X::pointer and X::const_pointer shall also satisfy the requirements for a random access iterator (24.2).

    -?- Let x1 and x2 denote objects of (possibly different) types X::void_pointer, X::const_void_pointer, X::pointer, or X::const_pointer. Then, x1 and x2 are equivalently-valued pointer values, if and only if both x1 and x2 can be explicitly converted to the two corresponding objects px1 and px2 of type X::const_pointer, using a sequence of static_casts using only these four types, and the expression px1 == px2 evaluates to true.

    Drafting note: This wording uses the seemingly complicated route via X::const_pointer, because these are (contrary to X::const_void_pointer) random access iterators and we can rely here for dereferenceable values on the fundamental pointee equivalence of 24.3.5.5 [forward.iterators] p6:

    If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

    while for null pointer values we can rely on the special equality relation induced by 16.4.4.4 [nullablepointer.requirements].

    -?- Let w1 and w2 denote objects of type X::void_pointer. Then for the expressions 

    w1 == w2
w1 != w2

    either or both objects may be replaced by an equivalently-valued object of type X::const_void_pointer with no change in semantics.

    -?- Let p1 and p2 denote objects of type X::pointer. Then for the expressions 

    p1 == p2
p1 != p2
p1 < p2
p1 <= p2
p1 >= p2
p1 > p2
p1 - p2

    either or both objects may be replaced by an equivalently-valued object of type X::const_pointer with no change in semantics.

  2. Reinsert after 23.2 [container.requirements] p6:

    -6- begin() returns an iterator referring to the first element in the container. end() returns an iterator which is the past-the-end value for the container. If the container is empty, then begin() == end();

    -?- In the expressions 

    i == j
i != j
i < j
i <= j
i >= j
i > j
i - j

    where i and j denote objects of a container's iterator type, either or both may be replaced by an object of the container's const_iterator type referring to the same element with no change in semantics.