From Jason Turner

[unord.set.overview]

C++17 → C++20 10.0 KB 95 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/tmpx7nco38q/{from.md → to.md} +47 -41
tmp/tmpx7nco38q/{from.md → to.md} RENAMED
@@ -1,35 +1,35 @@
1
- #### Class template `unordered_set` overview <a id="unord.set.overview">[[unord.set.overview]]</a>
2
 
3
  An `unordered_set` is an unordered associative container that supports
4
  unique keys (an `unordered_set` contains at most one of each key value)
5
  and in which the elements’ keys are the elements themselves. The
6
  `unordered_set` class supports forward iterators.
7
 
8
- An `unordered_set` satisfies all of the requirements of a container, of
9
- an unordered associative container, and of an allocator-aware container
10
- (Table  [[tab:containers.allocatoraware]]). It provides the operations
11
- described in the preceding requirements table for unique keys; that is,
12
- an `unordered_set` supports the `a_uniq` operations in that table, not
13
- the `a_eq` operations. For an `unordered_set<Key>` the `key type` and
14
- the value type are both `Key`. The `iterator` and `const_iterator` types
15
- are both constant iterator types. It is unspecified whether they are the
16
  same type.
17
 
18
- This section only describes operations on `unordered_set` that are not
19
- described in one of the requirement tables, or for which there is
20
- additional semantic information.
21
 
22
  ``` cpp
23
  namespace std {
24
  template<class Key,
25
  class Hash = hash<Key>,
26
  class Pred = equal_to<Key>,
27
  class Allocator = allocator<Key>>
28
  class unordered_set {
29
  public:
30
- // types:
31
  using key_type = Key;
32
  using value_type = Key;
33
  using hasher = Hash;
34
  using key_equal = Pred;
35
  using allocator_type = Allocator;
@@ -43,11 +43,11 @@ namespace std {
43
  using iterator = implementation-defined // type of unordered_set::iterator; // see [container.requirements]
44
  using const_iterator = implementation-defined // type of unordered_set::const_iterator; // see [container.requirements]
45
  using local_iterator = implementation-defined // type of unordered_set::local_iterator; // see [container.requirements]
46
  using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
47
  using node_type = unspecified;
48
- using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
49
 
50
  // [unord.set.cnstr], construct/copy/destroy
51
  unordered_set();
52
  explicit unordered_set(size_type n,
53
  const hasher& hf = hasher(),
@@ -92,24 +92,24 @@ namespace std {
92
  is_nothrow_move_assignable_v<Hash> &&
93
  is_nothrow_move_assignable_v<Pred>);
94
  unordered_set& operator=(initializer_list<value_type>);
95
  allocator_type get_allocator() const noexcept;
96
 
97
- // iterators:
98
  iterator begin() noexcept;
99
  const_iterator begin() const noexcept;
100
  iterator end() noexcept;
101
  const_iterator end() const noexcept;
102
  const_iterator cbegin() const noexcept;
103
  const_iterator cend() const noexcept;
104
 
105
- // capacity:
106
- bool empty() const noexcept;
107
  size_type size() const noexcept;
108
  size_type max_size() const noexcept;
109
 
110
- // modifiers:
111
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
112
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
113
  pair<iterator, bool> insert(const value_type& obj);
114
  pair<iterator, bool> insert(value_type&& obj);
115
  iterator insert(const_iterator hint, const value_type& obj);
@@ -139,22 +139,35 @@ namespace std {
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_multiset<Key, H2, P2, Allocator>&& source);
143
 
144
- // observers:
145
  hasher hash_function() const;
146
  key_equal key_eq() const;
147
 
148
- // set operations:
149
  iterator find(const key_type& k);
150
  const_iterator find(const key_type& k) const;
 
 
 
 
151
  size_type count(const key_type& k) const;
 
 
 
 
 
152
  pair<iterator, iterator> equal_range(const key_type& k);
153
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
 
 
 
154
 
155
- // bucket interface:
156
  size_type bucket_count() const noexcept;
157
  size_type max_bucket_count() const noexcept;
158
  size_type bucket_size(size_type n) const;
159
  size_type bucket(const key_type& k) const;
160
  local_iterator begin(size_type n);
@@ -162,69 +175,62 @@ namespace std {
162
  local_iterator end(size_type n);
163
  const_local_iterator end(size_type n) const;
164
  const_local_iterator cbegin(size_type n) const;
165
  const_local_iterator cend(size_type n) const;
166
 
167
- // hash policy:
168
  float load_factor() const noexcept;
169
  float max_load_factor() const noexcept;
170
  void max_load_factor(float z);
171
  void rehash(size_type n);
172
  void reserve(size_type n);
173
  };
174
 
175
  template<class InputIterator,
176
- class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
177
- class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
178
- class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
179
  unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
180
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
181
- -> unordered_set<typename iterator_traits<InputIterator>::value_type,
182
  Hash, Pred, Allocator>;
183
 
184
  template<class T, class Hash = hash<T>,
185
  class Pred = equal_to<T>, class Allocator = allocator<T>>
186
  unordered_set(initializer_list<T>, typename see below::size_type = see below,
187
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
188
  -> unordered_set<T, Hash, Pred, Allocator>;
189
 
190
  template<class InputIterator, class Allocator>
191
  unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
192
- -> unordered_set<typename iterator_traits<InputIterator>::value_type,
193
- hash<typename iterator_traits<InputIterator>::value_type>,
194
- equal_to<typename iterator_traits<InputIterator>::value_type>,
195
  Allocator>;
196
 
197
  template<class InputIterator, class Hash, class Allocator>
198
  unordered_set(InputIterator, InputIterator, typename see below::size_type,
199
  Hash, Allocator)
200
- -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
201
- equal_to<typename iterator_traits<InputIterator>::value_type>,
202
  Allocator>;
203
 
204
  template<class T, class Allocator>
205
  unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
206
  -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
207
 
208
  template<class T, class Hash, class Allocator>
209
  unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
210
  -> unordered_set<T, Hash, equal_to<T>, Allocator>;
211
 
212
- template <class Key, class Hash, class Pred, class Alloc>
213
- bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
214
- const unordered_set<Key, Hash, Pred, Alloc>& b);
215
- template <class Key, class Hash, class Pred, class Alloc>
216
- bool operator!=(const unordered_set<Key, Hash, Pred, Alloc>& a,
217
- const unordered_set<Key, Hash, Pred, Alloc>& b);
218
-
219
- // [unord.set.swap], swap
220
  template<class Key, class Hash, class Pred, class Alloc>
221
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
222
  unordered_set<Key, Hash, Pred, Alloc>& y)
223
  noexcept(noexcept(x.swap(y)));
224
  }
225
  ```
