From Jason Turner

[unord.set]

C++14 → C++17 14.4 KB 178 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/tmpw9ykw3_e/{from.md → to.md} +121 -50
tmp/tmpw9ykw3_e/{from.md → to.md} RENAMED
@@ -12,45 +12,46 @@ an unordered associative container, and of an allocator-aware container
12
  (Table  [[tab:containers.allocatoraware]]). It provides the operations
13
  described in the preceding requirements table for unique keys; that is,
14
  an `unordered_set` supports the `a_uniq` operations in that table, not
15
  the `a_eq` operations. For an `unordered_set<Key>` the `key type` and
16
  the value type are both `Key`. The `iterator` and `const_iterator` types
17
- are both const iterator types. It is unspecified whether they are the
18
  same type.
19
 
20
  This section only describes operations on `unordered_set` that are not
21
  described in one of the requirement tables, or for which there is
22
  additional semantic information.
23
 
24
  ``` cpp
25
  namespace std {
26
  template <class Key,
27
  class Hash = hash<Key>,
28
- class Pred = std::equal_to<Key>,
29
- class Allocator = std::allocator<Key> >
30
- class unordered_set
31
- {
32
  public:
33
- // types
34
- typedef Key key_type;
35
- typedef Key value_type;
36
- typedef Hash hasher;
37
- typedef Pred key_equal;
38
- typedef Allocator allocator_type;
39
- typedef typename allocator_traits<Allocator>::pointer pointer;
40
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
41
- typedef value_type& reference;
42
- typedef const value_type& const_reference;
43
- typedef implementation-defined size_type;
44
- typedef implementation-defined difference_type;
45
 
46
- typedef implementation-defined iterator;
47
- typedef implementation-defined const_iterator;
48
- typedef implementation-defined local_iterator;
49
- typedef implementation-defined const_local_iterator;
 
 
50
 
51
- // construct/destroy/copy
52
  unordered_set();
53
  explicit unordered_set(size_type n,
54
  const hasher& hf = hasher(),
55
  const key_equal& eql = key_equal(),
56
  const allocator_type& a = allocator_type());
@@ -63,12 +64,12 @@ namespace std {
63
  unordered_set(const unordered_set&);
64
  unordered_set(unordered_set&&);
65
  explicit unordered_set(const Allocator&);
66
  unordered_set(const unordered_set&, const Allocator&);
67
  unordered_set(unordered_set&&, const Allocator&);
68
- unordered_set(initializer_list<value_type>,
69
- size_type = see below,
70
  const hasher& hf = hasher(),
71
  const key_equal& eql = key_equal(),
72
  const allocator_type& a = allocator_type());
73
  unordered_set(size_type n, const allocator_type& a)
74
  : unordered_set(n, hasher(), key_equal(), a) { }
@@ -86,56 +87,76 @@ namespace std {
86
  unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
87
  const allocator_type& a)
88
  : unordered_set(il, n, hf, key_equal(), a) { }
89
  ~unordered_set();
90
  unordered_set& operator=(const unordered_set&);
91
- unordered_set& operator=(unordered_set&&);
 
 
 
92
  unordered_set& operator=(initializer_list<value_type>);
93
  allocator_type get_allocator() const noexcept;
94
 
95
- // size and capacity
96
- bool empty() const noexcept;
97
- size_type size() const noexcept;
98
- size_type max_size() const noexcept;
99
-
100
- // iterators
101
  iterator begin() noexcept;
102
  const_iterator begin() const noexcept;
103
  iterator end() noexcept;
104
  const_iterator end() const noexcept;
105
  const_iterator cbegin() const noexcept;
106
  const_iterator cend() const noexcept;
107
 
108
- // modifiers
 
 
 
 
 
109
  template <class... Args> pair<iterator, bool> emplace(Args&&... args);
110
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
111
  pair<iterator, bool> insert(const value_type& obj);
112
  pair<iterator, bool> insert(value_type&& obj);
113
  iterator insert(const_iterator hint, const value_type& obj);
114
  iterator insert(const_iterator hint, value_type&& obj);
115
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
116
  void insert(initializer_list<value_type>);
117
 
 
 
 
 
 
 
118
  iterator erase(const_iterator position);
119
  size_type erase(const key_type& k);
120
  iterator erase(const_iterator first, const_iterator last);
 
 
 
 
121
  void clear() noexcept;
122
 
123
- void swap(unordered_set&);
 
 
 
 
 
 
 
124
 
125
- // observers
126
  hasher hash_function() const;
127
  key_equal key_eq() const;
128
 
129
- // lookup
130
  iterator find(const key_type& k);
131
  const_iterator find(const key_type& k) const;
132
  size_type count(const key_type& k) const;
133
- std::pair<iterator, iterator> equal_range(const key_type& k);
134
- std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
135
 
136
- // bucket interface
137
  size_type bucket_count() const noexcept;
138
  size_type max_bucket_count() const noexcept;
139
  size_type bucket_size(size_type n) const;
140
  size_type bucket(const key_type& k) const;
141
  local_iterator begin(size_type n);
@@ -143,31 +164,74 @@ namespace std {
143
  local_iterator end(size_type n);
144
  const_local_iterator end(size_type n) const;
145
  const_local_iterator cbegin(size_type n) const;
146
  const_local_iterator cend(size_type n) const;
147
 
148
- // hash policy
149
  float load_factor() const noexcept;
150
  float max_load_factor() const noexcept;
151
  void max_load_factor(float z);
152
  void rehash(size_type n);
153
  void reserve(size_type n);
154
  };
155
 
156
- template <class Key, class Hash, class Pred, class Alloc>
157
- void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
158
- unordered_set<Key, Hash, Pred, Alloc>& y);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
159
 
160
  template <class Key, class Hash, class Pred, class Alloc>
161
  bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
162
  const unordered_set<Key, Hash, Pred, Alloc>& b);
163
  template <class Key, class Hash, class Pred, class Alloc>
164
  bool operator!=(const unordered_set<Key, Hash, Pred, Alloc>& a,
165
  const unordered_set<Key, Hash, Pred, Alloc>& b);
 
 
 
 
 
 
166
  }
167
  ```
