From Jason Turner

[forwardlist]

C++14 → C++17 13.1 KB 116 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/tmp043kib9l/{from.md → to.md} +56 -43
tmp/tmp043kib9l/{from.md → to.md} RENAMED
@@ -3,14 +3,15 @@
3
  #### Class template `forward_list` overview <a id="forwardlist.overview">[[forwardlist.overview]]</a>
4
 
5
  A `forward_list` is a container that supports forward iterators and
6
  allows constant time insert and erase operations anywhere within the
7
  sequence, with storage management handled automatically. Fast random
8
- access to list elements is not supported. It is intended that
9
- `forward_list` have zero space or time overhead relative to a
10
- hand-written C-style singly linked list. Features that would conflict
11
- with that goal have been omitted.
 
12
 
13
  A `forward_list` satisfies all of the requirements of a container
14
  (Table  [[tab:containers.container.requirements]]), except that the
15
  `size()` member function is not provided and `operator==` has linear
16
  complexity. A `forward_list` also satisfies all of the requirements for
@@ -20,34 +21,34 @@ In addition, a `forward_list` provides the `assign` member functions
20
  optional container requirements (Table 
21
  [[tab:containers.sequence.optional]]). Descriptions are provided here
22
  only for operations on `forward_list` that are not described in that
23
  table or for operations where there is additional semantic information.
24
 
25
- Modifying any list requires access to the element preceding the first
26
- element of interest, but in a `forward_list` there is no constant-time
27
- way to access a preceding element. For this reason, ranges that are
28
- modified, such as those supplied to `erase` and `splice`, must be open
29
- at the beginning.
30
 
31
  ``` cpp
32
  namespace std {
33
  template <class T, class Allocator = allocator<T>>
34
  class forward_list {
35
  public:
36
  // types:
37
- typedef value_type& reference;
38
- typedef const value_type& const_reference;
39
- typedef implementation-defined iterator; // See [container.requirements]
40
- typedef implementation-defined const_iterator; // See [container.requirements]
41
- typedef implementation-defined size_type; // See [container.requirements]
42
- typedef implementation-defined difference_type;// See [container.requirements]
43
- typedef T value_type;
44
- typedef Allocator allocator_type;
45
- typedef typename allocator_traits<Allocator>::pointer pointer;
46
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
47
 
48
- // [forwardlist.cons], construct/copy/destroy:
49
  forward_list() : forward_list(Allocator()) { }
50
  explicit forward_list(const Allocator&);
51
  explicit forward_list(size_type n, const Allocator& = Allocator());
52
  forward_list(size_type n, const T& value,
53
  const Allocator& = Allocator());
@@ -59,19 +60,20 @@ namespace std {
59
  forward_list(const forward_list& x, const Allocator&);
60
  forward_list(forward_list&& x, const Allocator&);
61
  forward_list(initializer_list<T>, const Allocator& = Allocator());
62
  ~forward_list();
63
  forward_list& operator=(const forward_list& x);
64
- forward_list& operator=(forward_list&& x);
 
65
  forward_list& operator=(initializer_list<T>);
66
  template <class InputIterator>
67
  void assign(InputIterator first, InputIterator last);
68
  void assign(size_type n, const T& t);
69
  void assign(initializer_list<T>);
70
  allocator_type get_allocator() const noexcept;
71
 
72
- // [forwardlist.iter], iterators:
73
  iterator before_begin() noexcept;
74
  const_iterator before_begin() const noexcept;
75
  iterator begin() noexcept;
76
  const_iterator begin() const noexcept;
77
  iterator end() noexcept;
@@ -83,16 +85,16 @@ namespace std {
83
 
84
  // capacity:
85
  bool empty() const noexcept;
86
  size_type max_size() const noexcept;
87
 
88
- // [forwardlist.access], element access:
89
  reference front();
90
  const_reference front() const;
91
 
92
- // [forwardlist.modifiers], modifiers:
93
- template <class... Args> void emplace_front(Args&&... args);
94
  void push_front(const T& x);
95
  void push_front(T&& x);
96
  void pop_front();
97
 
98
  template <class... Args> iterator emplace_after(const_iterator position, Args&&... args);
@@ -104,17 +106,18 @@ namespace std {
104
  iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
105
  iterator insert_after(const_iterator position, initializer_list<T> il);
106
 
107
  iterator erase_after(const_iterator position);
108
  iterator erase_after(const_iterator position, const_iterator last);
109
- void swap(forward_list&);
 
110
 
111
  void resize(size_type sz);
112
  void resize(size_type sz, const value_type& c);
113
  void clear() noexcept;
114
 
115
- // [forwardlist.ops], forward_list operations:
116
  void splice_after(const_iterator position, forward_list& x);
117
  void splice_after(const_iterator position, forward_list&& x);
118
  void splice_after(const_iterator position, forward_list& x,
119
  const_iterator i);
120
  void splice_after(const_iterator position, forward_list&& x,
@@ -139,11 +142,15 @@ namespace std {
139
  template <class Compare> void sort(Compare comp);
140
 
141
  void reverse() noexcept;
142
  };
143
 
144
- // Comparison operators
 
 
 
 
145
  template <class T, class Allocator>
146
  bool operator==(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
147
  template <class T, class Allocator>
148
  bool operator< (const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
149
  template <class T, class Allocator>
@@ -153,16 +160,23 @@ namespace std {
153
  template <class T, class Allocator>
154
  bool operator>=(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
155
  template <class T, class Allocator>
156
  bool operator<=(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
157
 
158
- // [forwardlist.spec], specialized algorithms:
159
  template <class T, class Allocator>
160
- void swap(forward_list<T,Allocator>& x, forward_list<T,Allocator>& y);
 
161
  }
162
  ```
