From Jason Turner

[unord.multiset]

C++17 → C++20 10.9 KB 120 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/tmpk4g5lfpq/{from.md → to.md} +65 -48
tmp/tmpk4g5lfpq/{from.md → to.md} RENAMED
@@ -1,38 +1,38 @@
1
  ### Class template `unordered_multiset` <a id="unord.multiset">[[unord.multiset]]</a>
2
 
3
- #### Class template `unordered_multiset` overview <a id="unord.multiset.overview">[[unord.multiset.overview]]</a>
4
 
5
  An `unordered_multiset` is an unordered associative container that
6
  supports equivalent keys (an instance of `unordered_multiset` may
7
  contain multiple copies of the same key value) and in which each
8
  element’s key is the element itself. The `unordered_multiset` class
9
  supports forward iterators.
10
 
11
- An `unordered_multiset` satisfies all of the requirements of a
12
- container, of an unordered associative container, and of an
13
- allocator-aware container (Table  [[tab:containers.allocatoraware]]). It
14
- provides the operations described in the preceding requirements table
15
- for equivalent keys; that is, an `unordered_multiset` supports the
16
- `a_eq` operations in that table, not the `a_uniq` operations. For an
17
- `unordered_multiset<Key>` the `key type` and the value type are both
18
- `Key`. The `iterator` and `const_iterator` types are both constant
19
- iterator types. It is unspecified whether they are the same type.
20
 
21
- This section only describes operations on `unordered_multiset` that are
22
- not described in one of the requirement tables, or for which there is
23
- additional semantic information.
24
 
25
  ``` cpp
26
  namespace std {
27
  template<class Key,
28
  class Hash = hash<Key>,
29
  class Pred = equal_to<Key>,
30
  class Allocator = allocator<Key>>
31
  class unordered_multiset {
32
  public:
33
- // types:
34
  using key_type = Key;
35
  using value_type = Key;
36
  using hasher = Hash;
37
  using key_equal = Pred;
38
  using allocator_type = Allocator;
@@ -94,24 +94,24 @@ namespace std {
94
  is_nothrow_move_assignable_v<Hash> &&
95
  is_nothrow_move_assignable_v<Pred>);
96
  unordered_multiset& operator=(initializer_list<value_type>);
97
  allocator_type get_allocator() const noexcept;
98
 
99
- // iterators:
100
  iterator begin() noexcept;
101
  const_iterator begin() const noexcept;
102
  iterator end() noexcept;
103
  const_iterator end() const noexcept;
104
  const_iterator cbegin() const noexcept;
105
  const_iterator cend() const noexcept;
106
 
107
- // capacity:
108
- bool empty() const noexcept;
109
  size_type size() const noexcept;
110
  size_type max_size() const noexcept;
111
 
112
- // modifiers:
113
  template<class... Args> iterator emplace(Args&&... args);
114
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
115
  iterator insert(const value_type& obj);
116
  iterator insert(value_type&& obj);
117
  iterator insert(const_iterator hint, const value_type& obj);
@@ -141,22 +141,35 @@ namespace std {
141
  template<class H2, class P2>
142
  void merge(unordered_set<Key, H2, P2, Allocator>& source);
143
  template<class H2, class P2>
144
  void merge(unordered_set<Key, H2, P2, Allocator>&& source);
145
 
146
- // observers:
147
  hasher hash_function() const;
148
  key_equal key_eq() const;
149
 
150
- // set operations:
151
  iterator find(const key_type& k);
152
  const_iterator find(const key_type& k) const;
 
 
 
 
153
  size_type count(const key_type& k) const;
 
 
 
 
 
154
  pair<iterator, iterator> equal_range(const key_type& k);
155
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
 
 
 
156
 
157
- // bucket interface:
158
  size_type bucket_count() const noexcept;
159
  size_type max_bucket_count() const noexcept;
160
  size_type bucket_size(size_type n) const;
161
  size_type bucket(const key_type& k) const;
162
  local_iterator begin(size_type n);
@@ -164,75 +177,68 @@ namespace std {
164
  local_iterator end(size_type n);
165
  const_local_iterator end(size_type n) const;
166
  const_local_iterator cbegin(size_type n) const;
167
  const_local_iterator cend(size_type n) const;
168
 
169
- // hash policy:
170
  float load_factor() const noexcept;
171
  float max_load_factor() const noexcept;
172
  void max_load_factor(float z);
173
  void rehash(size_type n);
174
  void reserve(size_type n);
175
  };
176
 
177
  template<class InputIterator,
178
- class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
179
- class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
180
- class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
181
  unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
182
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
183
- -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
184
  Hash, Pred, Allocator>;
185
 
186
  template<class T, class Hash = hash<T>,
187
  class Pred = equal_to<T>, class Allocator = allocator<T>>
188
  unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
189
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
190
  -> unordered_multiset<T, Hash, Pred, Allocator>;
191
 
192
  template<class InputIterator, class Allocator>
193
  unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
194
- -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
195
- hash<typename iterator_traits<InputIterator>::value_type>,
196
- equal_to<typename iterator_traits<InputIterator>::value_type>,
197
  Allocator>;
198
 
199
  template<class InputIterator, class Hash, class Allocator>
200
  unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
201
  Hash, Allocator)
202
- -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash,
203
- equal_to<typename iterator_traits<InputIterator>::value_type>,
204
  Allocator>;
205
 
206
  template<class T, class Allocator>
207
  unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
208
  -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>;
209
 
210
  template<class T, class Hash, class Allocator>
211
  unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
212
  -> unordered_multiset<T, Hash, equal_to<T>, Allocator>;
213
 
214
- template <class Key, class Hash, class Pred, class Alloc>
215
- bool operator==(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
216
- const unordered_multiset<Key, Hash, Pred, Alloc>& b);
217
- template <class Key, class Hash, class Pred, class Alloc>
218
- bool operator!=(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
219
- const unordered_multiset<Key, Hash, Pred, Alloc>& b);
220
-
221
- // [unord.multiset.swap], swap
222
  template<class Key, class Hash, class Pred, class Alloc>
223
  void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
224
  unordered_multiset<Key, Hash, Pred, Alloc>& y)
225
  noexcept(noexcept(x.swap(y)));
226
  }
227
  ```
