]>
Commit | Line | Data |
---|---|---|
e63637ea BK |
1 | // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- |
2 | ||
5624e564 | 3 | // Copyright (C) 2003-2015 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 | ||
734f5023 | 32 | #if __cplusplus < 201103L |
ab65a4c7 | 33 | # include <bits/c++0x_warning.h> |
c878d6ba PC |
34 | #else |
35 | # include <unordered_map> | |
e63637ea | 36 | |
364c862b | 37 | #include <debug/safe_unordered_container.h> |
15ee1a77 | 38 | #include <debug/safe_container.h> |
ced3cb9f | 39 | #include <debug/safe_iterator.h> |
77e0bf4e | 40 | #include <debug/safe_local_iterator.h> |
e63637ea | 41 | |
12ffa228 | 42 | namespace std _GLIBCXX_VISIBILITY(default) |
e63637ea BK |
43 | { |
44 | namespace __debug | |
45 | { | |
1ceb9e06 | 46 | /// Class std::unordered_map with safety/checking/debug instrumentation. |
e63637ea | 47 | template<typename _Key, typename _Tp, |
ced3cb9f | 48 | typename _Hash = std::hash<_Key>, |
e63637ea | 49 | typename _Pred = std::equal_to<_Key>, |
03d7aff6 | 50 | typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > |
e63637ea | 51 | class unordered_map |
15ee1a77 FD |
52 | : public __gnu_debug::_Safe_container< |
53 | unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, | |
54 | __gnu_debug::_Safe_unordered_container>, | |
55 | public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> | |
e63637ea | 56 | { |
12ffa228 | 57 | typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, |
15ee1a77 FD |
58 | _Pred, _Alloc> _Base; |
59 | typedef __gnu_debug::_Safe_container<unordered_map, | |
60 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
61 | typedef typename _Base::const_iterator _Base_const_iterator; | |
62 | typedef typename _Base::iterator _Base_iterator; | |
63 | typedef typename _Base::const_local_iterator | |
64 | _Base_const_local_iterator; | |
65 | typedef typename _Base::local_iterator _Base_local_iterator; | |
0462b6aa | 66 | |
e63637ea | 67 | public: |
15ee1a77 FD |
68 | typedef typename _Base::size_type size_type; |
69 | typedef typename _Base::hasher hasher; | |
70 | typedef typename _Base::key_equal key_equal; | |
71 | typedef typename _Base::allocator_type allocator_type; | |
72 | ||
73 | typedef typename _Base::key_type key_type; | |
74 | typedef typename _Base::value_type value_type; | |
75 | ||
76 | typedef __gnu_debug::_Safe_iterator< | |
77 | _Base_iterator, unordered_map> iterator; | |
78 | typedef __gnu_debug::_Safe_iterator< | |
79 | _Base_const_iterator, unordered_map> const_iterator; | |
80 | typedef __gnu_debug::_Safe_local_iterator< | |
81 | _Base_local_iterator, unordered_map> local_iterator; | |
82 | typedef __gnu_debug::_Safe_local_iterator< | |
83 | _Base_const_local_iterator, unordered_map> const_local_iterator; | |
e63637ea | 84 | |
da27f556 FD |
85 | unordered_map() = default; |
86 | ||
e63637ea | 87 | explicit |
da27f556 | 88 | unordered_map(size_type __n, |
e63637ea BK |
89 | const hasher& __hf = hasher(), |
90 | const key_equal& __eql = key_equal(), | |
91 | const allocator_type& __a = allocator_type()) | |
ced3cb9f | 92 | : _Base(__n, __hf, __eql, __a) { } |
e63637ea BK |
93 | |
94 | template<typename _InputIterator> | |
15ee1a77 | 95 | unordered_map(_InputIterator __first, _InputIterator __last, |
417e896e | 96 | size_type __n = 0, |
15ee1a77 FD |
97 | const hasher& __hf = hasher(), |
98 | const key_equal& __eql = key_equal(), | |
e63637ea | 99 | const allocator_type& __a = allocator_type()) |
1f5ca1a1 PC |
100 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
101 | __last)), | |
102 | __gnu_debug::__base(__last), __n, | |
4c2d93db | 103 | __hf, __eql, __a) { } |
e63637ea | 104 | |
0462b6aa | 105 | unordered_map(const unordered_map&) = default; |
e63637ea | 106 | |
ced3cb9f | 107 | unordered_map(const _Base& __x) |
4c2d93db | 108 | : _Base(__x) { } |
ced3cb9f | 109 | |
0462b6aa FD |
110 | unordered_map(unordered_map&&) = default; |
111 | ||
112 | explicit | |
113 | unordered_map(const allocator_type& __a) | |
15ee1a77 | 114 | : _Base(__a) { } |
0462b6aa FD |
115 | |
116 | unordered_map(const unordered_map& __umap, | |
117 | const allocator_type& __a) | |
15ee1a77 | 118 | : _Base(__umap, __a) { } |
0462b6aa FD |
119 | |
120 | unordered_map(unordered_map&& __umap, | |
121 | const allocator_type& __a) | |
15ee1a77 FD |
122 | : _Safe(std::move(__umap._M_safe()), __a), |
123 | _Base(std::move(__umap._M_base()), __a) { } | |
69b3331e | 124 | |
988499f4 | 125 | unordered_map(initializer_list<value_type> __l, |
417e896e | 126 | size_type __n = 0, |
988499f4 JM |
127 | const hasher& __hf = hasher(), |
128 | const key_equal& __eql = key_equal(), | |
129 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 130 | : _Base(__l, __n, __hf, __eql, __a) { } |
ced3cb9f | 131 | |
e55b80f5 FD |
132 | unordered_map(size_type __n, const allocator_type& __a) |
133 | : unordered_map(__n, hasher(), key_equal(), __a) | |
134 | { } | |
135 | ||
136 | unordered_map(size_type __n, | |
137 | const hasher& __hf, | |
138 | const allocator_type& __a) | |
139 | : unordered_map(__n, __hf, key_equal(), __a) | |
140 | { } | |
141 | ||
142 | template<typename _InputIterator> | |
143 | unordered_map(_InputIterator __first, _InputIterator __last, | |
144 | size_type __n, | |
145 | const allocator_type& __a) | |
146 | : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) | |
147 | { } | |
148 | ||
149 | template<typename _InputIterator> | |
150 | unordered_map(_InputIterator __first, _InputIterator __last, | |
151 | size_type __n, | |
152 | const hasher& __hf, | |
153 | const allocator_type& __a) | |
154 | : unordered_map(__first, __last, __n, __hf, key_equal(), __a) | |
155 | { } | |
156 | ||
157 | unordered_map(initializer_list<value_type> __l, | |
158 | size_type __n, | |
159 | const allocator_type& __a) | |
160 | : unordered_map(__l, __n, hasher(), key_equal(), __a) | |
161 | { } | |
162 | ||
163 | unordered_map(initializer_list<value_type> __l, | |
164 | size_type __n, | |
165 | const hasher& __hf, | |
166 | const allocator_type& __a) | |
167 | : unordered_map(__l, __n, __hf, key_equal(), __a) | |
168 | { } | |
169 | ||
15ee1a77 | 170 | ~unordered_map() = default; |
6f59ea25 | 171 | |
ced3cb9f | 172 | unordered_map& |
15ee1a77 | 173 | operator=(const unordered_map&) = default; |
988499f4 | 174 | |
69b3331e | 175 | unordered_map& |
15ee1a77 | 176 | operator=(unordered_map&&) = default; |
69b3331e | 177 | |
988499f4 JM |
178 | unordered_map& |
179 | operator=(initializer_list<value_type> __l) | |
180 | { | |
0462b6aa FD |
181 | _M_base() = __l; |
182 | this->_M_invalidate_all(); | |
988499f4 JM |
183 | return *this; |
184 | } | |
185 | ||
e63637ea | 186 | void |
ff74fd13 | 187 | swap(unordered_map& __x) |
15ee1a77 | 188 | noexcept( noexcept(declval<_Base>().swap(__x)) ) |
e63637ea | 189 | { |
15ee1a77 | 190 | _Safe::_M_swap(__x); |
ced3cb9f | 191 | _Base::swap(__x); |
e63637ea | 192 | } |
69b3331e PC |
193 | |
194 | void | |
d3677132 | 195 | clear() noexcept |
69b3331e PC |
196 | { |
197 | _Base::clear(); | |
198 | this->_M_invalidate_all(); | |
199 | } | |
200 | ||
15ee1a77 | 201 | iterator |
d3677132 | 202 | begin() noexcept |
ced3cb9f PC |
203 | { return iterator(_Base::begin(), this); } |
204 | ||
205 | const_iterator | |
d3677132 | 206 | begin() const noexcept |
ced3cb9f PC |
207 | { return const_iterator(_Base::begin(), this); } |
208 | ||
209 | iterator | |
d3677132 | 210 | end() noexcept |
ced3cb9f PC |
211 | { return iterator(_Base::end(), this); } |
212 | ||
213 | const_iterator | |
d3677132 | 214 | end() const noexcept |
ced3cb9f PC |
215 | { return const_iterator(_Base::end(), this); } |
216 | ||
217 | const_iterator | |
d3677132 | 218 | cbegin() const noexcept |
ced3cb9f PC |
219 | { return const_iterator(_Base::begin(), this); } |
220 | ||
221 | const_iterator | |
d3677132 | 222 | cend() const noexcept |
ced3cb9f PC |
223 | { return const_iterator(_Base::end(), this); } |
224 | ||
225 | // local versions | |
77e0bf4e FD |
226 | local_iterator |
227 | begin(size_type __b) | |
7181e991 FD |
228 | { |
229 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 230 | return local_iterator(_Base::begin(__b), this); |
7181e991 | 231 | } |
77e0bf4e FD |
232 | |
233 | local_iterator | |
234 | end(size_type __b) | |
7181e991 FD |
235 | { |
236 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 237 | return local_iterator(_Base::end(__b), this); |
7181e991 | 238 | } |
77e0bf4e FD |
239 | |
240 | const_local_iterator | |
241 | begin(size_type __b) const | |
7181e991 FD |
242 | { |
243 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 244 | return const_local_iterator(_Base::begin(__b), this); |
7181e991 | 245 | } |
77e0bf4e FD |
246 | |
247 | const_local_iterator | |
248 | end(size_type __b) const | |
7181e991 FD |
249 | { |
250 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 251 | return const_local_iterator(_Base::end(__b), this); |
7181e991 | 252 | } |
77e0bf4e FD |
253 | |
254 | const_local_iterator | |
255 | cbegin(size_type __b) const | |
7181e991 FD |
256 | { |
257 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 258 | return const_local_iterator(_Base::cbegin(__b), this); |
7181e991 | 259 | } |
77e0bf4e FD |
260 | |
261 | const_local_iterator | |
262 | cend(size_type __b) const | |
7181e991 FD |
263 | { |
264 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 265 | return const_local_iterator(_Base::cend(__b), this); |
7181e991 FD |
266 | } |
267 | ||
268 | size_type | |
269 | bucket_size(size_type __b) const | |
270 | { | |
271 | __glibcxx_check_bucket_index(__b); | |
272 | return _Base::bucket_size(__b); | |
273 | } | |
ced3cb9f | 274 | |
14cbb5d8 FD |
275 | float |
276 | max_load_factor() const noexcept | |
277 | { return _Base::max_load_factor(); } | |
278 | ||
279 | void | |
280 | max_load_factor(float __f) | |
281 | { | |
282 | __glibcxx_check_max_load_factor(__f); | |
283 | _Base::max_load_factor(__f); | |
284 | } | |
285 | ||
9b81593b FD |
286 | template<typename... _Args> |
287 | std::pair<iterator, bool> | |
288 | emplace(_Args&&... __args) | |
289 | { | |
290 | size_type __bucket_count = this->bucket_count(); | |
291 | std::pair<_Base_iterator, bool> __res | |
292 | = _Base::emplace(std::forward<_Args>(__args)...); | |
293 | _M_check_rehashed(__bucket_count); | |
294 | return std::make_pair(iterator(__res.first, this), __res.second); | |
295 | } | |
296 | ||
297 | template<typename... _Args> | |
298 | iterator | |
299 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
300 | { | |
301 | __glibcxx_check_insert(__hint); | |
302 | size_type __bucket_count = this->bucket_count(); | |
303 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
304 | std::forward<_Args>(__args)...); | |
305 | _M_check_rehashed(__bucket_count); | |
306 | return iterator(__it, this); | |
307 | } | |
308 | ||
ced3cb9f PC |
309 | std::pair<iterator, bool> |
310 | insert(const value_type& __obj) | |
311 | { | |
77e0bf4e | 312 | size_type __bucket_count = this->bucket_count(); |
afe96d41 | 313 | std::pair<_Base_iterator, bool> __res = _Base::insert(__obj); |
77e0bf4e | 314 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
315 | return std::make_pair(iterator(__res.first, this), __res.second); |
316 | } | |
317 | ||
318 | iterator | |
d66411ba | 319 | insert(const_iterator __hint, const value_type& __obj) |
ced3cb9f | 320 | { |
d66411ba | 321 | __glibcxx_check_insert(__hint); |
77e0bf4e | 322 | size_type __bucket_count = this->bucket_count(); |
15ee1a77 | 323 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); |
77e0bf4e FD |
324 | _M_check_rehashed(__bucket_count); |
325 | return iterator(__it, this); | |
ced3cb9f PC |
326 | } |
327 | ||
fb7342fd | 328 | template<typename _Pair, typename = typename |
57cee56a PC |
329 | std::enable_if<std::is_constructible<value_type, |
330 | _Pair&&>::value>::type> | |
77e0bf4e FD |
331 | std::pair<iterator, bool> |
332 | insert(_Pair&& __obj) | |
333 | { | |
334 | size_type __bucket_count = this->bucket_count(); | |
afe96d41 FD |
335 | std::pair<_Base_iterator, bool> __res = |
336 | _Base::insert(std::forward<_Pair>(__obj)); | |
77e0bf4e | 337 | _M_check_rehashed(__bucket_count); |
fb7342fd PC |
338 | return std::make_pair(iterator(__res.first, this), __res.second); |
339 | } | |
340 | ||
341 | template<typename _Pair, typename = typename | |
57cee56a PC |
342 | std::enable_if<std::is_constructible<value_type, |
343 | _Pair&&>::value>::type> | |
77e0bf4e FD |
344 | iterator |
345 | insert(const_iterator __hint, _Pair&& __obj) | |
346 | { | |
d66411ba | 347 | __glibcxx_check_insert(__hint); |
77e0bf4e FD |
348 | size_type __bucket_count = this->bucket_count(); |
349 | _Base_iterator __it = | |
350 | _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); | |
351 | _M_check_rehashed(__bucket_count); | |
352 | return iterator(__it, this); | |
fb7342fd PC |
353 | } |
354 | ||
ced3cb9f PC |
355 | void |
356 | insert(std::initializer_list<value_type> __l) | |
77e0bf4e FD |
357 | { |
358 | size_type __bucket_count = this->bucket_count(); | |
359 | _Base::insert(__l); | |
360 | _M_check_rehashed(__bucket_count); | |
361 | } | |
ced3cb9f PC |
362 | |
363 | template<typename _InputIterator> | |
77e0bf4e FD |
364 | void |
365 | insert(_InputIterator __first, _InputIterator __last) | |
366 | { | |
24167c42 FD |
367 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
368 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
77e0bf4e | 369 | size_type __bucket_count = this->bucket_count(); |
24167c42 FD |
370 | |
371 | if (__dist.second >= __gnu_debug::__dp_sign) | |
372 | _Base::insert(__gnu_debug::__unsafe(__first), | |
373 | __gnu_debug::__unsafe(__last)); | |
374 | else | |
375 | _Base::insert(__first, __last); | |
376 | ||
77e0bf4e | 377 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
378 | } |
379 | ||
380 | iterator | |
381 | find(const key_type& __key) | |
382 | { return iterator(_Base::find(__key), this); } | |
383 | ||
384 | const_iterator | |
385 | find(const key_type& __key) const | |
386 | { return const_iterator(_Base::find(__key), this); } | |
387 | ||
388 | std::pair<iterator, iterator> | |
389 | equal_range(const key_type& __key) | |
390 | { | |
afe96d41 FD |
391 | std::pair<_Base_iterator, _Base_iterator> __res = |
392 | _Base::equal_range(__key); | |
ced3cb9f PC |
393 | return std::make_pair(iterator(__res.first, this), |
394 | iterator(__res.second, this)); | |
395 | } | |
396 | ||
397 | std::pair<const_iterator, const_iterator> | |
398 | equal_range(const key_type& __key) const | |
399 | { | |
afe96d41 FD |
400 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
401 | _Base::equal_range(__key); | |
ced3cb9f PC |
402 | return std::make_pair(const_iterator(__res.first, this), |
403 | const_iterator(__res.second, this)); | |
404 | } | |
405 | ||
406 | size_type | |
407 | erase(const key_type& __key) | |
408 | { | |
409 | size_type __ret(0); | |
afe96d41 FD |
410 | _Base_iterator __victim(_Base::find(__key)); |
411 | if (__victim != _Base::end()) | |
ced3cb9f | 412 | { |
77e0bf4e FD |
413 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
414 | { return __it == __victim; }); | |
77e0bf4e | 415 | this->_M_invalidate_local_if( |
5b3be7cf | 416 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 417 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e | 418 | size_type __bucket_count = this->bucket_count(); |
afe96d41 | 419 | _Base::erase(__victim); |
77e0bf4e | 420 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
421 | __ret = 1; |
422 | } | |
423 | return __ret; | |
424 | } | |
425 | ||
d723ced2 | 426 | iterator |
ced3cb9f PC |
427 | erase(const_iterator __it) |
428 | { | |
429 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
430 | _Base_const_iterator __victim = __it.base(); |
431 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
432 | { return __it == __victim; }); | |
77e0bf4e | 433 | this->_M_invalidate_local_if( |
5b3be7cf | 434 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 435 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e | 436 | size_type __bucket_count = this->bucket_count(); |
15ee1a77 | 437 | _Base_iterator __next = _Base::erase(__it.base()); |
77e0bf4e FD |
438 | _M_check_rehashed(__bucket_count); |
439 | return iterator(__next, this); | |
ced3cb9f PC |
440 | } |
441 | ||
6dc88283 PC |
442 | iterator |
443 | erase(iterator __it) | |
444 | { return erase(const_iterator(__it)); } | |
445 | ||
d723ced2 | 446 | iterator |
ced3cb9f PC |
447 | erase(const_iterator __first, const_iterator __last) |
448 | { | |
449 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
450 | for (_Base_const_iterator __tmp = __first.base(); |
451 | __tmp != __last.base(); ++__tmp) | |
452 | { | |
453 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
454 | _M_message(__gnu_debug::__msg_valid_range) | |
455 | ._M_iterator(__first, "first") | |
456 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
457 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
458 | { return __it == __tmp; }); | |
77e0bf4e | 459 | this->_M_invalidate_local_if( |
5b3be7cf | 460 | [__tmp](_Base_const_local_iterator __it) |
92e16228 | 461 | { return __it._M_curr() == __tmp._M_cur; }); |
afe96d41 | 462 | } |
77e0bf4e FD |
463 | size_type __bucket_count = this->bucket_count(); |
464 | _Base_iterator __next = _Base::erase(__first.base(), __last.base()); | |
465 | _M_check_rehashed(__bucket_count); | |
466 | return iterator(__next, this); | |
ced3cb9f PC |
467 | } |
468 | ||
469 | _Base& | |
15ee1a77 | 470 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
471 | |
472 | const _Base& | |
15ee1a77 | 473 | _M_base() const noexcept { return *this; } |
ced3cb9f | 474 | |
69b3331e | 475 | private: |
77e0bf4e FD |
476 | void |
477 | _M_check_rehashed(size_type __prev_count) | |
478 | { | |
479 | if (__prev_count != this->bucket_count()) | |
15ee1a77 | 480 | this->_M_invalidate_locals(); |
77e0bf4e | 481 | } |
e63637ea BK |
482 | }; |
483 | ||
484 | template<typename _Key, typename _Tp, typename _Hash, | |
485 | typename _Pred, typename _Alloc> | |
69b3331e PC |
486 | inline void |
487 | swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
488 | unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
489 | { __x.swap(__y); } | |
e63637ea | 490 | |
5dc22714 PC |
491 | template<typename _Key, typename _Tp, typename _Hash, |
492 | typename _Pred, typename _Alloc> | |
493 | inline bool | |
494 | operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
495 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
099e644e | 496 | { return __x._M_base() == __y._M_base(); } |
5dc22714 PC |
497 | |
498 | template<typename _Key, typename _Tp, typename _Hash, | |
499 | typename _Pred, typename _Alloc> | |
500 | inline bool | |
501 | operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
502 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
503 | { return !(__x == __y); } | |
504 | ||
e63637ea | 505 | |
1ceb9e06 | 506 | /// Class std::unordered_multimap with safety/checking/debug instrumentation. |
e63637ea | 507 | template<typename _Key, typename _Tp, |
ced3cb9f | 508 | typename _Hash = std::hash<_Key>, |
e63637ea | 509 | typename _Pred = std::equal_to<_Key>, |
03d7aff6 | 510 | typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > |
e63637ea | 511 | class unordered_multimap |
15ee1a77 FD |
512 | : public __gnu_debug::_Safe_container< |
513 | unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, | |
514 | __gnu_debug::_Safe_unordered_container>, | |
515 | public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> | |
e63637ea | 516 | { |
12ffa228 | 517 | typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, |
15ee1a77 FD |
518 | _Pred, _Alloc> _Base; |
519 | typedef __gnu_debug::_Safe_container<unordered_multimap, | |
520 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
521 | typedef typename _Base::const_iterator _Base_const_iterator; | |
522 | typedef typename _Base::iterator _Base_iterator; | |
77e0bf4e | 523 | typedef typename _Base::const_local_iterator _Base_const_local_iterator; |
15ee1a77 | 524 | typedef typename _Base::local_iterator _Base_local_iterator; |
0462b6aa | 525 | |
e63637ea | 526 | public: |
15ee1a77 FD |
527 | typedef typename _Base::size_type size_type; |
528 | typedef typename _Base::hasher hasher; | |
529 | typedef typename _Base::key_equal key_equal; | |
530 | typedef typename _Base::allocator_type allocator_type; | |
531 | ||
532 | typedef typename _Base::key_type key_type; | |
533 | typedef typename _Base::value_type value_type; | |
534 | ||
535 | typedef __gnu_debug::_Safe_iterator< | |
536 | _Base_iterator, unordered_multimap> iterator; | |
537 | typedef __gnu_debug::_Safe_iterator< | |
538 | _Base_const_iterator, unordered_multimap> const_iterator; | |
77e0bf4e | 539 | typedef __gnu_debug::_Safe_local_iterator< |
15ee1a77 | 540 | _Base_local_iterator, unordered_multimap> local_iterator; |
77e0bf4e FD |
541 | typedef __gnu_debug::_Safe_local_iterator< |
542 | _Base_const_local_iterator, unordered_multimap> const_local_iterator; | |
e63637ea | 543 | |
da27f556 FD |
544 | unordered_multimap() = default; |
545 | ||
e63637ea | 546 | explicit |
da27f556 | 547 | unordered_multimap(size_type __n, |
ced3cb9f PC |
548 | const hasher& __hf = hasher(), |
549 | const key_equal& __eql = key_equal(), | |
550 | const allocator_type& __a = allocator_type()) | |
551 | : _Base(__n, __hf, __eql, __a) { } | |
e63637ea BK |
552 | |
553 | template<typename _InputIterator> | |
15ee1a77 | 554 | unordered_multimap(_InputIterator __first, _InputIterator __last, |
417e896e | 555 | size_type __n = 0, |
15ee1a77 FD |
556 | const hasher& __hf = hasher(), |
557 | const key_equal& __eql = key_equal(), | |
ced3cb9f | 558 | const allocator_type& __a = allocator_type()) |
1f5ca1a1 PC |
559 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
560 | __last)), | |
561 | __gnu_debug::__base(__last), __n, | |
4c2d93db | 562 | __hf, __eql, __a) { } |
ced3cb9f | 563 | |
0462b6aa | 564 | unordered_multimap(const unordered_multimap&) = default; |
ced3cb9f | 565 | |
15ee1a77 | 566 | unordered_multimap(const _Base& __x) |
4c2d93db | 567 | : _Base(__x) { } |
ced3cb9f | 568 | |
0462b6aa FD |
569 | unordered_multimap(unordered_multimap&&) = default; |
570 | ||
571 | explicit | |
572 | unordered_multimap(const allocator_type& __a) | |
15ee1a77 | 573 | : _Base(__a) { } |
0462b6aa FD |
574 | |
575 | unordered_multimap(const unordered_multimap& __umap, | |
576 | const allocator_type& __a) | |
15ee1a77 | 577 | : _Base(__umap, __a) { } |
0462b6aa FD |
578 | |
579 | unordered_multimap(unordered_multimap&& __umap, | |
580 | const allocator_type& __a) | |
15ee1a77 FD |
581 | : _Safe(std::move(__umap._M_safe()), __a), |
582 | _Base(std::move(__umap._M_base()), __a) { } | |
e63637ea | 583 | |
988499f4 | 584 | unordered_multimap(initializer_list<value_type> __l, |
417e896e | 585 | size_type __n = 0, |
988499f4 JM |
586 | const hasher& __hf = hasher(), |
587 | const key_equal& __eql = key_equal(), | |
588 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 589 | : _Base(__l, __n, __hf, __eql, __a) { } |
e63637ea | 590 | |
e55b80f5 FD |
591 | unordered_multimap(size_type __n, const allocator_type& __a) |
592 | : unordered_multimap(__n, hasher(), key_equal(), __a) | |
593 | { } | |
594 | ||
595 | unordered_multimap(size_type __n, const hasher& __hf, | |
596 | const allocator_type& __a) | |
597 | : unordered_multimap(__n, __hf, key_equal(), __a) | |
598 | { } | |
599 | ||
600 | template<typename _InputIterator> | |
601 | unordered_multimap(_InputIterator __first, _InputIterator __last, | |
602 | size_type __n, | |
603 | const allocator_type& __a) | |
604 | : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) | |
605 | { } | |
606 | ||
607 | template<typename _InputIterator> | |
608 | unordered_multimap(_InputIterator __first, _InputIterator __last, | |
609 | size_type __n, const hasher& __hf, | |
610 | const allocator_type& __a) | |
611 | : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) | |
612 | { } | |
613 | ||
614 | unordered_multimap(initializer_list<value_type> __l, | |
615 | size_type __n, | |
616 | const allocator_type& __a) | |
617 | : unordered_multimap(__l, __n, hasher(), key_equal(), __a) | |
618 | { } | |
619 | ||
620 | unordered_multimap(initializer_list<value_type> __l, | |
621 | size_type __n, const hasher& __hf, | |
622 | const allocator_type& __a) | |
623 | : unordered_multimap(__l, __n, __hf, key_equal(), __a) | |
624 | { } | |
625 | ||
15ee1a77 | 626 | ~unordered_multimap() = default; |
6f59ea25 | 627 | |
ced3cb9f | 628 | unordered_multimap& |
15ee1a77 | 629 | operator=(const unordered_multimap&) = default; |
69b3331e PC |
630 | |
631 | unordered_multimap& | |
15ee1a77 | 632 | operator=(unordered_multimap&&) = default; |
69b3331e | 633 | |
988499f4 JM |
634 | unordered_multimap& |
635 | operator=(initializer_list<value_type> __l) | |
636 | { | |
15ee1a77 | 637 | this->_M_base() = __l; |
0462b6aa | 638 | this->_M_invalidate_all(); |
988499f4 JM |
639 | return *this; |
640 | } | |
641 | ||
e63637ea | 642 | void |
ff74fd13 | 643 | swap(unordered_multimap& __x) |
15ee1a77 | 644 | noexcept( noexcept(declval<_Base>().swap(__x)) ) |
e63637ea | 645 | { |
15ee1a77 | 646 | _Safe::_M_swap(__x); |
ced3cb9f | 647 | _Base::swap(__x); |
e63637ea | 648 | } |
69b3331e PC |
649 | |
650 | void | |
d3677132 | 651 | clear() noexcept |
69b3331e PC |
652 | { |
653 | _Base::clear(); | |
654 | this->_M_invalidate_all(); | |
655 | } | |
656 | ||
15ee1a77 | 657 | iterator |
d3677132 | 658 | begin() noexcept |
ced3cb9f PC |
659 | { return iterator(_Base::begin(), this); } |
660 | ||
661 | const_iterator | |
d3677132 | 662 | begin() const noexcept |
ced3cb9f PC |
663 | { return const_iterator(_Base::begin(), this); } |
664 | ||
665 | iterator | |
d3677132 | 666 | end() noexcept |
ced3cb9f PC |
667 | { return iterator(_Base::end(), this); } |
668 | ||
669 | const_iterator | |
d3677132 | 670 | end() const noexcept |
ced3cb9f PC |
671 | { return const_iterator(_Base::end(), this); } |
672 | ||
673 | const_iterator | |
d3677132 | 674 | cbegin() const noexcept |
ced3cb9f PC |
675 | { return const_iterator(_Base::begin(), this); } |
676 | ||
677 | const_iterator | |
d3677132 | 678 | cend() const noexcept |
ced3cb9f PC |
679 | { return const_iterator(_Base::end(), this); } |
680 | ||
681 | // local versions | |
77e0bf4e FD |
682 | local_iterator |
683 | begin(size_type __b) | |
7181e991 FD |
684 | { |
685 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 686 | return local_iterator(_Base::begin(__b), this); |
7181e991 | 687 | } |
77e0bf4e FD |
688 | |
689 | local_iterator | |
690 | end(size_type __b) | |
7181e991 FD |
691 | { |
692 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 693 | return local_iterator(_Base::end(__b), this); |
7181e991 | 694 | } |
77e0bf4e FD |
695 | |
696 | const_local_iterator | |
697 | begin(size_type __b) const | |
7181e991 FD |
698 | { |
699 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 700 | return const_local_iterator(_Base::begin(__b), this); |
7181e991 | 701 | } |
77e0bf4e FD |
702 | |
703 | const_local_iterator | |
704 | end(size_type __b) const | |
7181e991 FD |
705 | { |
706 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 707 | return const_local_iterator(_Base::end(__b), this); |
7181e991 | 708 | } |
77e0bf4e FD |
709 | |
710 | const_local_iterator | |
711 | cbegin(size_type __b) const | |
7181e991 FD |
712 | { |
713 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 714 | return const_local_iterator(_Base::cbegin(__b), this); |
7181e991 | 715 | } |
77e0bf4e FD |
716 | |
717 | const_local_iterator | |
718 | cend(size_type __b) const | |
7181e991 FD |
719 | { |
720 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 721 | return const_local_iterator(_Base::cend(__b), this); |
7181e991 FD |
722 | } |
723 | ||
724 | size_type | |
725 | bucket_size(size_type __b) const | |
726 | { | |
727 | __glibcxx_check_bucket_index(__b); | |
728 | return _Base::bucket_size(__b); | |
729 | } | |
ced3cb9f | 730 | |
14cbb5d8 FD |
731 | float |
732 | max_load_factor() const noexcept | |
733 | { return _Base::max_load_factor(); } | |
734 | ||
735 | void | |
736 | max_load_factor(float __f) | |
737 | { | |
738 | __glibcxx_check_max_load_factor(__f); | |
739 | _Base::max_load_factor(__f); | |
740 | } | |
741 | ||
9b81593b FD |
742 | template<typename... _Args> |
743 | iterator | |
744 | emplace(_Args&&... __args) | |
745 | { | |
746 | size_type __bucket_count = this->bucket_count(); | |
747 | _Base_iterator __it | |
748 | = _Base::emplace(std::forward<_Args>(__args)...); | |
749 | _M_check_rehashed(__bucket_count); | |
750 | return iterator(__it, this); | |
751 | } | |
752 | ||
753 | template<typename... _Args> | |
754 | iterator | |
755 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
756 | { | |
757 | __glibcxx_check_insert(__hint); | |
758 | size_type __bucket_count = this->bucket_count(); | |
759 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
760 | std::forward<_Args>(__args)...); | |
761 | _M_check_rehashed(__bucket_count); | |
762 | return iterator(__it, this); | |
763 | } | |
764 | ||
ced3cb9f PC |
765 | iterator |
766 | insert(const value_type& __obj) | |
77e0bf4e FD |
767 | { |
768 | size_type __bucket_count = this->bucket_count(); | |
769 | _Base_iterator __it = _Base::insert(__obj); | |
770 | _M_check_rehashed(__bucket_count); | |
771 | return iterator(__it, this); | |
772 | } | |
ced3cb9f PC |
773 | |
774 | iterator | |
d66411ba FD |
775 | insert(const_iterator __hint, const value_type& __obj) |
776 | { | |
777 | __glibcxx_check_insert(__hint); | |
77e0bf4e FD |
778 | size_type __bucket_count = this->bucket_count(); |
779 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); | |
780 | _M_check_rehashed(__bucket_count); | |
781 | return iterator(__it, this); | |
d66411ba | 782 | } |
ced3cb9f | 783 | |
fb7342fd | 784 | template<typename _Pair, typename = typename |
57cee56a PC |
785 | std::enable_if<std::is_constructible<value_type, |
786 | _Pair&&>::value>::type> | |
77e0bf4e FD |
787 | iterator |
788 | insert(_Pair&& __obj) | |
789 | { | |
790 | size_type __bucket_count = this->bucket_count(); | |
791 | _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); | |
792 | _M_check_rehashed(__bucket_count); | |
793 | return iterator(__it, this); | |
794 | } | |
fb7342fd PC |
795 | |
796 | template<typename _Pair, typename = typename | |
57cee56a PC |
797 | std::enable_if<std::is_constructible<value_type, |
798 | _Pair&&>::value>::type> | |
afe96d41 | 799 | iterator |
d66411ba FD |
800 | insert(const_iterator __hint, _Pair&& __obj) |
801 | { | |
802 | __glibcxx_check_insert(__hint); | |
77e0bf4e FD |
803 | size_type __bucket_count = this->bucket_count(); |
804 | _Base_iterator __it = | |
805 | _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); | |
806 | _M_check_rehashed(__bucket_count); | |
807 | return iterator(__it, this); | |
d66411ba | 808 | } |
fb7342fd | 809 | |
ced3cb9f PC |
810 | void |
811 | insert(std::initializer_list<value_type> __l) | |
812 | { _Base::insert(__l); } | |
813 | ||
814 | template<typename _InputIterator> | |
77e0bf4e FD |
815 | void |
816 | insert(_InputIterator __first, _InputIterator __last) | |
817 | { | |
24167c42 FD |
818 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
819 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
77e0bf4e | 820 | size_type __bucket_count = this->bucket_count(); |
24167c42 FD |
821 | |
822 | if (__dist.second >= __gnu_debug::__dp_sign) | |
823 | _Base::insert(__gnu_debug::__unsafe(__first), | |
824 | __gnu_debug::__unsafe(__last)); | |
825 | else | |
826 | _Base::insert(__first, __last); | |
827 | ||
77e0bf4e | 828 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
829 | } |
830 | ||
831 | iterator | |
832 | find(const key_type& __key) | |
833 | { return iterator(_Base::find(__key), this); } | |
834 | ||
835 | const_iterator | |
836 | find(const key_type& __key) const | |
837 | { return const_iterator(_Base::find(__key), this); } | |
838 | ||
839 | std::pair<iterator, iterator> | |
840 | equal_range(const key_type& __key) | |
841 | { | |
afe96d41 FD |
842 | std::pair<_Base_iterator, _Base_iterator> __res = |
843 | _Base::equal_range(__key); | |
ced3cb9f PC |
844 | return std::make_pair(iterator(__res.first, this), |
845 | iterator(__res.second, this)); | |
846 | } | |
847 | ||
848 | std::pair<const_iterator, const_iterator> | |
849 | equal_range(const key_type& __key) const | |
850 | { | |
afe96d41 FD |
851 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
852 | _Base::equal_range(__key); | |
ced3cb9f PC |
853 | return std::make_pair(const_iterator(__res.first, this), |
854 | const_iterator(__res.second, this)); | |
855 | } | |
856 | ||
857 | size_type | |
858 | erase(const key_type& __key) | |
859 | { | |
860 | size_type __ret(0); | |
77e0bf4e | 861 | size_type __bucket_count = this->bucket_count(); |
d3b8263e FD |
862 | std::pair<_Base_iterator, _Base_iterator> __pair = |
863 | _Base::equal_range(__key); | |
864 | for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) | |
ced3cb9f | 865 | { |
77e0bf4e FD |
866 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
867 | { return __it == __victim; }); | |
77e0bf4e | 868 | this->_M_invalidate_local_if( |
5b3be7cf | 869 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 870 | { return __it._M_curr() == __victim._M_cur; }); |
d3b8263e FD |
871 | _Base::erase(__victim++); |
872 | ++__ret; | |
ced3cb9f | 873 | } |
77e0bf4e | 874 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
875 | return __ret; |
876 | } | |
877 | ||
d723ced2 | 878 | iterator |
ced3cb9f PC |
879 | erase(const_iterator __it) |
880 | { | |
881 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
882 | _Base_const_iterator __victim = __it.base(); |
883 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
884 | { return __it == __victim; }); | |
77e0bf4e | 885 | this->_M_invalidate_local_if( |
5b3be7cf | 886 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 887 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e FD |
888 | size_type __bucket_count = this->bucket_count(); |
889 | _Base_iterator __next = _Base::erase(__it.base()); | |
890 | _M_check_rehashed(__bucket_count); | |
891 | return iterator(__next, this); | |
ced3cb9f PC |
892 | } |
893 | ||
6dc88283 PC |
894 | iterator |
895 | erase(iterator __it) | |
896 | { return erase(const_iterator(__it)); } | |
897 | ||
d723ced2 | 898 | iterator |
ced3cb9f PC |
899 | erase(const_iterator __first, const_iterator __last) |
900 | { | |
901 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
902 | for (_Base_const_iterator __tmp = __first.base(); |
903 | __tmp != __last.base(); ++__tmp) | |
904 | { | |
905 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
906 | _M_message(__gnu_debug::__msg_valid_range) | |
907 | ._M_iterator(__first, "first") | |
908 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
909 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
910 | { return __it == __tmp; }); | |
77e0bf4e | 911 | this->_M_invalidate_local_if( |
5b3be7cf | 912 | [__tmp](_Base_const_local_iterator __it) |
92e16228 | 913 | { return __it._M_curr() == __tmp._M_cur; }); |
afe96d41 | 914 | } |
77e0bf4e FD |
915 | size_type __bucket_count = this->bucket_count(); |
916 | _Base_iterator __next = _Base::erase(__first.base(), __last.base()); | |
917 | _M_check_rehashed(__bucket_count); | |
918 | return iterator(__next, this); | |
ced3cb9f PC |
919 | } |
920 | ||
921 | _Base& | |
15ee1a77 | 922 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
923 | |
924 | const _Base& | |
d3677132 | 925 | _M_base() const noexcept { return *this; } |
ced3cb9f | 926 | |
69b3331e | 927 | private: |
77e0bf4e FD |
928 | void |
929 | _M_check_rehashed(size_type __prev_count) | |
930 | { | |
931 | if (__prev_count != this->bucket_count()) | |
15ee1a77 | 932 | this->_M_invalidate_locals(); |
77e0bf4e | 933 | } |
e63637ea BK |
934 | }; |
935 | ||
936 | template<typename _Key, typename _Tp, typename _Hash, | |
937 | typename _Pred, typename _Alloc> | |
69b3331e PC |
938 | inline void |
939 | swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
940 | unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
941 | { __x.swap(__y); } | |
e63637ea | 942 | |
5dc22714 PC |
943 | template<typename _Key, typename _Tp, typename _Hash, |
944 | typename _Pred, typename _Alloc> | |
945 | inline bool | |
946 | operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
947 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
099e644e | 948 | { return __x._M_base() == __y._M_base(); } |
5dc22714 PC |
949 | |
950 | template<typename _Key, typename _Tp, typename _Hash, | |
951 | typename _Pred, typename _Alloc> | |
952 | inline bool | |
953 | operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
954 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
955 | { return !(__x == __y); } | |
956 | ||
e63637ea BK |
957 | } // namespace __debug |
958 | } // namespace std | |
959 | ||
734f5023 | 960 | #endif // C++11 |
c878d6ba | 961 | |
e63637ea | 962 | #endif |