]>
Commit | Line | Data |
---|---|---|
e63637ea BK |
1 | // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- |
2 | ||
a945c346 | 3 | // Copyright (C) 2003-2024 Free Software Foundation, Inc. |
e63637ea BK |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
e63637ea BK |
9 | // any later version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
e63637ea BK |
24 | |
25 | /** @file debug/unordered_map | |
26 | * This file is a GNU debug extension to the Standard C++ Library. | |
27 | */ | |
28 | ||
29 | #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP | |
30 | #define _GLIBCXX_DEBUG_UNORDERED_MAP 1 | |
31 | ||
541a9b10 JW |
32 | #pragma GCC system_header |
33 | ||
734f5023 | 34 | #if __cplusplus < 201103L |
ab65a4c7 | 35 | # include <bits/c++0x_warning.h> |
c878d6ba | 36 | #else |
9ca2ac69 JW |
37 | # include <bits/c++config.h> |
38 | namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug { | |
39 | template<typename _Key, typename _Tp, typename _Hash, typename _Pred, | |
40 | typename _Allocator> | |
41 | class unordered_map; | |
42 | template<typename _Key, typename _Tp, typename _Hash, typename _Pred, | |
43 | typename _Allocator> | |
44 | class unordered_multimap; | |
45 | } } // namespace std::__debug | |
46 | ||
c878d6ba | 47 | # include <unordered_map> |
e63637ea | 48 | |
364c862b | 49 | #include <debug/safe_unordered_container.h> |
15ee1a77 | 50 | #include <debug/safe_container.h> |
ced3cb9f | 51 | #include <debug/safe_iterator.h> |
77e0bf4e | 52 | #include <debug/safe_local_iterator.h> |
e63637ea | 53 | |
12ffa228 | 54 | namespace std _GLIBCXX_VISIBILITY(default) |
e63637ea BK |
55 | { |
56 | namespace __debug | |
57 | { | |
1ceb9e06 | 58 | /// Class std::unordered_map with safety/checking/debug instrumentation. |
e63637ea | 59 | template<typename _Key, typename _Tp, |
ced3cb9f | 60 | typename _Hash = std::hash<_Key>, |
e63637ea | 61 | typename _Pred = std::equal_to<_Key>, |
03d7aff6 | 62 | typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > |
e63637ea | 63 | class unordered_map |
15ee1a77 FD |
64 | : public __gnu_debug::_Safe_container< |
65 | unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, | |
66 | __gnu_debug::_Safe_unordered_container>, | |
67 | public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> | |
e63637ea | 68 | { |
12ffa228 | 69 | typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, |
15ee1a77 FD |
70 | _Pred, _Alloc> _Base; |
71 | typedef __gnu_debug::_Safe_container<unordered_map, | |
72 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
73 | typedef typename _Base::const_iterator _Base_const_iterator; | |
74 | typedef typename _Base::iterator _Base_iterator; | |
75 | typedef typename _Base::const_local_iterator | |
76 | _Base_const_local_iterator; | |
77 | typedef typename _Base::local_iterator _Base_local_iterator; | |
0462b6aa | 78 | |
e9afbed0 FD |
79 | template<typename _ItT, typename _SeqT, typename _CatT> |
80 | friend class ::__gnu_debug::_Safe_iterator; | |
81 | template<typename _ItT, typename _SeqT> | |
82 | friend class ::__gnu_debug::_Safe_local_iterator; | |
83 | ||
eca833b8 JW |
84 | // Reference wrapper for base class. See PR libstdc++/90102. |
85 | struct _Base_ref | |
86 | { | |
87 | _Base_ref(const _Base& __r) : _M_ref(__r) { } | |
88 | ||
89 | const _Base& _M_ref; | |
90 | }; | |
91 | ||
e63637ea | 92 | public: |
15ee1a77 FD |
93 | typedef typename _Base::size_type size_type; |
94 | typedef typename _Base::hasher hasher; | |
95 | typedef typename _Base::key_equal key_equal; | |
96 | typedef typename _Base::allocator_type allocator_type; | |
97 | ||
98 | typedef typename _Base::key_type key_type; | |
99 | typedef typename _Base::value_type value_type; | |
f4b4ce15 | 100 | typedef typename _Base::mapped_type mapped_type; |
15ee1a77 | 101 | |
f4b4ce15 FD |
102 | typedef typename _Base::pointer pointer; |
103 | typedef typename _Base::const_pointer const_pointer; | |
104 | typedef typename _Base::reference reference; | |
105 | typedef typename _Base::const_reference const_reference; | |
15ee1a77 FD |
106 | typedef __gnu_debug::_Safe_iterator< |
107 | _Base_iterator, unordered_map> iterator; | |
108 | typedef __gnu_debug::_Safe_iterator< | |
109 | _Base_const_iterator, unordered_map> const_iterator; | |
110 | typedef __gnu_debug::_Safe_local_iterator< | |
111 | _Base_local_iterator, unordered_map> local_iterator; | |
112 | typedef __gnu_debug::_Safe_local_iterator< | |
113 | _Base_const_local_iterator, unordered_map> const_local_iterator; | |
f4b4ce15 | 114 | typedef typename _Base::difference_type difference_type; |
e63637ea | 115 | |
da27f556 FD |
116 | unordered_map() = default; |
117 | ||
e63637ea | 118 | explicit |
da27f556 | 119 | unordered_map(size_type __n, |
e63637ea BK |
120 | const hasher& __hf = hasher(), |
121 | const key_equal& __eql = key_equal(), | |
122 | const allocator_type& __a = allocator_type()) | |
ced3cb9f | 123 | : _Base(__n, __hf, __eql, __a) { } |
e63637ea BK |
124 | |
125 | template<typename _InputIterator> | |
15ee1a77 | 126 | unordered_map(_InputIterator __first, _InputIterator __last, |
417e896e | 127 | size_type __n = 0, |
15ee1a77 FD |
128 | const hasher& __hf = hasher(), |
129 | const key_equal& __eql = key_equal(), | |
e63637ea | 130 | const allocator_type& __a = allocator_type()) |
90aabc7e FD |
131 | : _Base(__gnu_debug::__base( |
132 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
1f5ca1a1 | 133 | __gnu_debug::__base(__last), __n, |
4c2d93db | 134 | __hf, __eql, __a) { } |
e63637ea | 135 | |
0462b6aa | 136 | unordered_map(const unordered_map&) = default; |
e63637ea | 137 | |
eca833b8 JW |
138 | unordered_map(_Base_ref __x) |
139 | : _Base(__x._M_ref) { } | |
ced3cb9f | 140 | |
0462b6aa FD |
141 | unordered_map(unordered_map&&) = default; |
142 | ||
143 | explicit | |
144 | unordered_map(const allocator_type& __a) | |
15ee1a77 | 145 | : _Base(__a) { } |
0462b6aa FD |
146 | |
147 | unordered_map(const unordered_map& __umap, | |
148 | const allocator_type& __a) | |
15ee1a77 | 149 | : _Base(__umap, __a) { } |
0462b6aa FD |
150 | |
151 | unordered_map(unordered_map&& __umap, | |
152 | const allocator_type& __a) | |
e9a53a4f FD |
153 | noexcept( noexcept(_Base(std::move(__umap), __a)) ) |
154 | : _Safe(std::move(__umap), __a), | |
155 | _Base(std::move(__umap), __a) { } | |
69b3331e | 156 | |
988499f4 | 157 | unordered_map(initializer_list<value_type> __l, |
417e896e | 158 | size_type __n = 0, |
988499f4 JM |
159 | const hasher& __hf = hasher(), |
160 | const key_equal& __eql = key_equal(), | |
161 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 162 | : _Base(__l, __n, __hf, __eql, __a) { } |
ced3cb9f | 163 | |
e55b80f5 FD |
164 | unordered_map(size_type __n, const allocator_type& __a) |
165 | : unordered_map(__n, hasher(), key_equal(), __a) | |
166 | { } | |
167 | ||
168 | unordered_map(size_type __n, | |
169 | const hasher& __hf, | |
170 | const allocator_type& __a) | |
171 | : unordered_map(__n, __hf, key_equal(), __a) | |
172 | { } | |
173 | ||
174 | template<typename _InputIterator> | |
175 | unordered_map(_InputIterator __first, _InputIterator __last, | |
176 | size_type __n, | |
177 | const allocator_type& __a) | |
12324b9a | 178 | : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) |
e55b80f5 FD |
179 | { } |
180 | ||
181 | template<typename _InputIterator> | |
182 | unordered_map(_InputIterator __first, _InputIterator __last, | |
183 | size_type __n, | |
184 | const hasher& __hf, | |
185 | const allocator_type& __a) | |
12324b9a | 186 | : unordered_map(__first, __last, __n, __hf, key_equal(), __a) |
e55b80f5 FD |
187 | { } |
188 | ||
189 | unordered_map(initializer_list<value_type> __l, | |
190 | size_type __n, | |
191 | const allocator_type& __a) | |
12324b9a | 192 | : unordered_map(__l, __n, hasher(), key_equal(), __a) |
e55b80f5 FD |
193 | { } |
194 | ||
195 | unordered_map(initializer_list<value_type> __l, | |
196 | size_type __n, | |
197 | const hasher& __hf, | |
198 | const allocator_type& __a) | |
12324b9a | 199 | : unordered_map(__l, __n, __hf, key_equal(), __a) |
e55b80f5 FD |
200 | { } |
201 | ||
15ee1a77 | 202 | ~unordered_map() = default; |
6f59ea25 | 203 | |
ced3cb9f | 204 | unordered_map& |
15ee1a77 | 205 | operator=(const unordered_map&) = default; |
988499f4 | 206 | |
69b3331e | 207 | unordered_map& |
15ee1a77 | 208 | operator=(unordered_map&&) = default; |
69b3331e | 209 | |
988499f4 JM |
210 | unordered_map& |
211 | operator=(initializer_list<value_type> __l) | |
212 | { | |
e9a53a4f | 213 | _Base::operator=(__l); |
0462b6aa | 214 | this->_M_invalidate_all(); |
988499f4 JM |
215 | return *this; |
216 | } | |
217 | ||
f4b4ce15 FD |
218 | using _Base::get_allocator; |
219 | using _Base::empty; | |
220 | using _Base::size; | |
221 | using _Base::max_size; | |
222 | ||
e63637ea | 223 | void |
ff74fd13 | 224 | swap(unordered_map& __x) |
c5d9ec56 | 225 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) |
e63637ea | 226 | { |
15ee1a77 | 227 | _Safe::_M_swap(__x); |
ced3cb9f | 228 | _Base::swap(__x); |
e63637ea | 229 | } |
69b3331e PC |
230 | |
231 | void | |
d3677132 | 232 | clear() noexcept |
69b3331e PC |
233 | { |
234 | _Base::clear(); | |
235 | this->_M_invalidate_all(); | |
236 | } | |
237 | ||
15ee1a77 | 238 | iterator |
d3677132 | 239 | begin() noexcept |
4b763dee | 240 | { return { _Base::begin(), this }; } |
ced3cb9f PC |
241 | |
242 | const_iterator | |
d3677132 | 243 | begin() const noexcept |
4b763dee | 244 | { return { _Base::begin(), this }; } |
ced3cb9f PC |
245 | |
246 | iterator | |
d3677132 | 247 | end() noexcept |
4b763dee | 248 | { return { _Base::end(), this }; } |
ced3cb9f PC |
249 | |
250 | const_iterator | |
d3677132 | 251 | end() const noexcept |
4b763dee | 252 | { return { _Base::end(), this }; } |
ced3cb9f PC |
253 | |
254 | const_iterator | |
d3677132 | 255 | cbegin() const noexcept |
4b763dee | 256 | { return { _Base::cbegin(), this }; } |
ced3cb9f PC |
257 | |
258 | const_iterator | |
d3677132 | 259 | cend() const noexcept |
4b763dee | 260 | { return { _Base::cend(), this }; } |
ced3cb9f PC |
261 | |
262 | // local versions | |
77e0bf4e FD |
263 | local_iterator |
264 | begin(size_type __b) | |
7181e991 FD |
265 | { |
266 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 267 | return { _Base::begin(__b), this }; |
7181e991 | 268 | } |
77e0bf4e FD |
269 | |
270 | local_iterator | |
271 | end(size_type __b) | |
7181e991 FD |
272 | { |
273 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 274 | return { _Base::end(__b), this }; |
7181e991 | 275 | } |
77e0bf4e FD |
276 | |
277 | const_local_iterator | |
278 | begin(size_type __b) const | |
7181e991 FD |
279 | { |
280 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 281 | return { _Base::begin(__b), this }; |
7181e991 | 282 | } |
77e0bf4e FD |
283 | |
284 | const_local_iterator | |
285 | end(size_type __b) const | |
7181e991 FD |
286 | { |
287 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 288 | return { _Base::end(__b), this }; |
7181e991 | 289 | } |
77e0bf4e FD |
290 | |
291 | const_local_iterator | |
292 | cbegin(size_type __b) const | |
7181e991 FD |
293 | { |
294 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 295 | return { _Base::cbegin(__b), this }; |
7181e991 | 296 | } |
77e0bf4e FD |
297 | |
298 | const_local_iterator | |
299 | cend(size_type __b) const | |
7181e991 FD |
300 | { |
301 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 302 | return { _Base::cend(__b), this }; |
7181e991 FD |
303 | } |
304 | ||
f4b4ce15 FD |
305 | using _Base::bucket_count; |
306 | using _Base::max_bucket_count; | |
307 | using _Base::bucket; | |
308 | ||
7181e991 FD |
309 | size_type |
310 | bucket_size(size_type __b) const | |
311 | { | |
312 | __glibcxx_check_bucket_index(__b); | |
313 | return _Base::bucket_size(__b); | |
314 | } | |
ced3cb9f | 315 | |
f4b4ce15 FD |
316 | using _Base::load_factor; |
317 | ||
14cbb5d8 FD |
318 | float |
319 | max_load_factor() const noexcept | |
320 | { return _Base::max_load_factor(); } | |
321 | ||
322 | void | |
323 | max_load_factor(float __f) | |
324 | { | |
325 | __glibcxx_check_max_load_factor(__f); | |
326 | _Base::max_load_factor(__f); | |
327 | } | |
328 | ||
9b81593b FD |
329 | template<typename... _Args> |
330 | std::pair<iterator, bool> | |
331 | emplace(_Args&&... __args) | |
332 | { | |
333 | size_type __bucket_count = this->bucket_count(); | |
4b763dee | 334 | auto __res = _Base::emplace(std::forward<_Args>(__args)...); |
9b81593b | 335 | _M_check_rehashed(__bucket_count); |
4b763dee | 336 | return { { __res.first, this }, __res.second }; |
9b81593b FD |
337 | } |
338 | ||
339 | template<typename... _Args> | |
340 | iterator | |
341 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
342 | { | |
343 | __glibcxx_check_insert(__hint); | |
344 | size_type __bucket_count = this->bucket_count(); | |
4b763dee FD |
345 | auto __it = _Base::emplace_hint(__hint.base(), |
346 | std::forward<_Args>(__args)...); | |
9b81593b | 347 | _M_check_rehashed(__bucket_count); |
4b763dee | 348 | return { __it, this }; |
9b81593b FD |
349 | } |
350 | ||
ced3cb9f PC |
351 | std::pair<iterator, bool> |
352 | insert(const value_type& __obj) | |
353 | { | |
77e0bf4e | 354 | size_type __bucket_count = this->bucket_count(); |
1679da15 | 355 | auto __res = _Base::insert(__obj); |
77e0bf4e | 356 | _M_check_rehashed(__bucket_count); |
4b763dee | 357 | return { { __res.first, this }, __res.second }; |
ced3cb9f PC |
358 | } |
359 | ||
1679da15 FD |
360 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
361 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
362 | std::pair<iterator, bool> | |
363 | insert(value_type&& __x) | |
ced3cb9f | 364 | { |
77e0bf4e | 365 | size_type __bucket_count = this->bucket_count(); |
1679da15 | 366 | auto __res = _Base::insert(std::move(__x)); |
77e0bf4e | 367 | _M_check_rehashed(__bucket_count); |
4b763dee | 368 | return { { __res.first, this }, __res.second }; |
ced3cb9f PC |
369 | } |
370 | ||
fb7342fd | 371 | template<typename _Pair, typename = typename |
57cee56a PC |
372 | std::enable_if<std::is_constructible<value_type, |
373 | _Pair&&>::value>::type> | |
77e0bf4e FD |
374 | std::pair<iterator, bool> |
375 | insert(_Pair&& __obj) | |
376 | { | |
377 | size_type __bucket_count = this->bucket_count(); | |
4b763dee | 378 | auto __res = _Base::insert(std::forward<_Pair>(__obj)); |
77e0bf4e | 379 | _M_check_rehashed(__bucket_count); |
4b763dee | 380 | return { { __res.first, this }, __res.second }; |
fb7342fd PC |
381 | } |
382 | ||
1679da15 FD |
383 | iterator |
384 | insert(const_iterator __hint, const value_type& __obj) | |
385 | { | |
386 | __glibcxx_check_insert(__hint); | |
387 | size_type __bucket_count = this->bucket_count(); | |
4b763dee | 388 | auto __it = _Base::insert(__hint.base(), __obj); |
1679da15 | 389 | _M_check_rehashed(__bucket_count); |
4b763dee | 390 | return { __it, this }; |
1679da15 FD |
391 | } |
392 | ||
393 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
394 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
395 | iterator | |
396 | insert(const_iterator __hint, value_type&& __x) | |
397 | { | |
398 | __glibcxx_check_insert(__hint); | |
399 | size_type __bucket_count = this->bucket_count(); | |
400 | auto __it = _Base::insert(__hint.base(), std::move(__x)); | |
401 | _M_check_rehashed(__bucket_count); | |
4b763dee | 402 | return { __it, this }; |
1679da15 FD |
403 | } |
404 | ||
fb7342fd | 405 | template<typename _Pair, typename = typename |
57cee56a PC |
406 | std::enable_if<std::is_constructible<value_type, |
407 | _Pair&&>::value>::type> | |
77e0bf4e FD |
408 | iterator |
409 | insert(const_iterator __hint, _Pair&& __obj) | |
410 | { | |
d66411ba | 411 | __glibcxx_check_insert(__hint); |
77e0bf4e | 412 | size_type __bucket_count = this->bucket_count(); |
4b763dee | 413 | auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); |
77e0bf4e | 414 | _M_check_rehashed(__bucket_count); |
4b763dee | 415 | return { __it, this }; |
fb7342fd PC |
416 | } |
417 | ||
ced3cb9f PC |
418 | void |
419 | insert(std::initializer_list<value_type> __l) | |
77e0bf4e FD |
420 | { |
421 | size_type __bucket_count = this->bucket_count(); | |
422 | _Base::insert(__l); | |
423 | _M_check_rehashed(__bucket_count); | |
424 | } | |
ced3cb9f PC |
425 | |
426 | template<typename _InputIterator> | |
77e0bf4e FD |
427 | void |
428 | insert(_InputIterator __first, _InputIterator __last) | |
429 | { | |
24167c42 FD |
430 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
431 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
77e0bf4e | 432 | size_type __bucket_count = this->bucket_count(); |
24167c42 FD |
433 | |
434 | if (__dist.second >= __gnu_debug::__dp_sign) | |
435 | _Base::insert(__gnu_debug::__unsafe(__first), | |
436 | __gnu_debug::__unsafe(__last)); | |
437 | else | |
438 | _Base::insert(__first, __last); | |
439 | ||
77e0bf4e | 440 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
441 | } |
442 | ||
66c182be JW |
443 | #if __cplusplus > 201402L |
444 | template <typename... _Args> | |
4b763dee FD |
445 | pair<iterator, bool> |
446 | try_emplace(const key_type& __k, _Args&&... __args) | |
447 | { | |
66c182be JW |
448 | auto __res = _Base::try_emplace(__k, |
449 | std::forward<_Args>(__args)...); | |
4b763dee | 450 | return { { __res.first, this }, __res.second }; |
66c182be JW |
451 | } |
452 | ||
453 | template <typename... _Args> | |
4b763dee FD |
454 | pair<iterator, bool> |
455 | try_emplace(key_type&& __k, _Args&&... __args) | |
456 | { | |
66c182be JW |
457 | auto __res = _Base::try_emplace(std::move(__k), |
458 | std::forward<_Args>(__args)...); | |
4b763dee | 459 | return { { __res.first, this }, __res.second }; |
66c182be JW |
460 | } |
461 | ||
462 | template <typename... _Args> | |
4b763dee FD |
463 | iterator |
464 | try_emplace(const_iterator __hint, const key_type& __k, | |
465 | _Args&&... __args) | |
466 | { | |
66c182be | 467 | __glibcxx_check_insert(__hint); |
4b763dee FD |
468 | return { _Base::try_emplace(__hint.base(), __k, |
469 | std::forward<_Args>(__args)...), | |
470 | this }; | |
66c182be JW |
471 | } |
472 | ||
473 | template <typename... _Args> | |
4b763dee FD |
474 | iterator |
475 | try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) | |
476 | { | |
66c182be | 477 | __glibcxx_check_insert(__hint); |
4b763dee FD |
478 | return { _Base::try_emplace(__hint.base(), std::move(__k), |
479 | std::forward<_Args>(__args)...), | |
480 | this }; | |
66c182be JW |
481 | } |
482 | ||
483 | template <typename _Obj> | |
4b763dee FD |
484 | pair<iterator, bool> |
485 | insert_or_assign(const key_type& __k, _Obj&& __obj) | |
486 | { | |
66c182be JW |
487 | auto __res = _Base::insert_or_assign(__k, |
488 | std::forward<_Obj>(__obj)); | |
4b763dee | 489 | return { { __res.first, this }, __res.second }; |
66c182be JW |
490 | } |
491 | ||
492 | template <typename _Obj> | |
4b763dee FD |
493 | pair<iterator, bool> |
494 | insert_or_assign(key_type&& __k, _Obj&& __obj) | |
495 | { | |
66c182be JW |
496 | auto __res = _Base::insert_or_assign(std::move(__k), |
497 | std::forward<_Obj>(__obj)); | |
4b763dee | 498 | return { { __res.first, this }, __res.second }; |
66c182be JW |
499 | } |
500 | ||
501 | template <typename _Obj> | |
4b763dee FD |
502 | iterator |
503 | insert_or_assign(const_iterator __hint, const key_type& __k, | |
504 | _Obj&& __obj) | |
505 | { | |
66c182be | 506 | __glibcxx_check_insert(__hint); |
4b763dee FD |
507 | return { _Base::insert_or_assign(__hint.base(), __k, |
508 | std::forward<_Obj>(__obj)), | |
509 | this }; | |
66c182be JW |
510 | } |
511 | ||
512 | template <typename _Obj> | |
4b763dee FD |
513 | iterator |
514 | insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) | |
515 | { | |
66c182be | 516 | __glibcxx_check_insert(__hint); |
4b763dee FD |
517 | return { _Base::insert_or_assign(__hint.base(), std::move(__k), |
518 | std::forward<_Obj>(__obj)), | |
519 | this }; | |
66c182be | 520 | } |
2dbe56bd | 521 | #endif // C++17 |
66c182be | 522 | |
2dbe56bd JW |
523 | #if __cplusplus > 201402L |
524 | using node_type = typename _Base::node_type; | |
adaefe2a | 525 | using insert_return_type = _Node_insert_return<iterator, node_type>; |
2dbe56bd JW |
526 | |
527 | node_type | |
528 | extract(const_iterator __position) | |
529 | { | |
530 | __glibcxx_check_erase(__position); | |
4b763dee | 531 | return _M_extract(__position.base()); |
2dbe56bd JW |
532 | } |
533 | ||
534 | node_type | |
535 | extract(const key_type& __key) | |
536 | { | |
4b763dee FD |
537 | const auto __position = _Base::find(__key); |
538 | if (__position != _Base::end()) | |
539 | return _M_extract(__position); | |
2dbe56bd JW |
540 | return {}; |
541 | } | |
542 | ||
543 | insert_return_type | |
544 | insert(node_type&& __nh) | |
545 | { | |
546 | auto __ret = _Base::insert(std::move(__nh)); | |
4b763dee FD |
547 | return |
548 | { { __ret.position, this }, __ret.inserted, std::move(__ret.node) }; | |
2dbe56bd JW |
549 | } |
550 | ||
551 | iterator | |
552 | insert(const_iterator __hint, node_type&& __nh) | |
553 | { | |
554 | __glibcxx_check_insert(__hint); | |
4b763dee | 555 | return { _Base::insert(__hint.base(), std::move(__nh)), this }; |
2dbe56bd JW |
556 | } |
557 | ||
f4b4ce15 FD |
558 | template<typename _H2, typename _P2> |
559 | void | |
560 | merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) | |
561 | { | |
562 | auto __guard | |
563 | = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source); | |
e9a53a4f | 564 | _Base::merge(__source); |
f4b4ce15 FD |
565 | } |
566 | ||
567 | template<typename _H2, typename _P2> | |
568 | void | |
569 | merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) | |
570 | { merge(__source); } | |
571 | ||
572 | template<typename _H2, typename _P2> | |
573 | void | |
574 | merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) | |
575 | { | |
576 | auto __guard | |
577 | = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source); | |
e9a53a4f | 578 | _Base::merge(__source); |
f4b4ce15 FD |
579 | } |
580 | ||
581 | template<typename _H2, typename _P2> | |
582 | void | |
583 | merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) | |
584 | { merge(__source); } | |
2dbe56bd | 585 | #endif // C++17 |
66c182be | 586 | |
f4b4ce15 FD |
587 | using _Base::hash_function; |
588 | using _Base::key_eq; | |
589 | ||
ced3cb9f PC |
590 | iterator |
591 | find(const key_type& __key) | |
4b763dee | 592 | { return { _Base::find(__key), this }; } |
ced3cb9f | 593 | |
d2b1a684 FD |
594 | #if __cplusplus > 201703L |
595 | template<typename _Kt, | |
596 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
597 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
598 | iterator | |
599 | find(const _Kt& __k) | |
600 | { return { _Base::find(__k), this }; } | |
601 | #endif | |
602 | ||
ced3cb9f PC |
603 | const_iterator |
604 | find(const key_type& __key) const | |
4b763dee | 605 | { return { _Base::find(__key), this }; } |
ced3cb9f | 606 | |
d2b1a684 FD |
607 | #if __cplusplus > 201703L |
608 | template<typename _Kt, | |
609 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
610 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
611 | const_iterator | |
612 | find(const _Kt& __k) const | |
613 | { return { _Base::find(__k), this }; } | |
614 | #endif | |
615 | ||
f4b4ce15 FD |
616 | using _Base::count; |
617 | #if __cplusplus > 201703L | |
618 | using _Base::contains; | |
619 | #endif | |
620 | ||
ced3cb9f PC |
621 | std::pair<iterator, iterator> |
622 | equal_range(const key_type& __key) | |
623 | { | |
4b763dee FD |
624 | auto __res = _Base::equal_range(__key); |
625 | return { { __res.first, this }, { __res.second, this } }; | |
ced3cb9f PC |
626 | } |
627 | ||
d2b1a684 FD |
628 | #if __cplusplus > 201703L |
629 | template<typename _Kt, | |
630 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
631 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
632 | std::pair<iterator, iterator> | |
633 | equal_range(const _Kt& __k) | |
634 | { | |
635 | auto __res = _Base::equal_range(__k); | |
636 | return { { __res.first, this }, { __res.second, this } }; | |
637 | } | |
638 | #endif | |
639 | ||
ced3cb9f PC |
640 | std::pair<const_iterator, const_iterator> |
641 | equal_range(const key_type& __key) const | |
642 | { | |
4b763dee FD |
643 | auto __res = _Base::equal_range(__key); |
644 | return { { __res.first, this }, { __res.second, this } }; | |
ced3cb9f PC |
645 | } |
646 | ||
d2b1a684 FD |
647 | #if __cplusplus > 201703L |
648 | template<typename _Kt, | |
649 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
650 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
651 | std::pair<const_iterator, const_iterator> | |
652 | equal_range(const _Kt& __k) const | |
653 | { | |
654 | auto __res = _Base::equal_range(__k); | |
655 | return { { __res.first, this }, { __res.second, this } }; | |
656 | } | |
657 | #endif | |
658 | ||
f4b4ce15 FD |
659 | using _Base::operator[]; |
660 | using _Base::at; | |
661 | ||
ced3cb9f PC |
662 | size_type |
663 | erase(const key_type& __key) | |
664 | { | |
665 | size_type __ret(0); | |
4b763dee | 666 | auto __victim = _Base::find(__key); |
afe96d41 | 667 | if (__victim != _Base::end()) |
ced3cb9f | 668 | { |
4b763dee | 669 | _M_erase(__victim); |
ced3cb9f PC |
670 | __ret = 1; |
671 | } | |
672 | return __ret; | |
673 | } | |
674 | ||
d723ced2 | 675 | iterator |
ced3cb9f PC |
676 | erase(const_iterator __it) |
677 | { | |
678 | __glibcxx_check_erase(__it); | |
4b763dee | 679 | return { _M_erase(__it.base()), this }; |
ced3cb9f PC |
680 | } |
681 | ||
5f40d34b FD |
682 | _Base_iterator |
683 | erase(_Base_const_iterator __it) | |
684 | { | |
685 | __glibcxx_check_erase2(__it); | |
686 | return _M_erase(__it); | |
687 | } | |
688 | ||
6dc88283 PC |
689 | iterator |
690 | erase(iterator __it) | |
4b763dee FD |
691 | { |
692 | __glibcxx_check_erase(__it); | |
693 | return { _M_erase(__it.base()), this }; | |
694 | } | |
6dc88283 | 695 | |
d723ced2 | 696 | iterator |
ced3cb9f PC |
697 | erase(const_iterator __first, const_iterator __last) |
698 | { | |
699 | __glibcxx_check_erase_range(__first, __last); | |
4b763dee | 700 | for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp) |
afe96d41 | 701 | { |
4b763dee | 702 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(), |
afe96d41 FD |
703 | _M_message(__gnu_debug::__msg_valid_range) |
704 | ._M_iterator(__first, "first") | |
705 | ._M_iterator(__last, "last")); | |
4b763dee | 706 | _M_invalidate(__tmp); |
afe96d41 | 707 | } |
4b763dee | 708 | |
77e0bf4e | 709 | size_type __bucket_count = this->bucket_count(); |
4b763dee | 710 | auto __next = _Base::erase(__first.base(), __last.base()); |
77e0bf4e | 711 | _M_check_rehashed(__bucket_count); |
4b763dee | 712 | return { __next, this }; |
ced3cb9f PC |
713 | } |
714 | ||
f4b4ce15 FD |
715 | using _Base::rehash; |
716 | using _Base::reserve; | |
717 | ||
ced3cb9f | 718 | _Base& |
15ee1a77 | 719 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
720 | |
721 | const _Base& | |
15ee1a77 | 722 | _M_base() const noexcept { return *this; } |
ced3cb9f | 723 | |
69b3331e | 724 | private: |
77e0bf4e FD |
725 | void |
726 | _M_check_rehashed(size_type __prev_count) | |
727 | { | |
728 | if (__prev_count != this->bucket_count()) | |
20a4550c | 729 | this->_M_invalidate_all(); |
77e0bf4e | 730 | } |
4b763dee FD |
731 | |
732 | void | |
733 | _M_invalidate(_Base_const_iterator __victim) | |
734 | { | |
735 | this->_M_invalidate_if( | |
736 | [__victim](_Base_const_iterator __it) { return __it == __victim; }); | |
737 | this->_M_invalidate_local_if( | |
738 | [__victim](_Base_const_local_iterator __it) | |
acc1d1a9 | 739 | { return __it == __victim; }); |
4b763dee FD |
740 | } |
741 | ||
742 | _Base_iterator | |
743 | _M_erase(_Base_const_iterator __victim) | |
744 | { | |
745 | _M_invalidate(__victim); | |
746 | size_type __bucket_count = this->bucket_count(); | |
747 | _Base_iterator __next = _Base::erase(__victim); | |
748 | _M_check_rehashed(__bucket_count); | |
749 | return __next; | |
750 | } | |
751 | ||
752 | #if __cplusplus > 201402L | |
753 | node_type | |
754 | _M_extract(_Base_const_iterator __victim) | |
755 | { | |
756 | _M_invalidate(__victim); | |
757 | return _Base::extract(__victim); | |
758 | } | |
759 | #endif | |
e63637ea BK |
760 | }; |
761 | ||
957f5fea VV |
762 | #if __cpp_deduction_guides >= 201606 |
763 | ||
764 | template<typename _InputIterator, | |
765 | typename _Hash = hash<__iter_key_t<_InputIterator>>, | |
766 | typename _Pred = equal_to<__iter_key_t<_InputIterator>>, | |
767 | typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, | |
768 | typename = _RequireInputIter<_InputIterator>, | |
c0cb38c2 FD |
769 | typename = _RequireNotAllocatorOrIntegral<_Hash>, |
770 | typename = _RequireNotAllocator<_Pred>, | |
957f5fea VV |
771 | typename = _RequireAllocator<_Allocator>> |
772 | unordered_map(_InputIterator, _InputIterator, | |
773 | typename unordered_map<int, int>::size_type = {}, | |
774 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
775 | -> unordered_map<__iter_key_t<_InputIterator>, | |
776 | __iter_val_t<_InputIterator>, | |
777 | _Hash, _Pred, _Allocator>; | |
778 | ||
779 | template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, | |
780 | typename _Pred = equal_to<_Key>, | |
781 | typename _Allocator = allocator<pair<const _Key, _Tp>>, | |
c0cb38c2 FD |
782 | typename = _RequireNotAllocatorOrIntegral<_Hash>, |
783 | typename = _RequireNotAllocator<_Pred>, | |
957f5fea VV |
784 | typename = _RequireAllocator<_Allocator>> |
785 | unordered_map(initializer_list<pair<_Key, _Tp>>, | |
786 | typename unordered_map<int, int>::size_type = {}, | |
787 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
788 | -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>; | |
789 | ||
790 | template<typename _InputIterator, typename _Allocator, | |
791 | typename = _RequireInputIter<_InputIterator>, | |
792 | typename = _RequireAllocator<_Allocator>> | |
793 | unordered_map(_InputIterator, _InputIterator, | |
794 | typename unordered_map<int, int>::size_type, _Allocator) | |
795 | -> unordered_map<__iter_key_t<_InputIterator>, | |
796 | __iter_val_t<_InputIterator>, | |
797 | hash<__iter_key_t<_InputIterator>>, | |
798 | equal_to<__iter_key_t<_InputIterator>>, | |
799 | _Allocator>; | |
800 | ||
801 | template<typename _InputIterator, typename _Allocator, | |
802 | typename = _RequireInputIter<_InputIterator>, | |
803 | typename = _RequireAllocator<_Allocator>> | |
804 | unordered_map(_InputIterator, _InputIterator, _Allocator) | |
805 | -> unordered_map<__iter_key_t<_InputIterator>, | |
806 | __iter_val_t<_InputIterator>, | |
807 | hash<__iter_key_t<_InputIterator>>, | |
808 | equal_to<__iter_key_t<_InputIterator>>, | |
809 | _Allocator>; | |
810 | ||
811 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
812 | typename = _RequireInputIter<_InputIterator>, | |
c0cb38c2 | 813 | typename = _RequireNotAllocatorOrIntegral<_Hash>, |
957f5fea VV |
814 | typename = _RequireAllocator<_Allocator>> |
815 | unordered_map(_InputIterator, _InputIterator, | |
816 | typename unordered_map<int, int>::size_type, | |
817 | _Hash, _Allocator) | |
818 | -> unordered_map<__iter_key_t<_InputIterator>, | |
819 | __iter_val_t<_InputIterator>, _Hash, | |
820 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; | |
821 | ||
822 | template<typename _Key, typename _Tp, typename _Allocator, | |
823 | typename = _RequireAllocator<_Allocator>> | |
824 | unordered_map(initializer_list<pair<_Key, _Tp>>, | |
825 | typename unordered_map<int, int>::size_type, | |
826 | _Allocator) | |
827 | -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; | |
828 | ||
829 | template<typename _Key, typename _Tp, typename _Allocator, | |
68e601d8 | 830 | typename = _RequireAllocator<_Allocator>> |
957f5fea VV |
831 | unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) |
832 | -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; | |
833 | ||
834 | template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, | |
c0cb38c2 | 835 | typename = _RequireNotAllocatorOrIntegral<_Hash>, |
957f5fea VV |
836 | typename = _RequireAllocator<_Allocator>> |
837 | unordered_map(initializer_list<pair<_Key, _Tp>>, | |
838 | typename unordered_map<int, int>::size_type, | |
839 | _Hash, _Allocator) | |
840 | -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; | |
841 | ||
842 | #endif | |
843 | ||
e63637ea BK |
844 | template<typename _Key, typename _Tp, typename _Hash, |
845 | typename _Pred, typename _Alloc> | |
69b3331e PC |
846 | inline void |
847 | swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
848 | unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
c5d9ec56 | 849 | noexcept(noexcept(__x.swap(__y))) |
69b3331e | 850 | { __x.swap(__y); } |
e63637ea | 851 | |
5dc22714 PC |
852 | template<typename _Key, typename _Tp, typename _Hash, |
853 | typename _Pred, typename _Alloc> | |
854 | inline bool | |
855 | operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
856 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
099e644e | 857 | { return __x._M_base() == __y._M_base(); } |
5dc22714 | 858 | |
7ab9c243 | 859 | #if __cpp_impl_three_way_comparison < 201907L |
5dc22714 PC |
860 | template<typename _Key, typename _Tp, typename _Hash, |
861 | typename _Pred, typename _Alloc> | |
862 | inline bool | |
863 | operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
864 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
865 | { return !(__x == __y); } | |
7ab9c243 | 866 | #endif |
e63637ea | 867 | |
1ceb9e06 | 868 | /// Class std::unordered_multimap with safety/checking/debug instrumentation. |
e63637ea | 869 | template<typename _Key, typename _Tp, |
ced3cb9f | 870 | typename _Hash = std::hash<_Key>, |
e63637ea | 871 | typename _Pred = std::equal_to<_Key>, |
03d7aff6 | 872 | typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > |
e63637ea | 873 | class unordered_multimap |
15ee1a77 FD |
874 | : public __gnu_debug::_Safe_container< |
875 | unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, | |
876 | __gnu_debug::_Safe_unordered_container>, | |
c0cb38c2 FD |
877 | public _GLIBCXX_STD_C::unordered_multimap< |
878 | _Key, _Tp, _Hash, _Pred, _Alloc> | |
e63637ea | 879 | { |
12ffa228 | 880 | typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, |
15ee1a77 FD |
881 | _Pred, _Alloc> _Base; |
882 | typedef __gnu_debug::_Safe_container<unordered_multimap, | |
883 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
884 | typedef typename _Base::const_iterator _Base_const_iterator; | |
885 | typedef typename _Base::iterator _Base_iterator; | |
77e0bf4e | 886 | typedef typename _Base::const_local_iterator _Base_const_local_iterator; |
15ee1a77 | 887 | typedef typename _Base::local_iterator _Base_local_iterator; |
0462b6aa | 888 | |
e9afbed0 FD |
889 | template<typename _ItT, typename _SeqT, typename _CatT> |
890 | friend class ::__gnu_debug::_Safe_iterator; | |
891 | template<typename _ItT, typename _SeqT> | |
892 | friend class ::__gnu_debug::_Safe_local_iterator; | |
893 | ||
eca833b8 JW |
894 | // Reference wrapper for base class. See PR libstdc++/90102. |
895 | struct _Base_ref | |
896 | { | |
897 | _Base_ref(const _Base& __r) : _M_ref(__r) { } | |
898 | ||
899 | const _Base& _M_ref; | |
900 | }; | |
901 | ||
e63637ea | 902 | public: |
15ee1a77 FD |
903 | typedef typename _Base::size_type size_type; |
904 | typedef typename _Base::hasher hasher; | |
905 | typedef typename _Base::key_equal key_equal; | |
906 | typedef typename _Base::allocator_type allocator_type; | |
907 | ||
908 | typedef typename _Base::key_type key_type; | |
909 | typedef typename _Base::value_type value_type; | |
f4b4ce15 | 910 | typedef typename _Base::mapped_type mapped_type; |
15ee1a77 | 911 | |
f4b4ce15 FD |
912 | typedef typename _Base::pointer pointer; |
913 | typedef typename _Base::const_pointer const_pointer; | |
914 | typedef typename _Base::reference reference; | |
915 | typedef typename _Base::const_reference const_reference; | |
15ee1a77 FD |
916 | typedef __gnu_debug::_Safe_iterator< |
917 | _Base_iterator, unordered_multimap> iterator; | |
918 | typedef __gnu_debug::_Safe_iterator< | |
919 | _Base_const_iterator, unordered_multimap> const_iterator; | |
77e0bf4e | 920 | typedef __gnu_debug::_Safe_local_iterator< |
15ee1a77 | 921 | _Base_local_iterator, unordered_multimap> local_iterator; |
77e0bf4e | 922 | typedef __gnu_debug::_Safe_local_iterator< |
e9afbed0 | 923 | _Base_const_local_iterator, unordered_multimap> const_local_iterator; |
f4b4ce15 | 924 | typedef typename _Base::difference_type difference_type; |
e63637ea | 925 | |
da27f556 FD |
926 | unordered_multimap() = default; |
927 | ||
e63637ea | 928 | explicit |
da27f556 | 929 | unordered_multimap(size_type __n, |
ced3cb9f PC |
930 | const hasher& __hf = hasher(), |
931 | const key_equal& __eql = key_equal(), | |
932 | const allocator_type& __a = allocator_type()) | |
933 | : _Base(__n, __hf, __eql, __a) { } | |
e63637ea BK |
934 | |
935 | template<typename _InputIterator> | |
15ee1a77 | 936 | unordered_multimap(_InputIterator __first, _InputIterator __last, |
417e896e | 937 | size_type __n = 0, |
15ee1a77 FD |
938 | const hasher& __hf = hasher(), |
939 | const key_equal& __eql = key_equal(), | |
ced3cb9f | 940 | const allocator_type& __a = allocator_type()) |
90aabc7e FD |
941 | : _Base(__gnu_debug::__base( |
942 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
1f5ca1a1 | 943 | __gnu_debug::__base(__last), __n, |
4c2d93db | 944 | __hf, __eql, __a) { } |
ced3cb9f | 945 | |
0462b6aa | 946 | unordered_multimap(const unordered_multimap&) = default; |
ced3cb9f | 947 | |
eca833b8 JW |
948 | unordered_multimap(_Base_ref __x) |
949 | : _Base(__x._M_ref) { } | |
ced3cb9f | 950 | |
0462b6aa FD |
951 | unordered_multimap(unordered_multimap&&) = default; |
952 | ||
953 | explicit | |
954 | unordered_multimap(const allocator_type& __a) | |
15ee1a77 | 955 | : _Base(__a) { } |
0462b6aa FD |
956 | |
957 | unordered_multimap(const unordered_multimap& __umap, | |
958 | const allocator_type& __a) | |
15ee1a77 | 959 | : _Base(__umap, __a) { } |
0462b6aa FD |
960 | |
961 | unordered_multimap(unordered_multimap&& __umap, | |
962 | const allocator_type& __a) | |
e9a53a4f FD |
963 | noexcept( noexcept(_Base(std::move(__umap), __a)) ) |
964 | : _Safe(std::move(__umap), __a), | |
965 | _Base(std::move(__umap), __a) { } | |
e63637ea | 966 | |
988499f4 | 967 | unordered_multimap(initializer_list<value_type> __l, |
417e896e | 968 | size_type __n = 0, |
988499f4 JM |
969 | const hasher& __hf = hasher(), |
970 | const key_equal& __eql = key_equal(), | |
971 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 972 | : _Base(__l, __n, __hf, __eql, __a) { } |
e63637ea | 973 | |
e55b80f5 FD |
974 | unordered_multimap(size_type __n, const allocator_type& __a) |
975 | : unordered_multimap(__n, hasher(), key_equal(), __a) | |
976 | { } | |
977 | ||
978 | unordered_multimap(size_type __n, const hasher& __hf, | |
979 | const allocator_type& __a) | |
980 | : unordered_multimap(__n, __hf, key_equal(), __a) | |
981 | { } | |
982 | ||
983 | template<typename _InputIterator> | |
984 | unordered_multimap(_InputIterator __first, _InputIterator __last, | |
985 | size_type __n, | |
986 | const allocator_type& __a) | |
12324b9a | 987 | : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) |
e55b80f5 FD |
988 | { } |
989 | ||
990 | template<typename _InputIterator> | |
991 | unordered_multimap(_InputIterator __first, _InputIterator __last, | |
992 | size_type __n, const hasher& __hf, | |
993 | const allocator_type& __a) | |
12324b9a | 994 | : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) |
e55b80f5 FD |
995 | { } |
996 | ||
997 | unordered_multimap(initializer_list<value_type> __l, | |
998 | size_type __n, | |
999 | const allocator_type& __a) | |
12324b9a | 1000 | : unordered_multimap(__l, __n, hasher(), key_equal(), __a) |
e55b80f5 FD |
1001 | { } |
1002 | ||
1003 | unordered_multimap(initializer_list<value_type> __l, | |
1004 | size_type __n, const hasher& __hf, | |
1005 | const allocator_type& __a) | |
12324b9a | 1006 | : unordered_multimap(__l, __n, __hf, key_equal(), __a) |
e55b80f5 FD |
1007 | { } |
1008 | ||
15ee1a77 | 1009 | ~unordered_multimap() = default; |
6f59ea25 | 1010 | |
ced3cb9f | 1011 | unordered_multimap& |
15ee1a77 | 1012 | operator=(const unordered_multimap&) = default; |
69b3331e PC |
1013 | |
1014 | unordered_multimap& | |
15ee1a77 | 1015 | operator=(unordered_multimap&&) = default; |
69b3331e | 1016 | |
988499f4 JM |
1017 | unordered_multimap& |
1018 | operator=(initializer_list<value_type> __l) | |
1019 | { | |
e9a53a4f | 1020 | _Base::operator=(__l); |
0462b6aa | 1021 | this->_M_invalidate_all(); |
988499f4 JM |
1022 | return *this; |
1023 | } | |
1024 | ||
f4b4ce15 FD |
1025 | using _Base::get_allocator; |
1026 | using _Base::empty; | |
1027 | using _Base::size; | |
1028 | using _Base::max_size; | |
1029 | ||
e63637ea | 1030 | void |
ff74fd13 | 1031 | swap(unordered_multimap& __x) |
c5d9ec56 | 1032 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) |
e63637ea | 1033 | { |
15ee1a77 | 1034 | _Safe::_M_swap(__x); |
ced3cb9f | 1035 | _Base::swap(__x); |
e63637ea | 1036 | } |
69b3331e PC |
1037 | |
1038 | void | |
d3677132 | 1039 | clear() noexcept |
69b3331e PC |
1040 | { |
1041 | _Base::clear(); | |
1042 | this->_M_invalidate_all(); | |
1043 | } | |
1044 | ||
15ee1a77 | 1045 | iterator |
d3677132 | 1046 | begin() noexcept |
4b763dee | 1047 | { return { _Base::begin(), this }; } |
ced3cb9f PC |
1048 | |
1049 | const_iterator | |
d3677132 | 1050 | begin() const noexcept |
4b763dee | 1051 | { return { _Base::begin(), this }; } |
ced3cb9f PC |
1052 | |
1053 | iterator | |
d3677132 | 1054 | end() noexcept |
4b763dee | 1055 | { return { _Base::end(), this }; } |
ced3cb9f PC |
1056 | |
1057 | const_iterator | |
d3677132 | 1058 | end() const noexcept |
4b763dee | 1059 | { return { _Base::end(), this }; } |
ced3cb9f PC |
1060 | |
1061 | const_iterator | |
d3677132 | 1062 | cbegin() const noexcept |
4b763dee | 1063 | { return { _Base::cbegin(), this }; } |
ced3cb9f PC |
1064 | |
1065 | const_iterator | |
d3677132 | 1066 | cend() const noexcept |
4b763dee | 1067 | { return { _Base::cend(), this }; } |
ced3cb9f PC |
1068 | |
1069 | // local versions | |
77e0bf4e FD |
1070 | local_iterator |
1071 | begin(size_type __b) | |
7181e991 FD |
1072 | { |
1073 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 1074 | return { _Base::begin(__b), this }; |
7181e991 | 1075 | } |
77e0bf4e FD |
1076 | |
1077 | local_iterator | |
1078 | end(size_type __b) | |
7181e991 FD |
1079 | { |
1080 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 1081 | return { _Base::end(__b), this }; |
7181e991 | 1082 | } |
77e0bf4e FD |
1083 | |
1084 | const_local_iterator | |
1085 | begin(size_type __b) const | |
7181e991 FD |
1086 | { |
1087 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 1088 | return { _Base::begin(__b), this }; |
7181e991 | 1089 | } |
77e0bf4e FD |
1090 | |
1091 | const_local_iterator | |
1092 | end(size_type __b) const | |
7181e991 FD |
1093 | { |
1094 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 1095 | return { _Base::end(__b), this }; |
7181e991 | 1096 | } |
77e0bf4e FD |
1097 | |
1098 | const_local_iterator | |
1099 | cbegin(size_type __b) const | |
7181e991 FD |
1100 | { |
1101 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 1102 | return { _Base::cbegin(__b), this }; |
7181e991 | 1103 | } |
77e0bf4e FD |
1104 | |
1105 | const_local_iterator | |
1106 | cend(size_type __b) const | |
7181e991 FD |
1107 | { |
1108 | __glibcxx_check_bucket_index(__b); | |
4b763dee | 1109 | return { _Base::cend(__b), this }; |
7181e991 FD |
1110 | } |
1111 | ||
f4b4ce15 FD |
1112 | using _Base::bucket_count; |
1113 | using _Base::max_bucket_count; | |
1114 | using _Base::bucket; | |
1115 | ||
7181e991 FD |
1116 | size_type |
1117 | bucket_size(size_type __b) const | |
1118 | { | |
1119 | __glibcxx_check_bucket_index(__b); | |
1120 | return _Base::bucket_size(__b); | |
1121 | } | |
ced3cb9f | 1122 | |
14cbb5d8 FD |
1123 | float |
1124 | max_load_factor() const noexcept | |
1125 | { return _Base::max_load_factor(); } | |
1126 | ||
1127 | void | |
1128 | max_load_factor(float __f) | |
1129 | { | |
1130 | __glibcxx_check_max_load_factor(__f); | |
1131 | _Base::max_load_factor(__f); | |
1132 | } | |
1133 | ||
9b81593b FD |
1134 | template<typename... _Args> |
1135 | iterator | |
1136 | emplace(_Args&&... __args) | |
1137 | { | |
1138 | size_type __bucket_count = this->bucket_count(); | |
4b763dee | 1139 | auto __it = _Base::emplace(std::forward<_Args>(__args)...); |
9b81593b | 1140 | _M_check_rehashed(__bucket_count); |
4b763dee | 1141 | return { __it, this }; |
9b81593b FD |
1142 | } |
1143 | ||
1144 | template<typename... _Args> | |
1145 | iterator | |
1146 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
1147 | { | |
1148 | __glibcxx_check_insert(__hint); | |
1149 | size_type __bucket_count = this->bucket_count(); | |
4b763dee FD |
1150 | auto __it = _Base::emplace_hint(__hint.base(), |
1151 | std::forward<_Args>(__args)...); | |
9b81593b | 1152 | _M_check_rehashed(__bucket_count); |
4b763dee | 1153 | return { __it, this }; |
9b81593b FD |
1154 | } |
1155 | ||
ced3cb9f PC |
1156 | iterator |
1157 | insert(const value_type& __obj) | |
77e0bf4e FD |
1158 | { |
1159 | size_type __bucket_count = this->bucket_count(); | |
4b763dee | 1160 | auto __it = _Base::insert(__obj); |
77e0bf4e | 1161 | _M_check_rehashed(__bucket_count); |
4b763dee | 1162 | return { __it, this }; |
77e0bf4e | 1163 | } |
ced3cb9f | 1164 | |
1679da15 FD |
1165 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1166 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
1167 | iterator | |
1168 | insert(value_type&& __x) | |
1169 | { | |
1170 | size_type __bucket_count = this->bucket_count(); | |
1171 | auto __it = _Base::insert(std::move(__x)); | |
1172 | _M_check_rehashed(__bucket_count); | |
1173 | return { __it, this }; | |
1174 | } | |
1175 | ||
ced3cb9f | 1176 | iterator |
d66411ba FD |
1177 | insert(const_iterator __hint, const value_type& __obj) |
1178 | { | |
1179 | __glibcxx_check_insert(__hint); | |
77e0bf4e | 1180 | size_type __bucket_count = this->bucket_count(); |
4b763dee | 1181 | auto __it = _Base::insert(__hint.base(), __obj); |
77e0bf4e | 1182 | _M_check_rehashed(__bucket_count); |
4b763dee | 1183 | return { __it, this }; |
d66411ba | 1184 | } |
ced3cb9f | 1185 | |
1679da15 FD |
1186 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1187 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
1188 | iterator | |
1189 | insert(const_iterator __hint, value_type&& __x) | |
1190 | { | |
1191 | __glibcxx_check_insert(__hint); | |
1192 | size_type __bucket_count = this->bucket_count(); | |
1193 | auto __it = _Base::insert(__hint.base(), std::move(__x)); | |
1194 | _M_check_rehashed(__bucket_count); | |
4b763dee | 1195 | return { __it, this }; |
1679da15 FD |
1196 | } |
1197 | ||
fb7342fd | 1198 | template<typename _Pair, typename = typename |
57cee56a PC |
1199 | std::enable_if<std::is_constructible<value_type, |
1200 | _Pair&&>::value>::type> | |
77e0bf4e FD |
1201 | iterator |
1202 | insert(_Pair&& __obj) | |
1203 | { | |
1204 | size_type __bucket_count = this->bucket_count(); | |
4b763dee | 1205 | auto __it = _Base::insert(std::forward<_Pair>(__obj)); |
77e0bf4e | 1206 | _M_check_rehashed(__bucket_count); |
4b763dee | 1207 | return { __it, this }; |
77e0bf4e | 1208 | } |
fb7342fd PC |
1209 | |
1210 | template<typename _Pair, typename = typename | |
57cee56a PC |
1211 | std::enable_if<std::is_constructible<value_type, |
1212 | _Pair&&>::value>::type> | |
afe96d41 | 1213 | iterator |
d66411ba FD |
1214 | insert(const_iterator __hint, _Pair&& __obj) |
1215 | { | |
1216 | __glibcxx_check_insert(__hint); | |
77e0bf4e | 1217 | size_type __bucket_count = this->bucket_count(); |
4b763dee | 1218 | auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); |
77e0bf4e | 1219 | _M_check_rehashed(__bucket_count); |
4b763dee | 1220 | return { __it, this }; |
d66411ba | 1221 | } |
fb7342fd | 1222 | |
ced3cb9f PC |
1223 | void |
1224 | insert(std::initializer_list<value_type> __l) | |
1225 | { _Base::insert(__l); } | |
1226 | ||
1227 | template<typename _InputIterator> | |
77e0bf4e FD |
1228 | void |
1229 | insert(_InputIterator __first, _InputIterator __last) | |
1230 | { | |
24167c42 FD |
1231 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
1232 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
77e0bf4e | 1233 | size_type __bucket_count = this->bucket_count(); |
24167c42 FD |
1234 | |
1235 | if (__dist.second >= __gnu_debug::__dp_sign) | |
1236 | _Base::insert(__gnu_debug::__unsafe(__first), | |
1237 | __gnu_debug::__unsafe(__last)); | |
1238 | else | |
1239 | _Base::insert(__first, __last); | |
1240 | ||
77e0bf4e | 1241 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
1242 | } |
1243 | ||
2dbe56bd JW |
1244 | #if __cplusplus > 201402L |
1245 | using node_type = typename _Base::node_type; | |
1246 | ||
1247 | node_type | |
1248 | extract(const_iterator __position) | |
1249 | { | |
1250 | __glibcxx_check_erase(__position); | |
4b763dee | 1251 | return _M_extract(__position.base()); |
2dbe56bd JW |
1252 | } |
1253 | ||
1254 | node_type | |
1255 | extract(const key_type& __key) | |
1256 | { | |
4b763dee FD |
1257 | const auto __position = _Base::find(__key); |
1258 | if (__position != _Base::end()) | |
1259 | return _M_extract(__position); | |
2dbe56bd JW |
1260 | return {}; |
1261 | } | |
1262 | ||
1263 | iterator | |
1264 | insert(node_type&& __nh) | |
4b763dee | 1265 | { return { _Base::insert(std::move(__nh)), this }; } |
2dbe56bd JW |
1266 | |
1267 | iterator | |
1268 | insert(const_iterator __hint, node_type&& __nh) | |
1269 | { | |
1270 | __glibcxx_check_insert(__hint); | |
4b763dee | 1271 | return { _Base::insert(__hint.base(), std::move(__nh)), this }; |
2dbe56bd JW |
1272 | } |
1273 | ||
f4b4ce15 FD |
1274 | template<typename _H2, typename _P2> |
1275 | void | |
1276 | merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) | |
1277 | { | |
1278 | auto __guard | |
1279 | = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source); | |
e9a53a4f | 1280 | _Base::merge(__source); |
f4b4ce15 FD |
1281 | } |
1282 | ||
1283 | template<typename _H2, typename _P2> | |
1284 | void | |
1285 | merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) | |
1286 | { merge(__source); } | |
1287 | ||
1288 | template<typename _H2, typename _P2> | |
1289 | void | |
1290 | merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) | |
1291 | { | |
1292 | auto __guard | |
1293 | = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source); | |
e9a53a4f | 1294 | _Base::merge(__source); |
f4b4ce15 FD |
1295 | } |
1296 | ||
1297 | template<typename _H2, typename _P2> | |
1298 | void | |
1299 | merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) | |
1300 | { merge(__source); } | |
2dbe56bd JW |
1301 | #endif // C++17 |
1302 | ||
f4b4ce15 FD |
1303 | using _Base::hash_function; |
1304 | using _Base::key_eq; | |
1305 | ||
ced3cb9f PC |
1306 | iterator |
1307 | find(const key_type& __key) | |
4b763dee | 1308 | { return { _Base::find(__key), this }; } |
ced3cb9f | 1309 | |
d2b1a684 FD |
1310 | #if __cplusplus > 201703L |
1311 | template<typename _Kt, | |
1312 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
1313 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
1314 | iterator | |
1315 | find(const _Kt& __k) | |
1316 | { return { _Base::find(__k), this }; } | |
1317 | #endif | |
1318 | ||
ced3cb9f PC |
1319 | const_iterator |
1320 | find(const key_type& __key) const | |
4b763dee | 1321 | { return { _Base::find(__key), this }; } |
ced3cb9f | 1322 | |
d2b1a684 FD |
1323 | #if __cplusplus > 201703L |
1324 | template<typename _Kt, | |
1325 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
1326 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
1327 | const_iterator | |
1328 | find(const _Kt& __k) const | |
1329 | { return { _Base::find(__k), this }; } | |
1330 | #endif | |
1331 | ||
f4b4ce15 FD |
1332 | using _Base::count; |
1333 | #if __cplusplus > 201703L | |
1334 | using _Base::contains; | |
1335 | #endif | |
1336 | ||
ced3cb9f PC |
1337 | std::pair<iterator, iterator> |
1338 | equal_range(const key_type& __key) | |
1339 | { | |
4b763dee FD |
1340 | auto __res = _Base::equal_range(__key); |
1341 | return { { __res.first, this }, { __res.second, this } }; | |
ced3cb9f PC |
1342 | } |
1343 | ||
d2b1a684 FD |
1344 | #if __cplusplus > 201703L |
1345 | template<typename _Kt, | |
1346 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
1347 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
1348 | std::pair<iterator, iterator> | |
1349 | equal_range(const _Kt& __k) | |
1350 | { | |
1351 | auto __res = _Base::equal_range(__k); | |
1352 | return { { __res.first, this }, { __res.second, this } }; | |
1353 | } | |
1354 | #endif | |
1355 | ||
ced3cb9f PC |
1356 | std::pair<const_iterator, const_iterator> |
1357 | equal_range(const key_type& __key) const | |
1358 | { | |
4b763dee FD |
1359 | auto __res = _Base::equal_range(__key); |
1360 | return { { __res.first, this }, { __res.second, this } }; | |
ced3cb9f PC |
1361 | } |
1362 | ||
d2b1a684 FD |
1363 | #if __cplusplus > 201703L |
1364 | template<typename _Kt, | |
1365 | typename = std::__has_is_transparent_t<_Hash, _Kt>, | |
1366 | typename = std::__has_is_transparent_t<_Pred, _Kt>> | |
1367 | std::pair<const_iterator, const_iterator> | |
1368 | equal_range(const _Kt& __k) const | |
1369 | { | |
1370 | auto __res = _Base::equal_range(__k); | |
1371 | return { { __res.first, this }, { __res.second, this } }; | |
1372 | } | |
1373 | #endif | |
1374 | ||
ced3cb9f PC |
1375 | size_type |
1376 | erase(const key_type& __key) | |
1377 | { | |
1378 | size_type __ret(0); | |
77e0bf4e | 1379 | size_type __bucket_count = this->bucket_count(); |
4b763dee FD |
1380 | auto __pair = _Base::equal_range(__key); |
1381 | for (auto __victim = __pair.first; __victim != __pair.second;) | |
ced3cb9f | 1382 | { |
4b763dee FD |
1383 | _M_invalidate(__victim); |
1384 | __victim = _Base::erase(__victim); | |
d3b8263e | 1385 | ++__ret; |
ced3cb9f | 1386 | } |
4b763dee | 1387 | |
77e0bf4e | 1388 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
1389 | return __ret; |
1390 | } | |
1391 | ||
d723ced2 | 1392 | iterator |
ced3cb9f PC |
1393 | erase(const_iterator __it) |
1394 | { | |
1395 | __glibcxx_check_erase(__it); | |
4b763dee | 1396 | return { _M_erase(__it.base()), this }; |
ced3cb9f PC |
1397 | } |
1398 | ||
5f40d34b FD |
1399 | _Base_iterator |
1400 | erase(_Base_const_iterator __it) | |
1401 | { | |
1402 | __glibcxx_check_erase2(__it); | |
1403 | return _M_erase(__it); | |
1404 | } | |
1405 | ||
6dc88283 PC |
1406 | iterator |
1407 | erase(iterator __it) | |
4b763dee FD |
1408 | { |
1409 | __glibcxx_check_erase(__it); | |
1410 | return { _M_erase(__it.base()), this }; | |
1411 | } | |
6dc88283 | 1412 | |
d723ced2 | 1413 | iterator |
ced3cb9f PC |
1414 | erase(const_iterator __first, const_iterator __last) |
1415 | { | |
1416 | __glibcxx_check_erase_range(__first, __last); | |
4b763dee | 1417 | for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp) |
afe96d41 | 1418 | { |
4b763dee | 1419 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(), |
afe96d41 FD |
1420 | _M_message(__gnu_debug::__msg_valid_range) |
1421 | ._M_iterator(__first, "first") | |
1422 | ._M_iterator(__last, "last")); | |
4b763dee | 1423 | _M_invalidate(__tmp); |
afe96d41 | 1424 | } |
4b763dee | 1425 | |
77e0bf4e | 1426 | size_type __bucket_count = this->bucket_count(); |
4b763dee | 1427 | auto __next = _Base::erase(__first.base(), __last.base()); |
77e0bf4e | 1428 | _M_check_rehashed(__bucket_count); |
4b763dee | 1429 | return { __next, this }; |
ced3cb9f PC |
1430 | } |
1431 | ||
f4b4ce15 FD |
1432 | using _Base::rehash; |
1433 | using _Base::reserve; | |
1434 | ||
ced3cb9f | 1435 | _Base& |
15ee1a77 | 1436 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
1437 | |
1438 | const _Base& | |
d3677132 | 1439 | _M_base() const noexcept { return *this; } |
ced3cb9f | 1440 | |
69b3331e | 1441 | private: |
77e0bf4e FD |
1442 | void |
1443 | _M_check_rehashed(size_type __prev_count) | |
1444 | { | |
1445 | if (__prev_count != this->bucket_count()) | |
20a4550c | 1446 | this->_M_invalidate_all(); |
77e0bf4e | 1447 | } |
4b763dee FD |
1448 | |
1449 | void | |
1450 | _M_invalidate(_Base_const_iterator __victim) | |
1451 | { | |
1452 | this->_M_invalidate_if( | |
1453 | [__victim](_Base_const_iterator __it) { return __it == __victim; }); | |
1454 | this->_M_invalidate_local_if( | |
1455 | [__victim](_Base_const_local_iterator __it) | |
acc1d1a9 | 1456 | { return __it == __victim; }); |
4b763dee FD |
1457 | } |
1458 | ||
1459 | _Base_iterator | |
1460 | _M_erase(_Base_const_iterator __victim) | |
1461 | { | |
1462 | _M_invalidate(__victim); | |
1463 | size_type __bucket_count = this->bucket_count(); | |
1464 | _Base_iterator __next = _Base::erase(__victim); | |
1465 | _M_check_rehashed(__bucket_count); | |
1466 | return __next; | |
1467 | } | |
1468 | ||
1469 | #if __cplusplus > 201402L | |
1470 | node_type | |
1471 | _M_extract(_Base_const_iterator __victim) | |
1472 | { | |
1473 | _M_invalidate(__victim); | |
1474 | return _Base::extract(__victim); | |
1475 | } | |
1476 | #endif | |
e63637ea BK |
1477 | }; |
1478 | ||
957f5fea VV |
1479 | #if __cpp_deduction_guides >= 201606 |
1480 | ||
1481 | template<typename _InputIterator, | |
1482 | typename _Hash = hash<__iter_key_t<_InputIterator>>, | |
1483 | typename _Pred = equal_to<__iter_key_t<_InputIterator>>, | |
1484 | typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, | |
1485 | typename = _RequireInputIter<_InputIterator>, | |
c0cb38c2 FD |
1486 | typename = _RequireNotAllocatorOrIntegral<_Hash>, |
1487 | typename = _RequireNotAllocator<_Pred>, | |
957f5fea VV |
1488 | typename = _RequireAllocator<_Allocator>> |
1489 | unordered_multimap(_InputIterator, _InputIterator, | |
1490 | unordered_multimap<int, int>::size_type = {}, | |
1491 | _Hash = _Hash(), _Pred = _Pred(), | |
1492 | _Allocator = _Allocator()) | |
1493 | -> unordered_multimap<__iter_key_t<_InputIterator>, | |
1494 | __iter_val_t<_InputIterator>, _Hash, _Pred, | |
1495 | _Allocator>; | |
1496 | ||
1497 | template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, | |
1498 | typename _Pred = equal_to<_Key>, | |
1499 | typename _Allocator = allocator<pair<const _Key, _Tp>>, | |
c0cb38c2 FD |
1500 | typename = _RequireNotAllocatorOrIntegral<_Hash>, |
1501 | typename = _RequireNotAllocator<_Pred>, | |
957f5fea VV |
1502 | typename = _RequireAllocator<_Allocator>> |
1503 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, | |
1504 | unordered_multimap<int, int>::size_type = {}, | |
1505 | _Hash = _Hash(), _Pred = _Pred(), | |
1506 | _Allocator = _Allocator()) | |
1507 | -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>; | |
1508 | ||
1509 | template<typename _InputIterator, typename _Allocator, | |
1510 | typename = _RequireInputIter<_InputIterator>, | |
1511 | typename = _RequireAllocator<_Allocator>> | |
1512 | unordered_multimap(_InputIterator, _InputIterator, | |
1513 | unordered_multimap<int, int>::size_type, _Allocator) | |
1514 | -> unordered_multimap<__iter_key_t<_InputIterator>, | |
1515 | __iter_val_t<_InputIterator>, | |
1516 | hash<__iter_key_t<_InputIterator>>, | |
1517 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; | |
1518 | ||
1519 | template<typename _InputIterator, typename _Allocator, | |
1520 | typename = _RequireInputIter<_InputIterator>, | |
1521 | typename = _RequireAllocator<_Allocator>> | |
1522 | unordered_multimap(_InputIterator, _InputIterator, _Allocator) | |
1523 | -> unordered_multimap<__iter_key_t<_InputIterator>, | |
1524 | __iter_val_t<_InputIterator>, | |
1525 | hash<__iter_key_t<_InputIterator>>, | |
1526 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; | |
1527 | ||
1528 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
1529 | typename = _RequireInputIter<_InputIterator>, | |
c0cb38c2 | 1530 | typename = _RequireNotAllocatorOrIntegral<_Hash>, |
957f5fea VV |
1531 | typename = _RequireAllocator<_Allocator>> |
1532 | unordered_multimap(_InputIterator, _InputIterator, | |
1533 | unordered_multimap<int, int>::size_type, _Hash, | |
1534 | _Allocator) | |
1535 | -> unordered_multimap<__iter_key_t<_InputIterator>, | |
1536 | __iter_val_t<_InputIterator>, _Hash, | |
1537 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; | |
1538 | ||
1539 | template<typename _Key, typename _Tp, typename _Allocator, | |
1540 | typename = _RequireAllocator<_Allocator>> | |
1541 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, | |
1542 | unordered_multimap<int, int>::size_type, | |
1543 | _Allocator) | |
1544 | -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; | |
1545 | ||
1546 | template<typename _Key, typename _Tp, typename _Allocator, | |
1547 | typename = _RequireAllocator<_Allocator>> | |
1548 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) | |
1549 | -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; | |
1550 | ||
1551 | template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, | |
c0cb38c2 | 1552 | typename = _RequireNotAllocatorOrIntegral<_Hash>, |
957f5fea VV |
1553 | typename = _RequireAllocator<_Allocator>> |
1554 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, | |
1555 | unordered_multimap<int, int>::size_type, | |
1556 | _Hash, _Allocator) | |
1557 | -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; | |
1558 | ||
1559 | #endif | |
1560 | ||
e63637ea BK |
1561 | template<typename _Key, typename _Tp, typename _Hash, |
1562 | typename _Pred, typename _Alloc> | |
69b3331e PC |
1563 | inline void |
1564 | swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
1565 | unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
c5d9ec56 | 1566 | noexcept(noexcept(__x.swap(__y))) |
69b3331e | 1567 | { __x.swap(__y); } |
e63637ea | 1568 | |
5dc22714 PC |
1569 | template<typename _Key, typename _Tp, typename _Hash, |
1570 | typename _Pred, typename _Alloc> | |
1571 | inline bool | |
1572 | operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
1573 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
099e644e | 1574 | { return __x._M_base() == __y._M_base(); } |
5dc22714 | 1575 | |
7ab9c243 | 1576 | #if __cpp_impl_three_way_comparison < 201907L |
5dc22714 PC |
1577 | template<typename _Key, typename _Tp, typename _Hash, |
1578 | typename _Pred, typename _Alloc> | |
1579 | inline bool | |
1580 | operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
1581 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
1582 | { return !(__x == __y); } | |
7ab9c243 | 1583 | #endif |
5dc22714 | 1584 | |
e63637ea BK |
1585 | } // namespace __debug |
1586 | } // namespace std | |
1587 | ||
734f5023 | 1588 | #endif // C++11 |
c878d6ba | 1589 | |
e63637ea | 1590 | #endif |