228
 
229
  A `size_type` parameter type in an `unordered_multiset` deduction guide
230
- refers to the `size_type` member type of the primary
231
- `unordered_multiset` template.
232
 
233
- #### `unordered_multiset` constructors <a id="unord.multiset.cnstr">[[unord.multiset.cnstr]]</a>
234
 
235
  ``` cpp
236
  unordered_multiset() : unordered_multiset(size_type(see below)) { }
237
  explicit unordered_multiset(size_type n,
238
  const hasher& hf = hasher(),
@@ -268,16 +274,27 @@ hash function, key equality predicate, and allocator, and using at least
268
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
269
  for the second form. `max_load_factor()` returns `1.0`.
270
 
271
  *Complexity:* Average case linear, worst case quadratic.
272
 
273
- #### `unordered_multiset` swap <a id="unord.multiset.swap">[[unord.multiset.swap]]</a>
274
 
275
  ``` cpp
276
- template <class Key, class Hash, class Pred, class Alloc>
277
- void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
278
- unordered_multiset<Key, Hash, Pred, Alloc>& y)
279
- noexcept(noexcept(x.swap(y)));
280
  ```
281
 
282
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
283
 
 
1
  ### Class template `unordered_multiset` <a id="unord.multiset">[[unord.multiset]]</a>
2
 
3
+ #### Overview <a id="unord.multiset.overview">[[unord.multiset.overview]]</a>
4
 
5
  An `unordered_multiset` is an unordered associative container that
6
  supports equivalent keys (an instance of `unordered_multiset` may
7
  contain multiple copies of the same key value) and in which each
8
  element’s key is the element itself. The `unordered_multiset` class
9
  supports forward iterators.
10
 
11
+ An `unordered_multiset` meets all of the requirements of a container, of
12
+ an unordered associative container, and of an allocator-aware container
13
+ ([[container.alloc.req]]). It provides the operations described in the
14
+ preceding requirements table for equivalent keys; that is, an
15
+ `unordered_multiset` supports the `a_eq` operations in that table, not
16
+ the `a_uniq` operations. For an `unordered_multiset<Key>` the `key type`
17
+ and the value type are both `Key`. The `iterator` and `const_iterator`
18
+ types are both constant iterator types. It is unspecified whether they
19
+ are the same type.
20
 
21
+ Subclause  [[unord.multiset]] only describes operations on
22
+ `unordered_multiset` that are not described in one of the requirement
23
+ tables, or for which there is additional semantic information.
24
 
25
  ``` cpp
