]>
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 | |
77e0bf4e | 38 | #include <debug/safe_unordered_sequence.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>, |
77e0bf4e FD |
53 | public __gnu_debug::_Safe_unordered_sequence<unordered_map<_Key, _Tp, |
54 | _Hash, _Pred, _Alloc> > | |
e63637ea | 55 | { |
12ffa228 | 56 | typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, |
ced3cb9f | 57 | _Pred, _Alloc> _Base; |
77e0bf4e | 58 | typedef __gnu_debug::_Safe_unordered_sequence<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) | |
6f59ea25 PC |
107 | noexcept(__and_<is_nothrow_copy_constructible<_Hash>, |
108 | is_nothrow_copy_constructible<_Pred>>::value) | |
4c2d93db | 109 | : _Base(std::move(__x)) { } |
69b3331e | 110 | |
988499f4 | 111 | unordered_map(initializer_list<value_type> __l, |
417e896e | 112 | size_type __n = 0, |
988499f4 JM |
113 | const hasher& __hf = hasher(), |
114 | const key_equal& __eql = key_equal(), | |
115 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 116 | : _Base(__l, __n, __hf, __eql, __a) { } |
ced3cb9f | 117 | |
6f59ea25 PC |
118 | ~unordered_map() noexcept { } |
119 | ||
ced3cb9f PC |
120 | unordered_map& |
121 | operator=(const unordered_map& __x) | |
122 | { | |
123 | *static_cast<_Base*>(this) = __x; | |
124 | this->_M_invalidate_all(); | |
125 | return *this; | |
126 | } | |
988499f4 | 127 | |
69b3331e PC |
128 | unordered_map& |
129 | operator=(unordered_map&& __x) | |
130 | { | |
0462fd5e PC |
131 | // NB: DR 1204. |
132 | // NB: DR 675. | |
133 | clear(); | |
134 | swap(__x); | |
69b3331e PC |
135 | return *this; |
136 | } | |
137 | ||
988499f4 JM |
138 | unordered_map& |
139 | operator=(initializer_list<value_type> __l) | |
140 | { | |
141 | this->clear(); | |
142 | this->insert(__l); | |
143 | return *this; | |
144 | } | |
145 | ||
e63637ea | 146 | void |
ff74fd13 | 147 | swap(unordered_map& __x) |
e63637ea | 148 | { |
ced3cb9f | 149 | _Base::swap(__x); |
e63637ea BK |
150 | _Safe_base::_M_swap(__x); |
151 | } | |
69b3331e PC |
152 | |
153 | void | |
d3677132 | 154 | clear() noexcept |
69b3331e PC |
155 | { |
156 | _Base::clear(); | |
157 | this->_M_invalidate_all(); | |
158 | } | |
159 | ||
ced3cb9f | 160 | iterator |
d3677132 | 161 | begin() noexcept |
ced3cb9f PC |
162 | { return iterator(_Base::begin(), this); } |
163 | ||
164 | const_iterator | |
d3677132 | 165 | begin() const noexcept |
ced3cb9f PC |
166 | { return const_iterator(_Base::begin(), this); } |
167 | ||
168 | iterator | |
d3677132 | 169 | end() noexcept |
ced3cb9f PC |
170 | { return iterator(_Base::end(), this); } |
171 | ||
172 | const_iterator | |
d3677132 | 173 | end() const noexcept |
ced3cb9f PC |
174 | { return const_iterator(_Base::end(), this); } |
175 | ||
176 | const_iterator | |
d3677132 | 177 | cbegin() const noexcept |
ced3cb9f PC |
178 | { return const_iterator(_Base::begin(), this); } |
179 | ||
180 | const_iterator | |
d3677132 | 181 | cend() const noexcept |
ced3cb9f PC |
182 | { return const_iterator(_Base::end(), this); } |
183 | ||
184 | // local versions | |
77e0bf4e FD |
185 | local_iterator |
186 | begin(size_type __b) | |
187 | { return local_iterator(_Base::begin(__b), __b, this); } | |
188 | ||
189 | local_iterator | |
190 | end(size_type __b) | |
191 | { return local_iterator(_Base::end(__b), __b, this); } | |
192 | ||
193 | const_local_iterator | |
194 | begin(size_type __b) const | |
195 | { return const_local_iterator(_Base::begin(__b), __b, this); } | |
196 | ||
197 | const_local_iterator | |
198 | end(size_type __b) const | |
199 | { return const_local_iterator(_Base::end(__b), __b, this); } | |
200 | ||
201 | const_local_iterator | |
202 | cbegin(size_type __b) const | |
203 | { return const_local_iterator(_Base::cbegin(__b), __b, this); } | |
204 | ||
205 | const_local_iterator | |
206 | cend(size_type __b) const | |
207 | { return const_local_iterator(_Base::cend(__b), __b, this); } | |
ced3cb9f PC |
208 | |
209 | std::pair<iterator, bool> | |
210 | insert(const value_type& __obj) | |
211 | { | |
77e0bf4e | 212 | size_type __bucket_count = this->bucket_count(); |
afe96d41 | 213 | std::pair<_Base_iterator, bool> __res = _Base::insert(__obj); |
77e0bf4e | 214 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
215 | return std::make_pair(iterator(__res.first, this), __res.second); |
216 | } | |
217 | ||
218 | iterator | |
d66411ba | 219 | insert(const_iterator __hint, const value_type& __obj) |
ced3cb9f | 220 | { |
d66411ba | 221 | __glibcxx_check_insert(__hint); |
77e0bf4e FD |
222 | size_type __bucket_count = this->bucket_count(); |
223 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); | |
224 | _M_check_rehashed(__bucket_count); | |
225 | return iterator(__it, this); | |
ced3cb9f PC |
226 | } |
227 | ||
fb7342fd PC |
228 | template<typename _Pair, typename = typename |
229 | std::enable_if<std::is_convertible<_Pair, | |
230 | value_type>::value>::type> | |
77e0bf4e FD |
231 | std::pair<iterator, bool> |
232 | insert(_Pair&& __obj) | |
233 | { | |
234 | size_type __bucket_count = this->bucket_count(); | |
afe96d41 FD |
235 | std::pair<_Base_iterator, bool> __res = |
236 | _Base::insert(std::forward<_Pair>(__obj)); | |
77e0bf4e | 237 | _M_check_rehashed(__bucket_count); |
fb7342fd PC |
238 | return std::make_pair(iterator(__res.first, this), __res.second); |
239 | } | |
240 | ||
241 | template<typename _Pair, typename = typename | |
242 | std::enable_if<std::is_convertible<_Pair, | |
243 | value_type>::value>::type> | |
77e0bf4e FD |
244 | iterator |
245 | insert(const_iterator __hint, _Pair&& __obj) | |
246 | { | |
d66411ba | 247 | __glibcxx_check_insert(__hint); |
77e0bf4e FD |
248 | size_type __bucket_count = this->bucket_count(); |
249 | _Base_iterator __it = | |
250 | _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); | |
251 | _M_check_rehashed(__bucket_count); | |
252 | return iterator(__it, this); | |
fb7342fd PC |
253 | } |
254 | ||
ced3cb9f PC |
255 | void |
256 | insert(std::initializer_list<value_type> __l) | |
77e0bf4e FD |
257 | { |
258 | size_type __bucket_count = this->bucket_count(); | |
259 | _Base::insert(__l); | |
260 | _M_check_rehashed(__bucket_count); | |
261 | } | |
ced3cb9f PC |
262 | |
263 | template<typename _InputIterator> | |
77e0bf4e FD |
264 | void |
265 | insert(_InputIterator __first, _InputIterator __last) | |
266 | { | |
ced3cb9f | 267 | __glibcxx_check_valid_range(__first, __last); |
77e0bf4e | 268 | size_type __bucket_count = this->bucket_count(); |
1f5ca1a1 PC |
269 | _Base::insert(__gnu_debug::__base(__first), |
270 | __gnu_debug::__base(__last)); | |
77e0bf4e | 271 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
272 | } |
273 | ||
274 | iterator | |
275 | find(const key_type& __key) | |
276 | { return iterator(_Base::find(__key), this); } | |
277 | ||
278 | const_iterator | |
279 | find(const key_type& __key) const | |
280 | { return const_iterator(_Base::find(__key), this); } | |
281 | ||
282 | std::pair<iterator, iterator> | |
283 | equal_range(const key_type& __key) | |
284 | { | |
afe96d41 FD |
285 | std::pair<_Base_iterator, _Base_iterator> __res = |
286 | _Base::equal_range(__key); | |
ced3cb9f PC |
287 | return std::make_pair(iterator(__res.first, this), |
288 | iterator(__res.second, this)); | |
289 | } | |
290 | ||
291 | std::pair<const_iterator, const_iterator> | |
292 | equal_range(const key_type& __key) const | |
293 | { | |
afe96d41 FD |
294 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
295 | _Base::equal_range(__key); | |
ced3cb9f PC |
296 | return std::make_pair(const_iterator(__res.first, this), |
297 | const_iterator(__res.second, this)); | |
298 | } | |
299 | ||
300 | size_type | |
301 | erase(const key_type& __key) | |
302 | { | |
303 | size_type __ret(0); | |
afe96d41 FD |
304 | _Base_iterator __victim(_Base::find(__key)); |
305 | if (__victim != _Base::end()) | |
ced3cb9f | 306 | { |
77e0bf4e FD |
307 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
308 | { return __it == __victim; }); | |
309 | _Base_local_iterator __local_victim = _S_to_local(__victim); | |
310 | this->_M_invalidate_local_if( | |
311 | [__local_victim](_Base_const_local_iterator __it) | |
312 | { return __it == __local_victim; }); | |
313 | size_type __bucket_count = this->bucket_count(); | |
afe96d41 | 314 | _Base::erase(__victim); |
77e0bf4e | 315 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
316 | __ret = 1; |
317 | } | |
318 | return __ret; | |
319 | } | |
320 | ||
d723ced2 | 321 | iterator |
ced3cb9f PC |
322 | erase(const_iterator __it) |
323 | { | |
324 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
325 | _Base_const_iterator __victim = __it.base(); |
326 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
327 | { return __it == __victim; }); | |
328 | _Base_const_local_iterator __local_victim = _S_to_local(__victim); | |
329 | this->_M_invalidate_local_if( | |
330 | [__local_victim](_Base_const_local_iterator __it) | |
331 | { return __it == __local_victim; }); | |
332 | size_type __bucket_count = this->bucket_count(); | |
333 | _Base_iterator __next = _Base::erase(__it.base()); | |
334 | _M_check_rehashed(__bucket_count); | |
335 | return iterator(__next, this); | |
ced3cb9f PC |
336 | } |
337 | ||
d723ced2 | 338 | iterator |
ced3cb9f PC |
339 | erase(const_iterator __first, const_iterator __last) |
340 | { | |
341 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
342 | for (_Base_const_iterator __tmp = __first.base(); |
343 | __tmp != __last.base(); ++__tmp) | |
344 | { | |
345 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
346 | _M_message(__gnu_debug::__msg_valid_range) | |
347 | ._M_iterator(__first, "first") | |
348 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
349 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
350 | { return __it == __tmp; }); | |
351 | _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); | |
352 | this->_M_invalidate_local_if( | |
353 | [__local_tmp](_Base_const_local_iterator __it) | |
354 | { return __it == __local_tmp; }); | |
afe96d41 | 355 | } |
77e0bf4e FD |
356 | size_type __bucket_count = this->bucket_count(); |
357 | _Base_iterator __next = _Base::erase(__first.base(), __last.base()); | |
358 | _M_check_rehashed(__bucket_count); | |
359 | return iterator(__next, this); | |
ced3cb9f PC |
360 | } |
361 | ||
362 | _Base& | |
d3677132 | 363 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
364 | |
365 | const _Base& | |
d3677132 | 366 | _M_base() const noexcept { return *this; } |
ced3cb9f | 367 | |
69b3331e | 368 | private: |
77e0bf4e FD |
369 | void |
370 | _M_invalidate_locals() | |
371 | { | |
372 | _Base_local_iterator __local_end = _Base::end(0); | |
373 | this->_M_invalidate_local_if( | |
374 | [__local_end](_Base_const_local_iterator __it) | |
375 | { return __it != __local_end; }); | |
376 | } | |
377 | ||
69b3331e PC |
378 | void |
379 | _M_invalidate_all() | |
380 | { | |
77e0bf4e FD |
381 | _Base_iterator __end = _Base::end(); |
382 | this->_M_invalidate_if([__end](_Base_const_iterator __it) | |
383 | { return __it != __end; }); | |
384 | _M_invalidate_locals(); | |
69b3331e | 385 | } |
77e0bf4e FD |
386 | |
387 | void | |
388 | _M_check_rehashed(size_type __prev_count) | |
389 | { | |
390 | if (__prev_count != this->bucket_count()) | |
391 | _M_invalidate_locals(); | |
392 | } | |
393 | ||
394 | static _Base_local_iterator | |
395 | _S_to_local(_Base_iterator __it) | |
396 | { return _Base_local_iterator(__it._M_cur_node); } | |
397 | ||
398 | static _Base_const_local_iterator | |
399 | _S_to_local(_Base_const_iterator __it) | |
400 | { return _Base_const_local_iterator(__it._M_cur_node); } | |
e63637ea BK |
401 | }; |
402 | ||
403 | template<typename _Key, typename _Tp, typename _Hash, | |
404 | typename _Pred, typename _Alloc> | |
69b3331e PC |
405 | inline void |
406 | swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
407 | unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
408 | { __x.swap(__y); } | |
e63637ea | 409 | |
5dc22714 PC |
410 | template<typename _Key, typename _Tp, typename _Hash, |
411 | typename _Pred, typename _Alloc> | |
412 | inline bool | |
413 | operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
414 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
415 | { return __x._M_equal(__y); } | |
416 | ||
417 | template<typename _Key, typename _Tp, typename _Hash, | |
418 | typename _Pred, typename _Alloc> | |
419 | inline bool | |
420 | operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
421 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
422 | { return !(__x == __y); } | |
423 | ||
e63637ea | 424 | |
1ceb9e06 | 425 | /// Class std::unordered_multimap with safety/checking/debug instrumentation. |
e63637ea | 426 | template<typename _Key, typename _Tp, |
ced3cb9f | 427 | typename _Hash = std::hash<_Key>, |
e63637ea | 428 | typename _Pred = std::equal_to<_Key>, |
ced3cb9f | 429 | typename _Alloc = std::allocator<_Key> > |
e63637ea | 430 | class unordered_multimap |
12ffa228 | 431 | : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, |
ced3cb9f | 432 | _Pred, _Alloc>, |
77e0bf4e FD |
433 | public __gnu_debug::_Safe_unordered_sequence<unordered_multimap<_Key, |
434 | _Tp, _Hash, _Pred, _Alloc> > | |
e63637ea | 435 | { |
12ffa228 | 436 | typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, |
ced3cb9f | 437 | _Pred, _Alloc> _Base; |
77e0bf4e FD |
438 | typedef __gnu_debug::_Safe_unordered_sequence<unordered_multimap> |
439 | _Safe_base; | |
afe96d41 FD |
440 | typedef typename _Base::const_iterator _Base_const_iterator; |
441 | typedef typename _Base::iterator _Base_iterator; | |
77e0bf4e FD |
442 | typedef typename _Base::const_local_iterator _Base_const_local_iterator; |
443 | typedef typename _Base::local_iterator _Base_local_iterator; | |
e63637ea BK |
444 | |
445 | public: | |
ced3cb9f PC |
446 | typedef typename _Base::size_type size_type; |
447 | typedef typename _Base::hasher hasher; | |
448 | typedef typename _Base::key_equal key_equal; | |
449 | typedef typename _Base::allocator_type allocator_type; | |
450 | ||
451 | typedef typename _Base::key_type key_type; | |
452 | typedef typename _Base::value_type value_type; | |
453 | ||
afe96d41 | 454 | typedef __gnu_debug::_Safe_iterator<_Base_iterator, |
ced3cb9f | 455 | unordered_multimap> iterator; |
afe96d41 | 456 | typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, |
ced3cb9f | 457 | unordered_multimap> const_iterator; |
77e0bf4e FD |
458 | typedef __gnu_debug::_Safe_local_iterator< |
459 | _Base_local_iterator, unordered_multimap> local_iterator; | |
460 | typedef __gnu_debug::_Safe_local_iterator< | |
461 | _Base_const_local_iterator, unordered_multimap> const_local_iterator; | |
e63637ea BK |
462 | |
463 | explicit | |
464 | unordered_multimap(size_type __n = 10, | |
ced3cb9f PC |
465 | const hasher& __hf = hasher(), |
466 | const key_equal& __eql = key_equal(), | |
467 | const allocator_type& __a = allocator_type()) | |
468 | : _Base(__n, __hf, __eql, __a) { } | |
e63637ea BK |
469 | |
470 | template<typename _InputIterator> | |
77e0bf4e | 471 | unordered_multimap(_InputIterator __first, _InputIterator __last, |
417e896e | 472 | size_type __n = 0, |
ced3cb9f PC |
473 | const hasher& __hf = hasher(), |
474 | const key_equal& __eql = key_equal(), | |
475 | const allocator_type& __a = allocator_type()) | |
1f5ca1a1 PC |
476 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
477 | __last)), | |
478 | __gnu_debug::__base(__last), __n, | |
4c2d93db | 479 | __hf, __eql, __a) { } |
ced3cb9f PC |
480 | |
481 | unordered_multimap(const unordered_multimap& __x) | |
4c2d93db | 482 | : _Base(__x) { } |
ced3cb9f PC |
483 | |
484 | unordered_multimap(const _Base& __x) | |
4c2d93db | 485 | : _Base(__x) { } |
ced3cb9f | 486 | |
6f59ea25 PC |
487 | unordered_multimap(unordered_multimap&& __x) |
488 | noexcept(__and_<is_nothrow_copy_constructible<_Hash>, | |
489 | is_nothrow_copy_constructible<_Pred>>::value) | |
4c2d93db | 490 | : _Base(std::move(__x)) { } |
e63637ea | 491 | |
988499f4 | 492 | unordered_multimap(initializer_list<value_type> __l, |
417e896e | 493 | size_type __n = 0, |
988499f4 JM |
494 | const hasher& __hf = hasher(), |
495 | const key_equal& __eql = key_equal(), | |
496 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 497 | : _Base(__l, __n, __hf, __eql, __a) { } |
e63637ea | 498 | |
6f59ea25 PC |
499 | ~unordered_multimap() noexcept { } |
500 | ||
ced3cb9f PC |
501 | unordered_multimap& |
502 | operator=(const unordered_multimap& __x) | |
503 | { | |
504 | *static_cast<_Base*>(this) = __x; | |
505 | this->_M_invalidate_all(); | |
506 | return *this; | |
507 | } | |
69b3331e PC |
508 | |
509 | unordered_multimap& | |
510 | operator=(unordered_multimap&& __x) | |
511 | { | |
0462fd5e PC |
512 | // NB: DR 1204. |
513 | // NB: DR 675. | |
514 | clear(); | |
515 | swap(__x); | |
69b3331e PC |
516 | return *this; |
517 | } | |
518 | ||
988499f4 JM |
519 | unordered_multimap& |
520 | operator=(initializer_list<value_type> __l) | |
521 | { | |
522 | this->clear(); | |
523 | this->insert(__l); | |
524 | return *this; | |
525 | } | |
526 | ||
e63637ea | 527 | void |
ff74fd13 | 528 | swap(unordered_multimap& __x) |
e63637ea | 529 | { |
ced3cb9f | 530 | _Base::swap(__x); |
e63637ea BK |
531 | _Safe_base::_M_swap(__x); |
532 | } | |
69b3331e PC |
533 | |
534 | void | |
d3677132 | 535 | clear() noexcept |
69b3331e PC |
536 | { |
537 | _Base::clear(); | |
538 | this->_M_invalidate_all(); | |
539 | } | |
540 | ||
ced3cb9f | 541 | iterator |
d3677132 | 542 | begin() noexcept |
ced3cb9f PC |
543 | { return iterator(_Base::begin(), this); } |
544 | ||
545 | const_iterator | |
d3677132 | 546 | begin() const noexcept |
ced3cb9f PC |
547 | { return const_iterator(_Base::begin(), this); } |
548 | ||
549 | iterator | |
d3677132 | 550 | end() noexcept |
ced3cb9f PC |
551 | { return iterator(_Base::end(), this); } |
552 | ||
553 | const_iterator | |
d3677132 | 554 | end() const noexcept |
ced3cb9f PC |
555 | { return const_iterator(_Base::end(), this); } |
556 | ||
557 | const_iterator | |
d3677132 | 558 | cbegin() const noexcept |
ced3cb9f PC |
559 | { return const_iterator(_Base::begin(), this); } |
560 | ||
561 | const_iterator | |
d3677132 | 562 | cend() const noexcept |
ced3cb9f PC |
563 | { return const_iterator(_Base::end(), this); } |
564 | ||
565 | // local versions | |
77e0bf4e FD |
566 | local_iterator |
567 | begin(size_type __b) | |
568 | { return local_iterator(_Base::begin(__b), __b, this); } | |
569 | ||
570 | local_iterator | |
571 | end(size_type __b) | |
572 | { return local_iterator(_Base::end(__b), __b, this); } | |
573 | ||
574 | const_local_iterator | |
575 | begin(size_type __b) const | |
576 | { return const_local_iterator(_Base::begin(__b), __b, this); } | |
577 | ||
578 | const_local_iterator | |
579 | end(size_type __b) const | |
580 | { return const_local_iterator(_Base::end(__b), __b, this); } | |
581 | ||
582 | const_local_iterator | |
583 | cbegin(size_type __b) const | |
584 | { return const_local_iterator(_Base::cbegin(__b), __b, this); } | |
585 | ||
586 | const_local_iterator | |
587 | cend(size_type __b) const | |
588 | { return const_local_iterator(_Base::cend(__b), __b, this); } | |
ced3cb9f PC |
589 | |
590 | iterator | |
591 | insert(const value_type& __obj) | |
77e0bf4e FD |
592 | { |
593 | size_type __bucket_count = this->bucket_count(); | |
594 | _Base_iterator __it = _Base::insert(__obj); | |
595 | _M_check_rehashed(__bucket_count); | |
596 | return iterator(__it, this); | |
597 | } | |
ced3cb9f PC |
598 | |
599 | iterator | |
d66411ba FD |
600 | insert(const_iterator __hint, const value_type& __obj) |
601 | { | |
602 | __glibcxx_check_insert(__hint); | |
77e0bf4e FD |
603 | size_type __bucket_count = this->bucket_count(); |
604 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); | |
605 | _M_check_rehashed(__bucket_count); | |
606 | return iterator(__it, this); | |
d66411ba | 607 | } |
ced3cb9f | 608 | |
fb7342fd PC |
609 | template<typename _Pair, typename = typename |
610 | std::enable_if<std::is_convertible<_Pair, | |
611 | value_type>::value>::type> | |
77e0bf4e FD |
612 | iterator |
613 | insert(_Pair&& __obj) | |
614 | { | |
615 | size_type __bucket_count = this->bucket_count(); | |
616 | _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); | |
617 | _M_check_rehashed(__bucket_count); | |
618 | return iterator(__it, this); | |
619 | } | |
fb7342fd PC |
620 | |
621 | template<typename _Pair, typename = typename | |
622 | std::enable_if<std::is_convertible<_Pair, | |
623 | value_type>::value>::type> | |
afe96d41 | 624 | iterator |
d66411ba FD |
625 | insert(const_iterator __hint, _Pair&& __obj) |
626 | { | |
627 | __glibcxx_check_insert(__hint); | |
77e0bf4e FD |
628 | size_type __bucket_count = this->bucket_count(); |
629 | _Base_iterator __it = | |
630 | _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); | |
631 | _M_check_rehashed(__bucket_count); | |
632 | return iterator(__it, this); | |
d66411ba | 633 | } |
fb7342fd | 634 | |
ced3cb9f PC |
635 | void |
636 | insert(std::initializer_list<value_type> __l) | |
637 | { _Base::insert(__l); } | |
638 | ||
639 | template<typename _InputIterator> | |
77e0bf4e FD |
640 | void |
641 | insert(_InputIterator __first, _InputIterator __last) | |
642 | { | |
ced3cb9f | 643 | __glibcxx_check_valid_range(__first, __last); |
77e0bf4e | 644 | size_type __bucket_count = this->bucket_count(); |
1f5ca1a1 PC |
645 | _Base::insert(__gnu_debug::__base(__first), |
646 | __gnu_debug::__base(__last)); | |
77e0bf4e | 647 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
648 | } |
649 | ||
650 | iterator | |
651 | find(const key_type& __key) | |
652 | { return iterator(_Base::find(__key), this); } | |
653 | ||
654 | const_iterator | |
655 | find(const key_type& __key) const | |
656 | { return const_iterator(_Base::find(__key), this); } | |
657 | ||
658 | std::pair<iterator, iterator> | |
659 | equal_range(const key_type& __key) | |
660 | { | |
afe96d41 FD |
661 | std::pair<_Base_iterator, _Base_iterator> __res = |
662 | _Base::equal_range(__key); | |
ced3cb9f PC |
663 | return std::make_pair(iterator(__res.first, this), |
664 | iterator(__res.second, this)); | |
665 | } | |
666 | ||
667 | std::pair<const_iterator, const_iterator> | |
668 | equal_range(const key_type& __key) const | |
669 | { | |
afe96d41 FD |
670 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
671 | _Base::equal_range(__key); | |
ced3cb9f PC |
672 | return std::make_pair(const_iterator(__res.first, this), |
673 | const_iterator(__res.second, this)); | |
674 | } | |
675 | ||
676 | size_type | |
677 | erase(const key_type& __key) | |
678 | { | |
679 | size_type __ret(0); | |
77e0bf4e | 680 | size_type __bucket_count = this->bucket_count(); |
d3b8263e FD |
681 | std::pair<_Base_iterator, _Base_iterator> __pair = |
682 | _Base::equal_range(__key); | |
683 | for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) | |
ced3cb9f | 684 | { |
77e0bf4e FD |
685 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
686 | { return __it == __victim; }); | |
687 | _Base_local_iterator __local_victim = _S_to_local(__victim); | |
688 | this->_M_invalidate_local_if( | |
689 | [__local_victim](_Base_const_local_iterator __it) | |
690 | { return __it == __local_victim; }); | |
d3b8263e FD |
691 | _Base::erase(__victim++); |
692 | ++__ret; | |
ced3cb9f | 693 | } |
77e0bf4e | 694 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
695 | return __ret; |
696 | } | |
697 | ||
d723ced2 | 698 | iterator |
ced3cb9f PC |
699 | erase(const_iterator __it) |
700 | { | |
701 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
702 | _Base_const_iterator __victim = __it.base(); |
703 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
704 | { return __it == __victim; }); | |
705 | _Base_const_local_iterator __local_victim = _S_to_local(__victim); | |
706 | this->_M_invalidate_local_if( | |
707 | [__local_victim](_Base_const_local_iterator __it) | |
708 | { return __it == __local_victim; }); | |
709 | size_type __bucket_count = this->bucket_count(); | |
710 | _Base_iterator __next = _Base::erase(__it.base()); | |
711 | _M_check_rehashed(__bucket_count); | |
712 | return iterator(__next, this); | |
ced3cb9f PC |
713 | } |
714 | ||
d723ced2 | 715 | iterator |
ced3cb9f PC |
716 | erase(const_iterator __first, const_iterator __last) |
717 | { | |
718 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
719 | for (_Base_const_iterator __tmp = __first.base(); |
720 | __tmp != __last.base(); ++__tmp) | |
721 | { | |
722 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
723 | _M_message(__gnu_debug::__msg_valid_range) | |
724 | ._M_iterator(__first, "first") | |
725 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
726 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
727 | { return __it == __tmp; }); | |
728 | _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); | |
729 | this->_M_invalidate_local_if( | |
730 | [__local_tmp](_Base_const_local_iterator __it) | |
731 | { return __it == __local_tmp; }); | |
afe96d41 | 732 | } |
77e0bf4e FD |
733 | size_type __bucket_count = this->bucket_count(); |
734 | _Base_iterator __next = _Base::erase(__first.base(), __last.base()); | |
735 | _M_check_rehashed(__bucket_count); | |
736 | return iterator(__next, this); | |
ced3cb9f PC |
737 | } |
738 | ||
739 | _Base& | |
d3677132 | 740 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
741 | |
742 | const _Base& | |
d3677132 | 743 | _M_base() const noexcept { return *this; } |
ced3cb9f | 744 | |
69b3331e | 745 | private: |
77e0bf4e FD |
746 | void |
747 | _M_invalidate_locals() | |
748 | { | |
749 | _Base_local_iterator __local_end = _Base::end(0); | |
750 | this->_M_invalidate_local_if( | |
751 | [__local_end](_Base_const_local_iterator __it) | |
752 | { return __it != __local_end; }); | |
753 | } | |
754 | ||
69b3331e PC |
755 | void |
756 | _M_invalidate_all() | |
757 | { | |
77e0bf4e FD |
758 | _Base_iterator __end = _Base::end(); |
759 | this->_M_invalidate_if([__end](_Base_const_iterator __it) | |
760 | { return __it != __end; }); | |
761 | _M_invalidate_locals(); | |
69b3331e | 762 | } |
77e0bf4e FD |
763 | |
764 | void | |
765 | _M_check_rehashed(size_type __prev_count) | |
766 | { | |
767 | if (__prev_count != this->bucket_count()) | |
768 | _M_invalidate_locals(); | |
769 | } | |
770 | ||
771 | static _Base_local_iterator | |
772 | _S_to_local(_Base_iterator __it) | |
773 | { return _Base_local_iterator(__it._M_cur_node); } | |
774 | ||
775 | static _Base_const_local_iterator | |
776 | _S_to_local(_Base_const_iterator __it) | |
777 | { return _Base_const_local_iterator(__it._M_cur_node); } | |
e63637ea BK |
778 | }; |
779 | ||
780 | template<typename _Key, typename _Tp, typename _Hash, | |
781 | typename _Pred, typename _Alloc> | |
69b3331e PC |
782 | inline void |
783 | swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
784 | unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
785 | { __x.swap(__y); } | |
e63637ea | 786 | |
5dc22714 PC |
787 | template<typename _Key, typename _Tp, typename _Hash, |
788 | typename _Pred, typename _Alloc> | |
789 | inline bool | |
790 | operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
791 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
792 | { return __x._M_equal(__y); } | |
793 | ||
794 | template<typename _Key, typename _Tp, typename _Hash, | |
795 | typename _Pred, typename _Alloc> | |
796 | inline bool | |
797 | operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, | |
798 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) | |
799 | { return !(__x == __y); } | |
800 | ||
e63637ea BK |
801 | } // namespace __debug |
802 | } // namespace std | |
803 | ||
c878d6ba PC |
804 | #endif // __GXX_EXPERIMENTAL_CXX0X__ |
805 | ||
e63637ea | 806 | #endif |