From Jason Turner

[container.requirements.general]

C++14 → C++17 13.5 KB 154 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpo75qrmrb/{from.md → to.md} +93 -54
tmp/tmpo75qrmrb/{from.md → to.md} RENAMED
@@ -3,46 +3,53 @@
3
  Containers are objects that store other objects. They control allocation
4
  and deallocation of these objects through constructors, destructors,
5
  insert and erase operations.
6
 
7
  All of the complexity requirements in this Clause are stated solely in
8
- terms of the number of operations on the contained objects. the copy
9
- constructor of type `vector <vector<int> >` has linear complexity, even
10
- though the complexity of copying each contained `vector<int>` is itself
11
- linear.
 
12
 
13
  For the components affected by this subclause that declare an
14
  `allocator_type`, objects stored in these components shall be
15
- constructed using the `allocator_traits<allocator_type>::construct`
16
- function and destroyed using the
17
- `allocator_traits<allocator_type>::destroy` function (
18
- [[allocator.traits.members]]). These functions are called only for the
19
- container’s element type, not for internal types used by the container.
20
- This means, for example, that a node-based container might need to
21
- construct nodes containing aligned buffers and call `construct` to place
22
- the element into the buffer.
 
 
 
 
23
 
24
  In Tables  [[tab:containers.container.requirements]],
25
  [[tab:containers.reversible.requirements]], and
26
  [[tab:containers.optional.operations]] `X` denotes a container class
27
  containing objects of type `T`, `a` and `b` denote values of type `X`,
28
  `u` denotes an identifier, `r` denotes a non-const value of type `X`,
29
  and `rv` denotes a non-const rvalue of type `X`.
30
 
31
- Notes: the algorithm `equal()` is defined in Clause  [[algorithms]].
32
  Those entries marked “(Note A)” or “(Note B)” have linear complexity for
33
  `array` and have constant complexity for all other standard containers.
34
 
 
 
 
35
  The member function `size()` returns the number of elements in the
36
  container. The number of elements is defined by the rules of
37
  constructors, inserts, and erases.
38
 
39
  `begin()`
40
 
41
  returns an iterator referring to the first element in the container.
42
  `end()` returns an iterator which is the past-the-end value for the
43
- container. If the container is empty, then `begin() == end()`;
44
 
45
  In the expressions
46
 
