From Jason Turner

[unord.map.overview]

C++17 → C++20 10.8 KB 104 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/tmplauqyxkq/{from.md → to.md} +52 -45
tmp/tmplauqyxkq/{from.md → to.md} RENAMED
@@ -1,35 +1,35 @@
1
- #### Class template `unordered_map` overview <a id="unord.map.overview">[[unord.map.overview]]</a>
2
 
3
  An `unordered_map` is an unordered associative container that supports
4
  unique keys (an `unordered_map` contains at most one of each key value)
5
  and that associates values of another type `mapped_type` with the keys.
6
  The `unordered_map` class supports forward iterators.
7
 
8
- An `unordered_map` 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_map` supports the `a_uniq` operations in that table, not
13
- the `a_eq` operations. For an `unordered_map<Key, T>` the `key type` is
14
  `Key`, the mapped type is `T`, and the value type is
15
  `pair<const Key, T>`.
16
 
17
- This section only describes operations on `unordered_map` that are not
18
- described in one of the requirement tables, or for which there is
19
- additional semantic information.
20
 
21
  ``` cpp
22
  namespace std {
23
  template<class Key,
24
  class T,
25
  class Hash = hash<Key>,
26
  class Pred = equal_to<Key>,
27
  class Allocator = allocator<pair<const Key, T>>>
28
  class unordered_map {
29
  public:
30
- // types:
31
  using key_type = Key;
32
  using mapped_type = T;
33
  using value_type = pair<const Key, T>;
34
  using hasher = Hash;
35
  using key_equal = Pred;
@@ -44,11 +44,11 @@ namespace std {
44
  using iterator = implementation-defined // type of unordered_map::iterator; // see [container.requirements]
45
  using const_iterator = implementation-defined // type of unordered_map::const_iterator; // see [container.requirements]
46
  using local_iterator = implementation-defined // type of unordered_map::local_iterator; // see [container.requirements]
47
  using const_local_iterator = implementation-defined // type of unordered_map::const_local_iterator; // see [container.requirements]
48
  using node_type = unspecified;
49
- using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
50
 
51
  // [unord.map.cnstr], construct/copy/destroy
52
  unordered_map();
53
  explicit unordered_map(size_type n,
54
  const hasher& hf = hasher(),
@@ -93,20 +93,20 @@ namespace std {
93
  is_nothrow_move_assignable_v<Hash> &&
94
  is_nothrow_move_assignable_v<Pred>);
95
  unordered_map& operator=(initializer_list<value_type>);
96
  allocator_type get_allocator() const noexcept;
97
 
98
- // iterators:
99
  iterator begin() noexcept;
100
  const_iterator begin() const noexcept;
101
  iterator end() noexcept;
102
  const_iterator end() const noexcept;
103
  const_iterator cbegin() const noexcept;
104
  const_iterator cend() const noexcept;
105
 
106
- // capacity:
107
- bool empty() const noexcept;
108
  size_type size() const noexcept;
109
  size_type max_size() const noexcept;
110
 
111
  // [unord.map.modifiers], modifiers
112
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
@@ -159,28 +159,42 @@ namespace std {
159
  template<class H2, class P2>
160
  void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
161
  template<class H2, class P2>
162
  void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
163
 
164
- // observers:
165
  hasher hash_function() const;
166
  key_equal key_eq() const;
167
 
168
- // map operations:
169
  iterator find(const key_type& k);
170
  const_iterator find(const key_type& k) const;
 
 
 
 
 
171
  size_type count(const key_type& k) const;
 
 
 
 
 
172
  pair<iterator, iterator> equal_range(const key_type& k);
173
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
 
 
 
174
 
175
  // [unord.map.elem], element access
176
  mapped_type& operator[](const key_type& k);
177
  mapped_type& operator[](key_type&& k);
178
  mapped_type& at(const key_type& k);
179
  const mapped_type& at(const key_type& k) const;
180
 
181
- // bucket interface:
182
  size_type bucket_count() const noexcept;
183
  size_type max_bucket_count() const noexcept;
184
  size_type bucket_size(size_type n) const;
185
  size_type bucket(const key_type& k) const;
186
  local_iterator begin(size_type n);
@@ -188,73 +202,66 @@ namespace std {
188
  local_iterator end(size_type n);
189
  const_local_iterator end(size_type n) const;
190
  const_local_iterator cbegin(size_type n) const;
191
  const_local_iterator cend(size_type n) const;
192
 
193
- // hash policy:
194
  float load_factor() const noexcept;
195
  float max_load_factor() const noexcept;
196
  void max_load_factor(float z);
197
  void rehash(size_type n);
198
  void reserve(size_type n);
199
  };
200
 
201
  template<class InputIterator,
202
- class Hash = hash<iter_key_t<InputIterator>>,
203
- class Pred = equal_to<iter_key_t<InputIterator>>,
204
- class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
205
  unordered_map(InputIterator, InputIterator, typename see below::size_type = see below,
206
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
207
- -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
208
  Allocator>;
209
 
210
  template<class Key, class T, class Hash = hash<Key>,
211
  class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
212
- unordered_map(initializer_list<pair<const Key, T>>,
213
  typename see below::size_type = see below, Hash = Hash(),
214
  Pred = Pred(), Allocator = Allocator())
215
  -> unordered_map<Key, T, Hash, Pred, Allocator>;
216
 
217
  template<class InputIterator, class Allocator>
218
  unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)
219
- -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
220
- hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>,
221
- Allocator>;
222
 
223
  template<class InputIterator, class Allocator>
224
  unordered_map(InputIterator, InputIterator, Allocator)
225
- -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
226
- hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>,
227
- Allocator>;
228
 
229
  template<class InputIterator, class Hash, class Allocator>
230
  unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
231
- -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
232
- equal_to<iter_key_t<InputIterator>>, Allocator>;
233
 
234
- template<class Key, class T, typename Allocator>
235
- unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type,
236
  Allocator)
237
  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
238
 
239
- template<class Key, class T, typename Allocator>
240
- unordered_map(initializer_list<pair<const Key, T>>, Allocator)
241
  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
242
 
243
  template<class Key, class T, class Hash, class Allocator>
244
- unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash,
245
  Allocator)
246
  -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>;
247
 
248
- template <class Key, class T, class Hash, class Pred, class Alloc>
249
- bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
250
- const unordered_map<Key, T, Hash, Pred, Alloc>& b);
251
- template <class Key, class T, class Hash, class Pred, class Alloc>
252
- bool operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
253
- const unordered_map<Key, T, Hash, Pred, Alloc>& b);
254
-
255
- // [unord.map.swap], swap
256
  template<class Key, class T, class Hash, class Pred, class Alloc>
257
  void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
258
  unordered_map<Key, T, Hash, Pred, Alloc>& y)
