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