2257. Simplify container requirements with the new algorithms

Section: 23.2.2 [container.requirements.general] Status: C++14 Submitter: Marshall Clow Opened: 2013-05-29 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [container.requirements.general].

View all other issues in [container.requirements.general].

View all issues with C++14 status.

Discussion:

Currently (n3690) Table 96 says, in the row for "a == b", that the Operational semantics are:

== is an equivalence relation.
distance(a.begin(), a.end()) == distance(b.begin(), b.end()) && equal(a.begin(), a.end(),b.begin())

Given the extension of equal for C++14, this can be simplified to:

== is an equivalence relation.
equal(a.begin(), a.end(), b.begin(), b.end())

[ Alisdair notes that a similar edit would apply to the unordered containers requirements. ]

Previous resolution from Marshall Clow:

Ammend the Operational Semantics for 23.2.2 [container.requirements.general], Table 96, row "a == b"

== is an equivalence relation.
distance(a.begin(), a.end()) == distance(b.begin(), b.end()) && equal(a.begin(), a.end(), b.begin(), b.end())

Ammend 23.2.8 [unord.req] p12:

Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key group [Ea1,Ea2) obtained from a.equal_range(Ea1), there exists an equivalent-key group [Eb1,Eb2) obtained from b.equal_range(Ea1), such that distance(Ea1, Ea2) == distance(Eb1, Eb2) and is_permutation(Ea1, Ea2, Eb1, Eb2) returns true. For ...

[2013-09 Chicago]

Marshall improves wording

[2013-09 Chicago (evening issues)]

Moved to ready, after confirming latest wording reflects the discussion earlier in the day.

Proposed resolution:

  1. Ammend 23.2.2 [container.requirements.general], Table 96 as indicated:

    Table 96 — Container requirements (continued)
    Expression Return type Operational
    semantics    		 Assertion/note
    pre-/post-condition    		 Complexity
    …
    a == b convertible to bool == is an equivalence relation.
    distance(a.begin(),
    a.end()) ==
    distance(b.begin(),
    b.end()) &&
    equal(a.begin(),
    a.end(),
    b.begin(), b.end())         		Requires: T is
    EqualityComparable     		Constant if a.size() != b.size(), linear otherwise
    …

  2. Ammend 23.2.8 [unord.req] p12:

    Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key group [Ea1,Ea2) obtained from a.equal_range(Ea1), there exists an equivalent-key group [Eb1,Eb2) obtained from b.equal_range(Ea1), such that distance(Ea1, Ea2) == distance(Eb1, Eb2) and is_permutation(Ea1, Ea2, Eb1, Eb2) returns true. For […]

  3. Amend [forwardlist.overview] p2:

    -2- A forward_list satisfies all of the requirements of a container (Table 96), except that the size() member function is not provided and operator== has linear complexity. […]