163
 
 
 
 
 
 
 
164
  #### `forward_list` constructors, copy, assignment <a id="forwardlist.cons">[[forwardlist.cons]]</a>
165
 
166
  ``` cpp
167
  explicit forward_list(const Allocator&);
168
  ```
@@ -239,11 +253,11 @@ elements into a `forward_list` is linear in `n`, and the number of calls
239
  to the copy or move constructor of `T` is exactly equal to `n`. Erasing
240
  `n` elements from a `forward_list` is linear in `n` and the number of
241
  calls to the destructor of type `T` is exactly equal to `n`.
242
 
243
  ``` cpp
244
- template <class... Args> void emplace_front(Args&&... args);
245
  ```
246
 
247
  *Effects:* Inserts an object of type `value_type` constructed with
248
  `value_type(std::forward<Args>(args)...)` at the beginning of the list.
249
 
@@ -256,11 +270,11 @@ void push_front(T&& x);
256
 
257
  ``` cpp
258
  void pop_front();
259
  ```
260
 
261
- *Effects:* `erase_after(before_begin())`
262
 
263
  ``` cpp
264
  iterator insert_after(const_iterator position, const T& x);
265
  iterator insert_after(const_iterator position, T&& x);
266
  ```
@@ -363,14 +377,12 @@ end of the list.
363
  void resize(size_type sz, const value_type& c);
364
  ```
365
 
366
  *Effects:* If `sz < distance(begin(), end())`, erases the last
367
  `distance(begin(), end()) - sz` elements from the list. Otherwise,
368
- inserts `sz - distance(begin(), end())` elements at the end of the list
369
- such that each new element, `e`, is initialized by a method equivalent
370
- to calling
371
- `allocator_traits<allocator_type>::construct(get_allocator(), std::addressof(e), c)`.
372
 
373
  *Requires:* `T` shall be `CopyInsertable` into `*this`.
374
 
375
  ``` cpp
376
  void clear() noexcept;
@@ -397,11 +409,11 @@ those same elements but as members of `*this`. Iterators referring to
397
  the moved elements will continue to refer to their elements, but they
398
  now behave as iterators into `*this`, not into `x`.
399
 
400
  *Throws:* Nothing.
401
 
402
- *Complexity:* 𝑂(distance(x.begin(), x.end()))
403
 
404
  ``` cpp
405
  void splice_after(const_iterator position, forward_list& x, const_iterator i);
406
  void splice_after(const_iterator position, forward_list&& x, const_iterator i);
407
  ```
