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

### 861. Incomplete specification of `EqualityComparable` for `std::forward_list`

Section: 24.2 [container.requirements] Status: C++11 Submitter: Daniel Krügler Opened: 2008-06-24 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [container.requirements].

View all issues with C++11 status.

Discussion:

Table 89, Container requirements, defines `operator==` in terms of the container member function `size()` and the algorithm `std::equal`:

> `==` is an equivalence relation. `a.size() == b.size() && equal(a.begin(), a.end(), b.begin()`

The new container `forward_list` does not provide a `size` member function by design but does provide `operator==` and `operator!=` without specifying it's semantic.

Other parts of the (sequence) container requirements do also depend on `size()`, e.g. `empty()` or `clear()`, but this issue explicitly attempts to solve the missing `EqualityComparable` specification, because of the special design choices of `forward_list`.

I propose to apply one of the following resolutions, which are described as:

1. Provide a definition, which is optimal for this special container without previous size test. This choice prevents two `O(N)` calls of `std::distance()` with the corresponding container ranges and instead uses a special `equals` implementation which takes two container ranges instead of 1 1/2.
2. The simple fix where the usual test is adapted such that `size()` is replaced by `distance` with corresponding performance disadvantages.

Both proposal choices are discussed, the preferred choice of the author is to apply (A).

[ San Francisco: ]

> There's an Option C: change the requirements table to use distance().

> LWG found Option C acceptable.

> Martin will draft the wording for Option C.

[ post San Francisco: ]

> Martin provided wording for Option C.

[ 2009-07 Frankfurt ]

> Other operational semantics (see, for example, Tables 82 and 83) are written in terms of a container's size() member. Daniel to update proposed resolution C.

> [ Howard: Commented out options A and B. ]

[ 2009-07-26 Daniel updated proposed resolution C. ]

[ 2009-10 Santa Cruz: ]

> Mark NAD Editorial. Addressed by N2986.

[ 2009-10 Santa Cruz: ]

> Reopened. N2986 was rejected in full committee on procedural grounds.

[ 2010-01-30 Howard updated Table numbers. ]

[ 2010 Pittsburgh: ]

> Moved to Ready for Pittsburgh.

Proposed resolution:

Option (C):

> 1. In 24.2.2.1 [container.requirements.general] change Table 90 -- Container requirements as indicated:

>    1. Change the text in the Assertion/note column in the row for "`X u`;" as follows:

>       > post: `u.size() == 0empty() == true`

>    2. Change the text in the Assertion/note column in the row for "`X();`" as follows:

>       > `X().size() == 0empty() == true`

>    3. Change the text in the Operational Semantics column in the row for "`a == b`" as follows:

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

>    4. Add text in the Ass./Note/pre-/post-condition column in the row for "`a == b`" as follows:

>       > Requires: `T` is `EqualityComparable`

>    5. Change the text in the Operational Semantics column in the row for "`a.size()`" as follows:

>       > `a.end() - a.begin()distance(a.begin(), a.end())`

>    6. Change the text in the Operational Semantics column in the row for "`a.max_size()`" as follows:

>       > `size()distance(begin(), end())` of the largest possible container

>    7. Change the text in the Operational Semantics column in the row for "`a.empty()`" as follows:

>       > `a.size() == 0a.begin() == a.end()`

> 2. In 24.2.2.1 [container.requirements.general] change Table 93 — Allocator-aware container requirements as indicated:

>    1. Change the text in the Assertion/note column in the row for "`X() / X u;`" as follows:

>       > Requires: `A` is `DefaultConstructible` post: `u.size() == 0u.empty() == true`, `get_allocator() == A()`

>    2. Change the text in the Assertion/note column in the row for "`X(m) / X u(m);`" as follows:

>       > post: `u.size() == 0u.empty() == true, get_allocator() == m`

> 3. In 24.2.4 [sequence.reqmts] change Table 94 — Sequence container requirements as indicated:

>    1. Change the text in the Assertion/note column in the row for "`X(n, t) / X a(n, t)`" as follows:

>       > post: `size()distance(begin(), end()) == n [..]`

>    2. Change the text in the Assertion/note column in the row for "`X(i, j) / X a(i, j)`" as follows:

>       > [..] post: `size() ==` distance between `i` and `j` `distance(begin(), end()) == distance(i, j)` [..]

>    3. Change the text in the Assertion/note column in the row for "`a.clear()`" as follows:

>       > `a.erase(a.begin(), a.end())` post: `size() == 0a.empty() == true`

> 4. In 24.2.7 [associative.reqmts] change Table 96 — Associative container requirements as indicated:

>    [ Not every occurrence of `size()` was replaced, because all current associative containers have a `size`. The following changes ensure consistency regarding the semantics of "`erase`" for all tables and adds some missing objects ]

>    1. Change the text in the Complexity column in the row for `X(i,j,c)/Xa(i,j,c);` as follows:

>       > `N` log `N` in general (`N` `== distance(i, j)`is the distance from `i` to `j`); ...

>    2. Change the text in the Complexity column in the row for "`a.insert(i, j)`" as follows:

>       > `N log(a.size() + N)` (`N` is the distance from `i` to `j`) where `N == distance(i, j)`

>    3. Change the text in the Complexity column in the row for "`a.erase(k)`" as follows:

>       > `log(a.size()) + a.count(k)`

>    4. Change the text in the Complexity column in the row for "`a.erase(q1, q2)`" as follows:

>       > `log(a.size()) + N` where `N` is the distance from `q1` to `q2` `== distance(q1, q2)`.

>    5. Change the text in the Assertion/note column in the row for "`a.clear()`" as follows:

>       > `a.erase(a.begin(),a.end())` post: `size() == 0a.empty() == true`

>    6. Change the text in the Complexity column in the row for "`a.clear()`" as follows:

>       > linear in `a.size()`

>    7. Change the text in the Complexity column in the row for "`a.count(k)`" as follows:

>       > `log(a.size()) + a.count(k)`

> 5. In 24.2.8 [unord.req] change Table 98 — Unordered associative container requirements as indicated:

>    [ The same rational as for Table 96 applies here ]

>    1. Change the text in the Assertion/note column in the row for "`a.clear()`" as follows:

>       > [..] Post: `a.size() == 0empty() == true`