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