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

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

Section: 22.2.1 [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 22.2.1 [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 22.2.7 [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 22.2.1 [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 22.2.7 [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. […]