From Jason Turner

[unord.multiset]

C++14 → C++17 15.0 KB 182 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpucpy1djd/{from.md → to.md} +123 -52
tmp/tmpucpy1djd/{from.md → to.md} RENAMED
@@ -13,45 +13,45 @@ 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 const iterator
19
- 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 = std::equal_to<Key>,
30
- class Allocator = std::allocator<Key> >
31
- class unordered_multiset
32
- {
33
  public:
34
- // types
35
- typedef Key key_type;
36
- typedef Key value_type;
37
- typedef Hash hasher;
38
- typedef Pred key_equal;
39
- typedef Allocator allocator_type;
40
- typedef typename allocator_traits<Allocator>::pointer pointer;
41
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
42
- typedef value_type& reference;
43
- typedef const value_type& const_reference;
44
- typedef implementation-defined size_type;
45
- typedef implementation-defined difference_type;
46
 
47
- typedef implementation-defined iterator;
48
- typedef implementation-defined const_iterator;
49
- typedef implementation-defined local_iterator;
50
- typedef implementation-defined const_local_iterator;
 
51
 
52
- // construct/destroy/copy
53
  unordered_multiset();
54
  explicit unordered_multiset(size_type n,
55
  const hasher& hf = hasher(),
56
  const key_equal& eql = key_equal(),
57
  const allocator_type& a = allocator_type());
@@ -64,12 +64,12 @@ namespace std {
64
  unordered_multiset(const unordered_multiset&);
65
  unordered_multiset(unordered_multiset&&);
66
  explicit unordered_multiset(const Allocator&);
67
  unordered_multiset(const unordered_multiset&, const Allocator&);
68
  unordered_multiset(unordered_multiset&&, const Allocator&);
69
- unordered_multiset(initializer_list<value_type>,
70
- size_type = see below,
71
  const hasher& hf = hasher(),
72
  const key_equal& eql = key_equal(),
73
  const allocator_type& a = allocator_type());
74
  unordered_multiset(size_type n, const allocator_type& a)
75
  : unordered_multiset(n, hasher(), key_equal(), a) { }
@@ -87,56 +87,76 @@ namespace std {
87
  unordered_multiset(initializer_list<value_type> il, size_type n, const hasher& hf,
88
  const allocator_type& a)
89
  : unordered_multiset(il, n, hf, key_equal(), a) { }
90
  ~unordered_multiset();
91
  unordered_multiset& operator=(const unordered_multiset&);
92
- unordered_multiset& operator=(unordered_multiset&&);
 
 
 
93
  unordered_multiset& operator=(initializer_list<value_type>);
94
  allocator_type get_allocator() const noexcept;
95
 
96
- // size and capacity
97
- bool empty() const noexcept;
98
- size_type size() const noexcept;
99
- size_type max_size() const noexcept;
100
-
101
- // iterators
102
  iterator begin() noexcept;
103
  const_iterator begin() const noexcept;
104
  iterator end() noexcept;
105
  const_iterator end() const noexcept;
106
  const_iterator cbegin() const noexcept;
107
  const_iterator cend() const noexcept;
108
 
109
- // modifiers
 
 
 
 
 
110
  template <class... Args> iterator emplace(Args&&... args);
111
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
112
  iterator insert(const value_type& obj);
113
  iterator insert(value_type&& obj);
114
  iterator insert(const_iterator hint, const value_type& obj);
115
  iterator insert(const_iterator hint, value_type&& obj);
116
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
117
  void insert(initializer_list<value_type>);
118
 
 
 
 
 
 
 
119
  iterator erase(const_iterator position);
120
  size_type erase(const key_type& k);
121
  iterator erase(const_iterator first, const_iterator last);
 
 
 
 
122
  void clear() noexcept;
123
 
124
- void swap(unordered_multiset&);
 
 
 
 
 
 
 
125
 
126
- // observers
127
  hasher hash_function() const;
128
  key_equal key_eq() const;
129
 
130
- // lookup
131
  iterator find(const key_type& k);
132
  const_iterator find(const key_type& k) const;
133
  size_type count(const key_type& k) const;
134
- std::pair<iterator, iterator> equal_range(const key_type& k);
135
- std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
136
 
137
- // bucket interface
138
  size_type bucket_count() const noexcept;
139
  size_type max_bucket_count() const noexcept;
140
  size_type bucket_size(size_type n) const;
141
  size_type bucket(const key_type& k) const;
142
  local_iterator begin(size_type n);
@@ -144,30 +164,74 @@ namespace std {
144
  local_iterator end(size_type n);
145
  const_local_iterator end(size_type n) const;
146
  const_local_iterator cbegin(size_type n) const;
147
  const_local_iterator cend(size_type n) const;
148
 
149
- // hash policy
150
  float load_factor() const noexcept;
151
  float max_load_factor() const noexcept;
152
  void max_load_factor(float z);
153
  void rehash(size_type n);
154
  void reserve(size_type n);
155
  };
156
 
157
- template <class Key, class Hash, class Pred, class Alloc>
158
- void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
159
- unordered_multiset<Key, Hash, Pred, Alloc>& y);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
160
  template <class Key, class Hash, class Pred, class Alloc>
161
  bool operator==(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
162
  const unordered_multiset<Key, Hash, Pred, Alloc>& b);
163
  template <class Key, class Hash, class Pred, class Alloc>
164
  bool operator!=(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
165
  const unordered_multiset<Key, Hash, Pred, Alloc>& b);
 
 
 
 
 
 
166
  }
167
  ```
168
 
 
 
 
 
169
  #### `unordered_multiset` constructors <a id="unord.multiset.cnstr">[[unord.multiset.cnstr]]</a>
170
 
171
  ``` cpp
172
  unordered_multiset() : unordered_multiset(size_type(see below)) { }
173
  explicit unordered_multiset(size_type n,
@@ -175,38 +239,45 @@ explicit unordered_multiset(size_type n,
175
  const key_equal& eql = key_equal(),
176
  const allocator_type& a = allocator_type());
177
  ```
178
 
179
  *Effects:* Constructs an empty `unordered_multiset` using the specified
180
- hash function, key equality function, and allocator, and using at least
181
- *`n`* buckets. For the default constructor, the number of buckets is
182
- *implementation-defined*. `max_load_factor()` returns 1.0.
183
 
184
  *Complexity:* Constant.
185
 
186
  ``` cpp
187
  template <class InputIterator>
188
  unordered_multiset(InputIterator f, InputIterator l,
189
  size_type n = see below,
190
  const hasher& hf = hasher(),
191
  const key_equal& eql = key_equal(),
192
  const allocator_type& a = allocator_type());
 
 
 
 
 
193
  ```
194
 
195
  *Effects:* Constructs an empty `unordered_multiset` using the specified
196
- hash function, key equality function, and allocator, and using at least
197
- *`n`* buckets. If *`n`* is not provided, the number of buckets is
198
- *implementation-defined*. Then inserts elements from the range
199
- `[`*`f`*`, `*`l`*`)`. `max_load_factor()` returns 1.0.
 
200
 
201
  *Complexity:* Average case linear, worst case quadratic.
202
 
203
  #### `unordered_multiset` swap <a id="unord.multiset.swap">[[unord.multiset.swap]]</a>
204
 
205
  ``` cpp
206
  template <class Key, class Hash, class Pred, class Alloc>
207
  void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
208
- unordered_multiset<Key, Hash, Pred, Alloc>& y);
 
209
  ```
210
 
211
- *Effects:* `x.swap(y);`
212
 
 
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;
39
+ using pointer = typename allocator_traits<Allocator>::pointer;
40
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
41
+ using reference = value_type&;
42
+ using const_reference = const value_type&;
43
+ using size_type = implementation-defined; // see [container.requirements]
44
+ using difference_type = implementation-defined; // see [container.requirements]
45
 
46
+ using iterator = implementation-defined // type of unordered_multiset::iterator; // see [container.requirements]
47
+ using const_iterator = implementation-defined // type of unordered_multiset::const_iterator; // see [container.requirements]
48
+ using local_iterator = implementation-defined // type of unordered_multiset::local_iterator; // see [container.requirements]
49
+ using const_local_iterator = implementation-defined // type of unordered_multiset::const_local_iterator; // see [container.requirements]
50
+ using node_type = unspecified;
51
 
52
+ // [unord.multiset.cnstr], construct/copy/destroy
53
  unordered_multiset();
54
  explicit unordered_multiset(size_type n,
55
  const hasher& hf = hasher(),
56
  const key_equal& eql = key_equal(),
57
  const allocator_type& a = allocator_type());
 
64
  unordered_multiset(const unordered_multiset&);
65
  unordered_multiset(unordered_multiset&&);
66
  explicit unordered_multiset(const Allocator&);
67
  unordered_multiset(const unordered_multiset&, const Allocator&);
68
  unordered_multiset(unordered_multiset&&, const Allocator&);
69
+ unordered_multiset(initializer_list<value_type> il,
70
+ size_type n = see below,
71
  const hasher& hf = hasher(),
72
  const key_equal& eql = key_equal(),
73
  const allocator_type& a = allocator_type());
74
  unordered_multiset(size_type n, const allocator_type& a)
75
  : unordered_multiset(n, hasher(), key_equal(), a) { }
 
87
  unordered_multiset(initializer_list<value_type> il, size_type n, const hasher& hf,
88
  const allocator_type& a)
89
  : unordered_multiset(il, n, hf, key_equal(), a) { }
90
  ~unordered_multiset();
91
  unordered_multiset& operator=(const unordered_multiset&);
92
+ unordered_multiset& operator=(unordered_multiset&&)
93
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
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);
118
  iterator insert(const_iterator hint, value_type&& obj);
119
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
120
  void insert(initializer_list<value_type>);
121
 
122
+ node_type extract(const_iterator position);
123
+ node_type extract(const key_type& x);
124
+ iterator insert(node_type&& nh);
125
+ iterator insert(const_iterator hint, node_type&& nh);
126
+
127
+ iterator erase(iterator position);
128
  iterator erase(const_iterator position);
129
  size_type erase(const key_type& k);
130
  iterator erase(const_iterator first, const_iterator last);
131
+ void swap(unordered_multiset&)
132
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
133
+ is_nothrow_swappable_v<Hash> &&
134
+ is_nothrow_swappable_v<Pred>);
135
  void clear() noexcept;
136
 
137
+ template<class H2, class P2>
138
+ void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
139
+ template<class H2, class P2>
140
+ void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
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
  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,
 
239
  const key_equal& eql = key_equal(),
240
  const allocator_type& a = allocator_type());
241
  ```
242
 
243
  *Effects:* Constructs an empty `unordered_multiset` using the specified
244
+ hash function, key equality predicate, and allocator, and using at least
245
+ `n` buckets. For the default constructor, the number of buckets is
246
+ *implementation-defined*. `max_load_factor()` returns `1.0`.
247
 
248
  *Complexity:* Constant.
249
 
250
  ``` cpp
251
  template <class InputIterator>
252
  unordered_multiset(InputIterator f, InputIterator l,
253
  size_type n = see below,
254
  const hasher& hf = hasher(),
255
  const key_equal& eql = key_equal(),
256
  const allocator_type& a = allocator_type());
257
+ unordered_multiset(initializer_list<value_type> il,
258
+ size_type n = see below,
259
+ const hasher& hf = hasher(),
260
+ const key_equal& eql = key_equal(),
261
+ const allocator_type& a = allocator_type());
262
  ```
263
 
264
  *Effects:* Constructs an empty `unordered_multiset` using the specified
265
+ hash function, key equality predicate, and allocator, and using at least
266
+ `n` buckets. If `n` is not provided, the number of buckets is
267
+ *implementation-defined*. Then inserts elements from the range \[`f`,
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