From Jason Turner

[deque]

C++14 → C++17 12.8 KB 144 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/tmpsqxa9wz2/{from.md → to.md} +74 -56
tmp/tmpsqxa9wz2/{from.md → to.md} RENAMED
@@ -1,15 +1,15 @@
1
  ### Class template `deque` <a id="deque">[[deque]]</a>
2
 
3
  #### Class template `deque` overview <a id="deque.overview">[[deque.overview]]</a>
4
 
5
- A `deque` is a sequence container that, like a `vector` ([[vector]]),
6
- supports random access iterators. In addition, it supports constant time
7
  insert and erase operations at the beginning or the end; insert and
8
  erase in the middle take linear time. That is, a deque is especially
9
- optimized for pushing and popping elements at the beginning and end. As
10
- with vectors, storage management is handled automatically.
11
 
12
  A `deque` satisfies all of the requirements of a container, of a
13
  reversible container (given in tables in  [[container.requirements]]),
14
  of a sequence container, including the optional sequence container
15
  requirements ([[sequence.reqmts]]), and of an allocator-aware container
@@ -22,24 +22,24 @@ information.
22
  namespace std {
23
  template <class T, class Allocator = allocator<T>>
24
  class deque {
25
  public:
26
  // types:
27
- typedef value_type& reference;
28
- typedef const value_type& const_reference;
29
- typedef implementation-defined iterator; // See [container.requirements]
30
- typedef implementation-defined const_iterator; // See [container.requirements]
31
- typedef implementation-defined size_type; // See [container.requirements]
32
- typedef implementation-defined difference_type;// See [container.requirements]
33
- typedef T value_type;
34
- typedef Allocator allocator_type;
35
- typedef typename allocator_traits<Allocator>::pointer pointer;
36
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
37
- typedef std::reverse_iterator<iterator> reverse_iterator;
38
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
39
 
40
- // [deque.cons], construct/copy/destroy:
41
  deque() : deque(Allocator()) { }
42
  explicit deque(const Allocator&);
43
  explicit deque(size_type n, const Allocator& = Allocator());
44
  deque(size_type n, const T& value, const Allocator& = Allocator());
45
  template <class InputIterator>
@@ -50,11 +50,12 @@ namespace std {
50
  deque(deque&&, const Allocator&);
51
  deque(initializer_list<T>, const Allocator& = Allocator());
52
 
53
  ~deque();
54
  deque& operator=(const deque& x);
55
- deque& operator=(deque&& x);
 
56
  deque& operator=(initializer_list<T>);
57
  template <class InputIterator>
58
  void assign(InputIterator first, InputIterator last);
59
  void assign(size_type n, const T& t);
60
  void assign(initializer_list<T>);
@@ -73,17 +74,17 @@ namespace std {
73
  const_iterator cbegin() const noexcept;
74
  const_iterator cend() const noexcept;
75
  const_reverse_iterator crbegin() const noexcept;
76
  const_reverse_iterator crend() const noexcept;
77
 
78
- // [deque.capacity], capacity:
 
79
  size_type size() const noexcept;
80
  size_type max_size() const noexcept;
81
  void resize(size_type sz);
82
  void resize(size_type sz, const T& c);
83
  void shrink_to_fit();
84
- bool empty() const noexcept;
85
 
86
  // element access:
87
  reference operator[](size_type n);
88
  const_reference operator[](size_type n) const;
89
  reference at(size_type n);
@@ -91,13 +92,13 @@ namespace std {
91
  reference front();
92
  const_reference front() const;
93
  reference back();
94
  const_reference back() const;
95
 
96
- // [deque.modifiers], modifiers:
97
- template <class... Args> void emplace_front(Args&&... args);
98
- template <class... Args> void emplace_back(Args&&... args);
99
  template <class... Args> iterator emplace(const_iterator position, Args&&... args);
100
 
101
  void push_front(const T& x);
102
  void push_front(T&& x);
103
  void push_back(const T& x);
@@ -113,14 +114,20 @@ namespace std {
113
  void pop_front();
114
  void pop_back();
115
 
116
  iterator erase(const_iterator position);
117
  iterator erase(const_iterator first, const_iterator last);
118
- void swap(deque&);
 
119
  void clear() noexcept;
120
  };
121
 
 
 
 
 
 
122
  template <class T, class Allocator>
123
  bool operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
124
  template <class T, class Allocator>
125
  bool operator< (const deque<T, Allocator>& x, const deque<T, Allocator>& y);
126
  template <class T, class Allocator>
@@ -130,13 +137,14 @@ namespace std {
130
  template <class T, class Allocator>
131
  bool operator>=(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
132
  template <class T, class Allocator>
133
  bool operator<=(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
134
 
135
- // specialized algorithms:
136
  template <class T, class Allocator>
137
- void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
 
138
  }
139
  ```
140
 
141
  #### `deque` constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
142
 
@@ -158,12 +166,11 @@ the specified allocator.
158
  *Requires:* `T` shall be `DefaultInsertable` into `*this`.
159
 
160
  *Complexity:* Linear in `n`.
161
 
162
  ``` cpp
163
- deque(size_type n, const T& value,
164
- const Allocator& = Allocator());
165
  ```
166
 
167
  *Effects:* Constructs a `deque` with `n` copies of `value`, using the
168
  specified allocator.
169
 
@@ -171,12 +178,11 @@ specified allocator.
171
 
172
  *Complexity:* Linear in `n`.
173
 
174
  ``` cpp
175
  template <class InputIterator>
176
- deque(InputIterator first, InputIterator last,
177
- const Allocator& = Allocator());
178
  ```
179
 
180
  *Effects:* Constructs a `deque` equal to the range \[`first`, `last`),
181
  using the specified allocator.
182
 
@@ -186,38 +192,47 @@ using the specified allocator.
186
 
187
  ``` cpp
188
  void resize(size_type sz);
189
  ```
190
 
191
- *Effects:* If `sz <= size()`, equivalent to calling `pop_back()`
192
- `size() - sz` times. If `size() < sz`, appends `sz - size()`
193
- default-inserted elements to the sequence.
194
 
195
  *Requires:* `T` shall be `MoveInsertable` and `DefaultInsertable` into
196
  `*this`.
197
 
198
  ``` cpp
199
  void resize(size_type sz, const T& c);
200
  ```
201
 
202
- *Effects:* If `sz <= size()`, equivalent to calling `pop_back()`
203
- `size() - sz` times. If `size() < sz`, appends `sz - size()` copies of
204
- `c` to the sequence.
205
 
206
  *Requires:* `T` shall be `CopyInsertable` into `*this`.
207
 
208
  ``` cpp
209
  void shrink_to_fit();
210
  ```
211
 
212
  *Requires:* `T` shall be `MoveInsertable` into `*this`.
213
 
 
 
 
 
 
 
 
 
 
214
  *Complexity:* Linear in the size of the sequence.
215
 
216
- *Remarks:* `shrink_to_fit` is a non-binding request to reduce memory use
217
- but does not change the size of the sequence. The request is non-binding
218
- to allow latitude for implementation-specific optimizations.
219
 
220
  #### `deque` modifiers <a id="deque.modifiers">[[deque.modifiers]]</a>
221
 
222
  ``` cpp
223
  iterator insert(const_iterator position, const T& x);
@@ -226,12 +241,12 @@ iterator insert(const_iterator position, size_type n, const T& x);
226
  template <class InputIterator>
227
  iterator insert(const_iterator position,
228
  InputIterator first, InputIterator last);
229
  iterator insert(const_iterator position, initializer_list<T>);
230
 
231
- template <class... Args> void emplace_front(Args&&... args);
232
- template <class... Args> void emplace_back(Args&&... args);
233
  template <class... Args> iterator emplace(const_iterator position, Args&&... args);
234
  void push_front(const T& x);
235
  void push_front(T&& x);
236
  void push_back(const T& x);
237
  void push_back(T&& x);
@@ -256,38 +271,41 @@ a deque always takes constant time and causes a single call to a
256
  constructor of `T`.
257
 
258
  ``` cpp
259
  iterator erase(const_iterator position);
260
  iterator erase(const_iterator first, const_iterator last);
 
 
261
  ```
262
 
263
  *Effects:* An erase operation that erases the last element of a deque
264
  invalidates only the past-the-end iterator and all iterators and
265
  references to the erased elements. An erase operation that erases the
266
- first element of a deque but not the last element invalidates only the
267
- erased elements. An erase operation that erases neither the first
268
- element nor the last element of a deque invalidates the past-the-end
269
- iterator and all iterators and references to all the elements of the
270
- deque.
271
 
272
- *Complexity:* The number of calls to the destructor is the same as the
273
- number of elements erased, but the number of calls to the assignment
274
- operator is no more than the lesser of the number of elements before the
275
- erased elements and the number of elements after the erased elements.
 
 
 
 
276
 
277
  *Throws:* Nothing unless an exception is thrown by the copy constructor,
278
  move constructor, assignment operator, or move assignment operator of
279
  `T`.
280
 
281
  #### `deque` specialized algorithms <a id="deque.special">[[deque.special]]</a>
282
 
283
  ``` cpp
284
  template <class T, class Allocator>
285
- void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
 
286
  ```
287
 
288
- *Effects:*
289
-
290
- ``` cpp
291
- x.swap(y);
292
- ```
293
 
 
1
  ### Class template `deque` <a id="deque">[[deque]]</a>
2
 
3
  #### Class template `deque` overview <a id="deque.overview">[[deque.overview]]</a>
4
 
5
+ A `deque` is a sequence container that supports random access iterators
6
+ ([[random.access.iterators]]). In addition, it supports constant time
7
  insert and erase operations at the beginning or the end; insert and
8
  erase in the middle take linear time. That is, a deque is especially
9
+ optimized for pushing and popping elements at the beginning and end.
10
+ Storage management is handled automatically.
11
 
12
  A `deque` satisfies all of the requirements of a container, of a
13
  reversible container (given in tables in  [[container.requirements]]),
14
  of a sequence container, including the optional sequence container
15
  requirements ([[sequence.reqmts]]), and of an allocator-aware container
 
22
  namespace std {
23
  template <class T, class Allocator = allocator<T>>
24
  class deque {
25
  public:
26
  // types:
27
+ using value_type = T;
28
+ using allocator_type = Allocator;
29
+ using pointer = typename allocator_traits<Allocator>::pointer;
30
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
31
+ using reference = value_type&;
32
+ using const_reference = const value_type&;
33
+ using size_type = implementation-defined; // see [container.requirements]
34
+ using difference_type = implementation-defined; // see [container.requirements]
35
+ using iterator = implementation-defined // type of deque::iterator; // see [container.requirements]
36
+ using const_iterator = implementation-defined // type of deque::const_iterator; // see [container.requirements]
37
+ using reverse_iterator = std::reverse_iterator<iterator>;
38
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
39
 
40
+ // [deque.cons], construct/copy/destroy
41
  deque() : deque(Allocator()) { }
42
  explicit deque(const Allocator&);
43
  explicit deque(size_type n, const Allocator& = Allocator());
44
  deque(size_type n, const T& value, const Allocator& = Allocator());
45
  template <class InputIterator>
 
50
  deque(deque&&, const Allocator&);
51
  deque(initializer_list<T>, const Allocator& = Allocator());
52
 
53
  ~deque();
54
  deque& operator=(const deque& x);
55
+ deque& operator=(deque&& x)
56
+ noexcept(allocator_traits<Allocator>::is_always_equal::value);
57
  deque& operator=(initializer_list<T>);
58
  template <class InputIterator>
59
  void assign(InputIterator first, InputIterator last);
60
  void assign(size_type n, const T& t);
61
  void assign(initializer_list<T>);
 
74
  const_iterator cbegin() const noexcept;
75
  const_iterator cend() const noexcept;
76
  const_reverse_iterator crbegin() const noexcept;
77
  const_reverse_iterator crend() const noexcept;
78
 
79
+ // [deque.capacity], capacity
80
+ bool empty() const noexcept;
81
  size_type size() const noexcept;
82
  size_type max_size() const noexcept;
83
  void resize(size_type sz);
84
  void resize(size_type sz, const T& c);
85
  void shrink_to_fit();
 
86
 
87
  // element access:
88
  reference operator[](size_type n);
89
  const_reference operator[](size_type n) const;
90
  reference at(size_type n);
 
92
  reference front();
93
  const_reference front() const;
94
  reference back();
95
  const_reference back() const;
96
 
97
+ // [deque.modifiers], modifiers
98
+ template <class... Args> reference emplace_front(Args&&... args);
99
+ template <class... Args> reference emplace_back(Args&&... args);
100
  template <class... Args> iterator emplace(const_iterator position, Args&&... args);
101
 
102
  void push_front(const T& x);
103
  void push_front(T&& x);
104
  void push_back(const T& x);
 
114
  void pop_front();
115
  void pop_back();
116
 
117
  iterator erase(const_iterator position);
118
  iterator erase(const_iterator first, const_iterator last);
119
+ void swap(deque&)
120
+ noexcept(allocator_traits<Allocator>::is_always_equal::value);
121
  void clear() noexcept;
122
  };
123
 
124
+ template<class InputIterator,
125
+ class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
126
+ deque(InputIterator, InputIterator, Allocator = Allocator())
127
+ -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;
128
+
129
  template <class T, class Allocator>
130
  bool operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
131
  template <class T, class Allocator>
132
  bool operator< (const deque<T, Allocator>& x, const deque<T, Allocator>& y);
133
  template <class T, class Allocator>
 
137
  template <class T, class Allocator>
138
  bool operator>=(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
139
  template <class T, class Allocator>
140
  bool operator<=(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
141
 
142
+ // [deque.special], specialized algorithms
143
  template <class T, class Allocator>
144
+ void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
145
+ noexcept(noexcept(x.swap(y)));
146
  }
147
  ```
148
 
149
  #### `deque` constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
150
 
 
166
  *Requires:* `T` shall be `DefaultInsertable` into `*this`.
167
 
168
  *Complexity:* Linear in `n`.
169
 
170
  ``` cpp
171
+ deque(size_type n, const T& value, const Allocator& = Allocator());
 
172
  ```
173
 
174
  *Effects:* Constructs a `deque` with `n` copies of `value`, using the
175
  specified allocator.
176
 
 
178
 
179
  *Complexity:* Linear in `n`.
180
 
181
  ``` cpp
182
  template <class InputIterator>
183
+ deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
184
  ```
185
 
186
  *Effects:* Constructs a `deque` equal to the range \[`first`, `last`),
187
  using the specified allocator.
188
 
 
192
 
193
  ``` cpp
194
  void resize(size_type sz);
195
  ```
196
 
197
+ *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
198
+ the sequence. Otherwise, appends `sz - size()` default-inserted elements
199
+ to the sequence.
200
 
201
  *Requires:* `T` shall be `MoveInsertable` and `DefaultInsertable` into
202
  `*this`.
203
 
204
  ``` cpp
205
  void resize(size_type sz, const T& c);
206
  ```
207
 
208
+ *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
209
+ the sequence. Otherwise, appends `sz - size()` copies of `c` to the
210
+ sequence.
211
 
212
  *Requires:* `T` shall be `CopyInsertable` into `*this`.
213
 
214
  ``` cpp
215
  void shrink_to_fit();
216
  ```
217
 
218
  *Requires:* `T` shall be `MoveInsertable` into `*this`.
219
 
220
+ *Effects:* `shrink_to_fit` is a non-binding request to reduce memory use
221
+ but does not change the size of the sequence.
222
+
223
+ [*Note 1*: The request is non-binding to allow latitude for
224
+ implementation-specific optimizations. — *end note*]
225
+
226
+ If an exception is thrown other than by the move constructor of a
227
+ non-`CopyInsertable` `T` there are no effects.
228
+
229
  *Complexity:* Linear in the size of the sequence.
230
 
231
+ *Remarks:* `shrink_to_fit` invalidates all the references, pointers, and
232
+ iterators referring to the elements in the sequence as well as the
233
+ past-the-end iterator.
234
 
235
  #### `deque` modifiers <a id="deque.modifiers">[[deque.modifiers]]</a>
236
 
237
  ``` cpp
238
  iterator insert(const_iterator position, const T& x);
 
241
  template <class InputIterator>
242
  iterator insert(const_iterator position,
243
  InputIterator first, InputIterator last);
244
  iterator insert(const_iterator position, initializer_list<T>);
245
 
246
+ template <class... Args> reference emplace_front(Args&&... args);
247
+ template <class... Args> reference emplace_back(Args&&... args);
248
  template <class... Args> iterator emplace(const_iterator position, Args&&... args);
249
  void push_front(const T& x);
250
  void push_front(T&& x);
251
  void push_back(const T& x);
252
  void push_back(T&& x);
 
271
  constructor of `T`.
272
 
273
  ``` cpp
274
  iterator erase(const_iterator position);
275
  iterator erase(const_iterator first, const_iterator last);
276
+ void pop_front();
277
+ void pop_back();
278
  ```
279
 
280
  *Effects:* An erase operation that erases the last element of a deque
281
  invalidates only the past-the-end iterator and all iterators and
282
  references to the erased elements. An erase operation that erases the
283
+ first element of a deque but not the last element invalidates only
284
+ iterators and references to the erased elements. An erase operation that
285
+ erases neither the first element nor the last element of a deque
286
+ invalidates the past-the-end iterator and all iterators and references
287
+ to all the elements of the deque.
288
 
289
+ [*Note 1*: `pop_front` and `pop_back` are erase
290
+ operations. — *end note*]
291
+
292
+ *Complexity:* The number of calls to the destructor of `T` is the same
293
+ as the number of elements erased, but the number of calls to the
294
+ assignment operator of `T` is no more than the lesser of the number of
295
+ elements before the erased elements and the number of elements after the
296
+ erased elements.
297
 
298
  *Throws:* Nothing unless an exception is thrown by the copy constructor,
299
  move constructor, assignment operator, or move assignment operator of
300
  `T`.
301
 
302
  #### `deque` specialized algorithms <a id="deque.special">[[deque.special]]</a>
303
 
304
  ``` cpp
305
  template <class T, class Allocator>
306
+ void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
307
+ noexcept(noexcept(x.swap(y)));
308
  ```
309
 
310
+ *Effects:* As if by `x.swap(y)`.
 
 
 
 
311