### 2257. Simplify container requirements with the new algorithms

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

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 24.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 24.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 24.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 24.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. […]