259
  noexcept(noexcept(x.swap(y)));
260
  }
 
1
+ #### Overview <a id="unord.map.overview">[[unord.map.overview]]</a>
2
 
3
  An `unordered_map` is an unordered associative container that supports
4
  unique keys (an `unordered_map` contains at most one of each key value)
5
  and that associates values of another type `mapped_type` with the keys.
6
  The `unordered_map` class supports forward iterators.
7
 
8
+ An `unordered_map` 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_map` supports the `a_uniq` operations in that table, not the
13
+ `a_eq` operations. For an `unordered_map<Key, T>` the `key type` is
14
  `Key`, the mapped type is `T`, and the value type is
15
  `pair<const Key, T>`.
16
 
17
+ Subclause  [[unord.map]] only describes operations on `unordered_map`
18
+ that are not described in one of the requirement tables, or for which
19
+ there is additional semantic information.
20
 
21
  ``` cpp
22
  namespace std {
23
  template<class Key,
24
  class T,
25
  class Hash = hash<Key>,
26
  class Pred = equal_to<Key>,
27
  class Allocator = allocator<pair<const Key, T>>>
28
  class unordered_map {
29
  public:
30
+ // types
31
  using key_type = Key;
32
  using mapped_type = T;
33
  using value_type = pair<const Key, T>;
34
  using hasher = Hash;
35
  using key_equal = Pred;
 
44
  using iterator = implementation-defined // type of unordered_map::iterator; // see [container.requirements]
45
  using const_iterator = implementation-defined // type of unordered_map::const_iterator; // see [container.requirements]
46
  using local_iterator = implementation-defined // type of unordered_map::local_iterator; // see [container.requirements]
47
  using const_local_iterator = implementation-defined // type of unordered_map::const_local_iterator; // see [container.requirements]
48
  using node_type = unspecified;
49
+ using insert_return_type = insert-return-type<iterator, node_type>;
50
 
51
  // [unord.map.cnstr], construct/copy/destroy
52
  unordered_map();
53
  explicit unordered_map(size_type n,
54
  const hasher& hf = hasher(),
 
93
  is_nothrow_move_assignable_v<Hash> &&
94
  is_nothrow_move_assignable_v<Pred>);
95
  unordered_map& operator=(initializer_list<value_type>);
96
  allocator_type get_allocator() const noexcept;
97
 
98
+ // iterators
99
  iterator begin() noexcept;
100
  const_iterator begin() const noexcept;
101
  iterator end() noexcept;
102
  const_iterator end() const noexcept;
103
  const_iterator cbegin() const noexcept;
104
  const_iterator cend() const noexcept;
105
 
106
+ // capacity
107
+ [[nodiscard]] bool empty() const noexcept;
108
  size_type size() const noexcept;
109
  size_type max_size() const noexcept;
110
 
111
  // [unord.map.modifiers], modifiers
112
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
 
159
  template<class H2, class P2>
160
  void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
161
  template<class H2, class P2>
162
  void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
163
 
164
+ // observers
165
  hasher hash_function() const;
166
  key_equal key_eq() const;
167
 
168
+ // map operations
169
  iterator find(const key_type& k);
170
  const_iterator find(const key_type& k) const;
171
+ template<class K>
172
+ iterator find(const K& k);
173
+ template<class K>
174
+ const_iterator find(const K& k) const;
175
+ template<class K>
176
  size_type count(const key_type& k) const;
177
+ template<class K>
178
+ size_type count(const K& k) const;
179
+ bool contains(const key_type& k) const;
180
+ template<class K>
181
+ bool contains(const K& k) const;
182
  pair<iterator, iterator> equal_range(const key_type& k);
183
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
184
+ template<class K>
185
+ pair<iterator, iterator> equal_range(const K& k);
186
+ template<class K>
187
+ pair<const_iterator, const_iterator> equal_range(const K& k) const;
188
 
189
  // [unord.map.elem], element access
190
  mapped_type& operator[](const key_type& k);
191
  mapped_type& operator[](key_type&& k);
192
  mapped_type& at(const key_type& k);
193
  const mapped_type& at(const key_type& k) const;
194
 
195
+ // bucket interface
196
  size_type bucket_count() const noexcept;
197
  size_type max_bucket_count() const noexcept;
198
  size_type bucket_size(size_type n) const;
199
  size_type bucket(const key_type& k) const;
200
  local_iterator begin(size_type n);
 
202
  local_iterator end(size_type n);
203
  const_local_iterator end(size_type n) const;
204
  const_local_iterator cbegin(size_type n) const;
205
  const_local_iterator cend(size_type n) const;
206
 
207
+ // hash policy
208
  float load_factor() const noexcept;
209
  float max_load_factor() const noexcept;
210
  void max_load_factor(float z);
211
  void rehash(size_type n);
212
  void reserve(size_type n);
213
  };
214
 
215
  template<class InputIterator,
216
+ class Hash = hash<iter-key-type<InputIterator>>,
217
+ class Pred = equal_to<iter-key-type<InputIterator>>,
218
+ class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
219
  unordered_map(InputIterator, InputIterator, typename see below::size_type = see below,
220
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
221
+ -> unordered_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Hash, Pred,
222
  Allocator>;
223
 
224
  template<class Key, class T, class Hash = hash<Key>,
225
  class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
226
+ unordered_map(initializer_list<pair<Key, T>>,
227
  typename see below::size_type = see below, Hash = Hash(),
228
  Pred = Pred(), Allocator = Allocator())
229
  -> unordered_map<Key, T, Hash, Pred, Allocator>;
230
 
231
  template<class InputIterator, class Allocator>
232
  unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)
233
+ -> unordered_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
234
+ hash<iter-key-type<InputIterator>>,
235
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
236
 
237
  template<class InputIterator, class Allocator>
238
  unordered_map(InputIterator, InputIterator, Allocator)
239
+ -> unordered_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
240
+ hash<iter-key-type<InputIterator>>,
241
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
242
 
243
  template<class InputIterator, class Hash, class Allocator>
244
  unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
245
+ -> unordered_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Hash,
246
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
247
 
248
+ template<class Key, class T, class Allocator>
249
+ unordered_map(initializer_list<pair<Key, T>>, typename see below::size_type,
250
  Allocator)
251
  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
252
 
253
+ template<class Key, class T, class Allocator>
254
+ unordered_map(initializer_list<pair<Key, T>>, Allocator)
255
  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
256
 
257
  template<class Key, class T, class Hash, class Allocator>
258
+ unordered_map(initializer_list<pair<Key, T>>, typename see below::size_type, Hash,
259
  Allocator)
260
  -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>;
261
 
262
+ // swap
 
 
 
 
 
 
 
263
  template<class Key, class T, class Hash, class Pred, class Alloc>
264
  void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
265
  unordered_map<Key, T, Hash, Pred, Alloc>& y)
266
  noexcept(noexcept(x.swap(y)));
267
  }