861. Incomplete specification of EqualityComparable for std::forward_list

Section: 23.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 23.2.2 [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 23.2.2 [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 23.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 jdistance(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 23.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 23.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