47
  ``` cpp
48
  i == j
@@ -58,50 +65,59 @@ where `i` and `j` denote objects of a container’s `iterator` type,
58
  either or both may be replaced by an object of the container’s
59
  `const_iterator` type referring to the same element with no change in
60
  semantics.
61
 
62
  Unless otherwise specified, all containers defined in this clause obtain
63
- memory using an allocator (see  [[allocator.requirements]]). Copy
64
- constructors for these container types obtain an allocator by calling
 
 
 
 
 
 
 
 
65
  `allocator_traits<allocator_type>::select_on_container_copy_construction`
66
  on the allocator belonging to the container being copied. Move
67
  constructors obtain an allocator by move construction from the allocator
68
  belonging to the container being moved. Such move construction of the
69
  allocator shall not exit via an exception. All other constructors for
70
- these container types take a `const allocator_type&` argument. If an
71
- invocation of a constructor uses the default value of an optional
72
- allocator argument, then the `Allocator` type must support value
73
- initialization. A copy of this allocator is used for any memory
74
- allocation performed, by these constructors and by all member functions,
75
- during the lifetime of each container object or until the allocator is
76
- replaced. The allocator may be replaced only via assignment or `swap()`.
77
- Allocator replacement is performed by copy assignment, move assignment,
78
- or swapping of the allocator only if
 
 
 
79
  `allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value`,
80
  `allocator_traits<allocator_type>::propagate_on_container_move_assignment::value`,
81
  or
82
  `allocator_traits<allocator_type>::propagate_on_container_swap::value`
83
- is true within the implementation of the corresponding container
84
- operation. The behavior of a call to a container’s `swap` function is
85
- undefined unless the objects being swapped have allocators that compare
86
- equal or
87
- `allocator_traits<allocator_type>::propagate_on_container_swap::value`
88
- is true. In all container types defined in this Clause, the member
89
  `get_allocator()` returns a copy of the allocator used to construct the
90
  container or, if that allocator has been replaced, a copy of the most
91
  recent replacement.
92
 
93
  The expression `a.swap(b)`, for containers `a` and `b` of a standard
94
  container type other than `array`, shall exchange the values of `a` and
95
  `b` without invoking any move, copy, or swap operations on the
96
- individual container elements. Any `Compare`, `Pred`, or `Hash` objects
97
- belonging to `a` and `b` shall be swappable and shall be exchanged by
98
- unqualified calls to non-member `swap`. If
 
99
  `allocator_traits<allocator_type>::propagate_on_container_swap::value`
100
- is `true`, then the allocators of `a` and `b` shall also be exchanged
101
- using an unqualified call to non-member `swap`. Otherwise, they shall
102
- not be swapped, and the behavior is undefined unless
 
103
  `a.get_allocator() == b.get_allocator()`. Every iterator referring to an
104
  element in one container before the swap shall refer to the same element
105
  in the other container after the swap. It is unspecified whether an
106
  iterator with value `a.end()` before the swap will have value `b.end()`
107
  after the swap.
@@ -126,39 +142,45 @@ requirements:
126
  - no copy constructor or assignment operator of a returned iterator
127
  throws an exception.
128
  - no `swap()` function throws an exception.
129
  - no `swap()` function invalidates any references, pointers, or
130
  iterators referring to the elements of the containers being swapped.
131
- The `end()` iterator does not refer to any element, so it may be
132
- invalidated.
133
 
134
  Unless otherwise specified (either explicitly or by defining a function
135
  in terms of other functions), invoking a container member function or
136
  passing a container as an argument to a library function shall not
137
  invalidate iterators to, or change the values of, objects within that
138
  container.
139
 
 
 
 
 
 
140
  Table  [[tab:containers.optional.operations]] lists operations that are
141
  provided for some types of containers but not others. Those containers
142
  for which the listed operations are provided shall implement the
143
  semantics described in Table  [[tab:containers.optional.operations]]
144
  unless otherwise stated.
145
 
146
- Note: the algorithm `lexicographical_compare()` is defined in Clause 
147
- [[algorithms]].
148
 
149
- All of the containers defined in this Clause and in ([[basic.string]])
150
  except `array` meet the additional requirements of an allocator-aware
151
  container, as described in Table  [[tab:containers.allocatoraware]].
152
 
153
- Given a container type `X` having an `allocator_type` identical to `A`
154
- and a `value_type` identical to `T` and given an lvalue `m` of type `A`,
155
- a pointer `p` of type `T*`, an expression `v` of type (possibly const)
156
- `T`, and an rvalue `rv` of type `T`, the following terms are defined. If
157
- `X` is not allocator-aware, the terms below are defined as if `A` were
158
- `std::allocator<T>` — no allocator object needs to be created and user
159
- specializations of `std::allocator<T>` are not instantiated:
 
160
 
161
  - `T` is *`DefaultInsertable` into `X`* means that the following
162
  expression is well-formed:
163
  ``` cpp
164
  allocator_traits<A>::construct(m, p)
@@ -177,11 +199,13 @@ specializations of `std::allocator<T>` are not instantiated:
177
  allocator_traits<A>::construct(m, p, rv)
178
  ```
179
 
180
  and its evaluation causes the following postcondition to hold: The
181
  value of `*p` is equivalent to the value of `rv` before the
182
- evaluation. rv remains a valid object. Its state is unspecified
 
 
183
  - `T` is *`CopyInsertable` into `X`* means that, in addition to `T`
184
  being `MoveInsertable` into `X`, the following expression is
185
  well-formed:
186
  ``` cpp
187
  allocator_traits<A>::construct(m, p, v)
@@ -198,17 +222,32 @@ specializations of `std::allocator<T>` are not instantiated:
198
  well-formed:
199
  ``` cpp
200
  allocator_traits<A>::destroy(m, p)
201
  ```
202
 
203
- A container calls `allocator_traits<A>::construct(m, p, args)` to
204
- construct an element at `p` using `args`. The default `construct` in
205
- `std::allocator` will call `::new((void*)p) T(args)`, but specialized
206
- allocators may choose a different definition.
 
207
 
208
  In Table  [[tab:containers.allocatoraware]], `X` denotes an
209
  allocator-aware container class with a `value_type` of `T` using
210
  allocator of type `A`, `u` denotes a variable, `a` and `b` denote
211
  non-const lvalues of type `X`, `t` denotes an lvalue or a const rvalue
212
  of type `X`, `rv` denotes a non-const rvalue of type `X`, and `m` is a
213
  value of type `A`.
214
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3
  Containers are objects that store other objects. They control allocation
4
  and deallocation of these objects through constructors, destructors,
5
  insert and erase operations.
6
 
7
  All of the complexity requirements in this Clause are stated solely in
8
+ terms of the number of operations on the contained objects.
9
+
10
+ [*Example 1*: The copy constructor of type `vector<vector<int>>` has
11
+ linear complexity, even though the complexity of copying each contained
12
+ `vector<int>` is itself linear. — *end example*]
13
 
14
  For the components affected by this subclause that declare an
15
  `allocator_type`, objects stored in these components shall be
