From Jason Turner

[set]

C++17 → C++20 9.4 KB 107 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpwqj_wrsl/{from.md → to.md} +46 -52
tmp/tmpwqj_wrsl/{from.md → to.md} RENAMED
@@ -1,32 +1,31 @@
1
  ### Class template `set` <a id="set">[[set]]</a>
2
 
3
- #### Class template `set` overview <a id="set.overview">[[set.overview]]</a>
4
 
5
  A `set` is an associative container that supports unique keys (contains
6
  at most one of each key value) and provides for fast retrieval of the
7
  keys themselves. The `set` class supports bidirectional iterators.
8
 
9
- A `set` satisfies all of the requirements of a container, of a
10
- reversible container ([[container.requirements]]), of an associative
11
- container ([[associative.reqmts]]), and of an allocator-aware container
12
- (Table  [[tab:containers.allocatoraware]]). A `set` also provides most
13
- operations described in  [[associative.reqmts]] for unique keys. This
14
- means that a `set` supports the `a_uniq` operations in 
15
- [[associative.reqmts]] but not the `a_eq` operations. For a `set<Key>`
16
- both the `key_type` and `value_type` are `Key`. Descriptions are
17
- provided here only for operations on `set` that are not described in one
18
- of these tables and for operations where there is additional semantic
19
- information.
20
 
21
  ``` cpp
22
  namespace std {
23
  template<class Key, class Compare = less<Key>,
24
  class Allocator = allocator<Key>>
25
  class set {
26
  public:
27
- // types:
28
  using key_type = Key;
29
  using key_compare = Compare;
30
  using value_type = Key;
31
  using value_compare = Compare;
32
  using allocator_type = Allocator;
@@ -39,11 +38,11 @@ namespace std {
39
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
40
  using const_iterator = implementation-defined // type of set::const_iterator; // see [container.requirements]
41
  using reverse_iterator = std::reverse_iterator<iterator>;
42
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
43
  using node_type = unspecified;
44
- using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
45
 
46
  // [set.cons], construct/copy/destroy
47
  set() : set(Compare()) { }
48
  explicit set(const Compare& comp, const Allocator& = Allocator());
49
  template<class InputIterator>
@@ -67,11 +66,11 @@ namespace std {
67
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
68
  is_nothrow_move_assignable_v<Compare>);
69
  set& operator=(initializer_list<value_type>);
70
  allocator_type get_allocator() const noexcept;
71
 
72
- // iterators:
73
  iterator begin() noexcept;
74
  const_iterator begin() const noexcept;
75
  iterator end() noexcept;
76
  const_iterator end() const noexcept;
77
 
@@ -83,16 +82,16 @@ namespace std {
83
  const_iterator cbegin() const noexcept;
84
  const_iterator cend() const noexcept;
85
  const_reverse_iterator crbegin() const noexcept;
86
  const_reverse_iterator crend() const noexcept;
87
 
88
- // capacity:
89
- bool empty() const noexcept;
90
  size_type size() const noexcept;
91
  size_type max_size() const noexcept;
92
 
93
- // modifiers:
94
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
95
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
96
  pair<iterator,bool> insert(const value_type& x);
97
  pair<iterator,bool> insert(value_type&& x);
98
  iterator insert(const_iterator position, const value_type& x);
@@ -122,23 +121,26 @@ namespace std {
122
  template<class C2>
123
  void merge(multiset<Key, C2, Allocator>& source);
124
  template<class C2>
125
  void merge(multiset<Key, C2, Allocator>&& source);
126
 
127
- // observers:
128
  key_compare key_comp() const;
129
  value_compare value_comp() const;
130
 
131
- // set operations:
132
  iterator find(const key_type& x);
133
  const_iterator find(const key_type& x) const;
134
  template<class K> iterator find(const K& x);
135
  template<class K> const_iterator find(const K& x) const;
136
 
137
  size_type count(const key_type& x) const;
138
  template<class K> size_type count(const K& x) const;
139
 
 
 
 
140
  iterator lower_bound(const key_type& x);
141
  const_iterator lower_bound(const key_type& x) const;
142
  template<class K> iterator lower_bound(const K& x);
143
  template<class K> const_iterator lower_bound(const K& x) const;
144
 
@@ -154,56 +156,37 @@ namespace std {
154
  template<class K>
155
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
156
  };
157
 
158
  template<class InputIterator,
159
- class Compare = less<typename iterator_traits<InputIterator>::value_type>,
160
- class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
161
  set(InputIterator, InputIterator,
162
  Compare = Compare(), Allocator = Allocator())
163
- -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>;
164
 
165
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
166
  set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
167
  -> set<Key, Compare, Allocator>;
168
 
169
  template<class InputIterator, class Allocator>
170
  set(InputIterator, InputIterator, Allocator)
171
- -> set<typename iterator_traits<InputIterator>::value_type,
172
- less<typename iterator_traits<InputIterator>::value_type>, Allocator>;
173
 
174
  template<class Key, class Allocator>
175
  set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>;
176
 
177
- template <class Key, class Compare, class Allocator>
178
- bool operator==(const set<Key, Compare, Allocator>& x,
179
- const set<Key, Compare, Allocator>& y);
180
- template <class Key, class Compare, class Allocator>
181
- bool operator< (const set<Key, Compare, Allocator>& x,
182
- const set<Key, Compare, Allocator>& y);
183
- template <class Key, class Compare, class Allocator>
184
- bool operator!=(const set<Key, Compare, Allocator>& x,
185
- const set<Key, Compare, Allocator>& y);
186
- template <class Key, class Compare, class Allocator>
187
- bool operator> (const set<Key, Compare, Allocator>& x,
188
- const set<Key, Compare, Allocator>& y);
189
- template <class Key, class Compare, class Allocator>
190
- bool operator>=(const set<Key, Compare, Allocator>& x,
191
- const set<Key, Compare, Allocator>& y);
192
- template <class Key, class Compare, class Allocator>
193
- bool operator<=(const set<Key, Compare, Allocator>& x,
194
- const set<Key, Compare, Allocator>& y);
195
-
196
- // [set.special], specialized algorithms
197
  template<class Key, class Compare, class Allocator>
198
  void swap(set<Key, Compare, Allocator>& x,
199
  set<Key, Compare, Allocator>& y)
200
  noexcept(noexcept(x.swap(y)));
201
  }
202
  ```
