]>
Commit | Line | Data |
---|---|---|
e63637ea BK |
1 | // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- |
2 | ||
6f59ea25 | 3 | // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 |
e63637ea BK |
4 | // Free Software Foundation, Inc. |
5 | // | |
6 | // This file is part of the GNU ISO C++ Library. This library is free | |
7 | // software; you can redistribute it and/or modify it under the | |
8 | // terms of the GNU General Public License as published by the | |
748086b7 | 9 | // Free Software Foundation; either version 3, or (at your option) |
e63637ea BK |
10 | // any later version. |
11 | ||
12 | // This library is distributed in the hope that it will be useful, | |
13 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | // GNU General Public License for more details. | |
16 | ||
748086b7 JJ |
17 | // Under Section 7 of GPL version 3, you are granted additional |
18 | // permissions described in the GCC Runtime Library Exception, version | |
19 | // 3.1, as published by the Free Software Foundation. | |
20 | ||
21 | // You should have received a copy of the GNU General Public License and | |
22 | // a copy of the GCC Runtime Library Exception along with this program; | |
23 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
24 | // <http://www.gnu.org/licenses/>. | |
e63637ea BK |
25 | |
26 | /** @file debug/unordered_map | |
27 | * This file is a GNU debug extension to the Standard C++ Library. | |
28 | */ | |
29 | ||
30 | #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP | |
31 | #define _GLIBCXX_DEBUG_UNORDERED_MAP 1 | |
32 | ||
c878d6ba | 33 | #ifndef __GXX_EXPERIMENTAL_CXX0X__ |
ab65a4c7 | 34 | # include <bits/c++0x_warning.h> |
c878d6ba PC |
35 | #else |
36 | # include <unordered_map> | |
e63637ea | 37 | |
364c862b | 38 | #include <debug/safe_unordered_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>, |
ced3cb9f | 50 | typename _Alloc = std::allocator<_Key> > |
e63637ea | 51 | class unordered_map |
12ffa228 | 52 | : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, |
364c862b | 53 | public __gnu_debug::_Safe_unordered_container<unordered_map<_Key, _Tp, |
77e0bf4e | 54 | _Hash, _Pred, _Alloc> > |
e63637ea | 55 | { |
12ffa228 | 56 | typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, |
ced3cb9f | 57 | _Pred, _Alloc> _Base; |
364c862b | 58 | typedef __gnu_debug::_Safe_unordered_container<unordered_map> _Safe_base; |
afe96d41 FD |
59 | typedef typename _Base::const_iterator _Base_const_iterator; |
60 | typedef typename _Base::iterator _Base_iterator; | |
77e0bf4e FD |
61 | typedef typename _Base::const_local_iterator _Base_const_local_iterator; |
62 | typedef typename _Base::local_iterator _Base_local_iterator; | |
e63637ea BK |
63 | |
64 | public: | |
ced3cb9f PC |
65 | typedef typename _Base::size_type size_type; |
66 | typedef typename _Base::hasher hasher; | |
67 | typedef typename _Base::key_equal key_equal; | |
68 | typedef typename _Base::allocator_type allocator_type; | |
69 | ||
70 | typedef typename _Base::key_type key_type; | |
71 | typedef typename _Base::value_type value_type; | |
72 | ||
afe96d41 | 73 | typedef __gnu_debug::_Safe_iterator<_Base_iterator, |
ced3cb9f | 74 | unordered_map> iterator; |
afe96d41 | 75 | typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, |
ced3cb9f | 76 | unordered_map> const_iterator; |
77e0bf4e FD |
77 | typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator, |
78 | unordered_map> local_iterator; | |
79 | typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator, | |
80 | unordered_map> const_local_iterator; | |
e63637ea BK |
81 | |
82 | explicit | |
83 | unordered_map(size_type __n = 10, | |
84 | const hasher& __hf = hasher(), | |
85 | const key_equal& __eql = key_equal(), | |
86 | const allocator_type& __a = allocator_type()) | |
ced3cb9f | 87 | : _Base(__n, __hf, __eql, __a) { } |
e63637ea BK |
88 | |
89 | template<typename _InputIterator> | |
77e0bf4e | 90 | unordered_map(_InputIterator __first, _InputIterator __last, |
417e896e | 91 | size_type __n = 0, |
e63637ea BK |
92 | const hasher& __hf = hasher(), |
93 | const key_equal& __eql = key_equal(), | |
94 | const allocator_type& __a = allocator_type()) | |
1f5ca1a1 PC |
95 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
96 | __last)), | |
97 | __gnu_debug::__base(__last), __n, | |
4c2d93db | 98 | __hf, __eql, __a) { } |
e63637ea | 99 | |
ced3cb9f | 100 | unordered_map(const unordered_map& __x) |
4c2d93db | 101 | : _Base(__x) { } |
e63637ea | 102 | |
ced3cb9f | 103 | unordered_map(const _Base& __x) |
4c2d93db | 104 | : _Base(__x) { } |
ced3cb9f PC |
105 | |
106 | unordered_map(unordered_map&& __x) | |
4c2d93db | 107 | : _Base(std::move(__x)) { } |
69b3331e | 108 | |
988499f4 | 109 | unordered_map(initializer_list<value_type> __l, |
417e896e | 110 | size_type __n = 0, |
988499f4 JM |
111 | const hasher& __hf = hasher(), |
112 | const key_equal& __eql = key_equal(), | |
113 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 114 | : _Base(__l, __n, __hf, __eql, __a) { } |
ced3cb9f | 115 | |
6f59ea25 PC |
116 | ~unordered_map() noexcept { } |
117 | ||
ced3cb9f PC |
118 | unordered_map& |
119 | operator=(const unordered_map& __x) | |
120 | { | |
121 | *static_cast<_Base*>(this) = __x; | |
122 | this->_M_invalidate_all(); | |
123 | return *this; | |
124 | } | |
988499f4 | 125 | |
69b3331e PC |
126 | unordered_map& |
127 | operator=(unordered_map&& __x) | |
128 | { | |
0462fd5e PC |
129 | // NB: DR 1204. |
130 | // NB: DR 675. | |
131 | clear(); | |
132 | swap(__x); | |
69b3331e PC |
133 | return *this; |
134 | } | |
135 | ||
988499f4 JM |
136 | unordered_map& |
137 | operator=(initializer_list<value_type> __l) | |
138 | { | |
139 | this->clear(); | |
140 | this->insert(__l); | |
141 | return *this; | |
142 | } | |
143 | ||
e63637ea | 144 | void |
ff74fd13 | 145 | swap(unordered_map& __x) |
e63637ea | 146 | { |
ced3cb9f | 147 | _Base::swap(__x); |
e63637ea BK |
148 | _Safe_base::_M_swap(__x); |
149 | } | |
69b3331e PC |
150 | |
151 | void | |
d3677132 | 152 | clear() noexcept |
69b3331e PC |
153 | { |
154 | _Base::clear(); | |
155 | this->_M_invalidate_all(); | |
156 | } | |
157 | ||
ced3cb9f | 158 | iterator |
d3677132 | 159 | begin() noexcept |
ced3cb9f PC |
160 | { return iterator(_Base::begin(), this); } |
161 | ||
162 | const_iterator | |
d3677132 | 163 | begin() const noexcept |
ced3cb9f PC |
164 | { return const_iterator(_Base::begin(), this); } |
165 | ||
166 | iterator | |
d3677132 | 167 | end() noexcept |
ced3cb9f PC |
168 | { return iterator(_Base::end(), this); } |
169 | ||
170 | const_iterator | |
d3677132 | 171 | end() const noexcept |
ced3cb9f PC |
172 | { return const_iterator(_Base::end(), this); } |
173 | ||
174 | const_iterator | |
d3677132 | 175 | cbegin() const noexcept |
ced3cb9f PC |
176 | { return const_iterator(_Base::begin(), this); } |
177 | ||
178 | const_iterator | |
d3677132 | 179 | cend() const noexcept |
ced3cb9f PC |
180 | { return const_iterator(_Base::end(), this); } |
181 | ||
182 | // local versions | |
77e0bf4e FD |
183 | local_iterator |
184 | begin(size_type __b) | |
185 | { return local_iterator(_Base::begin(__b), __b, this); } | |
186 | ||
187 | local_iterator | |
188 | end(size_type __b) | |
189 | { return local_iterator(_Base::end(__b), __b, this); } | |
190 | ||
191 | const_local_iterator | |
192 | begin(size_type __b) const | |
193 | { return const_local_iterator(_Base::begin(__b), __b, this); } | |
194 | ||
195 | const_local_iterator | |
196 | end(size_type __b) const | |
197 | { return const_local_iterator(_Base::end(__b), __b, this); } | |
198 | ||
199 | const_local_iterator | |
200 | cbegin(size_type __b) const | |
201 | { return const_local_iterator(_Base::cbegin(__b), __b, this); } | |
202 | ||
203 | const_local_iterator | |
204 | cend(size_type __b) const | |
205 | { return const_local_iterator(_Base::cend(__b), __b, this); } | |
ced3cb9f | 206 | |
9b81593b FD |
207 | template<typename... _Args> |
208 | std::pair<iterator, bool> | |
209 | emplace(_Args&&... __args) | |
210 | { | |
211 | size_type __bucket_count = this->bucket_count(); | |
212 | std::pair<_Base_iterator, bool> __res | |
213 | = _Base::emplace(std::forward<_Args>(__args)...); | |
214 | _M_check_rehashed(__bucket_count); | |
215 | return std::make_pair(iterator(__res.first, this), __res.second); | |
216 | } | |
217 | ||
218 | template<typename... _Args> | |
219 | iterator | |
220 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
221 | { | |
222 | __glibcxx_check_insert(__hint); | |
223 | size_type __bucket_count = this->bucket_count(); | |
224 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
225 | std::forward<_Args>(__args)...); | |
226 | _M_check_rehashed(__bucket_count); | |
227 | return iterator(__it, this); | |
228 | } | |
229 | ||
ced3cb9f PC |
230 | std::pair<iterator, bool> |
231 | insert(const value_type& __obj) | |
232 | { | |
77e0bf4e | 233 | size_type __bucket_count = this->bucket_count(); |
afe96d41 | 234 | std::pair<_Base_iterator, bool> __res = _Base::insert(__obj); |
77e0bf4e | 235 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
236 | return std::make_pair(iterator(__res.first, this), __res.second); |
237 | } | |
238 | ||
239 | iterator | |
d66411ba | 240 | insert(const_iterator __hint, const value_type& __obj) |
ced3cb9f | 241 | { |
d66411ba | 242 | __glibcxx_check_insert(__hint); |
77e0bf4e FD |
243 | size_type __bucket_count = this->bucket_count(); |
244 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); | |
245 | _M_check_rehashed(__bucket_count); | |
246 | return iterator(__it, this); | |
ced3cb9f PC |
247 | } |
248 | ||
fb7342fd PC |
249 | template<typename _Pair, typename = typename |
250 | std::enable_if<std::is_convertible<_Pair, | |
251 | value_type>::value>::type> | |
77e0bf4e FD |
252 | std::pair<iterator, bool> |
253 | insert(_Pair&& __obj) | |
254 | { | |
255 | size_type __bucket_count = this->bucket_count(); | |
afe96d41 FD |
256 | std::pair<_Base_iterator, bool> __res = |
257 | _Base::insert(std::forward<_Pair>(__obj)); | |
77e0bf4e | 258 | _M_check_rehashed(__bucket_count); |
fb7342fd PC |
259 | return std::make_pair(iterator(__res.first, this), __res.second); |
260 | } | |
261 | ||
262 | template<typename _Pair, typename = typename | |
263 | std::enable_if<std::is_convertible<_Pair, | |
264 | value_type>::value>::type> | |
77e0bf4e FD |
265 | iterator |
266 | insert(const_iterator __hint, _Pair&& __obj) | |
267 | { | |
d66411ba | 268 | __glibcxx_check_insert(__hint); |
77e0bf4e FD |
269 | size_type __bucket_count = this->bucket_count(); |
270 | _Base_iterator __it = | |
271 | _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); | |
272 | _M_check_rehashed(__bucket_count); | |
273 | return iterator(__it, this); | |
fb7342fd PC |
274 | } |
275 | ||
ced3cb9f PC |
276 | void |
277 | insert(std::initializer_list<value_type> __l) | |
77e0bf4e FD |
278 | { |
279 | size_type __bucket_count = this->bucket_count(); | |
280 | _Base::insert(__l); | |
281 | _M_check_rehashed(__bucket_count); | |
282 | } | |
ced3cb9f PC |
283 | |
284 | template<typename _InputIterator> | |
77e0bf4e FD |
285 | void |
286 | insert(_InputIterator __first, _InputIterator __last) | |
287 | { | |
ced3cb9f | 288 | __glibcxx_check_valid_range(__first, __last); |
77e0bf4e | 289 | size_type __bucket_count = this->bucket_count(); |
1f5ca1a1 PC |
290 | _Base::insert(__gnu_debug::__base(__first), |
291 | __gnu_debug::__base(__last)); | |
77e0bf4e | 292 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
293 | } |
294 | ||
295 | iterator | |
296 | find(const key_type& __key) | |
297 | { return iterator(_Base::find(__key), this); } | |
298 | ||
299 | const_iterator | |
300 | find(const key_type& __key) const | |
301 | { return const_iterator(_Base::find(__key), this); } | |
302 | ||
303 | std::pair<iterator, iterator> | |
304 | equal_range(const key_type& __key) | |
305 | { | |
afe96d41 FD |
306 | std::pair<_Base_iterator, _Base_iterator> __res = |
307 | _Base::equal_range(__key); | |
ced3cb9f PC |
308 | return std::make_pair(iterator(__res.first, this), |
309 | iterator(__res.second, this)); | |
310 | } | |
311 | ||
312 | std::pair<const_iterator, const_iterator> | |
313 | equal_range(const key_type& __key) const | |
314 | { | |
afe96d41 FD |
315 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
316 | _Base::equal_range(__key); | |
ced3cb9f PC |
317 | return std::make_pair(const_iterator(__res.first, this), |
318 | const_iterator(__res.second, this)); | |
319 | } | |
320 | ||
321 | size_type | |
322 | erase(const key_type& __key) | |
323 | { | |
324 | size_type __ret(0); | |
afe96d41 FD |
325 | _Base_iterator __victim(_Base::find(__key)); |
326 | if (__victim != _Base::end()) | |
ced3cb9f | 327 | { |
77e0bf4e FD |
328 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
329 | { return __it == __victim; }); | |
330 | _Base_local_iterator __local_victim = _S_to_local(__victim); | |
331 | this->_M_invalidate_local_if( | |
332 | [__local_victim](_Base_const_local_iterator __it) | |
333 | { return __it == __local_victim; }); | |
334 | size_type __bucket_count = this->bucket_count(); | |
afe96d41 | 335 | _Base::erase(__victim); |
77e0bf4e | 336 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
337 | __ret = 1; |
338 | } | |
339 | return __ret; | |
340 | } | |
341 | ||
d723ced2 | 342 | iterator |
ced3cb9f PC |
343 | erase(const_iterator __it) |
344 | { | |
345 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
346 | _Base_const_iterator __victim = __it.base(); |
347 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
348 | { return __it == __victim; }); | |
349 | _Base_const_local_iterator __local_victim = _S_to_local(__victim); | |
350 | this->_M_invalidate_local_if( | |
351 | [__local_victim](_Base_const_local_iterator __it) | |
352 | { return __it == __local_victim; }); | |
353 | size_type __bucket_count = this->bucket_count(); | |
354 | _Base_iterator __next = _Base::erase(__it.base()); | |
355 | _M_check_rehashed(__bucket_count); | |
356 | return iterator(__next, this); | |
ced3cb9f PC |
357 | } |
358 | ||
6dc88283 PC |
359 | iterator |
360 | erase(iterator __it) | |
361 | { return erase(const_iterator(__it)); } | |
362 | ||
d723ced2 | 363 | iterator |
ced3cb9f PC |
364 | erase(const_iterator __first, const_iterator __last) |
365 | { | |
366 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
367 | for (_Base_const_iterator __tmp = __first.base(); |
368 | __tmp != __last.base(); ++__tmp) | |
369 | { | |
370 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
371 | _M_message(__gnu_debug::__msg_valid_range) | |
372 | ._M_iterator(__first, "first") | |
373 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
374 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
375 | { return __it == __tmp; }); | |
376 | _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); | |
377 | this->_M_invalidate_local_if( | |
378 | [__local_tmp](_Base_const_local_iterator __it) | |
379 | { return __it == __local_tmp; }); | |
afe96d41 | 380 | } |
77e0bf4e FD |
381 | size_type __bucket_count = this->bucket_count(); |
382 | _Base_iterator __next = _Base::erase(__first.base(), __last.base()); | |
383 | _M_check_rehashed(__bucket_count); | |
384 | return iterator(__next, this); | |
ced3cb9f PC |
385 | } |
386 | ||
387 | _Base& | |
d3677132 | 388 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
389 | |
390 | const _Base& | |
d3677132 | 391 | _M_base() const noexcept { return *this; } |
ced3cb9f | 392 | |
69b3331e | 393 | private: |
77e0bf4e FD |
394 | void |
395 | _M_invalidate_locals() | |
396 | { | |
397 | _Base_local_iterator __local_end = _Base::end(0); | |
398 | this->_M_invalidate_local_if( | |
399 | [__local_end](_Base_const_local_iterator __it) | |
400 | { return __it != __local_end; }); | |
401 | } | |
402 | ||
69b3331e PC |
403 | void |
404 | _M_invalidate_all() | |
405 | { | |
77e0bf4e FD |
406 | _Base_iterator __end = _Base::end(); |
407 | this->_M_invalidate_if([__end](_Base_const_iterator __it) | |
408 | { return __it != __end; }); | |
409 | _M_invalidate_locals(); | |
69b3331e | 410 | } |
77e0bf4e FD |
411 | |
412 | void | |
413 | _M_check_rehashed(size_type __prev_count) | |
414 | { | |
415 | if (__prev_count != this->bucket_count()) | |
416 | _M_invalidate_locals(); | |
417 | } | |
418 | ||
419 | static _Base_local_iterator | |
420 | _S_to_local(_Base_iterator __it) | |
a188284c FD |
421 | { |
422 | // The returned local iterator will not be incremented so we don't | |
423 | // need to compute __it's node bucket | |
424 | return _Base_local_iterator(__it._M_cur, 0, 0); | |
425 | } | |
77e0bf4e FD |
426 | |
427 | static _Base_const_local_iterator | |
428 | _S_to_local(_Base_const_iterator __it) | |
a188284c FD |
429 | { |
430 | // The returned local iterator will not be incremented so we don't | |
431 | // need to compute __it's node bucket | |
432 | return _Base_const_local_iterator(__it._M_cur, 0, 0); | |
433 | } | |
e63637ea BK |
434 | }; |
435 | ||
436 | template<typename _Key, typename _Tp, typename _Hash, | |
437 | typename _Pred, typename _Alloc> | |
69b3331e PC |
438 | inline void |
439 | swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
440 | unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
441 | { __x.swap(__y); } | |
e63637ea | 442 | |
5dc22714 PC |
443 | template<typename _Key, typename _Tp, typename _Hash, |
444 | typename _Pred, typename _Alloc> | |
445 | inline bool | |
446 | operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
447 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
448 | { return __x._M_equal(__y); } | |
449 | ||
450 | template<typename _Key, typename _Tp, typename _Hash, | |
451 | typename _Pred, typename _Alloc> | |
452 | inline bool | |
453 | operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
454 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
455 | { return !(__x == __y); } | |
456 | ||
e63637ea | 457 | |
1ceb9e06 | 458 | /// Class std::unordered_multimap with safety/checking/debug instrumentation. |
e63637ea | 459 | template<typename _Key, typename _Tp, |
ced3cb9f | 460 | typename _Hash = std::hash<_Key>, |
e63637ea | 461 | typename _Pred = std::equal_to<_Key>, |
ced3cb9f | 462 | typename _Alloc = std::allocator<_Key> > |
e63637ea | 463 | class unordered_multimap |
12ffa228 | 464 | : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, |
ced3cb9f | 465 | _Pred, _Alloc>, |
364c862b | 466 | public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key, |
77e0bf4e | 467 | _Tp, _Hash, _Pred, _Alloc> > |
e63637ea | 468 | { |
12ffa228 | 469 | typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, |
ced3cb9f | 470 | _Pred, _Alloc> _Base; |
364c862b | 471 | typedef __gnu_debug::_Safe_unordered_container<unordered_multimap> |
77e0bf4e | 472 | _Safe_base; |
afe96d41 FD |
473 | typedef typename _Base::const_iterator _Base_const_iterator; |
474 | typedef typename _Base::iterator _Base_iterator; | |
77e0bf4e FD |
475 | typedef typename _Base::const_local_iterator _Base_const_local_iterator; |
476 | typedef typename _Base::local_iterator _Base_local_iterator; | |
e63637ea BK |
477 | |
478 | public: | |
ced3cb9f PC |
479 | typedef typename _Base::size_type size_type; |
480 | typedef typename _Base::hasher hasher; | |
481 | typedef typename _Base::key_equal key_equal; | |
482 | typedef typename _Base::allocator_type allocator_type; | |
483 | ||
484 | typedef typename _Base::key_type key_type; | |
485 | typedef typename _Base::value_type value_type; | |
486 | ||
afe96d41 | 487 | typedef __gnu_debug::_Safe_iterator<_Base_iterator, |
ced3cb9f | 488 | unordered_multimap> iterator; |
afe96d41 | 489 | typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, |
ced3cb9f | 490 | unordered_multimap> const_iterator; |
77e0bf4e FD |
491 | typedef __gnu_debug::_Safe_local_iterator< |
492 | _Base_local_iterator, unordered_multimap> local_iterator; | |
493 | typedef __gnu_debug::_Safe_local_iterator< | |
494 | _Base_const_local_iterator, unordered_multimap> const_local_iterator; | |
e63637ea BK |
495 | |
496 | explicit | |
497 | unordered_multimap(size_type __n = 10, | |
ced3cb9f PC |
498 | const hasher& __hf = hasher(), |
499 | const key_equal& __eql = key_equal(), | |
500 | const allocator_type& __a = allocator_type()) | |
501 | : _Base(__n, __hf, __eql, __a) { } | |
e63637ea BK |
502 | |
503 | template<typename _InputIterator> | |
77e0bf4e | 504 | unordered_multimap(_InputIterator __first, _InputIterator __last, |
417e896e | 505 | size_type __n = 0, |
ced3cb9f PC |
506 | const hasher& __hf = hasher(), |
507 | const key_equal& __eql = key_equal(), | |
508 | const allocator_type& __a = allocator_type()) | |
1f5ca1a1 PC |
509 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
510 | __last)), | |
511 | __gnu_debug::__base(__last), __n, | |
4c2d93db | 512 | __hf, __eql, __a) { } |
ced3cb9f PC |
513 | |
514 | unordered_multimap(const unordered_multimap& __x) | |
4c2d93db | 515 | : _Base(__x) { } |
ced3cb9f PC |
516 | |
517 | unordered_multimap(const _Base& __x) | |
4c2d93db | 518 | : _Base(__x) { } |
ced3cb9f | 519 | |
6f59ea25 | 520 | unordered_multimap(unordered_multimap&& __x) |
4c2d93db | 521 | : _Base(std::move(__x)) { } |
e63637ea | 522 | |
988499f4 | 523 | unordered_multimap(initializer_list<value_type> __l, |
417e896e | 524 | size_type __n = 0, |
988499f4 JM |
525 | const hasher& __hf = hasher(), |
526 | const key_equal& __eql = key_equal(), | |
527 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 528 | : _Base(__l, __n, __hf, __eql, __a) { } |
e63637ea | 529 | |
6f59ea25 PC |
530 | ~unordered_multimap() noexcept { } |
531 | ||
ced3cb9f PC |
532 | unordered_multimap& |
533 | operator=(const unordered_multimap& __x) | |
534 | { | |
535 | *static_cast<_Base*>(this) = __x; | |
536 | this->_M_invalidate_all(); | |
537 | return *this; | |
538 | } | |
69b3331e PC |
539 | |
540 | unordered_multimap& | |
541 | operator=(unordered_multimap&& __x) | |
542 | { | |
0462fd5e PC |
543 | // NB: DR 1204. |
544 | // NB: DR 675. | |
545 | clear(); | |
546 | swap(__x); | |
69b3331e PC |
547 | return *this; |
548 | } | |
549 | ||
988499f4 JM |
550 | unordered_multimap& |
551 | operator=(initializer_list<value_type> __l) | |
552 | { | |
553 | this->clear(); | |
554 | this->insert(__l); | |
555 | return *this; | |
556 | } | |
557 | ||
e63637ea | 558 | void |
ff74fd13 | 559 | swap(unordered_multimap& __x) |
e63637ea | 560 | { |
ced3cb9f | 561 | _Base::swap(__x); |
e63637ea BK |
562 | _Safe_base::_M_swap(__x); |
563 | } | |
69b3331e PC |
564 | |
565 | void | |
d3677132 | 566 | clear() noexcept |
69b3331e PC |
567 | { |
568 | _Base::clear(); | |
569 | this->_M_invalidate_all(); | |
570 | } | |
571 | ||
ced3cb9f | 572 | iterator |
d3677132 | 573 | begin() noexcept |
ced3cb9f PC |
574 | { return iterator(_Base::begin(), this); } |
575 | ||
576 | const_iterator | |
d3677132 | 577 | begin() const noexcept |
ced3cb9f PC |
578 | { return const_iterator(_Base::begin(), this); } |
579 | ||
580 | iterator | |
d3677132 | 581 | end() noexcept |
ced3cb9f PC |
582 | { return iterator(_Base::end(), this); } |
583 | ||
584 | const_iterator | |
d3677132 | 585 | end() const noexcept |
ced3cb9f PC |
586 | { return const_iterator(_Base::end(), this); } |
587 | ||
588 | const_iterator | |
d3677132 | 589 | cbegin() const noexcept |
ced3cb9f PC |
590 | { return const_iterator(_Base::begin(), this); } |
591 | ||
592 | const_iterator | |
d3677132 | 593 | cend() const noexcept |
ced3cb9f PC |
594 | { return const_iterator(_Base::end(), this); } |
595 | ||
596 | // local versions | |
77e0bf4e FD |
597 | local_iterator |
598 | begin(size_type __b) | |
599 | { return local_iterator(_Base::begin(__b), __b, this); } | |
600 | ||
601 | local_iterator | |
602 | end(size_type __b) | |
603 | { return local_iterator(_Base::end(__b), __b, this); } | |
604 | ||
605 | const_local_iterator | |
606 | begin(size_type __b) const | |
607 | { return const_local_iterator(_Base::begin(__b), __b, this); } | |
608 | ||
609 | const_local_iterator | |
610 | end(size_type __b) const | |
611 | { return const_local_iterator(_Base::end(__b), __b, this); } | |
612 | ||
613 | const_local_iterator | |
614 | cbegin(size_type __b) const | |
615 | { return const_local_iterator(_Base::cbegin(__b), __b, this); } | |
616 | ||
617 | const_local_iterator | |
618 | cend(size_type __b) const | |
619 | { return const_local_iterator(_Base::cend(__b), __b, this); } | |
ced3cb9f | 620 | |
9b81593b FD |
621 | template<typename... _Args> |
622 | iterator | |
623 | emplace(_Args&&... __args) | |
624 | { | |
625 | size_type __bucket_count = this->bucket_count(); | |
626 | _Base_iterator __it | |
627 | = _Base::emplace(std::forward<_Args>(__args)...); | |
628 | _M_check_rehashed(__bucket_count); | |
629 | return iterator(__it, this); | |
630 | } | |
631 | ||
632 | template<typename... _Args> | |
633 | iterator | |
634 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
635 | { | |
636 | __glibcxx_check_insert(__hint); | |
637 | size_type __bucket_count = this->bucket_count(); | |
638 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
639 | std::forward<_Args>(__args)...); | |
640 | _M_check_rehashed(__bucket_count); | |
641 | return iterator(__it, this); | |
642 | } | |
643 | ||
ced3cb9f PC |
644 | iterator |
645 | insert(const value_type& __obj) | |
77e0bf4e FD |
646 | { |
647 | size_type __bucket_count = this->bucket_count(); | |
648 | _Base_iterator __it = _Base::insert(__obj); | |
649 | _M_check_rehashed(__bucket_count); | |
650 | return iterator(__it, this); | |
651 | } | |
ced3cb9f PC |
652 | |
653 | iterator | |
d66411ba FD |
654 | insert(const_iterator __hint, const value_type& __obj) |
655 | { | |
656 | __glibcxx_check_insert(__hint); | |
77e0bf4e FD |
657 | size_type __bucket_count = this->bucket_count(); |
658 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); | |
659 | _M_check_rehashed(__bucket_count); | |
660 | return iterator(__it, this); | |
d66411ba | 661 | } |
ced3cb9f | 662 | |
fb7342fd PC |
663 | template<typename _Pair, typename = typename |
664 | std::enable_if<std::is_convertible<_Pair, | |
665 | value_type>::value>::type> | |
77e0bf4e FD |
666 | iterator |
667 | insert(_Pair&& __obj) | |
668 | { | |
669 | size_type __bucket_count = this->bucket_count(); | |
670 | _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); | |
671 | _M_check_rehashed(__bucket_count); | |
672 | return iterator(__it, this); | |
673 | } | |
fb7342fd PC |
674 | |
675 | template<typename _Pair, typename = typename | |
676 | std::enable_if<std::is_convertible<_Pair, | |
677 | value_type>::value>::type> | |
afe96d41 | 678 | iterator |
d66411ba FD |
679 | insert(const_iterator __hint, _Pair&& __obj) |
680 | { | |
681 | __glibcxx_check_insert(__hint); | |
77e0bf4e FD |
682 | size_type __bucket_count = this->bucket_count(); |
683 | _Base_iterator __it = | |
684 | _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); | |
685 | _M_check_rehashed(__bucket_count); | |
686 | return iterator(__it, this); | |
d66411ba | 687 | } |
fb7342fd | 688 | |
ced3cb9f PC |
689 | void |
690 | insert(std::initializer_list<value_type> __l) | |
691 | { _Base::insert(__l); } | |
692 | ||
693 | template<typename _InputIterator> | |
77e0bf4e FD |
694 | void |
695 | insert(_InputIterator __first, _InputIterator __last) | |
696 | { | |
ced3cb9f | 697 | __glibcxx_check_valid_range(__first, __last); |
77e0bf4e | 698 | size_type __bucket_count = this->bucket_count(); |
1f5ca1a1 PC |
699 | _Base::insert(__gnu_debug::__base(__first), |
700 | __gnu_debug::__base(__last)); | |
77e0bf4e | 701 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
702 | } |
703 | ||
704 | iterator | |
705 | find(const key_type& __key) | |
706 | { return iterator(_Base::find(__key), this); } | |
707 | ||
708 | const_iterator | |
709 | find(const key_type& __key) const | |
710 | { return const_iterator(_Base::find(__key), this); } | |
711 | ||
712 | std::pair<iterator, iterator> | |
713 | equal_range(const key_type& __key) | |
714 | { | |
afe96d41 FD |
715 | std::pair<_Base_iterator, _Base_iterator> __res = |
716 | _Base::equal_range(__key); | |
ced3cb9f PC |
717 | return std::make_pair(iterator(__res.first, this), |
718 | iterator(__res.second, this)); | |
719 | } | |
720 | ||
721 | std::pair<const_iterator, const_iterator> | |
722 | equal_range(const key_type& __key) const | |
723 | { | |
afe96d41 FD |
724 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
725 | _Base::equal_range(__key); | |
ced3cb9f PC |
726 | return std::make_pair(const_iterator(__res.first, this), |
727 | const_iterator(__res.second, this)); | |
728 | } | |
729 | ||
730 | size_type | |
731 | erase(const key_type& __key) | |
732 | { | |
733 | size_type __ret(0); | |
77e0bf4e | 734 | size_type __bucket_count = this->bucket_count(); |
d3b8263e FD |
735 | std::pair<_Base_iterator, _Base_iterator> __pair = |
736 | _Base::equal_range(__key); | |
737 | for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) | |
ced3cb9f | 738 | { |
77e0bf4e FD |
739 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
740 | { return __it == __victim; }); | |
741 | _Base_local_iterator __local_victim = _S_to_local(__victim); | |
742 | this->_M_invalidate_local_if( | |
743 | [__local_victim](_Base_const_local_iterator __it) | |
744 | { return __it == __local_victim; }); | |
d3b8263e FD |
745 | _Base::erase(__victim++); |
746 | ++__ret; | |
ced3cb9f | 747 | } |
77e0bf4e | 748 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
749 | return __ret; |
750 | } | |
751 | ||
d723ced2 | 752 | iterator |
ced3cb9f PC |
753 | erase(const_iterator __it) |
754 | { | |
755 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
756 | _Base_const_iterator __victim = __it.base(); |
757 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
758 | { return __it == __victim; }); | |
759 | _Base_const_local_iterator __local_victim = _S_to_local(__victim); | |
760 | this->_M_invalidate_local_if( | |
761 | [__local_victim](_Base_const_local_iterator __it) | |
762 | { return __it == __local_victim; }); | |
763 | size_type __bucket_count = this->bucket_count(); | |
764 | _Base_iterator __next = _Base::erase(__it.base()); | |
765 | _M_check_rehashed(__bucket_count); | |
766 | return iterator(__next, this); | |
ced3cb9f PC |
767 | } |
768 | ||
6dc88283 PC |
769 | iterator |
770 | erase(iterator __it) | |
771 | { return erase(const_iterator(__it)); } | |
772 | ||
d723ced2 | 773 | iterator |
ced3cb9f PC |
774 | erase(const_iterator __first, const_iterator __last) |
775 | { | |
776 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
777 | for (_Base_const_iterator __tmp = __first.base(); |
778 | __tmp != __last.base(); ++__tmp) | |
779 | { | |
780 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
781 | _M_message(__gnu_debug::__msg_valid_range) | |
782 | ._M_iterator(__first, "first") | |
783 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
784 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
785 | { return __it == __tmp; }); | |
786 | _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); | |
787 | this->_M_invalidate_local_if( | |
788 | [__local_tmp](_Base_const_local_iterator __it) | |
789 | { return __it == __local_tmp; }); | |
afe96d41 | 790 | } |
77e0bf4e FD |
791 | size_type __bucket_count = this->bucket_count(); |
792 | _Base_iterator __next = _Base::erase(__first.base(), __last.base()); | |
793 | _M_check_rehashed(__bucket_count); | |
794 | return iterator(__next, this); | |
ced3cb9f PC |
795 | } |
796 | ||
797 | _Base& | |
d3677132 | 798 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
799 | |
800 | const _Base& | |
d3677132 | 801 | _M_base() const noexcept { return *this; } |
ced3cb9f | 802 | |
69b3331e | 803 | private: |
77e0bf4e FD |
804 | void |
805 | _M_invalidate_locals() | |
806 | { | |
807 | _Base_local_iterator __local_end = _Base::end(0); | |
808 | this->_M_invalidate_local_if( | |
809 | [__local_end](_Base_const_local_iterator __it) | |
810 | { return __it != __local_end; }); | |
811 | } | |
812 | ||
69b3331e PC |
813 | void |
814 | _M_invalidate_all() | |
815 | { | |
77e0bf4e FD |
816 | _Base_iterator __end = _Base::end(); |
817 | this->_M_invalidate_if([__end](_Base_const_iterator __it) | |
818 | { return __it != __end; }); | |
819 | _M_invalidate_locals(); | |
69b3331e | 820 | } |
77e0bf4e FD |
821 | |
822 | void | |
823 | _M_check_rehashed(size_type __prev_count) | |
824 | { | |
825 | if (__prev_count != this->bucket_count()) | |
826 | _M_invalidate_locals(); | |
827 | } | |
828 | ||
829 | static _Base_local_iterator | |
830 | _S_to_local(_Base_iterator __it) | |
a188284c FD |
831 | { |
832 | // The returned local iterator will not be incremented so we don't | |
833 | // need to compute __it's node bucket | |
834 | return _Base_local_iterator(__it._M_cur, 0, 0); | |
835 | } | |
77e0bf4e FD |
836 | |
837 | static _Base_const_local_iterator | |
838 | _S_to_local(_Base_const_iterator __it) | |
a188284c FD |
839 | { |
840 | // The returned local iterator will not be incremented so we don't | |
841 | // need to compute __it's node bucket | |
842 | return _Base_const_local_iterator(__it._M_cur, 0, 0); | |
843 | } | |
e63637ea BK |
844 | }; |
845 | ||
846 | template<typename _Key, typename _Tp, typename _Hash, | |
847 | typename _Pred, typename _Alloc> | |
69b3331e PC |
848 | inline void |
849 | swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
850 | unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
851 | { __x.swap(__y); } | |
e63637ea | 852 | |
5dc22714 PC |
853 | template<typename _Key, typename _Tp, typename _Hash, |
854 | typename _Pred, typename _Alloc> | |
855 | inline bool | |
856 | operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
857 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
858 | { return __x._M_equal(__y); } | |
859 | ||
860 | template<typename _Key, typename _Tp, typename _Hash, | |
861 | typename _Pred, typename _Alloc> | |
862 | inline bool | |
863 | operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
864 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
865 | { return !(__x == __y); } | |
866 | ||
e63637ea BK |
867 | } // namespace __debug |
868 | } // namespace std | |
869 | ||
c878d6ba PC |
870 | #endif // __GXX_EXPERIMENTAL_CXX0X__ |
871 | ||
e63637ea | 872 | #endif |