168
 
 
 
 
 
169
  #### `unordered_set` constructors <a id="unord.set.cnstr">[[unord.set.cnstr]]</a>
170
 
171
  ``` cpp
172
  unordered_set() : unordered_set(size_type(see below)) { }
173
  explicit unordered_set(size_type n,
@@ -175,38 +239,45 @@ explicit unordered_set(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_set` using the specified hash
180
- function, key equality function, and allocator, and using at least *`n`*
181
  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_set(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_set` using the specified hash
196
- function, key equality function, and allocator, and using at least *`n`*
197
- 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_set` swap <a id="unord.set.swap">[[unord.set.swap]]</a>
204
 
205
  ``` cpp
206
  template <class Key, class Hash, class Pred, class Alloc>
207
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
208
- unordered_set<Key, Hash, Pred, Alloc>& y);
 
209
  ```
210
 
211
- *Effects:* `x.swap(y)`.
212
 
 
12
  (Table  [[tab:containers.allocatoraware]]). It provides the operations
13
  described in the preceding requirements table for unique keys; that is,
14
  an `unordered_set` supports the `a_uniq` operations in that table, not
15
  the `a_eq` operations. For an `unordered_set<Key>` the `key type` and
16
  the value type are both `Key`. The `iterator` and `const_iterator` types
17
+ are both constant iterator types. It is unspecified whether they are the
18
  same type.
19
 
20
  This section only describes operations on `unordered_set` that are not
21
  described in one of the requirement tables, or for which there is
22
  additional semantic information.
23
 
24
  ``` cpp
25
  namespace std {
26
  template <class Key,
27
  class Hash = hash<Key>,
28
+ class Pred = equal_to<Key>,
29
+ class Allocator = allocator<Key>>
30
+ class unordered_set {
 
31
  public:
32
+ // types:
33
+ using key_type = Key;
34
+ using value_type = Key;
35
+ using hasher = Hash;
36
+ using key_equal = Pred;
37
+ using allocator_type = Allocator;
38
+ using pointer = typename allocator_traits<Allocator>::pointer;
39
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
40
+ using reference = value_type&;
41
+ using const_reference = const value_type&;
42
+ using size_type = implementation-defined; // see [container.requirements]
43
+ using difference_type = implementation-defined; // see [container.requirements]
44
 
45
+ using iterator = implementation-defined // type of unordered_set::iterator; // see [container.requirements]
46
+ using const_iterator = implementation-defined // type of unordered_set::const_iterator; // see [container.requirements]
47
+ using local_iterator = implementation-defined // type of unordered_set::local_iterator; // see [container.requirements]
48
+ using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
49
+ using node_type = unspecified;
50
+ using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
51
 
52
+ // [unord.set.cnstr], construct/copy/destroy
53
  unordered_set();
54
  explicit unordered_set(size_type n,
55
  const hasher& hf = hasher(),
56
  const key_equal& eql = key_equal(),
57
  const allocator_type& a = allocator_type());
 
64
  unordered_set(const unordered_set&);
65
  unordered_set(unordered_set&&);
66
  explicit unordered_set(const Allocator&);
67
  unordered_set(const unordered_set&, const Allocator&);
68
  unordered_set(unordered_set&&, const Allocator&);
69
+ unordered_set(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_set(size_type n, const allocator_type& a)
75
  : unordered_set(n, hasher(), key_equal(), a) { }
 
87
  unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
88
  const allocator_type& a)
89
  : unordered_set(il, n, hf, key_equal(), a) { }
90
  ~unordered_set();
91
  unordered_set& operator=(const unordered_set&);
92
+ unordered_set& operator=(unordered_set&&)
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_set& 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> pair<iterator, bool> emplace(Args&&... args);
114
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
115
  pair<iterator, bool> insert(const value_type& obj);
116
  pair<iterator, bool> 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
+ insert_return_type 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_set&)
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_set<Key, H2, P2, Allocator>& source);
139
+ template<class H2, class P2>
140
+ void merge(unordered_set<Key, H2, P2, Allocator>&& source);
141
+ template<class H2, class P2>
142
+ void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
143
+ template<class H2, class P2>
144
+ void merge(unordered_multiset<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_set(InputIterator, InputIterator, typename see below::size_type = see below,
182
+ Hash = Hash(), Pred = Pred(), Allocator = Allocator())
183
+ -> unordered_set<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_set(initializer_list<T>, typename see below::size_type = see below,
189
+ Hash = Hash(), Pred = Pred(), Allocator = Allocator())
190
+ -> unordered_set<T, Hash, Pred, Allocator>;
191
+
192
+ template<class InputIterator, class Allocator>
193
+ unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
194
+ -> unordered_set<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_set(InputIterator, InputIterator, typename see below::size_type,
201
+ Hash, Allocator)
202
+ -> unordered_set<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_set(initializer_list<T>, typename see below::size_type, Allocator)
208
+ -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
209
+
210
+ template<class T, class Hash, class Allocator>
211
+ unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
212
+ -> unordered_set<T, Hash, equal_to<T>, Allocator>;
213
 
214
  template <class Key, class Hash, class Pred, class Alloc>
215
  bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
216
  const unordered_set<Key, Hash, Pred, Alloc>& b);
217
  template <class Key, class Hash, class Pred, class Alloc>
218
  bool operator!=(const unordered_set<Key, Hash, Pred, Alloc>& a,
219
  const unordered_set<Key, Hash, Pred, Alloc>& b);
220
+
221
+ // [unord.set.swap], swap
222
+ template <class Key, class Hash, class Pred, class Alloc>
223
+ void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
224
+ unordered_set<Key, Hash, Pred, Alloc>& y)
225
+ noexcept(noexcept(x.swap(y)));
226
  }
227
  ```
228
 
229
+ A `size_type` parameter type in an `unordered_set` deduction guide
230
+ refers to the `size_type` member type of the primary `unordered_set`
231
+ template.
232
+
233
  #### `unordered_set` constructors <a id="unord.set.cnstr">[[unord.set.cnstr]]</a>
234
 
235
  ``` cpp
236
  unordered_set() : unordered_set(size_type(see below)) { }
237
  explicit unordered_set(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_set` using the specified hash
244
+ function, key equality predicate, and allocator, and using at least `n`
245
  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_set(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_set(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_set` using the specified hash
265
+ function, key equality predicate, and allocator, and using at least `n`
266
+ 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_set` swap <a id="unord.set.swap">[[unord.set.swap]]</a>
274
 
275
  ``` cpp
276
  template <class Key, class Hash, class Pred, class Alloc>
277
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
278
+ unordered_set<Key, Hash, Pred, Alloc>& y)
279
+ noexcept(noexcept(x.swap(y)));
280
  ```
281
 
282
+ *Effects:* As if by `x.swap(y)`.
283