From Jason Turner

[unord.map.overview]

C++14 → C++17 13.8 KB 186 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/tmp0_yan92j/{from.md → to.md} +137 -43
tmp/tmp0_yan92j/{from.md → to.md} RENAMED
@@ -10,46 +10,47 @@ 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
- `std::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 = std::equal_to<Key>,
27
- class Allocator = std::allocator<std::pair<const Key, T> > >
28
- class unordered_map
29
- {
30
  public:
31
- // types
32
- typedef Key key_type;
33
- typedef std::pair<const Key, T> value_type;
34
- typedef T mapped_type;
35
- typedef Hash hasher;
36
- typedef Pred key_equal;
37
- typedef Allocator allocator_type;
38
- typedef typename allocator_traits<Allocator>::pointer pointer;
39
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
40
- typedef value_type& reference;
41
- typedef const value_type& const_reference;
42
- typedef implementation-defined size_type;
43
- typedef implementation-defined difference_type;
44
 
45
- typedef implementation-defined iterator;
46
- typedef implementation-defined const_iterator;
47
- typedef implementation-defined local_iterator;
48
- typedef implementation-defined const_local_iterator;
 
 
49
 
50
- // construct/destroy/copy
51
  unordered_map();
52
  explicit unordered_map(size_type n,
53
  const hasher& hf = hasher(),
54
  const key_equal& eql = key_equal(),
55
  const allocator_type& a = allocator_type());
@@ -62,12 +63,12 @@ namespace std {
62
  unordered_map(const unordered_map&);
63
  unordered_map(unordered_map&&);
64
  explicit unordered_map(const Allocator&);
65
  unordered_map(const unordered_map&, const Allocator&);
66
  unordered_map(unordered_map&&, const Allocator&);
67
- unordered_map(initializer_list<value_type>,
68
- size_type = see below,
69
  const hasher& hf = hasher(),
70
  const key_equal& eql = key_equal(),
71
  const allocator_type& a = allocator_type());
72
  unordered_map(size_type n, const allocator_type& a)
73
  : unordered_map(n, hasher(), key_equal(), a) { }
@@ -85,61 +86,101 @@ namespace std {
85
  unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
86
  const allocator_type& a)
87
  : unordered_map(il, n, hf, key_equal(), a) { }
88
  ~unordered_map();
89
  unordered_map& operator=(const unordered_map&);
90
- unordered_map& operator=(unordered_map&&);
 
 
 
91
  unordered_map& operator=(initializer_list<value_type>);
92
  allocator_type get_allocator() const noexcept;
93
 
94
- // size and capacity
95
- bool empty() const noexcept;
96
- size_type size() const noexcept;
97
- size_type max_size() 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
- // modifiers
 
 
 
 
 
108
  template <class... Args> pair<iterator, bool> emplace(Args&&... args);
109
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
110
  pair<iterator, bool> insert(const value_type& obj);
 
111
  template <class P> pair<iterator, bool> insert(P&& obj);
112
  iterator insert(const_iterator hint, const value_type& obj);
 
113
  template <class P> iterator insert(const_iterator hint, P&& obj);
114
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
115
  void insert(initializer_list<value_type>);
116
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
117
  iterator erase(const_iterator position);
118
  size_type erase(const key_type& k);
119
  iterator erase(const_iterator first, const_iterator last);
 
 
 
 
120
  void clear() noexcept;
121
 
122
- void swap(unordered_map&);
 
 
 
 
 
 
 
123
 
124
- // observers
125
  hasher hash_function() const;
126
  key_equal key_eq() const;
127
 
128
- // lookup
129
  iterator find(const key_type& k);
130
  const_iterator find(const key_type& k) const;
131
  size_type count(const key_type& k) const;
132
- std::pair<iterator, iterator> equal_range(const key_type& k);
133
- std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
134
 
 
135
  mapped_type& operator[](const key_type& k);
136
  mapped_type& operator[](key_type&& k);
137
  mapped_type& at(const key_type& k);
138
  const mapped_type& at(const key_type& k) const;
139
 
140
- // bucket interface
141
  size_type bucket_count() const noexcept;
142
  size_type max_bucket_count() const noexcept;
143
  size_type bucket_size(size_type n) const;
144
  size_type bucket(const key_type& k) const;
145
  local_iterator begin(size_type n);
@@ -147,26 +188,79 @@ namespace std {
147
  local_iterator end(size_type n);
148
  const_local_iterator end(size_type n) const;
149
  const_local_iterator cbegin(size_type n) const;
150
  const_local_iterator cend(size_type n) const;
151
 
152
- // hash policy
153
  float load_factor() const noexcept;
154
  float max_load_factor() const noexcept;
155
  void max_load_factor(float z);
156
  void rehash(size_type n);
157
  void reserve(size_type n);
158
  };
159
 
160
- template <class Key, class T, class Hash, class Pred, class Alloc>
161
- void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
162
- unordered_map<Key, T, Hash, Pred, Alloc>& y);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
163
 
164
  template <class Key, class T, class Hash, class Pred, class Alloc>
165
  bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
166
  const unordered_map<Key, T, Hash, Pred, Alloc>& b);
167
  template <class Key, class T, class Hash, class Pred, class Alloc>
168
  bool operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
169
  const unordered_map<Key, T, Hash, Pred, Alloc>& b);
 
 
 
 
 
 
170
  }
171
  ```