@@ -440,20 +452,20 @@ dereferenceable. `position` is not an iterator in the range (`first`,
440
  the moved elements of `x` now refer to those same elements but as
441
  members of `*this`. Iterators referring to the moved elements will
442
  continue to refer to their elements, but they now behave as iterators
443
  into `*this`, not into `x`.
444
 
445
- *Complexity:* 𝑂(distance(first, last))
446
 
447
  ``` cpp
448
  void remove(const T& value);
449
  template <class Predicate> void remove_if(Predicate pred);
450
  ```
451
 
452
  *Effects:* Erases all the elements in the list referred by a list
453
  iterator `i` for which the following conditions hold: `*i == value` (for
454
- `remove()`), `pred(*i)` is true (for `remove_if()`). Invalidates only
455
  the iterators and references to the erased elements.
456
 
457
  *Throws:* Nothing unless an exception is thrown by the equality
458
  comparison or the predicate.
459
 
@@ -499,11 +511,11 @@ references to the moved elements of `x` now refer to those same elements
499
  but as members of `*this`. Iterators referring to the moved elements
500
  will continue to refer to their elements, but they now behave as
501
  iterators into `*this`, not into `x`.
502
 
503
  *Remarks:* Stable ([[algorithm.stable]]). The behavior is undefined if
504
- `this->get_allocator() != x.get_allocator()`.
505
 
506
  *Complexity:* At most
507
  `distance(begin(), end()) + distance(x.begin(), x.end()) - 1`
508
  comparisons.
509
 
@@ -515,11 +527,11 @@ template <class Compare> void sort(Compare comp);
515
  *Requires:* `operator<` (for the version with no arguments) or `comp`
516
  (for the version with a comparison argument) defines a strict weak
517
  ordering ([[alg.sorting]]).
518
 
519
  *Effects:* Sorts the list according to the `operator<` or the `comp`
520
- function object. If an exception is thrown the order of the elements in
521
  `*this` is unspecified. Does not affect the validity of iterators and
522
  references.
523
 
524
  *Remarks:* Stable ([[algorithm.stable]]).
525
 
@@ -537,10 +549,11 @@ affect the validity of iterators and references.
537
 
538
  #### `forward_list` specialized algorithms <a id="forwardlist.spec">[[forwardlist.spec]]</a>
539
 
540
  ``` cpp
541
  template <class T, class Allocator>
542
- void swap(forward_list<T,Allocator>& x, forward_list<T,Allocator>& y);
 
543
  ```
544
 
545
- *Effects:* `x.swap(y)`
546
 
 
3
  #### Class template `forward_list` overview <a id="forwardlist.overview">[[forwardlist.overview]]</a>
4
 
5
  A `forward_list` is a container that supports forward iterators and
6
  allows constant time insert and erase operations anywhere within the
7
  sequence, with storage management handled automatically. Fast random
8
+ access to list elements is not supported.
9
+
10
+ [*Note 1*: It is intended that `forward_list` have zero space or time
11
+ overhead relative to a hand-written C-style singly linked list. Features
12
+ that would conflict with that goal have been omitted. — *end note*]
13
 
14
  A `forward_list` satisfies all of the requirements of a container
15
  (Table  [[tab:containers.container.requirements]]), except that the
16
  `size()` member function is not provided and `operator==` has linear
17
  complexity. A `forward_list` also satisfies all of the requirements for
 
21
  optional container requirements (Table 
22
  [[tab:containers.sequence.optional]]). Descriptions are provided here
23
  only for operations on `forward_list` that are not described in that
24
  table or for operations where there is additional semantic information.
25
 
26
+ [*Note 2*: Modifying any list requires access to the element preceding
27
+ the first element of interest, but in a `forward_list` there is no
28
+ constant-time way to access a preceding element. For this reason, ranges
29
+ that are modified, such as those supplied to `erase` and `splice`, must
30
+ be open at the beginning. — *end note*]
31
 
32
  ``` cpp
33
  namespace std {
34
  template <class T, class Allocator = allocator<T>>
35
  class forward_list {
36
  public:
37
  // types:
38
+ using value_type = T;
39
+ using allocator_type = Allocator;
40
+ using pointer = typename allocator_traits<Allocator>::pointer;
41
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
42
+ using reference = value_type&;
43
+ using const_reference = const value_type&;
44
+ using size_type = implementation-defined; // see [container.requirements]
45
+ using difference_type = implementation-defined; // see [container.requirements]
46
+ using iterator = implementation-defined // type of forward_list::iterator; // see [container.requirements]
47
+ using const_iterator = implementation-defined // type of forward_list::const_iterator; // see [container.requirements]
48
 
49
+ // [forwardlist.cons], construct/copy/destroy
50
  forward_list() : forward_list(Allocator()) { }
51
  explicit forward_list(const Allocator&);
52
  explicit forward_list(size_type n, const Allocator& = Allocator());
53
  forward_list(size_type n, const T& value,
54
  const Allocator& = Allocator());
 
60
  forward_list(const forward_list& x, const Allocator&);
61
  forward_list(forward_list&& x, const Allocator&);
62
  forward_list(initializer_list<T>, const Allocator& = Allocator());
63
  ~forward_list();
64
  forward_list& operator=(const forward_list& x);
65
+ forward_list& operator=(forward_list&& x)
66
+ noexcept(allocator_traits<Allocator>::is_always_equal::value);
67
  forward_list& operator=(initializer_list<T>);
68
  template <class InputIterator>
69
  void assign(InputIterator first, InputIterator last);
70
  void assign(size_type n, const T& t);
71
  void assign(initializer_list<T>);
72
  allocator_type get_allocator() const noexcept;
73
 
74
+ // [forwardlist.iter], iterators
75
  iterator before_begin() noexcept;
76
  const_iterator before_begin() const noexcept;
77
  iterator begin() noexcept;
78
  const_iterator begin() const noexcept;
79
  iterator end() noexcept;
 
85
 
86
  // capacity:
87
  bool empty() const noexcept;
88
  size_type max_size() const noexcept;
89
 
90
+ // [forwardlist.access], element access
91
  reference front();
92
  const_reference front() const;
93
 
94
+ // [forwardlist.modifiers], modifiers
95
+ template <class... Args> reference emplace_front(Args&&... args);
96
  void push_front(const T& x);
97
  void push_front(T&& x);
98
  void pop_front();
99
 
100
  template <class... Args> iterator emplace_after(const_iterator position, Args&&... args);
 
106
  iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
107
  iterator insert_after(const_iterator position, initializer_list<T> il);
108
 
109
  iterator erase_after(const_iterator position);
110
  iterator erase_after(const_iterator position, const_iterator last);
111
+ void swap(forward_list&)
112
+ noexcept(allocator_traits<Allocator>::is_always_equal::value);
113
 
114
  void resize(size_type sz);
115
  void resize(size_type sz, const value_type& c);
116
  void clear() noexcept;
117
 
118
+ // [forwardlist.ops], forward_list operations
119
  void splice_after(const_iterator position, forward_list& x);
120
  void splice_after(const_iterator position, forward_list&& x);
121
  void splice_after(const_iterator position, forward_list& x,
122
  const_iterator i);
123
  void splice_after(const_iterator position, forward_list&& x,
 
142
  template <class Compare> void sort(Compare comp);
143
 
144
  void reverse() noexcept;
145
  };
146
 
147
+ template<class InputIterator,
148
+ class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
149
+ forward_list(InputIterator, InputIterator, Allocator = Allocator())
150
+ -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>;
151
+
152
  template <class T, class Allocator>
153
  bool operator==(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
154
  template <class T, class Allocator>
155
  bool operator< (const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
156
  template <class T, class Allocator>
 
160
  template <class T, class Allocator>
161
  bool operator>=(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
162
  template <class T, class Allocator>
163
  bool operator<=(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
164
 
165
+ // [forwardlist.spec], specialized algorithms
166
  template <class T, class Allocator>
167
+ void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
168
+ noexcept(noexcept(x.swap(y)));
169
  }
170
  ```
171
 
172
+ An incomplete type `T` may be used when instantiating `forward_list` if
173
+ the allocator satisfies the allocator completeness requirements (
174
+ [[allocator.requirements.completeness]]). `T` shall be complete before
175
+ any member of the resulting specialization of `forward_list` is
176
+ referenced.
177
+
178
  #### `forward_list` constructors, copy, assignment <a id="forwardlist.cons">[[forwardlist.cons]]</a>
179
 
180
  ``` cpp
181
  explicit forward_list(const Allocator&);
182
  ```
 
253
  to the copy or move constructor of `T` is exactly equal to `n`. Erasing
254
  `n` elements from a `forward_list` is linear in `n` and the number of
255
  calls to the destructor of type `T` is exactly equal to `n`.
256
 
257
  ``` cpp
258
+ template <class... Args> reference emplace_front(Args&&... args);
259
  ```
260
 
261
  *Effects:* Inserts an object of type `value_type` constructed with
262
  `value_type(std::forward<Args>(args)...)` at the beginning of the list.
263
 
 
270
 
271
  ``` cpp
272
  void pop_front();
273
  ```
274
 
275
+ *Effects:* As if by `erase_after(before_begin())`.
276
 
277
  ``` cpp
278
  iterator insert_after(const_iterator position, const T& x);
279
  iterator insert_after(const_iterator position, T&& x);
280
  ```
 
377
  void resize(size_type sz, const value_type& c);
378
  ```
379
 
380
  *Effects:* If `sz < distance(begin(), end())`, erases the last
381
  `distance(begin(), end()) - sz` elements from the list. Otherwise,
382
+ inserts `sz - distance(begin(), end())` copies of `c` at the end of the
383
+ list.
 
 
384
 
385
  *Requires:* `T` shall be `CopyInsertable` into `*this`.
386
 
387
  ``` cpp
388
  void clear() noexcept;
 
409
  the moved elements will continue to refer to their elements, but they
410
  now behave as iterators into `*this`, not into `x`.
411
 
412
  *Throws:* Nothing.
413
 
414
+ *Complexity:* 𝑂(`distance(x.begin(), x.end())`)
415
 
416
  ``` cpp
417
  void splice_after(const_iterator position, forward_list& x, const_iterator i);
418
  void splice_after(const_iterator position, forward_list&& x, const_iterator i);
419
  ```
 
452
  the moved elements of `x` now refer to those same elements but as
453
  members of `*this`. Iterators referring to the moved elements will
454
  continue to refer to their elements, but they now behave as iterators
455
  into `*this`, not into `x`.
456
 
457
+ *Complexity:* 𝑂(`distance(first, last)`)
458
 
459
  ``` cpp
460
  void remove(const T& value);
461
  template <class Predicate> void remove_if(Predicate pred);
462
  ```
463
 
464
  *Effects:* Erases all the elements in the list referred by a list
465
  iterator `i` for which the following conditions hold: `*i == value` (for
466
+ `remove()`), `pred(*i)` is `true` (for `remove_if()`). Invalidates only
467
  the iterators and references to the erased elements.
468
 
469
  *Throws:* Nothing unless an exception is thrown by the equality
470
  comparison or the predicate.
471
 
 
511
  but as members of `*this`. Iterators referring to the moved elements
512
  will continue to refer to their elements, but they now behave as
513
  iterators into `*this`, not into `x`.
514
 
515
  *Remarks:* Stable ([[algorithm.stable]]). The behavior is undefined if
516
+ `get_allocator() != x.get_allocator()`.
517
 
518
  *Complexity:* At most
519
  `distance(begin(), end()) + distance(x.begin(), x.end()) - 1`
520
  comparisons.
521
 
 
527
  *Requires:* `operator<` (for the version with no arguments) or `comp`
528
  (for the version with a comparison argument) defines a strict weak
529
  ordering ([[alg.sorting]]).
530
 
531
  *Effects:* Sorts the list according to the `operator<` or the `comp`
532
+ function object. If an exception is thrown, the order of the elements in
533
  `*this` is unspecified. Does not affect the validity of iterators and
534
  references.
535
 
536
  *Remarks:* Stable ([[algorithm.stable]]).
537
 
 
549
 
550
  #### `forward_list` specialized algorithms <a id="forwardlist.spec">[[forwardlist.spec]]</a>
551
 
552
  ``` cpp
553
  template <class T, class Allocator>
554
+ void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
555
+ noexcept(noexcept(x.swap(y)));
556
  ```
557
 
558
+ *Effects:* As if by `x.swap(y)`.
559