203
 
204
- #### `set` constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
205
 
206
  ``` cpp
207
  explicit set(const Compare& comp, const Allocator& = Allocator());
208
  ```
209
 
@@ -223,16 +206,27 @@ object and allocator, and inserts elements from the range \[`first`,
223
  `last`).
224
 
225
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
226
  sorted using `comp` and otherwise N log N, where N is `last - first`.
227
 
228
- #### `set` specialized algorithms <a id="set.special">[[set.special]]</a>
229
 
230
  ``` cpp
231
- template <class Key, class Compare, class Allocator>
232
- void swap(set<Key, Compare, Allocator>& x,
233
- set<Key, Compare, Allocator>& y)
234
- noexcept(noexcept(x.swap(y)));
235
  ```
236
 
237
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
238
 
 
1
  ### Class template `set` <a id="set">[[set]]</a>
2
 
3
+ #### Overview <a id="set.overview">[[set.overview]]</a>
4
 
5
  A `set` is an associative container that supports unique keys (contains
6
  at most one of each key value) and provides for fast retrieval of the
7
  keys themselves. The `set` class supports bidirectional iterators.
8
 
9
+ A `set` meets all of the requirements of a container, of a reversible
10
+ container [[container.requirements]], of an associative container
11
+ [[associative.reqmts]], and of an allocator-aware container (
12
+ [[container.alloc.req]]). A `set` also provides most operations
13
+ described in  [[associative.reqmts]] for unique keys. This means that a
14
+ `set` supports the `a_uniq` operations in  [[associative.reqmts]] but
15
+ not the `a_eq` operations. For a `set<Key>` both the `key_type` and
16
+ `value_type` are `Key`. Descriptions are provided here only for
17
+ operations on `set` that are not described in one of these tables and
18
+ for operations where there is additional semantic information.
 
19
 