26
  namespace std {
27
  template<class Key,
28
  class Hash = hash<Key>,
29
  class Pred = equal_to<Key>,
30
  class Allocator = allocator<Key>>
31
  class unordered_multiset {
32
  public:
33
+ // types
34
  using key_type = Key;
35
  using value_type = Key;
36
  using hasher = Hash;
37
  using key_equal = Pred;
38
  using allocator_type = Allocator;
 
94
  is_nothrow_move_assignable_v<Hash> &&
95
  is_nothrow_move_assignable_v<Pred>);
96
  unordered_multiset& operator=(initializer_list<value_type>);
97
  allocator_type get_allocator() const noexcept;
98
 
99
+ // iterators
100
  iterator begin() noexcept;
101
  const_iterator begin() const noexcept;
102
  iterator end() noexcept;
103
  const_iterator end() const noexcept;
104
  const_iterator cbegin() const noexcept;
105
  const_iterator cend() const noexcept;
106
 
107
+ // capacity
108
+ [[nodiscard]] bool empty() const noexcept;
109
  size_type size() const noexcept;
110
  size_type max_size() const noexcept;
111
 
112
+ // modifiers
113
  template<class... Args> iterator emplace(Args&&... args);
114
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
115
  iterator insert(const value_type& obj);
116
  iterator insert(value_type&& obj);
117
  iterator insert(const_iterator hint, const value_type& obj);
 
141
  template<class H2, class P2>
142
  void merge(unordered_set<Key, H2, P2, Allocator>& source);
143
  template<class H2, class P2>
144
  void merge(unordered_set<Key, H2, P2, Allocator>&& source);
145
 
146
+ // observers
147
  hasher hash_function() const;
148
  key_equal key_eq() const;
149
 
150
+ // set operations
151
  iterator find(const key_type& k);
152
  const_iterator find(const key_type& k) const;
153
+ template<class K>
154
+ iterator find(const K& k);
155
+ template<class K>
156
+ const_iterator find(const K& k) const;
157
  size_type count(const key_type& k) const;
158
+ template<class K>
159
+ size_type count(const K& k) const;
160
+ bool contains(const key_type& k) const;
161
+ template<class K>
162
+ bool contains(const K& k) const;
163
  pair<iterator, iterator> equal_range(const key_type& k);
164
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
165
+ template<class K>
166
+ pair<iterator, iterator> equal_range(const K& k);
167
+ template<class K>
168
+ pair<const_iterator, const_iterator> equal_range(const K& k) const;
169
 
170
+ // bucket interface
171
  size_type bucket_count() const noexcept;
172
  size_type max_bucket_count() const noexcept;
173
  size_type bucket_size(size_type n) const;
174
  size_type bucket(const key_type& k) const;
175
  local_iterator begin(size_type n);
 
177
  local_iterator end(size_type n);
178
  const_local_iterator end(size_type n) const;
179
  const_local_iterator cbegin(size_type n) const;
180
  const_local_iterator cend(size_type n) const;
181
 
182
+ // hash policy
183
  float load_factor() const noexcept;
184
  float max_load_factor() const noexcept;
185
  void max_load_factor(float z);
186
  void rehash(size_type n);
187
  void reserve(size_type n);
188
  };
189
 
190
  template<class InputIterator,
191
+ class Hash = hash<iter-value-type<InputIterator>>,
192
+ class Pred = equal_to<iter-value-type<InputIterator>>,
193
+ class Allocator = allocator<iter-value-type<InputIterator>>>
194
  unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
195
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
196
+ -> unordered_multiset<iter-value-type<InputIterator>,
197
  Hash, Pred, Allocator>;
198
 
199
  template<class T, class Hash = hash<T>,
200
  class Pred = equal_to<T>, class Allocator = allocator<T>>
201
  unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
202
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
203
  -> unordered_multiset<T, Hash, Pred, Allocator>;
204
 
205
  template<class InputIterator, class Allocator>
206
  unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
207
+ -> unordered_multiset<iter-value-type<InputIterator>,
208
+ hash<iter-value-type<InputIterator>>,
209
+ equal_to<iter-value-type<InputIterator>>,
210
  Allocator>;
211
 
212
  template<class InputIterator, class Hash, class Allocator>
213
  unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
214
  Hash, Allocator)
215
+ -> unordered_multiset<iter-value-type<InputIterator>, Hash,
216
+ equal_to<iter-value-type<InputIterator>>,
217
  Allocator>;
218
 
219
  template<class T, class Allocator>
220
  unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
221
  -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>;
222
 
223
  template<class T, class Hash, class Allocator>
224
  unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
225
  -> unordered_multiset<T, Hash, equal_to<T>, Allocator>;
226
 
227
+ // swap
 
 
 
 
 
 
 
228
  template<class Key, class Hash, class Pred, class Alloc>
229
  void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
230
  unordered_multiset<Key, Hash, Pred, Alloc>& y)
231
  noexcept(noexcept(x.swap(y)));
232
  }
233
  ```
234
 
235
  A `size_type` parameter type in an `unordered_multiset` deduction guide
236
+ refers to the `size_type` member type of the type deduced by the
237
+ deduction guide.
238
 
239
+ #### Constructors <a id="unord.multiset.cnstr">[[unord.multiset.cnstr]]</a>
240
 
241
  ``` cpp
242
  unordered_multiset() : unordered_multiset(size_type(see below)) { }
243
  explicit unordered_multiset(size_type n,
244
  const hasher& hf = hasher(),
 
274
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
275
  for the second form. `max_load_factor()` returns `1.0`.
276
 
277
  *Complexity:* Average case linear, worst case quadratic.
278
 
279
+ #### Erasure <a id="unord.multiset.erasure">[[unord.multiset.erasure]]</a>
280
 
281
  ``` cpp
282
+ template<class K, class H, class P, class A, class Predicate>
283
+ typename unordered_multiset<K, H, P, A>::size_type
284
+ erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred);
 
285
  ```
286
 
287
+ *Effects:* Equivalent to:
288
+
289
+ ``` cpp
290
+ auto original_size = c.size();
291
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
292
+ if (pred(*i)) {
293
+ i = c.erase(i);
294
+ } else {
295
+ ++i;
296
+ }
297
+ }
298
+ return original_size - c.size();
299
+ ```
300