]>
Commit | Line | Data |
---|---|---|
e63637ea BK |
1 | // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- |
2 | ||
85ec4feb | 3 | // Copyright (C) 2003-2018 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 PC |
36 | #else |
37 | # include <unordered_map> | |
e63637ea | 38 | |
364c862b | 39 | #include <debug/safe_unordered_container.h> |
15ee1a77 | 40 | #include <debug/safe_container.h> |
ced3cb9f | 41 | #include <debug/safe_iterator.h> |
77e0bf4e | 42 | #include <debug/safe_local_iterator.h> |
e63637ea | 43 | |
12ffa228 | 44 | namespace std _GLIBCXX_VISIBILITY(default) |
e63637ea BK |
45 | { |
46 | namespace __debug | |
47 | { | |
1ceb9e06 | 48 | /// Class std::unordered_map with safety/checking/debug instrumentation. |
e63637ea | 49 | template<typename _Key, typename _Tp, |
ced3cb9f | 50 | typename _Hash = std::hash<_Key>, |
e63637ea | 51 | typename _Pred = std::equal_to<_Key>, |
03d7aff6 | 52 | typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > |
e63637ea | 53 | class unordered_map |
15ee1a77 FD |
54 | : public __gnu_debug::_Safe_container< |
55 | unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, | |
56 | __gnu_debug::_Safe_unordered_container>, | |
57 | public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> | |
e63637ea | 58 | { |
12ffa228 | 59 | typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, |
15ee1a77 FD |
60 | _Pred, _Alloc> _Base; |
61 | typedef __gnu_debug::_Safe_container<unordered_map, | |
62 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
63 | typedef typename _Base::const_iterator _Base_const_iterator; | |
64 | typedef typename _Base::iterator _Base_iterator; | |
65 | typedef typename _Base::const_local_iterator | |
66 | _Base_const_local_iterator; | |
67 | typedef typename _Base::local_iterator _Base_local_iterator; | |
0462b6aa | 68 | |
e9afbed0 FD |
69 | template<typename _ItT, typename _SeqT, typename _CatT> |
70 | friend class ::__gnu_debug::_Safe_iterator; | |
71 | template<typename _ItT, typename _SeqT> | |
72 | friend class ::__gnu_debug::_Safe_local_iterator; | |
73 | ||
e63637ea | 74 | public: |
15ee1a77 FD |
75 | typedef typename _Base::size_type size_type; |
76 | typedef typename _Base::hasher hasher; | |
77 | typedef typename _Base::key_equal key_equal; | |
78 | typedef typename _Base::allocator_type allocator_type; | |
79 | ||
80 | typedef typename _Base::key_type key_type; | |
81 | typedef typename _Base::value_type value_type; | |
82 | ||
83 | typedef __gnu_debug::_Safe_iterator< | |
84 | _Base_iterator, unordered_map> iterator; | |
85 | typedef __gnu_debug::_Safe_iterator< | |
86 | _Base_const_iterator, unordered_map> const_iterator; | |
87 | typedef __gnu_debug::_Safe_local_iterator< | |
88 | _Base_local_iterator, unordered_map> local_iterator; | |
89 | typedef __gnu_debug::_Safe_local_iterator< | |
90 | _Base_const_local_iterator, unordered_map> const_local_iterator; | |
e63637ea | 91 | |
da27f556 FD |
92 | unordered_map() = default; |
93 | ||
e63637ea | 94 | explicit |
da27f556 | 95 | unordered_map(size_type __n, |
e63637ea BK |
96 | const hasher& __hf = hasher(), |
97 | const key_equal& __eql = key_equal(), | |
98 | const allocator_type& __a = allocator_type()) | |
ced3cb9f | 99 | : _Base(__n, __hf, __eql, __a) { } |
e63637ea BK |
100 | |
101 | template<typename _InputIterator> | |
15ee1a77 | 102 | unordered_map(_InputIterator __first, _InputIterator __last, |
417e896e | 103 | size_type __n = 0, |
15ee1a77 FD |
104 | const hasher& __hf = hasher(), |
105 | const key_equal& __eql = key_equal(), | |
e63637ea | 106 | const allocator_type& __a = allocator_type()) |
90aabc7e FD |
107 | : _Base(__gnu_debug::__base( |
108 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
1f5ca1a1 | 109 | __gnu_debug::__base(__last), __n, |
4c2d93db | 110 | __hf, __eql, __a) { } |
e63637ea | 111 | |
0462b6aa | 112 | unordered_map(const unordered_map&) = default; |
e63637ea | 113 | |
ced3cb9f | 114 | unordered_map(const _Base& __x) |
4c2d93db | 115 | : _Base(__x) { } |
ced3cb9f | 116 | |
0462b6aa FD |
117 | unordered_map(unordered_map&&) = default; |
118 | ||
119 | explicit | |
120 | unordered_map(const allocator_type& __a) | |
15ee1a77 | 121 | : _Base(__a) { } |
0462b6aa FD |
122 | |
123 | unordered_map(const unordered_map& __umap, | |
124 | const allocator_type& __a) | |
15ee1a77 | 125 | : _Base(__umap, __a) { } |
0462b6aa FD |
126 | |
127 | unordered_map(unordered_map&& __umap, | |
128 | const allocator_type& __a) | |
15ee1a77 FD |
129 | : _Safe(std::move(__umap._M_safe()), __a), |
130 | _Base(std::move(__umap._M_base()), __a) { } | |
69b3331e | 131 | |
988499f4 | 132 | unordered_map(initializer_list<value_type> __l, |
417e896e | 133 | size_type __n = 0, |
988499f4 JM |
134 | const hasher& __hf = hasher(), |
135 | const key_equal& __eql = key_equal(), | |
136 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 137 | : _Base(__l, __n, __hf, __eql, __a) { } |
ced3cb9f | 138 | |
e55b80f5 FD |
139 | unordered_map(size_type __n, const allocator_type& __a) |
140 | : unordered_map(__n, hasher(), key_equal(), __a) | |
141 | { } | |
142 | ||
143 | unordered_map(size_type __n, | |
144 | const hasher& __hf, | |
145 | const allocator_type& __a) | |
146 | : unordered_map(__n, __hf, key_equal(), __a) | |
147 | { } | |
148 | ||
149 | template<typename _InputIterator> | |
150 | unordered_map(_InputIterator __first, _InputIterator __last, | |
151 | size_type __n, | |
152 | const allocator_type& __a) | |
153 | : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) | |
154 | { } | |
155 | ||
156 | template<typename _InputIterator> | |
157 | unordered_map(_InputIterator __first, _InputIterator __last, | |
158 | size_type __n, | |
159 | const hasher& __hf, | |
160 | const allocator_type& __a) | |
161 | : unordered_map(__first, __last, __n, __hf, key_equal(), __a) | |
162 | { } | |
163 | ||
164 | unordered_map(initializer_list<value_type> __l, | |
165 | size_type __n, | |
166 | const allocator_type& __a) | |
167 | : unordered_map(__l, __n, hasher(), key_equal(), __a) | |
168 | { } | |
169 | ||
170 | unordered_map(initializer_list<value_type> __l, | |
171 | size_type __n, | |
172 | const hasher& __hf, | |
173 | const allocator_type& __a) | |
174 | : unordered_map(__l, __n, __hf, key_equal(), __a) | |
175 | { } | |
176 | ||
15ee1a77 | 177 | ~unordered_map() = default; |
6f59ea25 | 178 | |
ced3cb9f | 179 | unordered_map& |
15ee1a77 | 180 | operator=(const unordered_map&) = default; |
988499f4 | 181 | |
69b3331e | 182 | unordered_map& |
15ee1a77 | 183 | operator=(unordered_map&&) = default; |
69b3331e | 184 | |
988499f4 JM |
185 | unordered_map& |
186 | operator=(initializer_list<value_type> __l) | |
187 | { | |
0462b6aa FD |
188 | _M_base() = __l; |
189 | this->_M_invalidate_all(); | |
988499f4 JM |
190 | return *this; |
191 | } | |
192 | ||
e63637ea | 193 | void |
ff74fd13 | 194 | swap(unordered_map& __x) |
c5d9ec56 | 195 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) |
e63637ea | 196 | { |
15ee1a77 | 197 | _Safe::_M_swap(__x); |
ced3cb9f | 198 | _Base::swap(__x); |
e63637ea | 199 | } |
69b3331e PC |
200 | |
201 | void | |
d3677132 | 202 | clear() noexcept |
69b3331e PC |
203 | { |
204 | _Base::clear(); | |
205 | this->_M_invalidate_all(); | |
206 | } | |
207 | ||
15ee1a77 | 208 | iterator |
d3677132 | 209 | begin() noexcept |
ced3cb9f PC |
210 | { return iterator(_Base::begin(), this); } |
211 | ||
212 | const_iterator | |
d3677132 | 213 | begin() const noexcept |
ced3cb9f PC |
214 | { return const_iterator(_Base::begin(), this); } |
215 | ||
216 | iterator | |
d3677132 | 217 | end() noexcept |
ced3cb9f PC |
218 | { return iterator(_Base::end(), this); } |
219 | ||
220 | const_iterator | |
d3677132 | 221 | end() const noexcept |
ced3cb9f PC |
222 | { return const_iterator(_Base::end(), this); } |
223 | ||
224 | const_iterator | |
d3677132 | 225 | cbegin() const noexcept |
ced3cb9f PC |
226 | { return const_iterator(_Base::begin(), this); } |
227 | ||
228 | const_iterator | |
d3677132 | 229 | cend() const noexcept |
ced3cb9f PC |
230 | { return const_iterator(_Base::end(), this); } |
231 | ||
232 | // local versions | |
77e0bf4e FD |
233 | local_iterator |
234 | begin(size_type __b) | |
7181e991 FD |
235 | { |
236 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 237 | return local_iterator(_Base::begin(__b), this); |
7181e991 | 238 | } |
77e0bf4e FD |
239 | |
240 | local_iterator | |
241 | end(size_type __b) | |
7181e991 FD |
242 | { |
243 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 244 | return local_iterator(_Base::end(__b), this); |
7181e991 | 245 | } |
77e0bf4e FD |
246 | |
247 | const_local_iterator | |
248 | begin(size_type __b) const | |
7181e991 FD |
249 | { |
250 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 251 | return const_local_iterator(_Base::begin(__b), this); |
7181e991 | 252 | } |
77e0bf4e FD |
253 | |
254 | const_local_iterator | |
255 | end(size_type __b) const | |
7181e991 FD |
256 | { |
257 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 258 | return const_local_iterator(_Base::end(__b), this); |
7181e991 | 259 | } |
77e0bf4e FD |
260 | |
261 | const_local_iterator | |
262 | cbegin(size_type __b) const | |
7181e991 FD |
263 | { |
264 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 265 | return const_local_iterator(_Base::cbegin(__b), this); |
7181e991 | 266 | } |
77e0bf4e FD |
267 | |
268 | const_local_iterator | |
269 | cend(size_type __b) const | |
7181e991 FD |
270 | { |
271 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 272 | return const_local_iterator(_Base::cend(__b), this); |
7181e991 FD |
273 | } |
274 | ||
275 | size_type | |
276 | bucket_size(size_type __b) const | |
277 | { | |
278 | __glibcxx_check_bucket_index(__b); | |
279 | return _Base::bucket_size(__b); | |
280 | } | |
ced3cb9f | 281 | |
14cbb5d8 FD |
282 | float |
283 | max_load_factor() const noexcept | |
284 | { return _Base::max_load_factor(); } | |
285 | ||
286 | void | |
287 | max_load_factor(float __f) | |
288 | { | |
289 | __glibcxx_check_max_load_factor(__f); | |
290 | _Base::max_load_factor(__f); | |
291 | } | |
292 | ||
9b81593b FD |
293 | template<typename... _Args> |
294 | std::pair<iterator, bool> | |
295 | emplace(_Args&&... __args) | |
296 | { | |
297 | size_type __bucket_count = this->bucket_count(); | |
298 | std::pair<_Base_iterator, bool> __res | |
299 | = _Base::emplace(std::forward<_Args>(__args)...); | |
300 | _M_check_rehashed(__bucket_count); | |
301 | return std::make_pair(iterator(__res.first, this), __res.second); | |
302 | } | |
303 | ||
304 | template<typename... _Args> | |
305 | iterator | |
306 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
307 | { | |
308 | __glibcxx_check_insert(__hint); | |
309 | size_type __bucket_count = this->bucket_count(); | |
310 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
311 | std::forward<_Args>(__args)...); | |
312 | _M_check_rehashed(__bucket_count); | |
313 | return iterator(__it, this); | |
314 | } | |
315 | ||
ced3cb9f PC |
316 | std::pair<iterator, bool> |
317 | insert(const value_type& __obj) | |
318 | { | |
77e0bf4e | 319 | size_type __bucket_count = this->bucket_count(); |
1679da15 | 320 | auto __res = _Base::insert(__obj); |
77e0bf4e | 321 | _M_check_rehashed(__bucket_count); |
1679da15 | 322 | return { iterator(__res.first, this), __res.second }; |
ced3cb9f PC |
323 | } |
324 | ||
1679da15 FD |
325 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
326 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
327 | std::pair<iterator, bool> | |
328 | insert(value_type&& __x) | |
ced3cb9f | 329 | { |
77e0bf4e | 330 | size_type __bucket_count = this->bucket_count(); |
1679da15 | 331 | auto __res = _Base::insert(std::move(__x)); |
77e0bf4e | 332 | _M_check_rehashed(__bucket_count); |
1679da15 | 333 | return { iterator(__res.first, this), __res.second }; |
ced3cb9f PC |
334 | } |
335 | ||
fb7342fd | 336 | template<typename _Pair, typename = typename |
57cee56a PC |
337 | std::enable_if<std::is_constructible<value_type, |
338 | _Pair&&>::value>::type> | |
77e0bf4e FD |
339 | std::pair<iterator, bool> |
340 | insert(_Pair&& __obj) | |
341 | { | |
342 | size_type __bucket_count = this->bucket_count(); | |
afe96d41 FD |
343 | std::pair<_Base_iterator, bool> __res = |
344 | _Base::insert(std::forward<_Pair>(__obj)); | |
77e0bf4e | 345 | _M_check_rehashed(__bucket_count); |
fb7342fd PC |
346 | return std::make_pair(iterator(__res.first, this), __res.second); |
347 | } | |
348 | ||
1679da15 FD |
349 | iterator |
350 | insert(const_iterator __hint, const value_type& __obj) | |
351 | { | |
352 | __glibcxx_check_insert(__hint); | |
353 | size_type __bucket_count = this->bucket_count(); | |
354 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); | |
355 | _M_check_rehashed(__bucket_count); | |
356 | return iterator(__it, this); | |
357 | } | |
358 | ||
359 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
360 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
361 | iterator | |
362 | insert(const_iterator __hint, value_type&& __x) | |
363 | { | |
364 | __glibcxx_check_insert(__hint); | |
365 | size_type __bucket_count = this->bucket_count(); | |
366 | auto __it = _Base::insert(__hint.base(), std::move(__x)); | |
367 | _M_check_rehashed(__bucket_count); | |
368 | return iterator(__it, this); | |
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 | iterator |
375 | insert(const_iterator __hint, _Pair&& __obj) | |
376 | { | |
d66411ba | 377 | __glibcxx_check_insert(__hint); |
77e0bf4e FD |
378 | size_type __bucket_count = this->bucket_count(); |
379 | _Base_iterator __it = | |
380 | _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); | |
381 | _M_check_rehashed(__bucket_count); | |
382 | return iterator(__it, this); | |
fb7342fd PC |
383 | } |
384 | ||
ced3cb9f PC |
385 | void |
386 | insert(std::initializer_list<value_type> __l) | |
77e0bf4e FD |
387 | { |
388 | size_type __bucket_count = this->bucket_count(); | |
389 | _Base::insert(__l); | |
390 | _M_check_rehashed(__bucket_count); | |
391 | } | |
ced3cb9f PC |
392 | |
393 | template<typename _InputIterator> | |
77e0bf4e FD |
394 | void |
395 | insert(_InputIterator __first, _InputIterator __last) | |
396 | { | |
24167c42 FD |
397 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
398 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
77e0bf4e | 399 | size_type __bucket_count = this->bucket_count(); |
24167c42 FD |
400 | |
401 | if (__dist.second >= __gnu_debug::__dp_sign) | |
402 | _Base::insert(__gnu_debug::__unsafe(__first), | |
403 | __gnu_debug::__unsafe(__last)); | |
404 | else | |
405 | _Base::insert(__first, __last); | |
406 | ||
77e0bf4e | 407 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
408 | } |
409 | ||
66c182be JW |
410 | #if __cplusplus > 201402L |
411 | template <typename... _Args> | |
412 | pair<iterator, bool> | |
413 | try_emplace(const key_type& __k, _Args&&... __args) | |
414 | { | |
415 | auto __res = _Base::try_emplace(__k, | |
416 | std::forward<_Args>(__args)...); | |
417 | return { iterator(__res.first, this), __res.second }; | |
418 | } | |
419 | ||
420 | template <typename... _Args> | |
421 | pair<iterator, bool> | |
422 | try_emplace(key_type&& __k, _Args&&... __args) | |
423 | { | |
424 | auto __res = _Base::try_emplace(std::move(__k), | |
425 | std::forward<_Args>(__args)...); | |
426 | return { iterator(__res.first, this), __res.second }; | |
427 | } | |
428 | ||
429 | template <typename... _Args> | |
430 | iterator | |
431 | try_emplace(const_iterator __hint, const key_type& __k, | |
432 | _Args&&... __args) | |
433 | { | |
434 | __glibcxx_check_insert(__hint); | |
435 | return iterator(_Base::try_emplace(__hint.base(), __k, | |
436 | std::forward<_Args>(__args)...), | |
437 | this); | |
438 | } | |
439 | ||
440 | template <typename... _Args> | |
441 | iterator | |
442 | try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) | |
443 | { | |
444 | __glibcxx_check_insert(__hint); | |
445 | return iterator(_Base::try_emplace(__hint.base(), std::move(__k), | |
446 | std::forward<_Args>(__args)...), | |
447 | this); | |
448 | } | |
449 | ||
450 | template <typename _Obj> | |
451 | pair<iterator, bool> | |
452 | insert_or_assign(const key_type& __k, _Obj&& __obj) | |
453 | { | |
454 | auto __res = _Base::insert_or_assign(__k, | |
455 | std::forward<_Obj>(__obj)); | |
456 | return { iterator(__res.first, this), __res.second }; | |
457 | } | |
458 | ||
459 | template <typename _Obj> | |
460 | pair<iterator, bool> | |
461 | insert_or_assign(key_type&& __k, _Obj&& __obj) | |
462 | { | |
463 | auto __res = _Base::insert_or_assign(std::move(__k), | |
464 | std::forward<_Obj>(__obj)); | |
465 | return { iterator(__res.first, this), __res.second }; | |
466 | } | |
467 | ||
468 | template <typename _Obj> | |
469 | iterator | |
470 | insert_or_assign(const_iterator __hint, const key_type& __k, | |
471 | _Obj&& __obj) | |
472 | { | |
473 | __glibcxx_check_insert(__hint); | |
474 | return iterator(_Base::insert_or_assign(__hint.base(), __k, | |
475 | std::forward<_Obj>(__obj)), | |
476 | this); | |
477 | } | |
478 | ||
479 | template <typename _Obj> | |
480 | iterator | |
481 | insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) | |
482 | { | |
483 | __glibcxx_check_insert(__hint); | |
484 | return iterator(_Base::insert_or_assign(__hint.base(), | |
485 | std::move(__k), | |
486 | std::forward<_Obj>(__obj)), | |
487 | this); | |
488 | } | |
2dbe56bd | 489 | #endif // C++17 |
66c182be | 490 | |
2dbe56bd JW |
491 | #if __cplusplus > 201402L |
492 | using node_type = typename _Base::node_type; | |
adaefe2a | 493 | using insert_return_type = _Node_insert_return<iterator, node_type>; |
2dbe56bd JW |
494 | |
495 | node_type | |
496 | extract(const_iterator __position) | |
497 | { | |
498 | __glibcxx_check_erase(__position); | |
499 | _Base_const_iterator __victim = __position.base(); | |
500 | this->_M_invalidate_if( | |
501 | [__victim](_Base_const_iterator __it) { return __it == __victim; } | |
502 | ); | |
503 | this->_M_invalidate_local_if( | |
504 | [__victim](_Base_const_local_iterator __it) { | |
505 | return __it._M_curr() == __victim._M_cur; | |
506 | }); | |
507 | return _Base::extract(__position.base()); | |
508 | } | |
509 | ||
510 | node_type | |
511 | extract(const key_type& __key) | |
512 | { | |
513 | const auto __position = find(__key); | |
514 | if (__position != end()) | |
515 | return extract(__position); | |
516 | return {}; | |
517 | } | |
518 | ||
519 | insert_return_type | |
520 | insert(node_type&& __nh) | |
521 | { | |
522 | auto __ret = _Base::insert(std::move(__nh)); | |
523 | iterator __pos = iterator(__ret.position, this); | |
adaefe2a | 524 | return { __pos, __ret.inserted, std::move(__ret.node) }; |
2dbe56bd JW |
525 | } |
526 | ||
527 | iterator | |
528 | insert(const_iterator __hint, node_type&& __nh) | |
529 | { | |
530 | __glibcxx_check_insert(__hint); | |
531 | return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); | |
532 | } | |
533 | ||
534 | using _Base::merge; | |
535 | #endif // C++17 | |
66c182be | 536 | |
ced3cb9f PC |
537 | iterator |
538 | find(const key_type& __key) | |
539 | { return iterator(_Base::find(__key), this); } | |
540 | ||
541 | const_iterator | |
542 | find(const key_type& __key) const | |
543 | { return const_iterator(_Base::find(__key), this); } | |
544 | ||
545 | std::pair<iterator, iterator> | |
546 | equal_range(const key_type& __key) | |
547 | { | |
afe96d41 FD |
548 | std::pair<_Base_iterator, _Base_iterator> __res = |
549 | _Base::equal_range(__key); | |
ced3cb9f PC |
550 | return std::make_pair(iterator(__res.first, this), |
551 | iterator(__res.second, this)); | |
552 | } | |
553 | ||
554 | std::pair<const_iterator, const_iterator> | |
555 | equal_range(const key_type& __key) const | |
556 | { | |
afe96d41 FD |
557 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
558 | _Base::equal_range(__key); | |
ced3cb9f PC |
559 | return std::make_pair(const_iterator(__res.first, this), |
560 | const_iterator(__res.second, this)); | |
561 | } | |
562 | ||
563 | size_type | |
564 | erase(const key_type& __key) | |
565 | { | |
566 | size_type __ret(0); | |
afe96d41 FD |
567 | _Base_iterator __victim(_Base::find(__key)); |
568 | if (__victim != _Base::end()) | |
ced3cb9f | 569 | { |
77e0bf4e FD |
570 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
571 | { return __it == __victim; }); | |
77e0bf4e | 572 | this->_M_invalidate_local_if( |
5b3be7cf | 573 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 574 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e | 575 | size_type __bucket_count = this->bucket_count(); |
afe96d41 | 576 | _Base::erase(__victim); |
77e0bf4e | 577 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
578 | __ret = 1; |
579 | } | |
580 | return __ret; | |
581 | } | |
582 | ||
d723ced2 | 583 | iterator |
ced3cb9f PC |
584 | erase(const_iterator __it) |
585 | { | |
586 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
587 | _Base_const_iterator __victim = __it.base(); |
588 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
589 | { return __it == __victim; }); | |
77e0bf4e | 590 | this->_M_invalidate_local_if( |
5b3be7cf | 591 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 592 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e | 593 | size_type __bucket_count = this->bucket_count(); |
15ee1a77 | 594 | _Base_iterator __next = _Base::erase(__it.base()); |
77e0bf4e FD |
595 | _M_check_rehashed(__bucket_count); |
596 | return iterator(__next, this); | |
ced3cb9f PC |
597 | } |
598 | ||
6dc88283 PC |
599 | iterator |
600 | erase(iterator __it) | |
601 | { return erase(const_iterator(__it)); } | |
602 | ||
d723ced2 | 603 | iterator |
ced3cb9f PC |
604 | erase(const_iterator __first, const_iterator __last) |
605 | { | |
606 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
607 | for (_Base_const_iterator __tmp = __first.base(); |
608 | __tmp != __last.base(); ++__tmp) | |
609 | { | |
610 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
611 | _M_message(__gnu_debug::__msg_valid_range) | |
612 | ._M_iterator(__first, "first") | |
613 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
614 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
615 | { return __it == __tmp; }); | |
77e0bf4e | 616 | this->_M_invalidate_local_if( |
5b3be7cf | 617 | [__tmp](_Base_const_local_iterator __it) |
92e16228 | 618 | { return __it._M_curr() == __tmp._M_cur; }); |
afe96d41 | 619 | } |
77e0bf4e FD |
620 | size_type __bucket_count = this->bucket_count(); |
621 | _Base_iterator __next = _Base::erase(__first.base(), __last.base()); | |
622 | _M_check_rehashed(__bucket_count); | |
623 | return iterator(__next, this); | |
ced3cb9f PC |
624 | } |
625 | ||
626 | _Base& | |
15ee1a77 | 627 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
628 | |
629 | const _Base& | |
15ee1a77 | 630 | _M_base() const noexcept { return *this; } |
ced3cb9f | 631 | |
69b3331e | 632 | private: |
77e0bf4e FD |
633 | void |
634 | _M_check_rehashed(size_type __prev_count) | |
635 | { | |
636 | if (__prev_count != this->bucket_count()) | |
15ee1a77 | 637 | this->_M_invalidate_locals(); |
77e0bf4e | 638 | } |
e63637ea BK |
639 | }; |
640 | ||
957f5fea VV |
641 | #if __cpp_deduction_guides >= 201606 |
642 | ||
643 | template<typename _InputIterator, | |
644 | typename _Hash = hash<__iter_key_t<_InputIterator>>, | |
645 | typename _Pred = equal_to<__iter_key_t<_InputIterator>>, | |
646 | typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, | |
647 | typename = _RequireInputIter<_InputIterator>, | |
648 | typename = _RequireAllocator<_Allocator>> | |
649 | unordered_map(_InputIterator, _InputIterator, | |
650 | typename unordered_map<int, int>::size_type = {}, | |
651 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
652 | -> unordered_map<__iter_key_t<_InputIterator>, | |
653 | __iter_val_t<_InputIterator>, | |
654 | _Hash, _Pred, _Allocator>; | |
655 | ||
656 | template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, | |
657 | typename _Pred = equal_to<_Key>, | |
658 | typename _Allocator = allocator<pair<const _Key, _Tp>>, | |
659 | typename = _RequireAllocator<_Allocator>> | |
660 | unordered_map(initializer_list<pair<_Key, _Tp>>, | |
661 | typename unordered_map<int, int>::size_type = {}, | |
662 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
663 | -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>; | |
664 | ||
665 | template<typename _InputIterator, typename _Allocator, | |
666 | typename = _RequireInputIter<_InputIterator>, | |
667 | typename = _RequireAllocator<_Allocator>> | |
668 | unordered_map(_InputIterator, _InputIterator, | |
669 | typename unordered_map<int, int>::size_type, _Allocator) | |
670 | -> unordered_map<__iter_key_t<_InputIterator>, | |
671 | __iter_val_t<_InputIterator>, | |
672 | hash<__iter_key_t<_InputIterator>>, | |
673 | equal_to<__iter_key_t<_InputIterator>>, | |
674 | _Allocator>; | |
675 | ||
676 | template<typename _InputIterator, typename _Allocator, | |
677 | typename = _RequireInputIter<_InputIterator>, | |
678 | typename = _RequireAllocator<_Allocator>> | |
679 | unordered_map(_InputIterator, _InputIterator, _Allocator) | |
680 | -> unordered_map<__iter_key_t<_InputIterator>, | |
681 | __iter_val_t<_InputIterator>, | |
682 | hash<__iter_key_t<_InputIterator>>, | |
683 | equal_to<__iter_key_t<_InputIterator>>, | |
684 | _Allocator>; | |
685 | ||
686 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
687 | typename = _RequireInputIter<_InputIterator>, | |
688 | typename = _RequireAllocator<_Allocator>> | |
689 | unordered_map(_InputIterator, _InputIterator, | |
690 | typename unordered_map<int, int>::size_type, | |
691 | _Hash, _Allocator) | |
692 | -> unordered_map<__iter_key_t<_InputIterator>, | |
693 | __iter_val_t<_InputIterator>, _Hash, | |
694 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; | |
695 | ||
696 | template<typename _Key, typename _Tp, typename _Allocator, | |
697 | typename = _RequireAllocator<_Allocator>> | |
698 | unordered_map(initializer_list<pair<_Key, _Tp>>, | |
699 | typename unordered_map<int, int>::size_type, | |
700 | _Allocator) | |
701 | -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; | |
702 | ||
703 | template<typename _Key, typename _Tp, typename _Allocator, | |
68e601d8 | 704 | typename = _RequireAllocator<_Allocator>> |
957f5fea VV |
705 | unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) |
706 | -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; | |
707 | ||
708 | template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, | |
709 | typename = _RequireAllocator<_Allocator>> | |
710 | unordered_map(initializer_list<pair<_Key, _Tp>>, | |
711 | typename unordered_map<int, int>::size_type, | |
712 | _Hash, _Allocator) | |
713 | -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; | |
714 | ||
715 | #endif | |
716 | ||
e63637ea BK |
717 | template<typename _Key, typename _Tp, typename _Hash, |
718 | typename _Pred, typename _Alloc> | |
69b3331e PC |
719 | inline void |
720 | swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
721 | unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
c5d9ec56 | 722 | noexcept(noexcept(__x.swap(__y))) |
69b3331e | 723 | { __x.swap(__y); } |
e63637ea | 724 | |
5dc22714 PC |
725 | template<typename _Key, typename _Tp, typename _Hash, |
726 | typename _Pred, typename _Alloc> | |
727 | inline bool | |
728 | operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
729 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
099e644e | 730 | { return __x._M_base() == __y._M_base(); } |
5dc22714 PC |
731 | |
732 | template<typename _Key, typename _Tp, typename _Hash, | |
733 | typename _Pred, typename _Alloc> | |
734 | inline bool | |
735 | operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
736 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
737 | { return !(__x == __y); } | |
738 | ||
e63637ea | 739 | |
1ceb9e06 | 740 | /// Class std::unordered_multimap with safety/checking/debug instrumentation. |
e63637ea | 741 | template<typename _Key, typename _Tp, |
ced3cb9f | 742 | typename _Hash = std::hash<_Key>, |
e63637ea | 743 | typename _Pred = std::equal_to<_Key>, |
03d7aff6 | 744 | typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > |
e63637ea | 745 | class unordered_multimap |
15ee1a77 FD |
746 | : public __gnu_debug::_Safe_container< |
747 | unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, | |
748 | __gnu_debug::_Safe_unordered_container>, | |
749 | public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> | |
e63637ea | 750 | { |
12ffa228 | 751 | typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, |
15ee1a77 FD |
752 | _Pred, _Alloc> _Base; |
753 | typedef __gnu_debug::_Safe_container<unordered_multimap, | |
754 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
755 | typedef typename _Base::const_iterator _Base_const_iterator; | |
756 | typedef typename _Base::iterator _Base_iterator; | |
77e0bf4e | 757 | typedef typename _Base::const_local_iterator _Base_const_local_iterator; |
15ee1a77 | 758 | typedef typename _Base::local_iterator _Base_local_iterator; |
0462b6aa | 759 | |
e9afbed0 FD |
760 | template<typename _ItT, typename _SeqT, typename _CatT> |
761 | friend class ::__gnu_debug::_Safe_iterator; | |
762 | template<typename _ItT, typename _SeqT> | |
763 | friend class ::__gnu_debug::_Safe_local_iterator; | |
764 | ||
e63637ea | 765 | public: |
15ee1a77 FD |
766 | typedef typename _Base::size_type size_type; |
767 | typedef typename _Base::hasher hasher; | |
768 | typedef typename _Base::key_equal key_equal; | |
769 | typedef typename _Base::allocator_type allocator_type; | |
770 | ||
771 | typedef typename _Base::key_type key_type; | |
772 | typedef typename _Base::value_type value_type; | |
773 | ||
774 | typedef __gnu_debug::_Safe_iterator< | |
775 | _Base_iterator, unordered_multimap> iterator; | |
776 | typedef __gnu_debug::_Safe_iterator< | |
777 | _Base_const_iterator, unordered_multimap> const_iterator; | |
77e0bf4e | 778 | typedef __gnu_debug::_Safe_local_iterator< |
15ee1a77 | 779 | _Base_local_iterator, unordered_multimap> local_iterator; |
77e0bf4e | 780 | typedef __gnu_debug::_Safe_local_iterator< |
e9afbed0 | 781 | _Base_const_local_iterator, unordered_multimap> const_local_iterator; |
e63637ea | 782 | |
da27f556 FD |
783 | unordered_multimap() = default; |
784 | ||
e63637ea | 785 | explicit |
da27f556 | 786 | unordered_multimap(size_type __n, |
ced3cb9f PC |
787 | const hasher& __hf = hasher(), |
788 | const key_equal& __eql = key_equal(), | |
789 | const allocator_type& __a = allocator_type()) | |
790 | : _Base(__n, __hf, __eql, __a) { } | |
e63637ea BK |
791 | |
792 | template<typename _InputIterator> | |
15ee1a77 | 793 | unordered_multimap(_InputIterator __first, _InputIterator __last, |
417e896e | 794 | size_type __n = 0, |
15ee1a77 FD |
795 | const hasher& __hf = hasher(), |
796 | const key_equal& __eql = key_equal(), | |
ced3cb9f | 797 | const allocator_type& __a = allocator_type()) |
90aabc7e FD |
798 | : _Base(__gnu_debug::__base( |
799 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
1f5ca1a1 | 800 | __gnu_debug::__base(__last), __n, |
4c2d93db | 801 | __hf, __eql, __a) { } |
ced3cb9f | 802 | |
0462b6aa | 803 | unordered_multimap(const unordered_multimap&) = default; |
ced3cb9f | 804 | |
15ee1a77 | 805 | unordered_multimap(const _Base& __x) |
4c2d93db | 806 | : _Base(__x) { } |
ced3cb9f | 807 | |
0462b6aa FD |
808 | unordered_multimap(unordered_multimap&&) = default; |
809 | ||
810 | explicit | |
811 | unordered_multimap(const allocator_type& __a) | |
15ee1a77 | 812 | : _Base(__a) { } |
0462b6aa FD |
813 | |
814 | unordered_multimap(const unordered_multimap& __umap, | |
815 | const allocator_type& __a) | |
15ee1a77 | 816 | : _Base(__umap, __a) { } |
0462b6aa FD |
817 | |
818 | unordered_multimap(unordered_multimap&& __umap, | |
819 | const allocator_type& __a) | |
15ee1a77 FD |
820 | : _Safe(std::move(__umap._M_safe()), __a), |
821 | _Base(std::move(__umap._M_base()), __a) { } | |
e63637ea | 822 | |
988499f4 | 823 | unordered_multimap(initializer_list<value_type> __l, |
417e896e | 824 | size_type __n = 0, |
988499f4 JM |
825 | const hasher& __hf = hasher(), |
826 | const key_equal& __eql = key_equal(), | |
827 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 828 | : _Base(__l, __n, __hf, __eql, __a) { } |
e63637ea | 829 | |
e55b80f5 FD |
830 | unordered_multimap(size_type __n, const allocator_type& __a) |
831 | : unordered_multimap(__n, hasher(), key_equal(), __a) | |
832 | { } | |
833 | ||
834 | unordered_multimap(size_type __n, const hasher& __hf, | |
835 | const allocator_type& __a) | |
836 | : unordered_multimap(__n, __hf, key_equal(), __a) | |
837 | { } | |
838 | ||
839 | template<typename _InputIterator> | |
840 | unordered_multimap(_InputIterator __first, _InputIterator __last, | |
841 | size_type __n, | |
842 | const allocator_type& __a) | |
843 | : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) | |
844 | { } | |
845 | ||
846 | template<typename _InputIterator> | |
847 | unordered_multimap(_InputIterator __first, _InputIterator __last, | |
848 | size_type __n, const hasher& __hf, | |
849 | const allocator_type& __a) | |
850 | : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) | |
851 | { } | |
852 | ||
853 | unordered_multimap(initializer_list<value_type> __l, | |
854 | size_type __n, | |
855 | const allocator_type& __a) | |
856 | : unordered_multimap(__l, __n, hasher(), key_equal(), __a) | |
857 | { } | |
858 | ||
859 | unordered_multimap(initializer_list<value_type> __l, | |
860 | size_type __n, const hasher& __hf, | |
861 | const allocator_type& __a) | |
862 | : unordered_multimap(__l, __n, __hf, key_equal(), __a) | |
863 | { } | |
864 | ||
15ee1a77 | 865 | ~unordered_multimap() = default; |
6f59ea25 | 866 | |
ced3cb9f | 867 | unordered_multimap& |
15ee1a77 | 868 | operator=(const unordered_multimap&) = default; |
69b3331e PC |
869 | |
870 | unordered_multimap& | |
15ee1a77 | 871 | operator=(unordered_multimap&&) = default; |
69b3331e | 872 | |
988499f4 JM |
873 | unordered_multimap& |
874 | operator=(initializer_list<value_type> __l) | |
875 | { | |
15ee1a77 | 876 | this->_M_base() = __l; |
0462b6aa | 877 | this->_M_invalidate_all(); |
988499f4 JM |
878 | return *this; |
879 | } | |
880 | ||
e63637ea | 881 | void |
ff74fd13 | 882 | swap(unordered_multimap& __x) |
c5d9ec56 | 883 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) |
e63637ea | 884 | { |
15ee1a77 | 885 | _Safe::_M_swap(__x); |
ced3cb9f | 886 | _Base::swap(__x); |
e63637ea | 887 | } |
69b3331e PC |
888 | |
889 | void | |
d3677132 | 890 | clear() noexcept |
69b3331e PC |
891 | { |
892 | _Base::clear(); | |
893 | this->_M_invalidate_all(); | |
894 | } | |
895 | ||
15ee1a77 | 896 | iterator |
d3677132 | 897 | begin() noexcept |
ced3cb9f PC |
898 | { return iterator(_Base::begin(), this); } |
899 | ||
900 | const_iterator | |
d3677132 | 901 | begin() const noexcept |
ced3cb9f PC |
902 | { return const_iterator(_Base::begin(), this); } |
903 | ||
904 | iterator | |
d3677132 | 905 | end() noexcept |
ced3cb9f PC |
906 | { return iterator(_Base::end(), this); } |
907 | ||
908 | const_iterator | |
d3677132 | 909 | end() const noexcept |
ced3cb9f PC |
910 | { return const_iterator(_Base::end(), this); } |
911 | ||
912 | const_iterator | |
d3677132 | 913 | cbegin() const noexcept |
ced3cb9f PC |
914 | { return const_iterator(_Base::begin(), this); } |
915 | ||
916 | const_iterator | |
d3677132 | 917 | cend() const noexcept |
ced3cb9f PC |
918 | { return const_iterator(_Base::end(), this); } |
919 | ||
920 | // local versions | |
77e0bf4e FD |
921 | local_iterator |
922 | begin(size_type __b) | |
7181e991 FD |
923 | { |
924 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 925 | return local_iterator(_Base::begin(__b), this); |
7181e991 | 926 | } |
77e0bf4e FD |
927 | |
928 | local_iterator | |
929 | end(size_type __b) | |
7181e991 FD |
930 | { |
931 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 932 | return local_iterator(_Base::end(__b), this); |
7181e991 | 933 | } |
77e0bf4e FD |
934 | |
935 | const_local_iterator | |
936 | begin(size_type __b) const | |
7181e991 FD |
937 | { |
938 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 939 | return const_local_iterator(_Base::begin(__b), this); |
7181e991 | 940 | } |
77e0bf4e FD |
941 | |
942 | const_local_iterator | |
943 | end(size_type __b) const | |
7181e991 FD |
944 | { |
945 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 946 | return const_local_iterator(_Base::end(__b), this); |
7181e991 | 947 | } |
77e0bf4e FD |
948 | |
949 | const_local_iterator | |
950 | cbegin(size_type __b) const | |
7181e991 FD |
951 | { |
952 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 953 | return const_local_iterator(_Base::cbegin(__b), this); |
7181e991 | 954 | } |
77e0bf4e FD |
955 | |
956 | const_local_iterator | |
957 | cend(size_type __b) const | |
7181e991 FD |
958 | { |
959 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 960 | return const_local_iterator(_Base::cend(__b), this); |
7181e991 FD |
961 | } |
962 | ||
963 | size_type | |
964 | bucket_size(size_type __b) const | |
965 | { | |
966 | __glibcxx_check_bucket_index(__b); | |
967 | return _Base::bucket_size(__b); | |
968 | } | |
ced3cb9f | 969 | |
14cbb5d8 FD |
970 | float |
971 | max_load_factor() const noexcept | |
972 | { return _Base::max_load_factor(); } | |
973 | ||
974 | void | |
975 | max_load_factor(float __f) | |
976 | { | |
977 | __glibcxx_check_max_load_factor(__f); | |
978 | _Base::max_load_factor(__f); | |
979 | } | |
980 | ||
9b81593b FD |
981 | template<typename... _Args> |
982 | iterator | |
983 | emplace(_Args&&... __args) | |
984 | { | |
985 | size_type __bucket_count = this->bucket_count(); | |
986 | _Base_iterator __it | |
987 | = _Base::emplace(std::forward<_Args>(__args)...); | |
988 | _M_check_rehashed(__bucket_count); | |
989 | return iterator(__it, this); | |
990 | } | |
991 | ||
992 | template<typename... _Args> | |
993 | iterator | |
994 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
995 | { | |
996 | __glibcxx_check_insert(__hint); | |
997 | size_type __bucket_count = this->bucket_count(); | |
998 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
999 | std::forward<_Args>(__args)...); | |
1000 | _M_check_rehashed(__bucket_count); | |
1001 | return iterator(__it, this); | |
1002 | } | |
1003 | ||
ced3cb9f PC |
1004 | iterator |
1005 | insert(const value_type& __obj) | |
77e0bf4e FD |
1006 | { |
1007 | size_type __bucket_count = this->bucket_count(); | |
1008 | _Base_iterator __it = _Base::insert(__obj); | |
1009 | _M_check_rehashed(__bucket_count); | |
1010 | return iterator(__it, this); | |
1011 | } | |
ced3cb9f | 1012 | |
1679da15 FD |
1013 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1014 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
1015 | iterator | |
1016 | insert(value_type&& __x) | |
1017 | { | |
1018 | size_type __bucket_count = this->bucket_count(); | |
1019 | auto __it = _Base::insert(std::move(__x)); | |
1020 | _M_check_rehashed(__bucket_count); | |
1021 | return { __it, this }; | |
1022 | } | |
1023 | ||
ced3cb9f | 1024 | iterator |
d66411ba FD |
1025 | insert(const_iterator __hint, const value_type& __obj) |
1026 | { | |
1027 | __glibcxx_check_insert(__hint); | |
77e0bf4e FD |
1028 | size_type __bucket_count = this->bucket_count(); |
1029 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); | |
1030 | _M_check_rehashed(__bucket_count); | |
1031 | return iterator(__it, this); | |
d66411ba | 1032 | } |
ced3cb9f | 1033 | |
1679da15 FD |
1034 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1035 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
1036 | iterator | |
1037 | insert(const_iterator __hint, value_type&& __x) | |
1038 | { | |
1039 | __glibcxx_check_insert(__hint); | |
1040 | size_type __bucket_count = this->bucket_count(); | |
1041 | auto __it = _Base::insert(__hint.base(), std::move(__x)); | |
1042 | _M_check_rehashed(__bucket_count); | |
1043 | return iterator(__it, this); | |
1044 | } | |
1045 | ||
fb7342fd | 1046 | template<typename _Pair, typename = typename |
57cee56a PC |
1047 | std::enable_if<std::is_constructible<value_type, |
1048 | _Pair&&>::value>::type> | |
77e0bf4e FD |
1049 | iterator |
1050 | insert(_Pair&& __obj) | |
1051 | { | |
1052 | size_type __bucket_count = this->bucket_count(); | |
1053 | _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); | |
1054 | _M_check_rehashed(__bucket_count); | |
1055 | return iterator(__it, this); | |
1056 | } | |
fb7342fd PC |
1057 | |
1058 | template<typename _Pair, typename = typename | |
57cee56a PC |
1059 | std::enable_if<std::is_constructible<value_type, |
1060 | _Pair&&>::value>::type> | |
afe96d41 | 1061 | iterator |
d66411ba FD |
1062 | insert(const_iterator __hint, _Pair&& __obj) |
1063 | { | |
1064 | __glibcxx_check_insert(__hint); | |
77e0bf4e FD |
1065 | size_type __bucket_count = this->bucket_count(); |
1066 | _Base_iterator __it = | |
1067 | _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); | |
1068 | _M_check_rehashed(__bucket_count); | |
1069 | return iterator(__it, this); | |
d66411ba | 1070 | } |
fb7342fd | 1071 | |
ced3cb9f PC |
1072 | void |
1073 | insert(std::initializer_list<value_type> __l) | |
1074 | { _Base::insert(__l); } | |
1075 | ||
1076 | template<typename _InputIterator> | |
77e0bf4e FD |
1077 | void |
1078 | insert(_InputIterator __first, _InputIterator __last) | |
1079 | { | |
24167c42 FD |
1080 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
1081 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
77e0bf4e | 1082 | size_type __bucket_count = this->bucket_count(); |
24167c42 FD |
1083 | |
1084 | if (__dist.second >= __gnu_debug::__dp_sign) | |
1085 | _Base::insert(__gnu_debug::__unsafe(__first), | |
1086 | __gnu_debug::__unsafe(__last)); | |
1087 | else | |
1088 | _Base::insert(__first, __last); | |
1089 | ||
77e0bf4e | 1090 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
1091 | } |
1092 | ||
2dbe56bd JW |
1093 | #if __cplusplus > 201402L |
1094 | using node_type = typename _Base::node_type; | |
1095 | ||
1096 | node_type | |
1097 | extract(const_iterator __position) | |
1098 | { | |
1099 | __glibcxx_check_erase(__position); | |
1100 | _Base_const_iterator __victim = __position.base(); | |
1101 | this->_M_invalidate_if( | |
1102 | [__victim](_Base_const_iterator __it) { return __it == __victim; } | |
1103 | ); | |
1104 | this->_M_invalidate_local_if( | |
1105 | [__victim](_Base_const_local_iterator __it) { | |
1106 | return __it._M_curr() == __victim._M_cur; | |
1107 | }); | |
1108 | return _Base::extract(__position.base()); | |
1109 | } | |
1110 | ||
1111 | node_type | |
1112 | extract(const key_type& __key) | |
1113 | { | |
1114 | const auto __position = find(__key); | |
1115 | if (__position != end()) | |
1116 | return extract(__position); | |
1117 | return {}; | |
1118 | } | |
1119 | ||
1120 | iterator | |
1121 | insert(node_type&& __nh) | |
1122 | { return iterator(_Base::insert(std::move(__nh)), this); } | |
1123 | ||
1124 | iterator | |
1125 | insert(const_iterator __hint, node_type&& __nh) | |
1126 | { | |
1127 | __glibcxx_check_insert(__hint); | |
1128 | return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); | |
1129 | } | |
1130 | ||
1131 | using _Base::merge; | |
1132 | #endif // C++17 | |
1133 | ||
ced3cb9f PC |
1134 | iterator |
1135 | find(const key_type& __key) | |
1136 | { return iterator(_Base::find(__key), this); } | |
1137 | ||
1138 | const_iterator | |
1139 | find(const key_type& __key) const | |
1140 | { return const_iterator(_Base::find(__key), this); } | |
1141 | ||
1142 | std::pair<iterator, iterator> | |
1143 | equal_range(const key_type& __key) | |
1144 | { | |
afe96d41 FD |
1145 | std::pair<_Base_iterator, _Base_iterator> __res = |
1146 | _Base::equal_range(__key); | |
ced3cb9f PC |
1147 | return std::make_pair(iterator(__res.first, this), |
1148 | iterator(__res.second, this)); | |
1149 | } | |
1150 | ||
1151 | std::pair<const_iterator, const_iterator> | |
1152 | equal_range(const key_type& __key) const | |
1153 | { | |
afe96d41 FD |
1154 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
1155 | _Base::equal_range(__key); | |
ced3cb9f PC |
1156 | return std::make_pair(const_iterator(__res.first, this), |
1157 | const_iterator(__res.second, this)); | |
1158 | } | |
1159 | ||
1160 | size_type | |
1161 | erase(const key_type& __key) | |
1162 | { | |
1163 | size_type __ret(0); | |
77e0bf4e | 1164 | size_type __bucket_count = this->bucket_count(); |
d3b8263e FD |
1165 | std::pair<_Base_iterator, _Base_iterator> __pair = |
1166 | _Base::equal_range(__key); | |
1167 | for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) | |
ced3cb9f | 1168 | { |
77e0bf4e FD |
1169 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
1170 | { return __it == __victim; }); | |
77e0bf4e | 1171 | this->_M_invalidate_local_if( |
5b3be7cf | 1172 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 1173 | { return __it._M_curr() == __victim._M_cur; }); |
d3b8263e FD |
1174 | _Base::erase(__victim++); |
1175 | ++__ret; | |
ced3cb9f | 1176 | } |
77e0bf4e | 1177 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
1178 | return __ret; |
1179 | } | |
1180 | ||
d723ced2 | 1181 | iterator |
ced3cb9f PC |
1182 | erase(const_iterator __it) |
1183 | { | |
1184 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
1185 | _Base_const_iterator __victim = __it.base(); |
1186 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
1187 | { return __it == __victim; }); | |
77e0bf4e | 1188 | this->_M_invalidate_local_if( |
5b3be7cf | 1189 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 1190 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e FD |
1191 | size_type __bucket_count = this->bucket_count(); |
1192 | _Base_iterator __next = _Base::erase(__it.base()); | |
1193 | _M_check_rehashed(__bucket_count); | |
1194 | return iterator(__next, this); | |
ced3cb9f PC |
1195 | } |
1196 | ||
6dc88283 PC |
1197 | iterator |
1198 | erase(iterator __it) | |
1199 | { return erase(const_iterator(__it)); } | |
1200 | ||
d723ced2 | 1201 | iterator |
ced3cb9f PC |
1202 | erase(const_iterator __first, const_iterator __last) |
1203 | { | |
1204 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
1205 | for (_Base_const_iterator __tmp = __first.base(); |
1206 | __tmp != __last.base(); ++__tmp) | |
1207 | { | |
1208 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
1209 | _M_message(__gnu_debug::__msg_valid_range) | |
1210 | ._M_iterator(__first, "first") | |
1211 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
1212 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
1213 | { return __it == __tmp; }); | |
77e0bf4e | 1214 | this->_M_invalidate_local_if( |
5b3be7cf | 1215 | [__tmp](_Base_const_local_iterator __it) |
92e16228 | 1216 | { return __it._M_curr() == __tmp._M_cur; }); |
afe96d41 | 1217 | } |
77e0bf4e FD |
1218 | size_type __bucket_count = this->bucket_count(); |
1219 | _Base_iterator __next = _Base::erase(__first.base(), __last.base()); | |
1220 | _M_check_rehashed(__bucket_count); | |
1221 | return iterator(__next, this); | |
ced3cb9f PC |
1222 | } |
1223 | ||
1224 | _Base& | |
15ee1a77 | 1225 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
1226 | |
1227 | const _Base& | |
d3677132 | 1228 | _M_base() const noexcept { return *this; } |
ced3cb9f | 1229 | |
69b3331e | 1230 | private: |
77e0bf4e FD |
1231 | void |
1232 | _M_check_rehashed(size_type __prev_count) | |
1233 | { | |
1234 | if (__prev_count != this->bucket_count()) | |
15ee1a77 | 1235 | this->_M_invalidate_locals(); |
77e0bf4e | 1236 | } |
e63637ea BK |
1237 | }; |
1238 | ||
957f5fea VV |
1239 | #if __cpp_deduction_guides >= 201606 |
1240 | ||
1241 | template<typename _InputIterator, | |
1242 | typename _Hash = hash<__iter_key_t<_InputIterator>>, | |
1243 | typename _Pred = equal_to<__iter_key_t<_InputIterator>>, | |
1244 | typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, | |
1245 | typename = _RequireInputIter<_InputIterator>, | |
1246 | typename = _RequireAllocator<_Allocator>> | |
1247 | unordered_multimap(_InputIterator, _InputIterator, | |
1248 | unordered_multimap<int, int>::size_type = {}, | |
1249 | _Hash = _Hash(), _Pred = _Pred(), | |
1250 | _Allocator = _Allocator()) | |
1251 | -> unordered_multimap<__iter_key_t<_InputIterator>, | |
1252 | __iter_val_t<_InputIterator>, _Hash, _Pred, | |
1253 | _Allocator>; | |
1254 | ||
1255 | template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, | |
1256 | typename _Pred = equal_to<_Key>, | |
1257 | typename _Allocator = allocator<pair<const _Key, _Tp>>, | |
1258 | typename = _RequireAllocator<_Allocator>> | |
1259 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, | |
1260 | unordered_multimap<int, int>::size_type = {}, | |
1261 | _Hash = _Hash(), _Pred = _Pred(), | |
1262 | _Allocator = _Allocator()) | |
1263 | -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>; | |
1264 | ||
1265 | template<typename _InputIterator, typename _Allocator, | |
1266 | typename = _RequireInputIter<_InputIterator>, | |
1267 | typename = _RequireAllocator<_Allocator>> | |
1268 | unordered_multimap(_InputIterator, _InputIterator, | |
1269 | unordered_multimap<int, int>::size_type, _Allocator) | |
1270 | -> unordered_multimap<__iter_key_t<_InputIterator>, | |
1271 | __iter_val_t<_InputIterator>, | |
1272 | hash<__iter_key_t<_InputIterator>>, | |
1273 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; | |
1274 | ||
1275 | template<typename _InputIterator, typename _Allocator, | |
1276 | typename = _RequireInputIter<_InputIterator>, | |
1277 | typename = _RequireAllocator<_Allocator>> | |
1278 | unordered_multimap(_InputIterator, _InputIterator, _Allocator) | |
1279 | -> unordered_multimap<__iter_key_t<_InputIterator>, | |
1280 | __iter_val_t<_InputIterator>, | |
1281 | hash<__iter_key_t<_InputIterator>>, | |
1282 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; | |
1283 | ||
1284 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
1285 | typename = _RequireInputIter<_InputIterator>, | |
1286 | typename = _RequireAllocator<_Allocator>> | |
1287 | unordered_multimap(_InputIterator, _InputIterator, | |
1288 | unordered_multimap<int, int>::size_type, _Hash, | |
1289 | _Allocator) | |
1290 | -> unordered_multimap<__iter_key_t<_InputIterator>, | |
1291 | __iter_val_t<_InputIterator>, _Hash, | |
1292 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; | |
1293 | ||
1294 | template<typename _Key, typename _Tp, typename _Allocator, | |
1295 | typename = _RequireAllocator<_Allocator>> | |
1296 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, | |
1297 | unordered_multimap<int, int>::size_type, | |
1298 | _Allocator) | |
1299 | -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; | |
1300 | ||
1301 | template<typename _Key, typename _Tp, typename _Allocator, | |
1302 | typename = _RequireAllocator<_Allocator>> | |
1303 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) | |
1304 | -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; | |
1305 | ||
1306 | template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, | |
1307 | typename = _RequireAllocator<_Allocator>> | |
1308 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, | |
1309 | unordered_multimap<int, int>::size_type, | |
1310 | _Hash, _Allocator) | |
1311 | -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; | |
1312 | ||
1313 | #endif | |
1314 | ||
e63637ea BK |
1315 | template<typename _Key, typename _Tp, typename _Hash, |
1316 | typename _Pred, typename _Alloc> | |
69b3331e PC |
1317 | inline void |
1318 | swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
1319 | unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
c5d9ec56 | 1320 | noexcept(noexcept(__x.swap(__y))) |
69b3331e | 1321 | { __x.swap(__y); } |
e63637ea | 1322 | |
5dc22714 PC |
1323 | template<typename _Key, typename _Tp, typename _Hash, |
1324 | typename _Pred, typename _Alloc> | |
1325 | inline bool | |
1326 | operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
1327 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
099e644e | 1328 | { return __x._M_base() == __y._M_base(); } |
5dc22714 PC |
1329 | |
1330 | template<typename _Key, typename _Tp, typename _Hash, | |
1331 | typename _Pred, typename _Alloc> | |
1332 | inline bool | |
1333 | operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
1334 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
1335 | { return !(__x == __y); } | |
1336 | ||
e63637ea BK |
1337 | } // namespace __debug |
1338 | } // namespace std | |
1339 | ||
734f5023 | 1340 | #endif // C++11 |
c878d6ba | 1341 | |
e63637ea | 1342 | #endif |