Issue 3028: Container requirements tables should distinguish const and non-const variables

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

3028. Container requirements tables should distinguish `const` and non-`const` variables

Section: 23.2.2 [container.requirements.general] Status: C++23 Submitter: Jonathan Wakely Opened: 2017-10-17 Last modified: 2023-11-22

Priority: 3

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

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

View all issues with C++23 status.

Discussion:

[container.requirements.general] p4 says:

In Tables 83, 84, and 85 X denotes a container class containing objects of type T, a and b denote values of type X, u denotes an identifier, r denotes a non-const value of type X, and rv denotes a non-const rvalue of type X.

This doesn't say anything about whether a and b are allowed to be const, or must be non-const. In fact Table 83 uses them inconsistently, e.g. the rows for "a = rv" and "a.swap(b)" most certainly require them to be non-const, but all other uses are valid for either const or non-const X.

[2017-11 Albuquerque Wednesday night issues processing]

Priority set to 3; Jonathan to provide updated wording.

Wording needs adjustment - could use "possibly const values of type X"

Will distinguish between lvalue/rvalue

Previous resolution [SUPERSEDED]:

This wording is relative to N4687.

Change 23.2.2 [container.requirements.general] p4 as indicated:

-4- In Tables 83, 84, and 85 X denotes a container class containing objects of type T, a and b denote values of type X, u denotes an identifier, r and s denote~~s a~~ non-const values of type X, and rv denotes a non-const rvalue of type X.

Change 23.2.2 [container.requirements.general], Table 83 "Container requirements", as indicated:

Table 83 — Container requirements
Expression Return type Operational
semantics Assertion/note
pre/post-condition Complexity

[…]

ar = rv X& All existing elements
of ar are either move
assigned to or
destroyed ar shall be equal to
the value that rv had
before this
assignment linear

[…]

ar.swap(bs) void exchanges the
contents of ar and bs (Note A)

[…]

swap(ar, bs) void ar.swap(bs) (Note A)

Table 83 — Container requirements
Expression	Return type	Operational semantics	Assertion/note pre/post-condition	Complexity
`[…]`
`ar = rv`	`X&`	All existing elements of `ar` are either move assigned to or destroyed	`ar` shall be equal to the value that `rv` had before this assignment	linear
`[…]`
`ar.swap(bs)`	`void`		exchanges the contents of `ar` and `bs`	(Note A)
`[…]`
`swap(ar, bs)`	`void`	`ar.swap(bs)`		(Note A)

[2020-05-03; Daniel provides alternative wording]

Previous resolution [SUPERSEDED]:

This wording is relative to N4861.

Change 23.2.2 [container.requirements.general] as indicated:

[Drafting note:

The following presentation also transforms the current list into a bullet list as we already have in 23.2.8 [unord.req] p11

It has been decided to replace the symbol r by s, because it is easy to confuse with rv but means an lvalue instead, and the other container tables use it rarely and for something completely different (iterator value)

A separate symbol v is introduced to unambigiously distinguish the counterpart of a non-const rvalue (See 16.4.4.2 [utility.arg.requirements])

Two separate symbols b and c represent now "(possibly const) values, while the existing symbol a represents an unspecified value, whose meaning becomes defined when context is provided, e.g. for overloads like begin() and end

-4- In Tables 73, 74, and 75:

(4.1) — X denotes a container class containing objects of type T,

(4.2) — a ~~and b~~ denotes a values of type X,

(4.2) — b and c denote (possibly const) values of type X,

(4.3) — i and j denote values of type (possibly const) X::iterator,

(4.4) — u denotes an identifier,

(?.?) — v denotes an lvalue of type (possibly const) X or an rvalue of type const X,

(4.5) — ~~r~~s and t denote~~s a~~ non-const ~~value~~lvalues of type X, and

(4.6) — rv denotes a non-const rvalue of type X.

Change 23.2.2 [container.requirements.general], Table 73 "Container requirements" [tab:container.req], as indicated:

[Drafting note: The following presentation also moves the copy-assignment expression just before the move-assignment expression]

Table 73: — Container requirements [tab:container.req]
Expression Return type Operational
semantics Assertion/note
pre/post-condition Complexity

[…]

X(av) Preconditions: T is Cpp17CopyInsertable
into X (see below).
Postconditions: av == X(av). linear

X u(av); X u = av; Preconditions: T is Cpp17CopyInsertable
into X (see below).
Postconditions: u == av. linear

X u(rv); X u = rv; Postconditions: u is equal to the value
that rv had before this construction (Note B)

t = v X& Postconditions: t == v. linear

at = rv X& All existing elements
of at are either move
assigned to or
destroyed at shall be equal to
the value that rv had
before this
assignment linear

[…]

ac == b convertible to bool == is an equivalence relation.
equal(ac.begin(), ac.end(), b.begin(), b.end()) Preconditions: T meets the
Cpp17EqualityComparable requirements Constant if ac.size() != b.size(),
linear otherwise

ac != b convertible to bool Equivalent to !(ac == b) linear

at.swap(bs) void exchanges the
contents of at and bs (Note A)

swap(at, bs) void at.swap(bs) (Note A)

~~r = a~~ ~~X&~~ Postconditions: r == a. ~~linear~~

ac.size() size_type distance(ac.begin(), ac.end()) constant

ac.max_size() size_type distance(begin(), end()) for the largest
possible container constant

ac.empty() convertible to bool ac.begin() == ac.end() constant

Table 73: — Container requirements [tab:container.req]
Expression	Return type	Operational semantics	Assertion/note pre/post-condition	Complexity
`[…]`
`X(av)`			Preconditions: `T` is Cpp17CopyInsertable into `X` (see below). Postconditions: `av == X(av)`.	linear
`X u(av); X u = av;`			Preconditions: `T` is Cpp17CopyInsertable into `X` (see below). Postconditions: `u == av`.	linear
`X u(rv); X u = rv;`			Postconditions: `u` is equal to the value that `rv` had before this construction	(Note B)
`t = v`	`X&`		Postconditions: `t == v`.	linear
`at = rv`	`X&`	All existing elements of `at` are either move assigned to or destroyed	`at` shall be equal to the value that `rv` had before this assignment	linear
`[…]`
`ac == b`	convertible to `bool`	`==` is an equivalence relation. `equal(ac.begin(), ac.end(), b.begin(), b.end())`	Preconditions: `T` meets the Cpp17EqualityComparable requirements	Constant if `ac.size() != b.size()`, linear otherwise
`ac != b`	convertible to `bool`	Equivalent to `!(ac == b)`		linear
`at.swap(bs)`	`void`		exchanges the contents of `at` and `bs`	(Note A)
`swap(at, bs)`	`void`	`at.swap(bs)`		(Note A)
~~`r = a`~~	~~`X&`~~		Postconditions: `r == a`.	~~linear~~
`ac.size()`	`size_type`	`distance(ac.begin(), ac.end())`		constant
`ac.max_size()`	`size_type`	`distance(begin(), end())` for the largest possible container		constant
`ac.empty()`	convertible to `bool`	`ac.begin() == ac.end()`		constant

[2022-04-20; Jonathan rebases the wording on the latest draft]

[2022-09-05; Reflector poll]

Set status to Tentatively Ready after five votes in favour during reflector poll in April 2022.

[2022-11-12 Approved at November 2022 meeting in Kona. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4910.

Change 23.2.2 [container.requirements.general] as indicated:
[Drafting note:
- It has been decided to replace the symbol r by s, because it is easy to confuse with rv but means an lvalue instead, and the other container tables use it rarely and for something completely different (iterator value)
- A separate symbol v is introduced to unambigiously distinguish the counterpart of a non-const rvalue (See 16.4.4.2 [utility.arg.requirements])
- Two separate symbols b and c represent now "(possibly const) values, while the existing symbol a represents an unspecified value, whose meaning becomes defined when context is provided, e.g. for overloads like begin() and end
-1- In subclause [container.gen.reqmts],
1. (1.1) — X denotes a container class containing objects of type T,
2. (1.2) — a ~~and b denote values~~ denotes a value of type X,
3. (?.?) — b and c denote values of type (possibly const) X,
4. (1.3) — i and j denote values of type (possibly const) X::iterator,
5. (1.4) — u denotes an identifier,
6. (?.?) — v denotes an lvalue of type (possibly const) X or an rvalue of type const X,
7. (1.5) — ~~r denotes a~~s and t denote non-const ~~value~~lvalues of type X, and
8. (1.6) — rv denotes a non-const rvalue of type X.
Change 23.2.2.2 [container.reqmts] as indicated:

[Drafting note: The following presentation also moves the copy-assignment expression just before the move-assignment expression]
```
  X u(av);
  X u = av;
```
-12- Preconditions: T is Cpp17CopyInsertable into X (see below).

-13- Postconditions: u == av.

-14- Complexity: Linear.
```
  X u(rv);
  X u = rv;
```
-15- Postconditions: u is equal to the value that rv had before this construction.

-14- Complexity: Linear for array and constant for all other standard containers.
```
  t = v
```
-?- Result: X&.

-?- Postconditions: t == v.

-?- Complexity: Linear.
```
  at = rv
```
-17- Result: X&.

-18- Effects: All existing elements of at are either move assigned to or destroyed.

-19- Postconditions: at shall be equal to the value that rv had before this assignment.

-20- Complexity: Linear.

[…]
```
  ab.begin()
```
-24- Result: iterator; const_iterator for constant ab.

-25- Returns: An iterator referring to the first element in the container.

-26- Complexity: Constant.
```
  ab.end()
```
-27- Result: iterator; const_iterator for constant ab.

-28- Returns: An iterator which is the past-the-end value for the container.

-29- Complexity: Constant.
```
  ab.cbegin()
```
-30- Result: const_iterator.

-31- Returns: const_cast<X const&>(ab).begin()

-32- Complexity: Constant.
```
  ab.cend()
```
-33- Result: const_iterator.

-34- Returns: const_cast<X const&>(ab).end()

-35- Complexity: Constant.

[…]
```
  ac == b
```
-39- Preconditions: T meets the Cpp17EqualityComparable requirements.

-40- Result: Convertible to bool.

-41- Returns: equal(ac.begin(), ac.end(), b.begin(), b.end()).

[Note 1: The algorithm equal is defined in 26.6.13 [alg.equal]. — end note]

-42- Complexity: Constant if ac.size() != b.size(), linear otherwise.

-43- Remarks: == is an equivalence relation.
```
  ac != b
```
-44- Effects: Equivalent to !(ac == b).
```
  at.swap(bs)
```
-45- Result: void.

-46- Effects: Exchanges the contents of at and bs.

-47- Complexity: Linear for array and constant for all other standard containers.
```
  swap(at, bs)
```
-48- Effects: Equivalent to at.swap(bs)
```
  r = a
```
~~-49- Result: X&.~~

~~-50- Postconditions: r == a.~~

~~-51- Complexity: Linear.~~
```
  ac.size()
```
-52- Result: size_type.

-53- Returns: distance(ac.begin(), ac.end()), i.e. the number of elements in the container.

-54- Complexity: Constant.

-55- Remarks: The number of elements is defined by the rules of constructors, inserts, and erases.
```
  ac.max_size()
```
-56- Result: size_type.

-57- Returns: distance(begin(), end()) for the largest possible container.

-58- Complexity: Constant.
```
  ac.empty()
```
-59- Result: Convertible to bool.

-60- Returns: ac.begin() == ac.end())

-61- Complexity: Constant.

-62- Remarks: If the container is empty, then ac.empty() is true.

3028. Container requirements tables should distinguish const and non-const variables

3028. Container requirements tables should distinguish `const` and non-`const` variables