226
 
227
  A `size_type` parameter type in an `unordered_set` deduction guide
228
- refers to the `size_type` member type of the primary `unordered_set`
229
- template.
230
 
 
1
+ #### Overview <a id="unord.set.overview">[[unord.set.overview]]</a>
2
 
3
  An `unordered_set` is an unordered associative container that supports
4
  unique keys (an `unordered_set` contains at most one of each key value)
5
  and in which the elements’ keys are the elements themselves. The
6
  `unordered_set` class supports forward iterators.
7
 
8
+ An `unordered_set` meets all of the requirements of a container, of an
9
+ unordered associative container, and of an allocator-aware container (
10
+ [[container.alloc.req]]). It provides the operations described in the
11
+ preceding requirements table for unique keys; that is, an
12
+ `unordered_set` supports the `a_uniq` operations in that table, not the
13
+ `a_eq` operations. For an `unordered_set<Key>` the `key type` and the
14
+ value type are both `Key`. The `iterator` and `const_iterator` types are
15
+ both constant iterator types. It is unspecified whether they are the
16
  same type.
17
 
18
+ Subclause  [[unord.set]] only describes operations on `unordered_set`
19
+ that are not described in one of the requirement tables, or for which
20
+ there is additional semantic information.
21
 
22
  ``` cpp
23
  namespace std {
24
  template<class Key,
25
  class Hash = hash<Key>,
26
  class Pred = equal_to<Key>,
27
  class Allocator = allocator<Key>>
28
  class unordered_set {
29
  public:
30
+ // types
31
  using key_type = Key;
32
  using value_type = Key;
33
  using hasher = Hash;
34
  using key_equal = Pred;
35
  using allocator_type = Allocator;
 
43
  using iterator = implementation-defined // type of unordered_set::iterator; // see [container.requirements]
44
  using const_iterator = implementation-defined // type of unordered_set::const_iterator; // see [container.requirements]
45
  using local_iterator = implementation-defined // type of unordered_set::local_iterator; // see [container.requirements]
46
  using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
47
  using node_type = unspecified;
48
+ using insert_return_type = insert-return-type<iterator, node_type>;
49
 
50
  // [unord.set.cnstr], construct/copy/destroy
51
  unordered_set();
52
  explicit unordered_set(size_type n,
53
  const hasher& hf = hasher(),
 
92
  is_nothrow_move_assignable_v<Hash> &&
93
  is_nothrow_move_assignable_v<Pred>);
94
  unordered_set& operator=(initializer_list<value_type>);
95
  allocator_type get_allocator() const noexcept;
96
 
97
+ // iterators
98
  iterator begin() noexcept;
99
  const_iterator begin() const noexcept;
100
  iterator end() noexcept;
101
  const_iterator end() const noexcept;
102
  const_iterator cbegin() const noexcept;
103
  const_iterator cend() const noexcept;
104
 
105
+ // capacity
106
+ [[nodiscard]] bool empty() const noexcept;
107
  size_type size() const noexcept;
108
  size_type max_size() const noexcept;
109
 
110
+ // modifiers
111
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
112
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
113
  pair<iterator, bool> insert(const value_type& obj);
114
  pair<iterator, bool> insert(value_type&& obj);
115
  iterator insert(const_iterator hint, const value_type& obj);
 
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_multiset<Key, H2, P2, Allocator>&& source);
143
 
144
+ // observers
145
  hasher hash_function() const;
146
  key_equal key_eq() const;
147
 
148
+ // set operations
149
  iterator find(const key_type& k);
150
  const_iterator find(const key_type& k) const;
151
+ template<class K>
152
+ iterator find(const K& k);
153
+ template<class K>
154
+ const_iterator find(const K& k) const;
155
  size_type count(const key_type& k) const;
156
+ template<class K>
157
+ size_type count(const K& k) const;
158
+ bool contains(const key_type& k) const;
159
+ template<class K>
160
+ bool contains(const K& k) const;
161
  pair<iterator, iterator> equal_range(const key_type& k);
162
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
163
+ template<class K>
164
+ pair<iterator, iterator> equal_range(const K& k);
165
+ template<class K>
166
+ pair<const_iterator, const_iterator> equal_range(const K& k) const;
167
 
168
+ // bucket interface
169
  size_type bucket_count() const noexcept;
170
  size_type max_bucket_count() const noexcept;
171
  size_type bucket_size(size_type n) const;
172
  size_type bucket(const key_type& k) const;
173
  local_iterator begin(size_type n);
 
175
  local_iterator end(size_type n);
176
  const_local_iterator end(size_type n) const;
177
  const_local_iterator cbegin(size_type n) const;
178
  const_local_iterator cend(size_type n) const;
179
 
180
+ // hash policy
181
  float load_factor() const noexcept;
182
  float max_load_factor() const noexcept;
183
  void max_load_factor(float z);
184
  void rehash(size_type n);
185
  void reserve(size_type n);
186
  };
187
 
188
  template<class InputIterator,
189
+ class Hash = hash<iter-value-type<InputIterator>>,
190
+ class Pred = equal_to<iter-value-type<InputIterator>>,
191
+ class Allocator = allocator<iter-value-type<InputIterator>>>
192
  unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
193
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
194
+ -> unordered_set<iter-value-type<InputIterator>,
195
  Hash, Pred, Allocator>;
196
 
197
  template<class T, class Hash = hash<T>,
198
  class Pred = equal_to<T>, class Allocator = allocator<T>>
199
  unordered_set(initializer_list<T>, typename see below::size_type = see below,
200
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
201
  -> unordered_set<T, Hash, Pred, Allocator>;
202
 
203
  template<class InputIterator, class Allocator>
204
  unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
205
+ -> unordered_set<iter-value-type<InputIterator>,
206
+ hash<iter-value-type<InputIterator>>,
207
+ equal_to<iter-value-type<InputIterator>>,
208
  Allocator>;
209
 
210
  template<class InputIterator, class Hash, class Allocator>
211
  unordered_set(InputIterator, InputIterator, typename see below::size_type,
212
  Hash, Allocator)
213
+ -> unordered_set<iter-value-type<InputIterator>, Hash,
214
+ equal_to<iter-value-type<InputIterator>>,
215
  Allocator>;
216
 
217
  template<class T, class Allocator>
218
  unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
219
  -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
220
 
221
  template<class T, class Hash, class Allocator>
222
  unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
223
  -> unordered_set<T, Hash, equal_to<T>, Allocator>;
224
 
225
+ // swap
 
 
 
 
 
 
 
226
  template<class Key, class Hash, class Pred, class Alloc>
227
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
228
  unordered_set<Key, Hash, Pred, Alloc>& y)
229
  noexcept(noexcept(x.swap(y)));
230
  }
231
  ```
232
 
233
  A `size_type` parameter type in an `unordered_set` deduction guide
234
+ refers to the `size_type` member type of the type deduced by the
235
+ deduction guide.
236