projects / thirdparty / gcc.git / blame
| Commit | Line | Data |
|---|---|---|
| e63637ea BK |
1 | // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- |
| 2 | ||
| cbe34bb5 | 3 | // Copyright (C) 2003-2017 Free Software Foundation, Inc. |
| e63637ea BK |
4 | // |
| 5 | // This file is part of the GNU ISO C++ Library. This library is free | |
| 6 | // software; you can redistribute it and/or modify it under the | |
| 7 | // terms of the GNU General Public License as published by the | |
| 748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
| e63637ea BK |
9 | // any later version. |
| 10 | ||
| 11 | // This library is distributed in the hope that it will be useful, | |
| 12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 14 | // GNU General Public License for more details. | |
| 15 | ||
| 748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
| 17 | // permissions described in the GCC Runtime Library Exception, version | |
| 18 | // 3.1, as published by the Free Software Foundation. | |
| 19 | ||
| 20 | // You should have received a copy of the GNU General Public License and | |
| 21 | // a copy of the GCC Runtime Library Exception along with this program; | |
| 22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
| 23 | // <http://www.gnu.org/licenses/>. | |
| e63637ea BK |
24 | |
| 25 | /** @file debug/unordered_set | |
| 26 | * This file is a GNU debug extension to the Standard C++ Library. | |
| 27 | */ | |
| 28 | ||
| 29 | #ifndef _GLIBCXX_DEBUG_UNORDERED_SET | |
| 30 | #define _GLIBCXX_DEBUG_UNORDERED_SET 1 | |
| 31 | ||
| 541a9b10 JW |
32 | #pragma GCC system_header |
| 33 | ||
| 734f5023 | 34 | #if __cplusplus < 201103L |
| ab65a4c7 | 35 | # include <bits/c++0x_warning.h> |
| c878d6ba PC |
36 | #else |
| 37 | # include <unordered_set> | |
| e63637ea | 38 | |
| 364c862b | 39 | #include <debug/safe_unordered_container.h> |
| 15ee1a77 | 40 | #include <debug/safe_container.h> |
| e63637ea | 41 | #include <debug/safe_iterator.h> |
| 77e0bf4e | 42 | #include <debug/safe_local_iterator.h> |
| e63637ea | 43 | |
| 12ffa228 | 44 | namespace std _GLIBCXX_VISIBILITY(default) |
| e63637ea BK |
45 | { |
| 46 | namespace __debug | |
| 47 | { | |
| 1ceb9e06 | 48 | /// Class std::unordered_set with safety/checking/debug instrumentation. |
| e63637ea | 49 | template<typename _Value, |
| ced3cb9f | 50 | typename _Hash = std::hash<_Value>, |
| e63637ea | 51 | typename _Pred = std::equal_to<_Value>, |
| ced3cb9f | 52 | typename _Alloc = std::allocator<_Value> > |
| e63637ea | 53 | class unordered_set |
| 15ee1a77 FD |
54 | : public __gnu_debug::_Safe_container< |
| 55 | unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc, | |
| 56 | __gnu_debug::_Safe_unordered_container>, | |
| 57 | public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc> | |
| e63637ea | 58 | { |
| 15ee1a77 FD |
59 | typedef _GLIBCXX_STD_C::unordered_set< |
| 60 | _Value, _Hash, _Pred, _Alloc> _Base; | |
| 61 | typedef __gnu_debug::_Safe_container< | |
| 62 | unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
| 63 | ||
| 64 | typedef typename _Base::const_iterator _Base_const_iterator; | |
| 65 | typedef typename _Base::iterator _Base_iterator; | |
| 77e0bf4e | 66 | typedef typename _Base::const_local_iterator _Base_const_local_iterator; |
| 15ee1a77 | 67 | typedef typename _Base::local_iterator _Base_local_iterator; |
| e63637ea BK |
68 | |
| 69 | public: | |
| 15ee1a77 FD |
70 | typedef typename _Base::size_type size_type; |
| 71 | typedef typename _Base::hasher hasher; | |
| 72 | typedef typename _Base::key_equal key_equal; | |
| 73 | typedef typename _Base::allocator_type allocator_type; | |
| 74 | ||
| 75 | typedef typename _Base::key_type key_type; | |
| 76 | typedef typename _Base::value_type value_type; | |
| 77 | ||
| 78 | typedef __gnu_debug::_Safe_iterator< | |
| 79 | _Base_iterator, unordered_set> iterator; | |
| 80 | typedef __gnu_debug::_Safe_iterator< | |
| 81 | _Base_const_iterator, unordered_set> const_iterator; | |
| 82 | typedef __gnu_debug::_Safe_local_iterator< | |
| 83 | _Base_local_iterator, unordered_set> local_iterator; | |
| 84 | typedef __gnu_debug::_Safe_local_iterator< | |
| 85 | _Base_const_local_iterator, unordered_set> const_local_iterator; | |
| e63637ea | 86 | |
| da27f556 FD |
87 | unordered_set() = default; |
| 88 | ||
| e63637ea | 89 | explicit |
| da27f556 | 90 | unordered_set(size_type __n, |
| e63637ea BK |
91 | const hasher& __hf = hasher(), |
| 92 | const key_equal& __eql = key_equal(), | |
| 93 | const allocator_type& __a = allocator_type()) | |
| ced3cb9f | 94 | : _Base(__n, __hf, __eql, __a) { } |
| e63637ea BK |
95 | |
| 96 | template<typename _InputIterator> | |
| 15ee1a77 | 97 | unordered_set(_InputIterator __first, _InputIterator __last, |
| 417e896e | 98 | size_type __n = 0, |
| 15ee1a77 FD |
99 | const hasher& __hf = hasher(), |
| 100 | const key_equal& __eql = key_equal(), | |
| e63637ea | 101 | const allocator_type& __a = allocator_type()) |
| 1f5ca1a1 PC |
102 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
| 103 | __last)), | |
| 104 | __gnu_debug::__base(__last), __n, | |
| 4c2d93db | 105 | __hf, __eql, __a) { } |
| ced3cb9f | 106 | |
| 0462b6aa | 107 | unordered_set(const unordered_set&) = default; |
| ced3cb9f | 108 | |
| 0462b6aa | 109 | unordered_set(const _Base& __x) |
| 15ee1a77 | 110 | : _Base(__x) { } |
| 0462b6aa FD |
111 | |
| 112 | unordered_set(unordered_set&&) = default; | |
| 113 | ||
| 114 | explicit | |
| 115 | unordered_set(const allocator_type& __a) | |
| 15ee1a77 | 116 | : _Base(__a) { } |
| 0462b6aa FD |
117 | |
| 118 | unordered_set(const unordered_set& __uset, | |
| 119 | const allocator_type& __a) | |
| 15ee1a77 | 120 | : _Base(__uset, __a) { } |
| ced3cb9f | 121 | |
| 0462b6aa FD |
122 | unordered_set(unordered_set&& __uset, |
| 123 | const allocator_type& __a) | |
| 15ee1a77 FD |
124 | : _Safe(std::move(__uset._M_safe()), __a), |
| 125 | _Base(std::move(__uset._M_base()), __a) { } | |
| e63637ea | 126 | |
| 988499f4 | 127 | unordered_set(initializer_list<value_type> __l, |
| 417e896e | 128 | size_type __n = 0, |
| 988499f4 JM |
129 | const hasher& __hf = hasher(), |
| 130 | const key_equal& __eql = key_equal(), | |
| 131 | const allocator_type& __a = allocator_type()) | |
| 4c2d93db | 132 | : _Base(__l, __n, __hf, __eql, __a) { } |
| e63637ea | 133 | |
| e55b80f5 FD |
134 | unordered_set(size_type __n, const allocator_type& __a) |
| 135 | : unordered_set(__n, hasher(), key_equal(), __a) | |
| 136 | { } | |
| 137 | ||
| 138 | unordered_set(size_type __n, const hasher& __hf, | |
| 139 | const allocator_type& __a) | |
| 140 | : unordered_set(__n, __hf, key_equal(), __a) | |
| 141 | { } | |
| 142 | ||
| 143 | template<typename _InputIterator> | |
| 144 | unordered_set(_InputIterator __first, _InputIterator __last, | |
| 145 | size_type __n, | |
| 146 | const allocator_type& __a) | |
| 147 | : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) | |
| 148 | { } | |
| 149 | ||
| 150 | template<typename _InputIterator> | |
| 151 | unordered_set(_InputIterator __first, _InputIterator __last, | |
| 152 | size_type __n, const hasher& __hf, | |
| 153 | const allocator_type& __a) | |
| 154 | : unordered_set(__first, __last, __n, __hf, key_equal(), __a) | |
| 155 | { } | |
| 156 | ||
| 157 | unordered_set(initializer_list<value_type> __l, | |
| 158 | size_type __n, | |
| 159 | const allocator_type& __a) | |
| 160 | : unordered_set(__l, __n, hasher(), key_equal(), __a) | |
| 161 | { } | |
| 162 | ||
| 163 | unordered_set(initializer_list<value_type> __l, | |
| 164 | size_type __n, const hasher& __hf, | |
| 165 | const allocator_type& __a) | |
| 166 | : unordered_set(__l, __n, __hf, key_equal(), __a) | |
| 167 | { } | |
| 168 | ||
| 15ee1a77 | 169 | ~unordered_set() = default; |
| 6f59ea25 | 170 | |
| ced3cb9f | 171 | unordered_set& |
| 15ee1a77 | 172 | operator=(const unordered_set&) = default; |
| 69b3331e PC |
173 | |
| 174 | unordered_set& | |
| 15ee1a77 | 175 | operator=(unordered_set&&) = default; |
| 69b3331e | 176 | |
| 988499f4 JM |
177 | unordered_set& |
| 178 | operator=(initializer_list<value_type> __l) | |
| 179 | { | |
| 0462b6aa FD |
180 | _M_base() = __l; |
| 181 | this->_M_invalidate_all(); | |
| 988499f4 JM |
182 | return *this; |
| 183 | } | |
| 184 | ||
| e63637ea | 185 | void |
| ff74fd13 | 186 | swap(unordered_set& __x) |
| c5d9ec56 | 187 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) |
| e63637ea | 188 | { |
| 15ee1a77 | 189 | _Safe::_M_swap(__x); |
| ced3cb9f | 190 | _Base::swap(__x); |
| e63637ea | 191 | } |
| 69b3331e PC |
192 | |
| 193 | void | |
| d3677132 | 194 | clear() noexcept |
| 69b3331e PC |
195 | { |
| 196 | _Base::clear(); | |
| 197 | this->_M_invalidate_all(); | |
| 198 | } | |
| 199 | ||
| 15ee1a77 | 200 | iterator |
| d3677132 | 201 | begin() noexcept |
| ced3cb9f PC |
202 | { return iterator(_Base::begin(), this); } |
| 203 | ||
| 204 | const_iterator | |
| d3677132 | 205 | begin() const noexcept |
| ced3cb9f PC |
206 | { return const_iterator(_Base::begin(), this); } |
| 207 | ||
| 208 | iterator | |
| d3677132 | 209 | end() noexcept |
| ced3cb9f PC |
210 | { return iterator(_Base::end(), this); } |
| 211 | ||
| 212 | const_iterator | |
| d3677132 | 213 | end() const noexcept |
| ced3cb9f PC |
214 | { return const_iterator(_Base::end(), this); } |
| 215 | ||
| 216 | const_iterator | |
| d3677132 | 217 | cbegin() const noexcept |
| ced3cb9f PC |
218 | { return const_iterator(_Base::begin(), this); } |
| 219 | ||
| 220 | const_iterator | |
| d3677132 | 221 | cend() const noexcept |
| ced3cb9f PC |
222 | { return const_iterator(_Base::end(), this); } |
| 223 | ||
| 224 | // local versions | |
| 77e0bf4e FD |
225 | local_iterator |
| 226 | begin(size_type __b) | |
| 7181e991 FD |
227 | { |
| 228 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 229 | return local_iterator(_Base::begin(__b), this); |
| 7181e991 | 230 | } |
| 77e0bf4e FD |
231 | |
| 232 | local_iterator | |
| 233 | end(size_type __b) | |
| 7181e991 FD |
234 | { |
| 235 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 236 | return local_iterator(_Base::end(__b), this); |
| 7181e991 | 237 | } |
| 77e0bf4e FD |
238 | |
| 239 | const_local_iterator | |
| 240 | begin(size_type __b) const | |
| 7181e991 FD |
241 | { |
| 242 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 243 | return const_local_iterator(_Base::begin(__b), this); |
| 7181e991 | 244 | } |
| 77e0bf4e FD |
245 | |
| 246 | const_local_iterator | |
| 247 | end(size_type __b) const | |
| 7181e991 FD |
248 | { |
| 249 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 250 | return const_local_iterator(_Base::end(__b), this); |
| 7181e991 | 251 | } |
| 77e0bf4e FD |
252 | |
| 253 | const_local_iterator | |
| 254 | cbegin(size_type __b) const | |
| 7181e991 FD |
255 | { |
| 256 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 257 | return const_local_iterator(_Base::cbegin(__b), this); |
| 7181e991 | 258 | } |
| 77e0bf4e FD |
259 | |
| 260 | const_local_iterator | |
| 261 | cend(size_type __b) const | |
| 7181e991 FD |
262 | { |
| 263 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 264 | return const_local_iterator(_Base::cend(__b), this); |
| 7181e991 FD |
265 | } |
| 266 | ||
| 267 | size_type | |
| 268 | bucket_size(size_type __b) const | |
| 269 | { | |
| 270 | __glibcxx_check_bucket_index(__b); | |
| 271 | return _Base::bucket_size(__b); | |
| 272 | } | |
| ced3cb9f | 273 | |
| 14cbb5d8 FD |
274 | float |
| 275 | max_load_factor() const noexcept | |
| 276 | { return _Base::max_load_factor(); } | |
| 277 | ||
| 278 | void | |
| 279 | max_load_factor(float __f) | |
| 280 | { | |
| 281 | __glibcxx_check_max_load_factor(__f); | |
| 282 | _Base::max_load_factor(__f); | |
| 283 | } | |
| 284 | ||
| 9b81593b FD |
285 | template<typename... _Args> |
| 286 | std::pair<iterator, bool> | |
| 287 | emplace(_Args&&... __args) | |
| 288 | { | |
| 289 | size_type __bucket_count = this->bucket_count(); | |
| 290 | std::pair<_Base_iterator, bool> __res | |
| 291 | = _Base::emplace(std::forward<_Args>(__args)...); | |
| 292 | _M_check_rehashed(__bucket_count); | |
| 293 | return std::make_pair(iterator(__res.first, this), __res.second); | |
| 294 | } | |
| 295 | ||
| 296 | template<typename... _Args> | |
| 297 | iterator | |
| 298 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
| 299 | { | |
| 300 | __glibcxx_check_insert(__hint); | |
| 301 | size_type __bucket_count = this->bucket_count(); | |
| 302 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
| 303 | std::forward<_Args>(__args)...); | |
| 304 | _M_check_rehashed(__bucket_count); | |
| 305 | return iterator(__it, this); | |
| 306 | } | |
| 307 | ||
| ced3cb9f PC |
308 | std::pair<iterator, bool> |
| 309 | insert(const value_type& __obj) | |
| 310 | { | |
| 77e0bf4e | 311 | size_type __bucket_count = this->bucket_count(); |
| 15ee1a77 FD |
312 | std::pair<_Base_iterator, bool> __res |
| 313 | = _Base::insert(__obj); | |
| 77e0bf4e | 314 | _M_check_rehashed(__bucket_count); |
| ced3cb9f PC |
315 | return std::make_pair(iterator(__res.first, this), __res.second); |
| 316 | } | |
| 317 | ||
| 318 | iterator | |
| d66411ba | 319 | insert(const_iterator __hint, const value_type& __obj) |
| ced3cb9f | 320 | { |
| d66411ba | 321 | __glibcxx_check_insert(__hint); |
| 77e0bf4e FD |
322 | size_type __bucket_count = this->bucket_count(); |
| 323 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); | |
| 324 | _M_check_rehashed(__bucket_count); | |
| 325 | return iterator(__it, this); | |
| ced3cb9f PC |
326 | } |
| 327 | ||
| fb7342fd PC |
328 | std::pair<iterator, bool> |
| 329 | insert(value_type&& __obj) | |
| 330 | { | |
| 77e0bf4e | 331 | size_type __bucket_count = this->bucket_count(); |
| 15ee1a77 FD |
332 | std::pair<_Base_iterator, bool> __res |
| 333 | = _Base::insert(std::move(__obj)); | |
| 77e0bf4e | 334 | _M_check_rehashed(__bucket_count); |
| fb7342fd PC |
335 | return std::make_pair(iterator(__res.first, this), __res.second); |
| 336 | } | |
| 337 | ||
| 338 | iterator | |
| d66411ba | 339 | insert(const_iterator __hint, value_type&& __obj) |
| fb7342fd | 340 | { |
| d66411ba | 341 | __glibcxx_check_insert(__hint); |
| 77e0bf4e FD |
342 | size_type __bucket_count = this->bucket_count(); |
| 343 | _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); | |
| 344 | _M_check_rehashed(__bucket_count); | |
| 345 | return iterator(__it, this); | |
| fb7342fd PC |
346 | } |
| 347 | ||
| ced3cb9f PC |
348 | void |
| 349 | insert(std::initializer_list<value_type> __l) | |
| 77e0bf4e FD |
350 | { |
| 351 | size_type __bucket_count = this->bucket_count(); | |
| 352 | _Base::insert(__l); | |
| 353 | _M_check_rehashed(__bucket_count); | |
| 354 | } | |
| ced3cb9f PC |
355 | |
| 356 | template<typename _InputIterator> | |
| 77e0bf4e FD |
357 | void |
| 358 | insert(_InputIterator __first, _InputIterator __last) | |
| 359 | { | |
| 24167c42 FD |
360 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
| 361 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
| 77e0bf4e | 362 | size_type __bucket_count = this->bucket_count(); |
| 24167c42 FD |
363 | |
| 364 | if (__dist.second >= __gnu_debug::__dp_sign) | |
| 365 | _Base::insert(__gnu_debug::__unsafe(__first), | |
| 366 | __gnu_debug::__unsafe(__last)); | |
| 367 | else | |
| 368 | _Base::insert(__first, __last); | |
| 369 | ||
| 77e0bf4e | 370 | _M_check_rehashed(__bucket_count); |
| ced3cb9f PC |
371 | } |
| 372 | ||
| 2dbe56bd JW |
373 | #if __cplusplus > 201402L |
| 374 | using node_type = typename _Base::node_type; | |
| 375 | ||
| 376 | struct insert_return_type | |
| 377 | { | |
| 378 | bool inserted; | |
| 379 | iterator position; | |
| 380 | node_type node; | |
| 381 | }; | |
| 382 | ||
| 383 | node_type | |
| 384 | extract(const_iterator __position) | |
| 385 | { | |
| 386 | __glibcxx_check_erase(__position); | |
| 387 | _Base_const_iterator __victim = __position.base(); | |
| 388 | this->_M_invalidate_if( | |
| 389 | [__victim](_Base_const_iterator __it) { return __it == __victim; } | |
| 390 | ); | |
| 391 | this->_M_invalidate_local_if( | |
| 392 | [__victim](_Base_const_local_iterator __it) { | |
| 393 | return __it._M_curr() == __victim._M_cur; | |
| 394 | }); | |
| 395 | return _Base::extract(__position.base()); | |
| 396 | } | |
| 397 | ||
| 398 | node_type | |
| 399 | extract(const key_type& __key) | |
| 400 | { | |
| 401 | const auto __position = find(__key); | |
| 402 | if (__position != end()) | |
| 403 | return extract(__position); | |
| 404 | return {}; | |
| 405 | } | |
| 406 | ||
| 407 | insert_return_type | |
| 408 | insert(node_type&& __nh) | |
| 409 | { | |
| 410 | auto __ret = _Base::insert(std::move(__nh)); | |
| 411 | iterator __pos = iterator(__ret.position, this); | |
| 412 | return { __ret.inserted, __pos, std::move(__ret.node) }; | |
| 413 | } | |
| 414 | ||
| 415 | iterator | |
| 416 | insert(const_iterator __hint, node_type&& __nh) | |
| 417 | { | |
| 418 | __glibcxx_check_insert(__hint); | |
| 419 | return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); | |
| 420 | } | |
| 421 | ||
| 422 | using _Base::merge; | |
| 423 | #endif // C++17 | |
| 424 | ||
| ced3cb9f PC |
425 | iterator |
| 426 | find(const key_type& __key) | |
| 427 | { return iterator(_Base::find(__key), this); } | |
| 428 | ||
| 429 | const_iterator | |
| 430 | find(const key_type& __key) const | |
| 431 | { return const_iterator(_Base::find(__key), this); } | |
| 432 | ||
| 433 | std::pair<iterator, iterator> | |
| 434 | equal_range(const key_type& __key) | |
| 435 | { | |
| 15ee1a77 FD |
436 | std::pair<_Base_iterator, _Base_iterator> __res |
| 437 | = _Base::equal_range(__key); | |
| ced3cb9f PC |
438 | return std::make_pair(iterator(__res.first, this), |
| 439 | iterator(__res.second, this)); | |
| 440 | } | |
| 441 | ||
| 442 | std::pair<const_iterator, const_iterator> | |
| 443 | equal_range(const key_type& __key) const | |
| 444 | { | |
| afe96d41 FD |
445 | std::pair<_Base_const_iterator, _Base_const_iterator> |
| 446 | __res = _Base::equal_range(__key); | |
| ced3cb9f PC |
447 | return std::make_pair(const_iterator(__res.first, this), |
| 448 | const_iterator(__res.second, this)); | |
| 449 | } | |
| 450 | ||
| 451 | size_type | |
| 452 | erase(const key_type& __key) | |
| 453 | { | |
| 454 | size_type __ret(0); | |
| afe96d41 FD |
455 | _Base_iterator __victim(_Base::find(__key)); |
| 456 | if (__victim != _Base::end()) | |
| ced3cb9f | 457 | { |
| 77e0bf4e FD |
458 | this->_M_invalidate_if( |
| 459 | [__victim](_Base_const_iterator __it) | |
| 460 | { return __it == __victim; }); | |
| 77e0bf4e | 461 | this->_M_invalidate_local_if( |
| 5b3be7cf | 462 | [__victim](_Base_const_local_iterator __it) |
| 92e16228 | 463 | { return __it._M_curr() == __victim._M_cur; }); |
| 77e0bf4e | 464 | size_type __bucket_count = this->bucket_count(); |
| afe96d41 | 465 | _Base::erase(__victim); |
| 77e0bf4e | 466 | _M_check_rehashed(__bucket_count); |
| ced3cb9f PC |
467 | __ret = 1; |
| 468 | } | |
| 469 | return __ret; | |
| 470 | } | |
| 471 | ||
| d723ced2 | 472 | iterator |
| ced3cb9f PC |
473 | erase(const_iterator __it) |
| 474 | { | |
| 475 | __glibcxx_check_erase(__it); | |
| 77e0bf4e FD |
476 | _Base_const_iterator __victim = __it.base(); |
| 477 | this->_M_invalidate_if( | |
| 478 | [__victim](_Base_const_iterator __it) | |
| 479 | { return __it == __victim; }); | |
| 77e0bf4e | 480 | this->_M_invalidate_local_if( |
| 5b3be7cf | 481 | [__victim](_Base_const_local_iterator __it) |
| 92e16228 | 482 | { return __it._M_curr() == __victim._M_cur; }); |
| 77e0bf4e FD |
483 | size_type __bucket_count = this->bucket_count(); |
| 484 | _Base_iterator __next = _Base::erase(__it.base()); | |
| 485 | _M_check_rehashed(__bucket_count); | |
| 486 | return iterator(__next, this); | |
| ced3cb9f PC |
487 | } |
| 488 | ||
| 6dc88283 PC |
489 | iterator |
| 490 | erase(iterator __it) | |
| 491 | { return erase(const_iterator(__it)); } | |
| 492 | ||
| d723ced2 | 493 | iterator |
| ced3cb9f PC |
494 | erase(const_iterator __first, const_iterator __last) |
| 495 | { | |
| 496 | __glibcxx_check_erase_range(__first, __last); | |
| afe96d41 FD |
497 | for (_Base_const_iterator __tmp = __first.base(); |
| 498 | __tmp != __last.base(); ++__tmp) | |
| 499 | { | |
| 500 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
| 501 | _M_message(__gnu_debug::__msg_valid_range) | |
| 502 | ._M_iterator(__first, "first") | |
| 503 | ._M_iterator(__last, "last")); | |
| 77e0bf4e FD |
504 | this->_M_invalidate_if( |
| 505 | [__tmp](_Base_const_iterator __it) | |
| 506 | { return __it == __tmp; }); | |
| 77e0bf4e | 507 | this->_M_invalidate_local_if( |
| 5b3be7cf | 508 | [__tmp](_Base_const_local_iterator __it) |
| 92e16228 | 509 | { return __it._M_curr() == __tmp._M_cur; }); |
| afe96d41 | 510 | } |
| 77e0bf4e FD |
511 | size_type __bucket_count = this->bucket_count(); |
| 512 | _Base_iterator __next = _Base::erase(__first.base(), | |
| 513 | __last.base()); | |
| 514 | _M_check_rehashed(__bucket_count); | |
| 515 | return iterator(__next, this); | |
| ced3cb9f PC |
516 | } |
| 517 | ||
| 518 | _Base& | |
| 15ee1a77 | 519 | _M_base() noexcept { return *this; } |
| ced3cb9f PC |
520 | |
| 521 | const _Base& | |
| d3677132 | 522 | _M_base() const noexcept { return *this; } |
| ced3cb9f | 523 | |
| 69b3331e | 524 | private: |
| 77e0bf4e FD |
525 | void |
| 526 | _M_check_rehashed(size_type __prev_count) | |
| 527 | { | |
| 528 | if (__prev_count != this->bucket_count()) | |
| 15ee1a77 | 529 | this->_M_invalidate_locals(); |
| 69b3331e | 530 | } |
| e63637ea BK |
531 | }; |
| 532 | ||
| 957f5fea VV |
533 | #if __cpp_deduction_guides >= 201606 |
| 534 | ||
| 535 | template<typename _InputIterator, | |
| 536 | typename _Hash = | |
| 537 | hash<typename iterator_traits<_InputIterator>::value_type>, | |
| 538 | typename _Pred = | |
| 539 | equal_to<typename iterator_traits<_InputIterator>::value_type>, | |
| 540 | typename _Allocator = | |
| 541 | allocator<typename iterator_traits<_InputIterator>::value_type>, | |
| 542 | typename = _RequireInputIter<_InputIterator>, | |
| 543 | typename = _RequireAllocator<_Allocator>> | |
| 544 | unordered_set(_InputIterator, _InputIterator, | |
| 545 | unordered_set<int>::size_type = {}, | |
| 546 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
| 547 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, | |
| 548 | _Hash, _Pred, _Allocator>; | |
| 549 | ||
| 550 | template<typename _Tp, typename _Hash = hash<_Tp>, | |
| 551 | typename _Pred = equal_to<_Tp>, | |
| 552 | typename _Allocator = allocator<_Tp>, | |
| 553 | typename = _RequireAllocator<_Allocator>> | |
| 554 | unordered_set(initializer_list<_Tp>, | |
| 555 | unordered_set<int>::size_type = {}, | |
| 556 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
| 557 | -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; | |
| 558 | ||
| 559 | template<typename _InputIterator, typename _Allocator, | |
| 560 | typename = _RequireInputIter<_InputIterator>, | |
| 561 | typename = _RequireAllocator<_Allocator>> | |
| 562 | unordered_set(_InputIterator, _InputIterator, | |
| 563 | unordered_set<int>::size_type, _Allocator) | |
| 564 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, | |
| 565 | hash< | |
| 566 | typename iterator_traits<_InputIterator>::value_type>, | |
| 567 | equal_to< | |
| 568 | typename iterator_traits<_InputIterator>::value_type>, | |
| 569 | _Allocator>; | |
| 570 | ||
| 571 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
| 572 | typename = _RequireInputIter<_InputIterator>, | |
| 573 | typename = _RequireAllocator<_Allocator>> | |
| 574 | unordered_set(_InputIterator, _InputIterator, | |
| 575 | unordered_set<int>::size_type, | |
| 576 | _Hash, _Allocator) | |
| 577 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, | |
| 578 | _Hash, | |
| 579 | equal_to< | |
| 580 | typename iterator_traits<_InputIterator>::value_type>, | |
| 581 | _Allocator>; | |
| 582 | ||
| 583 | template<typename _Tp, typename _Allocator, | |
| 584 | typename = _RequireAllocator<_Allocator>> | |
| 585 | unordered_set(initializer_list<_Tp>, | |
| 586 | unordered_set<int>::size_type, _Allocator) | |
| 587 | -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; | |
| 588 | ||
| 589 | template<typename _Tp, typename _Hash, typename _Allocator, | |
| 590 | typename = _RequireAllocator<_Allocator>> | |
| 591 | unordered_set(initializer_list<_Tp>, | |
| 592 | unordered_set<int>::size_type, _Hash, _Allocator) | |
| 593 | -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; | |
| 594 | ||
| 595 | #endif | |
| 596 | ||
| e63637ea | 597 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
| 69b3331e PC |
598 | inline void |
| 599 | swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
| 600 | unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
| c5d9ec56 | 601 | noexcept(noexcept(__x.swap(__y))) |
| 69b3331e | 602 | { __x.swap(__y); } |
| e63637ea | 603 | |
| 5dc22714 PC |
604 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
| 605 | inline bool | |
| 606 | operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
| 607 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
| 637fd8b3 | 608 | { return __x._M_base() == __y._M_base(); } |
| 5dc22714 PC |
609 | |
| 610 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
| 611 | inline bool | |
| 612 | operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
| 613 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
| 614 | { return !(__x == __y); } | |
| 615 | ||
| e63637ea | 616 | |
| 1ceb9e06 | 617 | /// Class std::unordered_multiset with safety/checking/debug instrumentation. |
| e63637ea | 618 | template<typename _Value, |
| ced3cb9f | 619 | typename _Hash = std::hash<_Value>, |
| e63637ea | 620 | typename _Pred = std::equal_to<_Value>, |
| ced3cb9f | 621 | typename _Alloc = std::allocator<_Value> > |
| e63637ea | 622 | class unordered_multiset |
| 15ee1a77 FD |
623 | : public __gnu_debug::_Safe_container< |
| 624 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, | |
| 625 | __gnu_debug::_Safe_unordered_container>, | |
| 626 | public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> | |
| e63637ea | 627 | { |
| 15ee1a77 FD |
628 | typedef _GLIBCXX_STD_C::unordered_multiset< |
| 629 | _Value, _Hash, _Pred, _Alloc> _Base; | |
| 630 | typedef __gnu_debug::_Safe_container<unordered_multiset, | |
| 631 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
| 632 | typedef typename _Base::const_iterator _Base_const_iterator; | |
| 633 | typedef typename _Base::iterator _Base_iterator; | |
| 634 | typedef typename _Base::const_local_iterator | |
| 635 | _Base_const_local_iterator; | |
| 636 | typedef typename _Base::local_iterator _Base_local_iterator; | |
| 0462b6aa | 637 | |
| e63637ea | 638 | public: |
| 15ee1a77 FD |
639 | typedef typename _Base::size_type size_type; |
| 640 | typedef typename _Base::hasher hasher; | |
| 641 | typedef typename _Base::key_equal key_equal; | |
| 642 | typedef typename _Base::allocator_type allocator_type; | |
| 643 | ||
| 644 | typedef typename _Base::key_type key_type; | |
| 645 | typedef typename _Base::value_type value_type; | |
| 646 | ||
| 647 | typedef __gnu_debug::_Safe_iterator< | |
| 648 | _Base_iterator, unordered_multiset> iterator; | |
| 649 | typedef __gnu_debug::_Safe_iterator< | |
| 650 | _Base_const_iterator, unordered_multiset> const_iterator; | |
| 77e0bf4e | 651 | typedef __gnu_debug::_Safe_local_iterator< |
| 15ee1a77 | 652 | _Base_local_iterator, unordered_multiset> local_iterator; |
| 77e0bf4e FD |
653 | typedef __gnu_debug::_Safe_local_iterator< |
| 654 | _Base_const_local_iterator, unordered_multiset> const_local_iterator; | |
| e63637ea | 655 | |
| da27f556 FD |
656 | unordered_multiset() = default; |
| 657 | ||
| e63637ea | 658 | explicit |
| da27f556 | 659 | unordered_multiset(size_type __n, |
| ced3cb9f PC |
660 | const hasher& __hf = hasher(), |
| 661 | const key_equal& __eql = key_equal(), | |
| 662 | const allocator_type& __a = allocator_type()) | |
| 663 | : _Base(__n, __hf, __eql, __a) { } | |
| e63637ea BK |
664 | |
| 665 | template<typename _InputIterator> | |
| 15ee1a77 | 666 | unordered_multiset(_InputIterator __first, _InputIterator __last, |
| 417e896e | 667 | size_type __n = 0, |
| 15ee1a77 FD |
668 | const hasher& __hf = hasher(), |
| 669 | const key_equal& __eql = key_equal(), | |
| ced3cb9f | 670 | const allocator_type& __a = allocator_type()) |
| 1f5ca1a1 PC |
671 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
| 672 | __last)), | |
| 673 | __gnu_debug::__base(__last), __n, | |
| 4c2d93db | 674 | __hf, __eql, __a) { } |
| ced3cb9f | 675 | |
| 0462b6aa | 676 | unordered_multiset(const unordered_multiset&) = default; |
| ced3cb9f | 677 | |
| 15ee1a77 | 678 | unordered_multiset(const _Base& __x) |
| 4c2d93db | 679 | : _Base(__x) { } |
| ced3cb9f | 680 | |
| 0462b6aa FD |
681 | unordered_multiset(unordered_multiset&&) = default; |
| 682 | ||
| 683 | explicit | |
| 684 | unordered_multiset(const allocator_type& __a) | |
| 15ee1a77 | 685 | : _Base(__a) { } |
| 0462b6aa FD |
686 | |
| 687 | unordered_multiset(const unordered_multiset& __uset, | |
| 688 | const allocator_type& __a) | |
| 15ee1a77 FD |
689 | : _Base(__uset, __a) { } |
| 690 | ||
| 0462b6aa FD |
691 | unordered_multiset(unordered_multiset&& __uset, |
| 692 | const allocator_type& __a) | |
| 15ee1a77 FD |
693 | : _Safe(std::move(__uset._M_safe()), __a), |
| 694 | _Base(std::move(__uset._M_base()), __a) { } | |
| e63637ea | 695 | |
| 988499f4 | 696 | unordered_multiset(initializer_list<value_type> __l, |
| 417e896e | 697 | size_type __n = 0, |
| 988499f4 JM |
698 | const hasher& __hf = hasher(), |
| 699 | const key_equal& __eql = key_equal(), | |
| 700 | const allocator_type& __a = allocator_type()) | |
| 4c2d93db | 701 | : _Base(__l, __n, __hf, __eql, __a) { } |
| e63637ea | 702 | |
| e55b80f5 FD |
703 | unordered_multiset(size_type __n, const allocator_type& __a) |
| 704 | : unordered_multiset(__n, hasher(), key_equal(), __a) | |
| 705 | { } | |
| 706 | ||
| 707 | unordered_multiset(size_type __n, const hasher& __hf, | |
| 708 | const allocator_type& __a) | |
| 709 | : unordered_multiset(__n, __hf, key_equal(), __a) | |
| 710 | { } | |
| 711 | ||
| 712 | template<typename _InputIterator> | |
| 713 | unordered_multiset(_InputIterator __first, _InputIterator __last, | |
| 714 | size_type __n, | |
| 715 | const allocator_type& __a) | |
| 716 | : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) | |
| 717 | { } | |
| 718 | ||
| 719 | template<typename _InputIterator> | |
| 720 | unordered_multiset(_InputIterator __first, _InputIterator __last, | |
| 721 | size_type __n, const hasher& __hf, | |
| 722 | const allocator_type& __a) | |
| 723 | : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) | |
| 724 | { } | |
| 725 | ||
| 726 | unordered_multiset(initializer_list<value_type> __l, | |
| 727 | size_type __n, | |
| 728 | const allocator_type& __a) | |
| 729 | : unordered_multiset(__l, __n, hasher(), key_equal(), __a) | |
| 730 | { } | |
| 731 | ||
| 732 | unordered_multiset(initializer_list<value_type> __l, | |
| 733 | size_type __n, const hasher& __hf, | |
| 734 | const allocator_type& __a) | |
| 735 | : unordered_multiset(__l, __n, __hf, key_equal(), __a) | |
| 736 | { } | |
| 737 | ||
| 15ee1a77 | 738 | ~unordered_multiset() = default; |
| 6f59ea25 | 739 | |
| ced3cb9f | 740 | unordered_multiset& |
| 15ee1a77 | 741 | operator=(const unordered_multiset&) = default; |
| 69b3331e PC |
742 | |
| 743 | unordered_multiset& | |
| 15ee1a77 | 744 | operator=(unordered_multiset&&) = default; |
| 69b3331e | 745 | |
| 988499f4 JM |
746 | unordered_multiset& |
| 747 | operator=(initializer_list<value_type> __l) | |
| 748 | { | |
| 15ee1a77 | 749 | this->_M_base() = __l; |
| 0462b6aa | 750 | this->_M_invalidate_all(); |
| 988499f4 JM |
751 | return *this; |
| 752 | } | |
| 753 | ||
| e63637ea | 754 | void |
| ff74fd13 | 755 | swap(unordered_multiset& __x) |
| c5d9ec56 | 756 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) |
| e63637ea | 757 | { |
| 15ee1a77 | 758 | _Safe::_M_swap(__x); |
| ced3cb9f | 759 | _Base::swap(__x); |
| e63637ea | 760 | } |
| 69b3331e | 761 | |
| ced3cb9f | 762 | void |
| d3677132 | 763 | clear() noexcept |
| 69b3331e PC |
764 | { |
| 765 | _Base::clear(); | |
| 766 | this->_M_invalidate_all(); | |
| 767 | } | |
| 768 | ||
| ced3cb9f | 769 | iterator |
| d3677132 | 770 | begin() noexcept |
| ced3cb9f PC |
771 | { return iterator(_Base::begin(), this); } |
| 772 | ||
| 773 | const_iterator | |
| d3677132 | 774 | begin() const noexcept |
| ced3cb9f PC |
775 | { return const_iterator(_Base::begin(), this); } |
| 776 | ||
| 777 | iterator | |
| d3677132 | 778 | end() noexcept |
| ced3cb9f PC |
779 | { return iterator(_Base::end(), this); } |
| 780 | ||
| 781 | const_iterator | |
| d3677132 | 782 | end() const noexcept |
| ced3cb9f PC |
783 | { return const_iterator(_Base::end(), this); } |
| 784 | ||
| 785 | const_iterator | |
| d3677132 | 786 | cbegin() const noexcept |
| ced3cb9f PC |
787 | { return const_iterator(_Base::begin(), this); } |
| 788 | ||
| 789 | const_iterator | |
| d3677132 | 790 | cend() const noexcept |
| ced3cb9f PC |
791 | { return const_iterator(_Base::end(), this); } |
| 792 | ||
| 793 | // local versions | |
| 77e0bf4e FD |
794 | local_iterator |
| 795 | begin(size_type __b) | |
| 7181e991 FD |
796 | { |
| 797 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 798 | return local_iterator(_Base::begin(__b), this); |
| 7181e991 | 799 | } |
| 77e0bf4e FD |
800 | |
| 801 | local_iterator | |
| 802 | end(size_type __b) | |
| 7181e991 FD |
803 | { |
| 804 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 805 | return local_iterator(_Base::end(__b), this); |
| 7181e991 | 806 | } |
| 77e0bf4e FD |
807 | |
| 808 | const_local_iterator | |
| 809 | begin(size_type __b) const | |
| 7181e991 FD |
810 | { |
| 811 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 812 | return const_local_iterator(_Base::begin(__b), this); |
| 7181e991 | 813 | } |
| 77e0bf4e FD |
814 | |
| 815 | const_local_iterator | |
| 816 | end(size_type __b) const | |
| 7181e991 FD |
817 | { |
| 818 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 819 | return const_local_iterator(_Base::end(__b), this); |
| 7181e991 | 820 | } |
| 77e0bf4e FD |
821 | |
| 822 | const_local_iterator | |
| 823 | cbegin(size_type __b) const | |
| 7181e991 FD |
824 | { |
| 825 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 826 | return const_local_iterator(_Base::cbegin(__b), this); |
| 7181e991 | 827 | } |
| 77e0bf4e FD |
828 | |
| 829 | const_local_iterator | |
| 830 | cend(size_type __b) const | |
| 7181e991 FD |
831 | { |
| 832 | __glibcxx_check_bucket_index(__b); | |
| 2e5189c8 | 833 | return const_local_iterator(_Base::cend(__b), this); |
| 7181e991 FD |
834 | } |
| 835 | ||
| 836 | size_type | |
| 837 | bucket_size(size_type __b) const | |
| 838 | { | |
| 839 | __glibcxx_check_bucket_index(__b); | |
| 840 | return _Base::bucket_size(__b); | |
| 841 | } | |
| 14cbb5d8 FD |
842 | |
| 843 | float | |
| 844 | max_load_factor() const noexcept | |
| 845 | { return _Base::max_load_factor(); } | |
| 846 | ||
| 847 | void | |
| 848 | max_load_factor(float __f) | |
| 849 | { | |
| 850 | __glibcxx_check_max_load_factor(__f); | |
| 851 | _Base::max_load_factor(__f); | |
| 852 | } | |
| ced3cb9f | 853 | |
| 9b81593b FD |
854 | template<typename... _Args> |
| 855 | iterator | |
| 856 | emplace(_Args&&... __args) | |
| 857 | { | |
| 858 | size_type __bucket_count = this->bucket_count(); | |
| 859 | _Base_iterator __it | |
| 860 | = _Base::emplace(std::forward<_Args>(__args)...); | |
| 861 | _M_check_rehashed(__bucket_count); | |
| 862 | return iterator(__it, this); | |
| 863 | } | |
| 864 | ||
| 865 | template<typename... _Args> | |
| 866 | iterator | |
| 867 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
| 868 | { | |
| 869 | __glibcxx_check_insert(__hint); | |
| 870 | size_type __bucket_count = this->bucket_count(); | |
| 871 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
| 872 | std::forward<_Args>(__args)...); | |
| 873 | _M_check_rehashed(__bucket_count); | |
| 874 | return iterator(__it, this); | |
| 875 | } | |
| 876 | ||
| ced3cb9f PC |
877 | iterator |
| 878 | insert(const value_type& __obj) | |
| 77e0bf4e FD |
879 | { |
| 880 | size_type __bucket_count = this->bucket_count(); | |
| 881 | _Base_iterator __it = _Base::insert(__obj); | |
| 882 | _M_check_rehashed(__bucket_count); | |
| 883 | return iterator(__it, this); | |
| 884 | } | |
| ced3cb9f PC |
885 | |
| 886 | iterator | |
| d66411ba FD |
887 | insert(const_iterator __hint, const value_type& __obj) |
| 888 | { | |
| 889 | __glibcxx_check_insert(__hint); | |
| 77e0bf4e | 890 | size_type __bucket_count = this->bucket_count(); |
| 15ee1a77 | 891 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); |
| 77e0bf4e FD |
892 | _M_check_rehashed(__bucket_count); |
| 893 | return iterator(__it, this); | |
| d66411ba | 894 | } |
| ced3cb9f | 895 | |
| fb7342fd PC |
896 | iterator |
| 897 | insert(value_type&& __obj) | |
| 77e0bf4e FD |
898 | { |
| 899 | size_type __bucket_count = this->bucket_count(); | |
| 15ee1a77 | 900 | _Base_iterator __it = _Base::insert(std::move(__obj)); |
| 77e0bf4e FD |
901 | _M_check_rehashed(__bucket_count); |
| 902 | return iterator(__it, this); | |
| 903 | } | |
| fb7342fd PC |
904 | |
| 905 | iterator | |
| d66411ba FD |
906 | insert(const_iterator __hint, value_type&& __obj) |
| 907 | { | |
| 908 | __glibcxx_check_insert(__hint); | |
| 77e0bf4e | 909 | size_type __bucket_count = this->bucket_count(); |
| 15ee1a77 | 910 | _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); |
| 77e0bf4e FD |
911 | _M_check_rehashed(__bucket_count); |
| 912 | return iterator(__it, this); | |
| d66411ba | 913 | } |
| fb7342fd | 914 | |
| ced3cb9f PC |
915 | void |
| 916 | insert(std::initializer_list<value_type> __l) | |
| 77e0bf4e FD |
917 | { |
| 918 | size_type __bucket_count = this->bucket_count(); | |
| 919 | _Base::insert(__l); | |
| 920 | _M_check_rehashed(__bucket_count); | |
| 921 | } | |
| ced3cb9f PC |
922 | |
| 923 | template<typename _InputIterator> | |
| 77e0bf4e FD |
924 | void |
| 925 | insert(_InputIterator __first, _InputIterator __last) | |
| 926 | { | |
| 24167c42 FD |
927 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
| 928 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
| 77e0bf4e | 929 | size_type __bucket_count = this->bucket_count(); |
| 24167c42 FD |
930 | |
| 931 | if (__dist.second >= __gnu_debug::__dp_sign) | |
| 932 | _Base::insert(__gnu_debug::__unsafe(__first), | |
| 933 | __gnu_debug::__unsafe(__last)); | |
| 934 | else | |
| 935 | _Base::insert(__first, __last); | |
| 936 | ||
| 77e0bf4e | 937 | _M_check_rehashed(__bucket_count); |
| ced3cb9f PC |
938 | } |
| 939 | ||
| 2dbe56bd JW |
940 | #if __cplusplus > 201402L |
| 941 | using node_type = typename _Base::node_type; | |
| 942 | ||
| 943 | node_type | |
| 944 | extract(const_iterator __position) | |
| 945 | { | |
| 946 | __glibcxx_check_erase(__position); | |
| 947 | _Base_const_iterator __victim = __position.base(); | |
| 948 | this->_M_invalidate_if( | |
| 949 | [__victim](_Base_const_iterator __it) { return __it == __victim; } | |
| 950 | ); | |
| 951 | this->_M_invalidate_local_if( | |
| 952 | [__victim](_Base_const_local_iterator __it) { | |
| 953 | return __it._M_curr() == __victim._M_cur; | |
| 954 | }); | |
| 955 | return _Base::extract(__position.base()); | |
| 956 | } | |
| 957 | ||
| 958 | node_type | |
| 959 | extract(const key_type& __key) | |
| 960 | { | |
| 961 | const auto __position = find(__key); | |
| 962 | if (__position != end()) | |
| 963 | return extract(__position); | |
| 964 | return {}; | |
| 965 | } | |
| 966 | ||
| 967 | iterator | |
| 968 | insert(node_type&& __nh) | |
| 969 | { return iterator(_Base::insert(std::move(__nh)), this); } | |
| 970 | ||
| 971 | iterator | |
| 972 | insert(const_iterator __hint, node_type&& __nh) | |
| 973 | { | |
| 974 | __glibcxx_check_insert(__hint); | |
| 975 | return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); | |
| 976 | } | |
| 977 | ||
| 978 | using _Base::merge; | |
| 979 | #endif // C++17 | |
| 980 | ||
| ced3cb9f PC |
981 | iterator |
| 982 | find(const key_type& __key) | |
| 983 | { return iterator(_Base::find(__key), this); } | |
| 984 | ||
| 985 | const_iterator | |
| 986 | find(const key_type& __key) const | |
| 987 | { return const_iterator(_Base::find(__key), this); } | |
| 988 | ||
| 989 | std::pair<iterator, iterator> | |
| 990 | equal_range(const key_type& __key) | |
| 991 | { | |
| 15ee1a77 FD |
992 | std::pair<_Base_iterator, _Base_iterator> __res |
| 993 | = _Base::equal_range(__key); | |
| ced3cb9f PC |
994 | return std::make_pair(iterator(__res.first, this), |
| 995 | iterator(__res.second, this)); | |
| 996 | } | |
| 997 | ||
| 998 | std::pair<const_iterator, const_iterator> | |
| 999 | equal_range(const key_type& __key) const | |
| 1000 | { | |
| afe96d41 FD |
1001 | std::pair<_Base_const_iterator, _Base_const_iterator> |
| 1002 | __res = _Base::equal_range(__key); | |
| ced3cb9f PC |
1003 | return std::make_pair(const_iterator(__res.first, this), |
| 1004 | const_iterator(__res.second, this)); | |
| 1005 | } | |
| 1006 | ||
| 1007 | size_type | |
| 1008 | erase(const key_type& __key) | |
| 1009 | { | |
| 1010 | size_type __ret(0); | |
| d3b8263e FD |
1011 | std::pair<_Base_iterator, _Base_iterator> __pair = |
| 1012 | _Base::equal_range(__key); | |
| 1013 | for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) | |
| ced3cb9f | 1014 | { |
| 77e0bf4e FD |
1015 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
| 1016 | { return __it == __victim; }); | |
| 77e0bf4e | 1017 | this->_M_invalidate_local_if( |
| 5b3be7cf | 1018 | [__victim](_Base_const_local_iterator __it) |
| 92e16228 | 1019 | { return __it._M_curr() == __victim._M_cur; }); |
| d3b8263e FD |
1020 | _Base::erase(__victim++); |
| 1021 | ++__ret; | |
| ced3cb9f PC |
1022 | } |
| 1023 | return __ret; | |
| 1024 | } | |
| 1025 | ||
| d723ced2 | 1026 | iterator |
| ced3cb9f PC |
1027 | erase(const_iterator __it) |
| 1028 | { | |
| 1029 | __glibcxx_check_erase(__it); | |
| 77e0bf4e FD |
1030 | _Base_const_iterator __victim = __it.base(); |
| 1031 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
| 1032 | { return __it == __victim; }); | |
| 77e0bf4e | 1033 | this->_M_invalidate_local_if( |
| 5b3be7cf | 1034 | [__victim](_Base_const_local_iterator __it) |
| 92e16228 | 1035 | { return __it._M_curr() == __victim._M_cur; }); |
| d723ced2 | 1036 | return iterator(_Base::erase(__it.base()), this); |
| ced3cb9f PC |
1037 | } |
| 1038 | ||
| 6dc88283 PC |
1039 | iterator |
| 1040 | erase(iterator __it) | |
| 1041 | { return erase(const_iterator(__it)); } | |
| 1042 | ||
| d723ced2 | 1043 | iterator |
| ced3cb9f PC |
1044 | erase(const_iterator __first, const_iterator __last) |
| 1045 | { | |
| 1046 | __glibcxx_check_erase_range(__first, __last); | |
| afe96d41 FD |
1047 | for (_Base_const_iterator __tmp = __first.base(); |
| 1048 | __tmp != __last.base(); ++__tmp) | |
| 1049 | { | |
| 1050 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
| 1051 | _M_message(__gnu_debug::__msg_valid_range) | |
| 1052 | ._M_iterator(__first, "first") | |
| 1053 | ._M_iterator(__last, "last")); | |
| 77e0bf4e FD |
1054 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
| 1055 | { return __it == __tmp; }); | |
| 77e0bf4e | 1056 | this->_M_invalidate_local_if( |
| 5b3be7cf | 1057 | [__tmp](_Base_const_local_iterator __it) |
| 92e16228 | 1058 | { return __it._M_curr() == __tmp._M_cur; }); |
| afe96d41 | 1059 | } |
| d723ced2 PC |
1060 | return iterator(_Base::erase(__first.base(), |
| 1061 | __last.base()), this); | |
| ced3cb9f PC |
1062 | } |
| 1063 | ||
| 1064 | _Base& | |
| 15ee1a77 | 1065 | _M_base() noexcept { return *this; } |
| ced3cb9f PC |
1066 | |
| 1067 | const _Base& | |
| 15ee1a77 | 1068 | _M_base() const noexcept { return *this; } |
| ced3cb9f | 1069 | |
| 69b3331e | 1070 | private: |
| 77e0bf4e FD |
1071 | void |
| 1072 | _M_check_rehashed(size_type __prev_count) | |
| 1073 | { | |
| 1074 | if (__prev_count != this->bucket_count()) | |
| 15ee1a77 | 1075 | this->_M_invalidate_locals(); |
| 69b3331e | 1076 | } |
| e63637ea BK |
1077 | }; |
| 1078 | ||
| 957f5fea VV |
1079 | #if __cpp_deduction_guides >= 201606 |
| 1080 | ||
| 1081 | template<typename _InputIterator, | |
| 1082 | typename _Hash = | |
| 1083 | hash<typename iterator_traits<_InputIterator>::value_type>, | |
| 1084 | typename _Pred = | |
| 1085 | equal_to<typename iterator_traits<_InputIterator>::value_type>, | |
| 1086 | typename _Allocator = | |
| 1087 | allocator<typename iterator_traits<_InputIterator>::value_type>, | |
| 1088 | typename = _RequireInputIter<_InputIterator>, | |
| 1089 | typename = _RequireAllocator<_Allocator>> | |
| 1090 | unordered_multiset(_InputIterator, _InputIterator, | |
| 1091 | unordered_multiset<int>::size_type = {}, | |
| 1092 | _Hash = _Hash(), _Pred = _Pred(), | |
| 1093 | _Allocator = _Allocator()) | |
| 1094 | -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, | |
| 1095 | _Hash, _Pred, _Allocator>; | |
| 1096 | ||
| 1097 | template<typename _Tp, typename _Hash = hash<_Tp>, | |
| 1098 | typename _Pred = equal_to<_Tp>, | |
| 1099 | typename _Allocator = allocator<_Tp>, | |
| 1100 | typename = _RequireAllocator<_Allocator>> | |
| 1101 | unordered_multiset(initializer_list<_Tp>, | |
| 1102 | unordered_multiset<int>::size_type = {}, | |
| 1103 | _Hash = _Hash(), _Pred = _Pred(), | |
| 1104 | _Allocator = _Allocator()) | |
| 1105 | -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; | |
| 1106 | ||
| 1107 | template<typename _InputIterator, typename _Allocator, | |
| 1108 | typename = _RequireInputIter<_InputIterator>, | |
| 1109 | typename = _RequireAllocator<_Allocator>> | |
| 1110 | unordered_multiset(_InputIterator, _InputIterator, | |
| 1111 | unordered_multiset<int>::size_type, _Allocator) | |
| 1112 | -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, | |
| 1113 | hash<typename | |
| 1114 | iterator_traits<_InputIterator>::value_type>, | |
| 1115 | equal_to<typename | |
| 1116 | iterator_traits<_InputIterator>::value_type>, | |
| 1117 | _Allocator>; | |
| 1118 | ||
| 1119 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
| 1120 | typename = _RequireInputIter<_InputIterator>, | |
| 1121 | typename = _RequireAllocator<_Allocator>> | |
| 1122 | unordered_multiset(_InputIterator, _InputIterator, | |
| 1123 | unordered_multiset<int>::size_type, | |
| 1124 | _Hash, _Allocator) | |
| 1125 | -> unordered_multiset<typename | |
| 1126 | iterator_traits<_InputIterator>::value_type, | |
| 1127 | _Hash, | |
| 1128 | equal_to< | |
| 1129 | typename | |
| 1130 | iterator_traits<_InputIterator>::value_type>, | |
| 1131 | _Allocator>; | |
| 1132 | ||
| 1133 | template<typename _Tp, typename _Allocator, | |
| 1134 | typename = _RequireAllocator<_Allocator>> | |
| 1135 | unordered_multiset(initializer_list<_Tp>, | |
| 1136 | unordered_multiset<int>::size_type, _Allocator) | |
| 1137 | -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; | |
| 1138 | ||
| 1139 | template<typename _Tp, typename _Hash, typename _Allocator, | |
| 1140 | typename = _RequireAllocator<_Allocator>> | |
| 1141 | unordered_multiset(initializer_list<_Tp>, | |
| 1142 | unordered_multiset<int>::size_type, _Hash, _Allocator) | |
| 1143 | -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; | |
| 1144 | ||
| 1145 | #endif | |
| 1146 | ||
| e63637ea | 1147 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
| 69b3331e PC |
1148 | inline void |
| 1149 | swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
| 1150 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
| c5d9ec56 | 1151 | noexcept(noexcept(__x.swap(__y))) |
| 69b3331e | 1152 | { __x.swap(__y); } |
| e63637ea | 1153 | |
| 5dc22714 PC |
1154 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
| 1155 | inline bool | |
| 1156 | operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
| 1157 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
| 637fd8b3 | 1158 | { return __x._M_base() == __y._M_base(); } |
| 5dc22714 PC |
1159 | |
| 1160 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
| 1161 | inline bool | |
| 1162 | operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
| 1163 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
| 1164 | { return !(__x == __y); } | |
| 1165 | ||
| e63637ea BK |
1166 | } // namespace __debug |
| 1167 | } // namespace std | |
| 1168 | ||
| 734f5023 | 1169 | #endif // C++11 |
| c878d6ba | 1170 | |
| e63637ea | 1171 | #endif |