16
+ constructed using the function
17
+ `allocator_traits<allocator_type>::rebind_traits<U>::{}construct` and
18
+ destroyed using the function
19
+ `allocator_traits<allocator_type>::rebind_traits<U>::{}destroy` (
20
+ [[allocator.traits.members]]), where `U` is either
21
+ `allocator_type::value_type` or an internal type used by the container.
22
+ These functions are called only for the container’s element type, not
23
+ for internal types used by the container.
24
+
25
+ [*Note 1*: This means, for example, that a node-based container might
26
+ need to construct nodes containing aligned buffers and call `construct`
27
+ to place the element into the buffer. — *end note*]
28
 
29
  In Tables  [[tab:containers.container.requirements]],
30
  [[tab:containers.reversible.requirements]], and
31
  [[tab:containers.optional.operations]] `X` denotes a container class
32
  containing objects of type `T`, `a` and `b` denote values of type `X`,
33
  `u` denotes an identifier, `r` denotes a non-const value of type `X`,
34
  and `rv` denotes a non-const rvalue of type `X`.
35
 
 
36
  Those entries marked “(Note A)” or “(Note B)” have linear complexity for
37
  `array` and have constant complexity for all other standard containers.
38
 
39
+ [*Note 2*: The algorithm `equal()` is defined in Clause 
40
+ [[algorithms]]. — *end note*]
41
+
42
  The member function `size()` returns the number of elements in the
43
  container. The number of elements is defined by the rules of
44
  constructors, inserts, and erases.
45
 
46
  `begin()`
47
 
48
  returns an iterator referring to the first element in the container.
49
  `end()` returns an iterator which is the past-the-end value for the
50
+ container. If the container is empty, then `begin() == end()`.
51
 
52
  In the expressions
53
 
54
  ``` cpp
55
  i == j
 
65
  either or both may be replaced by an object of the container’s
66
  `const_iterator` type referring to the same element with no change in
67
  semantics.
68
 
69
  Unless otherwise specified, all containers defined in this clause obtain
70
+ memory using an allocator (see  [[allocator.requirements]]).
71
+
72
+ [*Note 3*: In particular, containers and iterators do not store
73
+ references to allocated elements other than through the allocator’s
74
+ pointer type, i.e., as objects of type `P` or
75
+ `pointer_traits<P>::template rebind<unspecified>`, where `P` is
76
+ `allocator_traits<allocator_type>::pointer`. — *end note*]
77
+
78
+ Copy constructors for these container types obtain an allocator by
79
+ calling
80
  `allocator_traits<allocator_type>::select_on_container_copy_construction`
81
  on the allocator belonging to the container being copied. Move
82
  constructors obtain an allocator by move construction from the allocator
83
  belonging to the container being moved. Such move construction of the
84
  allocator shall not exit via an exception. All other constructors for
85
+ these container types take a `const allocator_type&` argument.
86
+
87
+ [*Note 4*: If an invocation of a constructor uses the default value of
88
+ an optional allocator argument, then the `Allocator` type must support
89
+ value-initialization. — *end note*]
90
+
91
+ A copy of this allocator is used for any memory allocation and element
92
+ construction performed, by these constructors and by all member
93
+ functions, during the lifetime of each container object or until the
94
+ allocator is replaced. The allocator may be replaced only via assignment
95
+ or `swap()`. Allocator replacement is performed by copy assignment, move
96
+ assignment, or swapping of the allocator only if
97
  `allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value`,
98
  `allocator_traits<allocator_type>::propagate_on_container_move_assignment::value`,
99
  or
100
  `allocator_traits<allocator_type>::propagate_on_container_swap::value`
101
+ is `true` within the implementation of the corresponding container
102
+ operation. In all container types defined in this Clause, the member
 
 
 
 
103
  `get_allocator()` returns a copy of the allocator used to construct the
104
  container or, if that allocator has been replaced, a copy of the most
105
  recent replacement.
106
 
107
  The expression `a.swap(b)`, for containers `a` and `b` of a standard
108
  container type other than `array`, shall exchange the values of `a` and
109
  `b` without invoking any move, copy, or swap operations on the
110
+ individual container elements. Lvalues of any `Compare`, `Pred`, or
111
+ `Hash` types belonging to `a` and `b` shall be swappable and shall be
112
+ exchanged by calling `swap` as described in  [[swappable.requirements]].
113
+ If
114
  `allocator_traits<allocator_type>::propagate_on_container_swap::value`
115
+ is `true`, then lvalues of type `allocator_type` shall be swappable and
116
+ the allocators of `a` and `b` shall also be exchanged by calling `swap`
117
+ as described in  [[swappable.requirements]]. Otherwise, the allocators
118
+ shall not be swapped, and the behavior is undefined unless
119
  `a.get_allocator() == b.get_allocator()`. Every iterator referring to an
120
  element in one container before the swap shall refer to the same element
121
  in the other container after the swap. It is unspecified whether an
122
  iterator with value `a.end()` before the swap will have value `b.end()`
123
  after the swap.
 
142
  - no copy constructor or assignment operator of a returned iterator
143
  throws an exception.
144
  - no `swap()` function throws an exception.
145
  - no `swap()` function invalidates any references, pointers, or
146
  iterators referring to the elements of the containers being swapped.
147
+ \[*Note 5*: The `end()` iterator does not refer to any element, so it
148
+ may be invalidated. — *end note*]
149
 
150
  Unless otherwise specified (either explicitly or by defining a function
151
  in terms of other functions), invoking a container member function or
152
  passing a container as an argument to a library function shall not
153
  invalidate iterators to, or change the values of, objects within that
154
  container.
155
 
156
+ A *contiguous container* is a container that supports random access
157
+ iterators ([[random.access.iterators]]) and whose member types
158
+ `iterator` and `const_iterator` are contiguous iterators (
159
+ [[iterator.requirements.general]]).
160
+
161
  Table  [[tab:containers.optional.operations]] lists operations that are
162
  provided for some types of containers but not others. Those containers
163
  for which the listed operations are provided shall implement the
164
  semantics described in Table  [[tab:containers.optional.operations]]
165
  unless otherwise stated.
166
 
167
+ [*Note 6*: The algorithm `lexicographical_compare()` is defined in
168
+ Clause  [[algorithms]]. — *end note*]
169
 
170
+ All of the containers defined in this Clause and in  [[basic.string]]
171
  except `array` meet the additional requirements of an allocator-aware
172
  container, as described in Table  [[tab:containers.allocatoraware]].
173
 
174
+ Given an allocator type `A` and given a container type `X` having a
175
+ `value_type` identical to `T` and an `allocator_type` identical to
176
+ `allocator_traits<A>::rebind_alloc<T>` and given an lvalue `m` of type
177
+ `A`, a pointer `p` of type `T*`, an expression `v` of type (possibly
178
+ `const`) `T`, and an rvalue `rv` of type `T`, the following terms are
179
+ defined. If `X` is not allocator-aware, the terms below are defined as
180
+ if `A` were `allocator<T>` — no allocator object needs to be created and
181
+ user specializations of `allocator<T>` are not instantiated:
182
 
183
  - `T` is *`DefaultInsertable` into `X`* means that the following
184
  expression is well-formed:
185
  ``` cpp