172
 
 
 
 
 
 
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;
36
+ using allocator_type = Allocator;
37
+ using pointer = typename allocator_traits<Allocator>::pointer;
38
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
39
+ using reference = value_type&;
40
+ using const_reference = const value_type&;
41
+ using size_type = implementation-defined; // see [container.requirements]
42
+ using difference_type = implementation-defined; // see [container.requirements]
43
 
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(),
55
  const key_equal& eql = key_equal(),
56
  const allocator_type& a = allocator_type());
 
63
  unordered_map(const unordered_map&);
64
  unordered_map(unordered_map&&);
65
  explicit unordered_map(const Allocator&);
66
  unordered_map(const unordered_map&, const Allocator&);
67
  unordered_map(unordered_map&&, const Allocator&);
68
+ unordered_map(initializer_list<value_type> il,
69
+ size_type n = see below,
70
  const hasher& hf = hasher(),
71
  const key_equal& eql = key_equal(),
72
  const allocator_type& a = allocator_type());
73
  unordered_map(size_type n, const allocator_type& a)
74
  : unordered_map(n, hasher(), key_equal(), a) { }
 
86
  unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
87
  const allocator_type& a)
88
  : unordered_map(il, n, hf, key_equal(), a) { }
89
  ~unordered_map();
90
  unordered_map& operator=(const unordered_map&);
91
+ unordered_map& operator=(unordered_map&&)
92
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
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);
113
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
114
  pair<iterator, bool> insert(const value_type& obj);
115
+ pair<iterator, bool> insert(value_type&& obj);
116
  template <class P> pair<iterator, bool> insert(P&& obj);
117
  iterator insert(const_iterator hint, const value_type& obj);
118
+ iterator insert(const_iterator hint, value_type&& obj);
119
  template <class P> iterator insert(const_iterator hint, P&& obj);
120
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
121
  void insert(initializer_list<value_type>);
122
 
123
+ node_type extract(const_iterator position);
124
+ node_type extract(const key_type& x);
125
+ insert_return_type insert(node_type&& nh);
126
+ iterator insert(const_iterator hint, node_type&& nh);
127
+
128
+ template <class... Args>
129
+ pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
130
+ template <class... Args>
131
+ pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
132
+ template <class... Args>
133
+ iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
134
+ template <class... Args>
135
+ iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
136
+ template <class M>
137
+ pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
138
+ template <class M>
139
+ pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
140
+ template <class M>
141
+ iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
142
+ template <class M>
143
+ iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
144
+
145
+ iterator erase(iterator position);
146
  iterator erase(const_iterator position);
147
  size_type erase(const key_type& k);
148
  iterator erase(const_iterator first, const_iterator last);
149
+ void swap(unordered_map&)
150
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
151
+ is_nothrow_swappable_v<Hash> &&
152
+ is_nothrow_swappable_v<Pred>);
153
  void clear() noexcept;
154
 
155
+ template<class H2, class P2>
156
+ void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
157
+ template<class H2, class P2>
158
+ void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
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
  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
  }
261
  ```
262
 
263
+ A `size_type` parameter type in an `unordered_map` deduction guide
264
+ refers to the `size_type` member type of the type deduced by the
265
+ deduction guide.
266
+