20
  ``` cpp
21
  namespace std {
22
  template<class Key, class Compare = less<Key>,
23
  class Allocator = allocator<Key>>
24
  class set {
25
  public:
26
+ // types
27
  using key_type = Key;
28
  using key_compare = Compare;
29
  using value_type = Key;
30
  using value_compare = Compare;
31
  using allocator_type = Allocator;
 
38
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
39
  using const_iterator = implementation-defined // type of set::const_iterator; // see [container.requirements]
40
  using reverse_iterator = std::reverse_iterator<iterator>;
41
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
42
  using node_type = unspecified;
43
+ using insert_return_type = insert-return-type<iterator, node_type>;
44
 
45
  // [set.cons], construct/copy/destroy
46
  set() : set(Compare()) { }
47
  explicit set(const Compare& comp, const Allocator& = Allocator());
48
  template<class InputIterator>
 
66
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
67
  is_nothrow_move_assignable_v<Compare>);
68
  set& operator=(initializer_list<value_type>);
69
  allocator_type get_allocator() const noexcept;
70
 
71
+ // iterators
72
  iterator begin() noexcept;
73
  const_iterator begin() const noexcept;
74
  iterator end() noexcept;
75
  const_iterator end() const noexcept;
76
 
 
82
  const_iterator cbegin() const noexcept;
83
  const_iterator cend() const noexcept;
84
  const_reverse_iterator crbegin() const noexcept;
85
  const_reverse_iterator crend() const noexcept;
86
 
87
+ // capacity
88
+ [[nodiscard]] bool empty() const noexcept;
89
  size_type size() const noexcept;
90
  size_type max_size() const noexcept;
91
 
92
+ // modifiers
93
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
94
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
95
  pair<iterator,bool> insert(const value_type& x);
96
  pair<iterator,bool> insert(value_type&& x);
97
  iterator insert(const_iterator position, const value_type& x);
 
121
  template<class C2>
122
  void merge(multiset<Key, C2, Allocator>& source);
123
  template<class C2>
124
  void merge(multiset<Key, C2, Allocator>&& source);
125
 
126
+ // observers
127
  key_compare key_comp() const;
128
  value_compare value_comp() const;
129
 
130
+ // set operations
131
  iterator find(const key_type& x);
132
  const_iterator find(const key_type& x) const;
133
  template<class K> iterator find(const K& x);
134
  template<class K> const_iterator find(const K& x) const;
135
 
136
  size_type count(const key_type& x) const;
137
  template<class K> size_type count(const K& x) const;
138
 
139
+ bool contains(const key_type& x) const;
140
+ template<class K> bool contains(const K& x) const;
141
+
142
  iterator lower_bound(const key_type& x);
143
  const_iterator lower_bound(const key_type& x) const;
144
  template<class K> iterator lower_bound(const K& x);
145
  template<class K> const_iterator lower_bound(const K& x) const;
146
 
 
156
  template<class K>
157
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
158
  };
159
 
160
  template<class InputIterator,
161
+ class Compare = less<iter-value-type<InputIterator>>,
162
+ class Allocator = allocator<iter-value-type<InputIterator>>>
163
  set(InputIterator, InputIterator,
164
  Compare = Compare(), Allocator = Allocator())
165
+ -> set<iter-value-type<InputIterator>, Compare, Allocator>;
166
 
167
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
168
  set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
169
  -> set<Key, Compare, Allocator>;
170
 
171
  template<class InputIterator, class Allocator>
172
  set(InputIterator, InputIterator, Allocator)
173
+ -> set<iter-value-type<InputIterator>,
174
+ less<iter-value-type<InputIterator>>, Allocator>;
175
 
176
  template<class Key, class Allocator>
177
  set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>;
178
 
179
+ // swap
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
180
  template<class Key, class Compare, class Allocator>
181
  void swap(set<Key, Compare, Allocator>& x,
182
  set<Key, Compare, Allocator>& y)
183
  noexcept(noexcept(x.swap(y)));
184
  }
185
  ```
186
 
187
+ #### Constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
188
 
189
  ``` cpp
190
  explicit set(const Compare& comp, const Allocator& = Allocator());
191
  ```
192
 
 
206
  `last`).
207
 
208
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
209
  sorted using `comp` and otherwise N log N, where N is `last - first`.
210
 
211
+ #### Erasure <a id="set.erasure">[[set.erasure]]</a>
212
 
213
  ``` cpp
214
+ template<class Key, class Compare, class Allocator, class Predicate>
215
+ typename set<Key, Compare, Allocator>::size_type
216
+ erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
 
217
  ```
218
 
219
+ *Effects:* Equivalent to:
220
+
221
+ ``` cpp
222
+ auto original_size = c.size();
223
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
224
+ if (pred(*i)) {
225
+ i = c.erase(i);
226
+ } else {
227
+ ++i;
228
+ }
229
+ }
230
+ return original_size - c.size();
231
+ ```
232