186
  allocator_traits<A>::construct(m, p)
 
199
  allocator_traits<A>::construct(m, p, rv)
200
  ```
201
 
202
  and its evaluation causes the following postcondition to hold: The
203
  value of `*p` is equivalent to the value of `rv` before the
204
+ evaluation.
205
+ \[*Note 7*: `rv` remains a valid object. Its state is
206
+ unspecified — *end note*]
207
  - `T` is *`CopyInsertable` into `X`* means that, in addition to `T`
208
  being `MoveInsertable` into `X`, the following expression is
209
  well-formed:
210
  ``` cpp
211
  allocator_traits<A>::construct(m, p, v)
 
222
  well-formed:
223
  ``` cpp
224
  allocator_traits<A>::destroy(m, p)
225
  ```
226
 
227
+ [*Note 8*: A container calls
228
+ `allocator_traits<A>::construct(m, p, args)` to construct an element at
229
+ `p` using `args`, with `m == get_allocator()`. The default `construct`
230
+ in `allocator` will call `::new((void*)p) T(args)`, but specialized
231
+ allocators may choose a different definition. — *end note*]
232
 
233
  In Table  [[tab:containers.allocatoraware]], `X` denotes an
234
  allocator-aware container class with a `value_type` of `T` using
235
  allocator of type `A`, `u` denotes a variable, `a` and `b` denote
236
  non-const lvalues of type `X`, `t` denotes an lvalue or a const rvalue
237
  of type `X`, `rv` denotes a non-const rvalue of type `X`, and `m` is a
238
  value of type `A`.
239
 
240
+ The behavior of certain container member functions and deduction guides
241
+ depends on whether types qualify as input iterators or allocators. The
242
+ extent to which an implementation determines that a type cannot be an
243
+ input iterator is unspecified, except that as a minimum integral types
244
+ shall not qualify as input iterators. Likewise, the extent to which an
245
+ implementation determines that a type cannot be an allocator is
246
+ unspecified, except that as a minimum a type `A` shall not qualify as an
247
+ allocator unless it satisfies both of the following conditions:
248
+
249
+ - The *qualified-id* `A::value_type` is valid and denotes a type (
250
+ [[temp.deduct]]).
251
+ - The expression `declval<A&>().allocate(size_t{})` is well-formed when
252
+ treated as an unevaluated operand.
253
+