1 // RB tree implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2014 Free Software Foundation, Inc. 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 8 // Free Software Foundation; either version 3, or (at your option) 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 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/>. 24 25 /* 26 * 27 * Copyright (c) 1996,1997 28 * Silicon Graphics Computer Systems, Inc. 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Silicon Graphics makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1994 40 * Hewlett-Packard Company 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Hewlett-Packard Company makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 * 50 * 51 */ 52 53 /** @file bits/stl_tree.h 54 * This is an internal header file, included by other library headers. 55 * Do not attempt to use it directly. @headername{map,set} 56 */ 57 58 #ifndef _STL_TREE_H 59 #define _STL_TREE_H 1 60 61 #include <bits/stl_algobase.h> 62 #include <bits/allocator.h> 63 #include <bits/stl_function.h> 64 #include <bits/cpp_type_traits.h> 65 #include <ext/alloc_traits.h> 66 #if __cplusplus >= 201103L 67 #include <ext/aligned_buffer.h> 68 #endif 69 70 namespace std _GLIBCXX_VISIBILITY(default) 71 { 72 _GLIBCXX_BEGIN_NAMESPACE_VERSION 73 74 // Red-black tree class, designed for use in implementing STL 75 // associative containers (set, multiset, map, and multimap). The 76 // insertion and deletion algorithms are based on those in Cormen, 77 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 78 // 1990), except that 79 // 80 // (1) the header cell is maintained with links not only to the root 81 // but also to the leftmost node of the tree, to enable constant 82 // time begin(), and to the rightmost node of the tree, to enable 83 // linear time performance when used with the generic set algorithms 84 // (set_union, etc.) 85 // 86 // (2) when a node being deleted has two children its successor node 87 // is relinked into its place, rather than copied, so that the only 88 // iterators invalidated are those referring to the deleted node. 89 90 enum _Rb_tree_color { _S_red = false, _S_black = true }; 91 92 struct _Rb_tree_node_base 93 { 94 typedef _Rb_tree_node_base* _Base_ptr; 95 typedef const _Rb_tree_node_base* _Const_Base_ptr; 96 97 _Rb_tree_color _M_color; 98 _Base_ptr _M_parent; 99 _Base_ptr _M_left; 100 _Base_ptr _M_right; 101 102 static _Base_ptr 103 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 104 { 105 while (__x->_M_left != 0) __x = __x->_M_left; 106 return __x; 107 } 108 109 static _Const_Base_ptr 110 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 111 { 112 while (__x->_M_left != 0) __x = __x->_M_left; 113 return __x; 114 } 115 116 static _Base_ptr 117 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 118 { 119 while (__x->_M_right != 0) __x = __x->_M_right; 120 return __x; 121 } 122 123 static _Const_Base_ptr 124 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 125 { 126 while (__x->_M_right != 0) __x = __x->_M_right; 127 return __x; 128 } 129 }; 130 131 template<typename _Val> 132 struct _Rb_tree_node : public _Rb_tree_node_base 133 { 134 typedef _Rb_tree_node<_Val>* _Link_type; 135 136 #if __cplusplus < 201103L 137 _Val _M_value_field; 138 139 _Val* 140 _M_valptr() 141 { return std::__addressof(_M_value_field); } 142 143 const _Val* 144 _M_valptr() const 145 { return std::__addressof(_M_value_field); } 146 #else 147 __gnu_cxx::__aligned_buffer<_Val> _M_storage; 148 149 _Val* 150 _M_valptr() 151 { return _M_storage._M_ptr(); } 152 153 const _Val* 154 _M_valptr() const 155 { return _M_storage._M_ptr(); } 156 #endif 157 }; 158 159 _GLIBCXX_PURE _Rb_tree_node_base* 160 _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); 161 162 _GLIBCXX_PURE const _Rb_tree_node_base* 163 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw (); 164 165 _GLIBCXX_PURE _Rb_tree_node_base* 166 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw (); 167 168 _GLIBCXX_PURE const _Rb_tree_node_base* 169 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw (); 170 171 template<typename _Tp> 172 struct _Rb_tree_iterator 173 { 174 typedef _Tp value_type; 175 typedef _Tp& reference; 176 typedef _Tp* pointer; 177 178 typedef bidirectional_iterator_tag iterator_category; 179 typedef ptrdiff_t difference_type; 180 181 typedef _Rb_tree_iterator<_Tp> _Self; 182 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 183 typedef _Rb_tree_node<_Tp>* _Link_type; 184 185 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT 186 : _M_node() { } 187 188 explicit 189 _Rb_tree_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT 190 : _M_node(__x) { } 191 192 reference 193 operator*() const _GLIBCXX_NOEXCEPT 194 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 195 196 pointer 197 operator->() const _GLIBCXX_NOEXCEPT 198 { return static_cast<_Link_type> (_M_node)->_M_valptr(); } 199 200 _Self& 201 operator++() _GLIBCXX_NOEXCEPT 202 { 203 _M_node = _Rb_tree_increment(_M_node); 204 return *this; 205 } 206 207 _Self 208 operator++(int) _GLIBCXX_NOEXCEPT 209 { 210 _Self __tmp = *this; 211 _M_node = _Rb_tree_increment(_M_node); 212 return __tmp; 213 } 214 215 _Self& 216 operator--() _GLIBCXX_NOEXCEPT 217 { 218 _M_node = _Rb_tree_decrement(_M_node); 219 return *this; 220 } 221 222 _Self 223 operator--(int) _GLIBCXX_NOEXCEPT 224 { 225 _Self __tmp = *this; 226 _M_node = _Rb_tree_decrement(_M_node); 227 return __tmp; 228 } 229 230 bool 231 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 232 { return _M_node == __x._M_node; } 233 234 bool 235 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 236 { return _M_node != __x._M_node; } 237 238 _Base_ptr _M_node; 239 }; 240 241 template<typename _Tp> 242 struct _Rb_tree_const_iterator 243 { 244 typedef _Tp value_type; 245 typedef const _Tp& reference; 246 typedef const _Tp* pointer; 247 248 typedef _Rb_tree_iterator<_Tp> iterator; 249 250 typedef bidirectional_iterator_tag iterator_category; 251 typedef ptrdiff_t difference_type; 252 253 typedef _Rb_tree_const_iterator<_Tp> _Self; 254 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 255 typedef const _Rb_tree_node<_Tp>* _Link_type; 256 257 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT 258 : _M_node() { } 259 260 explicit 261 _Rb_tree_const_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT 262 : _M_node(__x) { } 263 264 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT 265 : _M_node(__it._M_node) { } 266 267 iterator 268 _M_const_cast() const _GLIBCXX_NOEXCEPT 269 { return iterator(static_cast<typename iterator::_Link_type> 270 (const_cast<typename iterator::_Base_ptr>(_M_node))); } 271 272 reference 273 operator*() const _GLIBCXX_NOEXCEPT 274 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 275 276 pointer 277 operator->() const _GLIBCXX_NOEXCEPT 278 { return static_cast<_Link_type>(_M_node)->_M_valptr(); } 279 280 _Self& 281 operator++() _GLIBCXX_NOEXCEPT 282 { 283 _M_node = _Rb_tree_increment(_M_node); 284 return *this; 285 } 286 287 _Self 288 operator++(int) _GLIBCXX_NOEXCEPT 289 { 290 _Self __tmp = *this; 291 _M_node = _Rb_tree_increment(_M_node); 292 return __tmp; 293 } 294 295 _Self& 296 operator--() _GLIBCXX_NOEXCEPT 297 { 298 _M_node = _Rb_tree_decrement(_M_node); 299 return *this; 300 } 301 302 _Self 303 operator--(int) _GLIBCXX_NOEXCEPT 304 { 305 _Self __tmp = *this; 306 _M_node = _Rb_tree_decrement(_M_node); 307 return __tmp; 308 } 309 310 bool 311 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 312 { return _M_node == __x._M_node; } 313 314 bool 315 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 316 { return _M_node != __x._M_node; } 317 318 _Base_ptr _M_node; 319 }; 320 321 template<typename _Val> 322 inline bool 323 operator==(const _Rb_tree_iterator<_Val>& __x, 324 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 325 { return __x._M_node == __y._M_node; } 326 327 template<typename _Val> 328 inline bool 329 operator!=(const _Rb_tree_iterator<_Val>& __x, 330 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 331 { return __x._M_node != __y._M_node; } 332 333 void 334 _Rb_tree_insert_and_rebalance(const bool __insert_left, 335 _Rb_tree_node_base* __x, 336 _Rb_tree_node_base* __p, 337 _Rb_tree_node_base& __header) throw (); 338 339 _Rb_tree_node_base* 340 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 341 _Rb_tree_node_base& __header) throw (); 342 343 344 template<typename _Key, typename _Val, typename _KeyOfValue, 345 typename _Compare, typename _Alloc = allocator<_Val> > 346 class _Rb_tree 347 { 348 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 349 rebind<_Rb_tree_node<_Val> >::other _Node_allocator; 350 351 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits; 352 353 protected: 354 typedef _Rb_tree_node_base* _Base_ptr; 355 typedef const _Rb_tree_node_base* _Const_Base_ptr; 356 357 public: 358 typedef _Key key_type; 359 typedef _Val value_type; 360 typedef value_type* pointer; 361 typedef const value_type* const_pointer; 362 typedef value_type& reference; 363 typedef const value_type& const_reference; 364 typedef _Rb_tree_node<_Val>* _Link_type; 365 typedef const _Rb_tree_node<_Val>* _Const_Link_type; 366 typedef size_t size_type; 367 typedef ptrdiff_t difference_type; 368 typedef _Alloc allocator_type; 369 370 _Node_allocator& 371 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT 372 { return *static_cast<_Node_allocator*>(&this->_M_impl); } 373 374 const _Node_allocator& 375 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT 376 { return *static_cast<const _Node_allocator*>(&this->_M_impl); } 377 378 allocator_type 379 get_allocator() const _GLIBCXX_NOEXCEPT 380 { return allocator_type(_M_get_Node_allocator()); } 381 382 protected: 383 _Link_type 384 _M_get_node() 385 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); } 386 387 void 388 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT 389 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); } 390 391 #if __cplusplus < 201103L 392 _Link_type 393 _M_create_node(const value_type& __x) 394 { 395 _Link_type __tmp = _M_get_node(); 396 __try 397 { get_allocator().construct(__tmp->_M_valptr(), __x); } 398 __catch(...) 399 { 400 _M_put_node(__tmp); 401 __throw_exception_again; 402 } 403 return __tmp; 404 } 405 406 void 407 _M_destroy_node(_Link_type __p) 408 { 409 get_allocator().destroy(__p->_M_valptr()); 410 _M_put_node(__p); 411 } 412 #else 413 template<typename... _Args> 414 _Link_type 415 _M_create_node(_Args&&... __args) 416 { 417 _Link_type __tmp = _M_get_node(); 418 __try 419 { 420 ::new(__tmp) _Rb_tree_node<_Val>; 421 _Alloc_traits::construct(_M_get_Node_allocator(), 422 __tmp->_M_valptr(), 423 std::forward<_Args>(__args)...); 424 } 425 __catch(...) 426 { 427 _M_put_node(__tmp); 428 __throw_exception_again; 429 } 430 return __tmp; 431 } 432 433 void 434 _M_destroy_node(_Link_type __p) noexcept 435 { 436 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr()); 437 __p->~_Rb_tree_node<_Val>(); 438 _M_put_node(__p); 439 } 440 #endif 441 442 _Link_type 443 _M_clone_node(_Const_Link_type __x) 444 { 445 _Link_type __tmp = _M_create_node(*__x->_M_valptr()); 446 __tmp->_M_color = __x->_M_color; 447 __tmp->_M_left = 0; 448 __tmp->_M_right = 0; 449 return __tmp; 450 } 451 452 protected: 453 template<typename _Key_compare, 454 bool _Is_pod_comparator = __is_pod(_Key_compare)> 455 struct _Rb_tree_impl : public _Node_allocator 456 { 457 _Key_compare _M_key_compare; 458 _Rb_tree_node_base _M_header; 459 size_type _M_node_count; // Keeps track of size of tree. 460 461 _Rb_tree_impl() 462 : _Node_allocator(), _M_key_compare(), _M_header(), 463 _M_node_count(0) 464 { _M_initialize(); } 465 466 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 467 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), 468 _M_node_count(0) 469 { _M_initialize(); } 470 471 #if __cplusplus >= 201103L 472 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) 473 : _Node_allocator(std::move(__a)), _M_key_compare(__comp), 474 _M_header(), _M_node_count(0) 475 { _M_initialize(); } 476 #endif 477 478 private: 479 void 480 _M_initialize() 481 { 482 this->_M_header._M_color = _S_red; 483 this->_M_header._M_parent = 0; 484 this->_M_header._M_left = &this->_M_header; 485 this->_M_header._M_right = &this->_M_header; 486 } 487 }; 488 489 // Local modification: if __google_stl_debug_rbtree is defined to 490 // non-zero value, check sort predicate for strict weak ordering. 491 // Google ref b/1731200. 492 #if __google_stl_debug_rbtree 493 template<typename _KeyCompare> 494 struct _CheckedCompare { 495 _KeyCompare _M_key_compare; 496 497 _CheckedCompare(): _M_key_compare() { } 498 _CheckedCompare(const _KeyCompare & __comp): _M_key_compare(__comp) { } 499 500 // Template arg required to avoid duplicating code in the two op() 501 // operators below. User-provided _M_key_compare may not be const, 502 // but needs to be callable from our const op(). 503 // Google ref. b/1731200. 504 template <typename _KeyCompareT> 505 static bool _M_compare_with(_KeyCompareT& __comp, const _Key& __x, const _Key& __y) { 506 if (__comp(__x, __x)) 507 __throw_runtime_error("strict weak ordering: (__x LT __x) != false"); 508 if (__comp(__y, __y)) 509 __throw_runtime_error("strict weak ordering: (__y LT __y) != false"); 510 bool lt = __comp(__x, __y); 511 if (lt && __comp(__y, __x)) 512 __throw_runtime_error("strict weak ordering: ((__x LT __y) && (__y LT __x)) != false"); 513 return lt; 514 } 515 bool operator()(const _Key& __x, const _Key& __y) const { 516 return _M_compare_with(_M_key_compare, __x, __y); 517 } 518 519 bool operator()(const _Key& __x, const _Key& __y) { 520 return _M_compare_with(_M_key_compare, __x, __y); 521 } 522 523 operator _KeyCompare() const { return _M_key_compare; } 524 }; 525 526 _Rb_tree_impl<_CheckedCompare<_Compare> > _M_impl; 527 #else 528 _Rb_tree_impl<_Compare> _M_impl; 529 #endif 530 531 protected: 532 _Base_ptr& 533 _M_root() _GLIBCXX_NOEXCEPT 534 { return this->_M_impl._M_header._M_parent; } 535 536 _Const_Base_ptr 537 _M_root() const _GLIBCXX_NOEXCEPT 538 { return this->_M_impl._M_header._M_parent; } 539 540 _Base_ptr& 541 _M_leftmost() _GLIBCXX_NOEXCEPT 542 { return this->_M_impl._M_header._M_left; } 543 544 _Const_Base_ptr 545 _M_leftmost() const _GLIBCXX_NOEXCEPT 546 { return this->_M_impl._M_header._M_left; } 547 548 _Base_ptr& 549 _M_rightmost() _GLIBCXX_NOEXCEPT 550 { return this->_M_impl._M_header._M_right; } 551 552 _Const_Base_ptr 553 _M_rightmost() const _GLIBCXX_NOEXCEPT 554 { return this->_M_impl._M_header._M_right; } 555 556 _Link_type 557 _M_begin() _GLIBCXX_NOEXCEPT 558 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 559 560 _Const_Link_type 561 _M_begin() const _GLIBCXX_NOEXCEPT 562 { 563 return static_cast<_Const_Link_type> 564 (this->_M_impl._M_header._M_parent); 565 } 566 567 _Link_type 568 _M_end() _GLIBCXX_NOEXCEPT 569 { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); } 570 571 _Const_Link_type 572 _M_end() const _GLIBCXX_NOEXCEPT 573 { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); } 574 575 static const_reference 576 _S_value(_Const_Link_type __x) 577 { return *__x->_M_valptr(); } 578 579 static const _Key& 580 _S_key(_Const_Link_type __x) 581 { return _KeyOfValue()(_S_value(__x)); } 582 583 static _Link_type 584 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT 585 { return static_cast<_Link_type>(__x->_M_left); } 586 587 static _Const_Link_type 588 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 589 { return static_cast<_Const_Link_type>(__x->_M_left); } 590 591 static _Link_type 592 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT 593 { return static_cast<_Link_type>(__x->_M_right); } 594 595 static _Const_Link_type 596 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 597 { return static_cast<_Const_Link_type>(__x->_M_right); } 598 599 static const_reference 600 _S_value(_Const_Base_ptr __x) 601 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); } 602 603 static const _Key& 604 _S_key(_Const_Base_ptr __x) 605 { return _KeyOfValue()(_S_value(__x)); } 606 607 static _Base_ptr 608 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 609 { return _Rb_tree_node_base::_S_minimum(__x); } 610 611 static _Const_Base_ptr 612 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 613 { return _Rb_tree_node_base::_S_minimum(__x); } 614 615 static _Base_ptr 616 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 617 { return _Rb_tree_node_base::_S_maximum(__x); } 618 619 static _Const_Base_ptr 620 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 621 { return _Rb_tree_node_base::_S_maximum(__x); } 622 623 public: 624 typedef _Rb_tree_iterator<value_type> iterator; 625 typedef _Rb_tree_const_iterator<value_type> const_iterator; 626 627 typedef std::reverse_iterator<iterator> reverse_iterator; 628 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 629 630 private: 631 pair<_Base_ptr, _Base_ptr> 632 _M_get_insert_unique_pos(const key_type& __k); 633 634 pair<_Base_ptr, _Base_ptr> 635 _M_get_insert_equal_pos(const key_type& __k); 636 637 pair<_Base_ptr, _Base_ptr> 638 _M_get_insert_hint_unique_pos(const_iterator __pos, 639 const key_type& __k); 640 641 pair<_Base_ptr, _Base_ptr> 642 _M_get_insert_hint_equal_pos(const_iterator __pos, 643 const key_type& __k); 644 645 #if __cplusplus >= 201103L 646 template<typename _Arg> 647 iterator 648 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v); 649 650 iterator 651 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); 652 653 template<typename _Arg> 654 iterator 655 _M_insert_lower(_Base_ptr __y, _Arg&& __v); 656 657 template<typename _Arg> 658 iterator 659 _M_insert_equal_lower(_Arg&& __x); 660 661 iterator 662 _M_insert_lower_node(_Base_ptr __p, _Link_type __z); 663 664 iterator 665 _M_insert_equal_lower_node(_Link_type __z); 666 #else 667 iterator 668 _M_insert_(_Base_ptr __x, _Base_ptr __y, 669 const value_type& __v); 670 671 // _GLIBCXX_RESOLVE_LIB_DEFECTS 672 // 233. Insertion hints in associative containers. 673 iterator 674 _M_insert_lower(_Base_ptr __y, const value_type& __v); 675 676 iterator 677 _M_insert_equal_lower(const value_type& __x); 678 #endif 679 680 _Link_type 681 _M_copy(_Const_Link_type __x, _Link_type __p); 682 683 void 684 _M_erase(_Link_type __x); 685 686 iterator 687 _M_lower_bound(_Link_type __x, _Link_type __y, 688 const _Key& __k); 689 690 const_iterator 691 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 692 const _Key& __k) const; 693 694 iterator 695 _M_upper_bound(_Link_type __x, _Link_type __y, 696 const _Key& __k); 697 698 const_iterator 699 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 700 const _Key& __k) const; 701 702 public: 703 // allocation/deallocation 704 _Rb_tree() { } 705 706 _Rb_tree(const _Compare& __comp, 707 const allocator_type& __a = allocator_type()) 708 : _M_impl(__comp, _Node_allocator(__a)) { } 709 710 _Rb_tree(const _Rb_tree& __x) 711 : _M_impl(__x._M_impl._M_key_compare, 712 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator())) 713 { 714 if (__x._M_root() != 0) 715 { 716 _M_root() = _M_copy(__x._M_begin(), _M_end()); 717 _M_leftmost() = _S_minimum(_M_root()); 718 _M_rightmost() = _S_maximum(_M_root()); 719 _M_impl._M_node_count = __x._M_impl._M_node_count; 720 } 721 } 722 723 #if __cplusplus >= 201103L 724 _Rb_tree(const allocator_type& __a) 725 : _M_impl(_Compare(), _Node_allocator(__a)) 726 { } 727 728 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a) 729 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) 730 { 731 if (__x._M_root() != 0) 732 { 733 _M_root() = _M_copy(__x._M_begin(), _M_end()); 734 _M_leftmost() = _S_minimum(_M_root()); 735 _M_rightmost() = _S_maximum(_M_root()); 736 _M_impl._M_node_count = __x._M_impl._M_node_count; 737 } 738 } 739 740 _Rb_tree(_Rb_tree&& __x) 741 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) 742 { 743 if (__x._M_root() != 0) 744 _M_move_data(__x, std::true_type()); 745 } 746 747 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a) 748 : _Rb_tree(std::move(__x), _Node_allocator(__a)) 749 { } 750 751 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a); 752 #endif 753 754 ~_Rb_tree() _GLIBCXX_NOEXCEPT 755 { _M_erase(_M_begin()); } 756 757 _Rb_tree& 758 operator=(const _Rb_tree& __x); 759 760 // Accessors. 761 _Compare 762 key_comp() const 763 { return _M_impl._M_key_compare; } 764 765 iterator 766 begin() _GLIBCXX_NOEXCEPT 767 { 768 return iterator(static_cast<_Link_type> 769 (this->_M_impl._M_header._M_left)); 770 } 771 772 const_iterator 773 begin() const _GLIBCXX_NOEXCEPT 774 { 775 return const_iterator(static_cast<_Const_Link_type> 776 (this->_M_impl._M_header._M_left)); 777 } 778 779 iterator 780 end() _GLIBCXX_NOEXCEPT 781 { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); } 782 783 const_iterator 784 end() const _GLIBCXX_NOEXCEPT 785 { 786 return const_iterator(static_cast<_Const_Link_type> 787 (&this->_M_impl._M_header)); 788 } 789 790 reverse_iterator 791 rbegin() _GLIBCXX_NOEXCEPT 792 { return reverse_iterator(end()); } 793 794 const_reverse_iterator 795 rbegin() const _GLIBCXX_NOEXCEPT 796 { return const_reverse_iterator(end()); } 797 798 reverse_iterator 799 rend() _GLIBCXX_NOEXCEPT 800 { return reverse_iterator(begin()); } 801 802 const_reverse_iterator 803 rend() const _GLIBCXX_NOEXCEPT 804 { return const_reverse_iterator(begin()); } 805 806 bool 807 empty() const _GLIBCXX_NOEXCEPT 808 { return _M_impl._M_node_count == 0; } 809 810 size_type 811 size() const _GLIBCXX_NOEXCEPT 812 { return _M_impl._M_node_count; } 813 814 size_type 815 max_size() const _GLIBCXX_NOEXCEPT 816 { return _Alloc_traits::max_size(_M_get_Node_allocator()); } 817 818 void 819 #if __cplusplus >= 201103L 820 swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap()); 821 #else 822 swap(_Rb_tree& __t); 823 #endif 824 825 // Insert/erase. 826 #if __cplusplus >= 201103L 827 template<typename _Arg> 828 pair<iterator, bool> 829 _M_insert_unique(_Arg&& __x); 830 831 template<typename _Arg> 832 iterator 833 _M_insert_equal(_Arg&& __x); 834 835 template<typename _Arg> 836 iterator 837 _M_insert_unique_(const_iterator __position, _Arg&& __x); 838 839 template<typename _Arg> 840 iterator 841 _M_insert_equal_(const_iterator __position, _Arg&& __x); 842 843 template<typename... _Args> 844 pair<iterator, bool> 845 _M_emplace_unique(_Args&&... __args); 846 847 template<typename... _Args> 848 iterator 849 _M_emplace_equal(_Args&&... __args); 850 851 template<typename... _Args> 852 iterator 853 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); 854 855 template<typename... _Args> 856 iterator 857 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); 858 #else 859 pair<iterator, bool> 860 _M_insert_unique(const value_type& __x); 861 862 iterator 863 _M_insert_equal(const value_type& __x); 864 865 iterator 866 _M_insert_unique_(const_iterator __position, const value_type& __x); 867 868 iterator 869 _M_insert_equal_(const_iterator __position, const value_type& __x); 870 #endif 871 872 template<typename _InputIterator> 873 void 874 _M_insert_unique(_InputIterator __first, _InputIterator __last); 875 876 template<typename _InputIterator> 877 void 878 _M_insert_equal(_InputIterator __first, _InputIterator __last); 879 880 private: 881 void 882 _M_erase_aux(const_iterator __position); 883 884 void 885 _M_erase_aux(const_iterator __first, const_iterator __last); 886 887 public: 888 #if __cplusplus >= 201103L 889 // _GLIBCXX_RESOLVE_LIB_DEFECTS 890 // DR 130. Associative erase should return an iterator. 891 _GLIBCXX_ABI_TAG_CXX11 892 iterator 893 erase(const_iterator __position) 894 { 895 const_iterator __result = __position; 896 ++__result; 897 _M_erase_aux(__position); 898 return __result._M_const_cast(); 899 } 900 901 // LWG 2059. 902 _GLIBCXX_ABI_TAG_CXX11 903 iterator 904 erase(iterator __position) 905 { 906 iterator __result = __position; 907 ++__result; 908 _M_erase_aux(__position); 909 return __result; 910 } 911 #else 912 void 913 erase(iterator __position) 914 { _M_erase_aux(__position); } 915 916 void 917 erase(const_iterator __position) 918 { _M_erase_aux(__position); } 919 #endif 920 size_type 921 erase(const key_type& __x); 922 923 #if __cplusplus >= 201103L 924 // _GLIBCXX_RESOLVE_LIB_DEFECTS 925 // DR 130. Associative erase should return an iterator. 926 _GLIBCXX_ABI_TAG_CXX11 927 iterator 928 erase(const_iterator __first, const_iterator __last) 929 { 930 _M_erase_aux(__first, __last); 931 return __last._M_const_cast(); 932 } 933 #else 934 void 935 erase(iterator __first, iterator __last) 936 { _M_erase_aux(__first, __last); } 937 938 void 939 erase(const_iterator __first, const_iterator __last) 940 { _M_erase_aux(__first, __last); } 941 #endif 942 void 943 erase(const key_type* __first, const key_type* __last); 944 945 void 946 clear() _GLIBCXX_NOEXCEPT 947 { 948 _M_erase(_M_begin()); 949 _M_leftmost() = _M_end(); 950 _M_root() = 0; 951 _M_rightmost() = _M_end(); 952 _M_impl._M_node_count = 0; 953 } 954 955 // Set operations. 956 iterator 957 find(const key_type& __k); 958 959 const_iterator 960 find(const key_type& __k) const; 961 962 size_type 963 count(const key_type& __k) const; 964 965 iterator 966 lower_bound(const key_type& __k) 967 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 968 969 const_iterator 970 lower_bound(const key_type& __k) const 971 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 972 973 iterator 974 upper_bound(const key_type& __k) 975 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 976 977 const_iterator 978 upper_bound(const key_type& __k) const 979 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 980 981 pair<iterator, iterator> 982 equal_range(const key_type& __k); 983 984 pair<const_iterator, const_iterator> 985 equal_range(const key_type& __k) const; 986 987 // Debugging. 988 bool 989 __rb_verify() const; 990 991 #if __cplusplus >= 201103L 992 bool 993 _M_move_assign(_Rb_tree&); 994 995 private: 996 // Move elements from container with equal allocator. 997 void 998 _M_move_data(_Rb_tree&, std::true_type); 999 1000 // Move elements from container with possibly non-equal allocator, 1001 // which might result in a copy not a move. 1002 void 1003 _M_move_data(_Rb_tree&, std::false_type); 1004 #endif 1005 }; 1006 1007 template<typename _Key, typename _Val, typename _KeyOfValue, 1008 typename _Compare, typename _Alloc> 1009 inline bool 1010 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1011 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1012 { 1013 return __x.size() == __y.size() 1014 && std::equal(__x.begin(), __x.end(), __y.begin()); 1015 } 1016 1017 template<typename _Key, typename _Val, typename _KeyOfValue, 1018 typename _Compare, typename _Alloc> 1019 inline bool 1020 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1021 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1022 { 1023 return std::lexicographical_compare(__x.begin(), __x.end(), 1024 __y.begin(), __y.end()); 1025 } 1026 1027 template<typename _Key, typename _Val, typename _KeyOfValue, 1028 typename _Compare, typename _Alloc> 1029 inline bool 1030 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1031 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1032 { return !(__x == __y); } 1033 1034 template<typename _Key, typename _Val, typename _KeyOfValue, 1035 typename _Compare, typename _Alloc> 1036 inline bool 1037 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1038 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1039 { return __y < __x; } 1040 1041 template<typename _Key, typename _Val, typename _KeyOfValue, 1042 typename _Compare, typename _Alloc> 1043 inline bool 1044 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1045 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1046 { return !(__y < __x); } 1047 1048 template<typename _Key, typename _Val, typename _KeyOfValue, 1049 typename _Compare, typename _Alloc> 1050 inline bool 1051 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1052 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1053 { return !(__x < __y); } 1054 1055 template<typename _Key, typename _Val, typename _KeyOfValue, 1056 typename _Compare, typename _Alloc> 1057 inline void 1058 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1059 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1060 { __x.swap(__y); } 1061 1062 #if __cplusplus >= 201103L 1063 template<typename _Key, typename _Val, typename _KeyOfValue, 1064 typename _Compare, typename _Alloc> 1065 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1066 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) 1067 : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) 1068 { 1069 using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>; 1070 if (__x._M_root() != 0) 1071 _M_move_data(__x, __eq()); 1072 } 1073 1074 template<typename _Key, typename _Val, typename _KeyOfValue, 1075 typename _Compare, typename _Alloc> 1076 void 1077 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1078 _M_move_data(_Rb_tree& __x, std::true_type) 1079 { 1080 _M_root() = __x._M_root(); 1081 _M_leftmost() = __x._M_leftmost(); 1082 _M_rightmost() = __x._M_rightmost(); 1083 _M_root()->_M_parent = _M_end(); 1084 1085 __x._M_root() = 0; 1086 __x._M_leftmost() = __x._M_end(); 1087 __x._M_rightmost() = __x._M_end(); 1088 1089 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 1090 __x._M_impl._M_node_count = 0; 1091 } 1092 1093 template<typename _Key, typename _Val, typename _KeyOfValue, 1094 typename _Compare, typename _Alloc> 1095 void 1096 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1097 _M_move_data(_Rb_tree& __x, std::false_type) 1098 { 1099 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 1100 _M_move_data(__x, std::true_type()); 1101 else 1102 { 1103 _M_root() = _M_copy(__x._M_begin(), _M_end()); 1104 _M_leftmost() = _S_minimum(_M_root()); 1105 _M_rightmost() = _S_maximum(_M_root()); 1106 _M_impl._M_node_count = __x._M_impl._M_node_count; 1107 } 1108 } 1109 1110 template<typename _Key, typename _Val, typename _KeyOfValue, 1111 typename _Compare, typename _Alloc> 1112 bool 1113 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1114 _M_move_assign(_Rb_tree& __x) 1115 { 1116 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 1117 if (_Alloc_traits::_S_propagate_on_move_assign() 1118 || _Alloc_traits::_S_always_equal() 1119 || _M_get_Node_allocator() == __x._M_get_Node_allocator()) 1120 { 1121 clear(); 1122 if (__x._M_root() != 0) 1123 _M_move_data(__x, std::true_type()); 1124 std::__alloc_on_move(_M_get_Node_allocator(), 1125 __x._M_get_Node_allocator()); 1126 return true; 1127 } 1128 return false; 1129 } 1130 #endif 1131 1132 template<typename _Key, typename _Val, typename _KeyOfValue, 1133 typename _Compare, typename _Alloc> 1134 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 1135 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1136 operator=(const _Rb_tree& __x) 1137 { 1138 if (this != &__x) 1139 { 1140 // Note that _Key may be a constant type. 1141 clear(); 1142 #if __cplusplus >= 201103L 1143 if (_Alloc_traits::_S_propagate_on_copy_assign()) 1144 { 1145 auto& __this_alloc = this->_M_get_Node_allocator(); 1146 auto& __that_alloc = __x._M_get_Node_allocator(); 1147 if (!_Alloc_traits::_S_always_equal() 1148 && __this_alloc != __that_alloc) 1149 { 1150 std::__alloc_on_copy(__this_alloc, __that_alloc); 1151 } 1152 } 1153 #endif 1154 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 1155 if (__x._M_root() != 0) 1156 { 1157 _M_root() = _M_copy(__x._M_begin(), _M_end()); 1158 _M_leftmost() = _S_minimum(_M_root()); 1159 _M_rightmost() = _S_maximum(_M_root()); 1160 _M_impl._M_node_count = __x._M_impl._M_node_count; 1161 } 1162 } 1163 return *this; 1164 } 1165 1166 template<typename _Key, typename _Val, typename _KeyOfValue, 1167 typename _Compare, typename _Alloc> 1168 #if __cplusplus >= 201103L 1169 template<typename _Arg> 1170 #endif 1171 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1172 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1173 #if __cplusplus >= 201103L 1174 _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) 1175 #else 1176 _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 1177 #endif 1178 { 1179 bool __insert_left = (__x != 0 || __p == _M_end() 1180 || _M_impl._M_key_compare(_KeyOfValue()(__v), 1181 _S_key(__p))); 1182 1183 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 1184 1185 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1186 this->_M_impl._M_header); 1187 ++_M_impl._M_node_count; 1188 return iterator(__z); 1189 } 1190 1191 template<typename _Key, typename _Val, typename _KeyOfValue, 1192 typename _Compare, typename _Alloc> 1193 #if __cplusplus >= 201103L 1194 template<typename _Arg> 1195 #endif 1196 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1197 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1198 #if __cplusplus >= 201103L 1199 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 1200 #else 1201 _M_insert_lower(_Base_ptr __p, const _Val& __v) 1202 #endif 1203 { 1204 bool __insert_left = (__p == _M_end() 1205 || !_M_impl._M_key_compare(_S_key(__p), 1206 _KeyOfValue()(__v))); 1207 1208 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 1209 1210 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1211 this->_M_impl._M_header); 1212 ++_M_impl._M_node_count; 1213 return iterator(__z); 1214 } 1215 1216 template<typename _Key, typename _Val, typename _KeyOfValue, 1217 typename _Compare, typename _Alloc> 1218 #if __cplusplus >= 201103L 1219 template<typename _Arg> 1220 #endif 1221 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1222 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1223 #if __cplusplus >= 201103L 1224 _M_insert_equal_lower(_Arg&& __v) 1225 #else 1226 _M_insert_equal_lower(const _Val& __v) 1227 #endif 1228 { 1229 _Link_type __x = _M_begin(); 1230 _Link_type __y = _M_end(); 1231 while (__x != 0) 1232 { 1233 __y = __x; 1234 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 1235 _S_left(__x) : _S_right(__x); 1236 } 1237 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 1238 } 1239 1240 template<typename _Key, typename _Val, typename _KoV, 1241 typename _Compare, typename _Alloc> 1242 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 1243 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 1244 _M_copy(_Const_Link_type __x, _Link_type __p) 1245 { 1246 // Structural copy. __x and __p must be non-null. 1247 _Link_type __top = _M_clone_node(__x); 1248 __top->_M_parent = __p; 1249 1250 __try 1251 { 1252 if (__x->_M_right) 1253 __top->_M_right = _M_copy(_S_right(__x), __top); 1254 __p = __top; 1255 __x = _S_left(__x); 1256 1257 while (__x != 0) 1258 { 1259 _Link_type __y = _M_clone_node(__x); 1260 __p->_M_left = __y; 1261 __y->_M_parent = __p; 1262 if (__x->_M_right) 1263 __y->_M_right = _M_copy(_S_right(__x), __y); 1264 __p = __y; 1265 __x = _S_left(__x); 1266 } 1267 } 1268 __catch(...) 1269 { 1270 _M_erase(__top); 1271 __throw_exception_again; 1272 } 1273 return __top; 1274 } 1275 1276 template<typename _Key, typename _Val, typename _KeyOfValue, 1277 typename _Compare, typename _Alloc> 1278 void 1279 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1280 _M_erase(_Link_type __x) 1281 { 1282 // Erase without rebalancing. 1283 while (__x != 0) 1284 { 1285 _M_erase(_S_right(__x)); 1286 _Link_type __y = _S_left(__x); 1287 _M_destroy_node(__x); 1288 __x = __y; 1289 } 1290 } 1291 1292 template<typename _Key, typename _Val, typename _KeyOfValue, 1293 typename _Compare, typename _Alloc> 1294 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1295 _Compare, _Alloc>::iterator 1296 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1297 _M_lower_bound(_Link_type __x, _Link_type __y, 1298 const _Key& __k) 1299 { 1300 while (__x != 0) 1301 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1302 __y = __x, __x = _S_left(__x); 1303 else 1304 __x = _S_right(__x); 1305 return iterator(__y); 1306 } 1307 1308 template<typename _Key, typename _Val, typename _KeyOfValue, 1309 typename _Compare, typename _Alloc> 1310 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1311 _Compare, _Alloc>::const_iterator 1312 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1313 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 1314 const _Key& __k) const 1315 { 1316 while (__x != 0) 1317 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1318 __y = __x, __x = _S_left(__x); 1319 else 1320 __x = _S_right(__x); 1321 return const_iterator(__y); 1322 } 1323 1324 template<typename _Key, typename _Val, typename _KeyOfValue, 1325 typename _Compare, typename _Alloc> 1326 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1327 _Compare, _Alloc>::iterator 1328 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1329 _M_upper_bound(_Link_type __x, _Link_type __y, 1330 const _Key& __k) 1331 { 1332 while (__x != 0) 1333 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1334 __y = __x, __x = _S_left(__x); 1335 else 1336 __x = _S_right(__x); 1337 return iterator(__y); 1338 } 1339 1340 template<typename _Key, typename _Val, typename _KeyOfValue, 1341 typename _Compare, typename _Alloc> 1342 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1343 _Compare, _Alloc>::const_iterator 1344 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1345 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 1346 const _Key& __k) const 1347 { 1348 while (__x != 0) 1349 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1350 __y = __x, __x = _S_left(__x); 1351 else 1352 __x = _S_right(__x); 1353 return const_iterator(__y); 1354 } 1355 1356 template<typename _Key, typename _Val, typename _KeyOfValue, 1357 typename _Compare, typename _Alloc> 1358 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1359 _Compare, _Alloc>::iterator, 1360 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1361 _Compare, _Alloc>::iterator> 1362 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1363 equal_range(const _Key& __k) 1364 { 1365 _Link_type __x = _M_begin(); 1366 _Link_type __y = _M_end(); 1367 while (__x != 0) 1368 { 1369 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1370 __x = _S_right(__x); 1371 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1372 __y = __x, __x = _S_left(__x); 1373 else 1374 { 1375 _Link_type __xu(__x), __yu(__y); 1376 __y = __x, __x = _S_left(__x); 1377 __xu = _S_right(__xu); 1378 return pair<iterator, 1379 iterator>(_M_lower_bound(__x, __y, __k), 1380 _M_upper_bound(__xu, __yu, __k)); 1381 } 1382 } 1383 return pair<iterator, iterator>(iterator(__y), 1384 iterator(__y)); 1385 } 1386 1387 template<typename _Key, typename _Val, typename _KeyOfValue, 1388 typename _Compare, typename _Alloc> 1389 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1390 _Compare, _Alloc>::const_iterator, 1391 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1392 _Compare, _Alloc>::const_iterator> 1393 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1394 equal_range(const _Key& __k) const 1395 { 1396 _Const_Link_type __x = _M_begin(); 1397 _Const_Link_type __y = _M_end(); 1398 while (__x != 0) 1399 { 1400 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1401 __x = _S_right(__x); 1402 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1403 __y = __x, __x = _S_left(__x); 1404 else 1405 { 1406 _Const_Link_type __xu(__x), __yu(__y); 1407 __y = __x, __x = _S_left(__x); 1408 __xu = _S_right(__xu); 1409 return pair<const_iterator, 1410 const_iterator>(_M_lower_bound(__x, __y, __k), 1411 _M_upper_bound(__xu, __yu, __k)); 1412 } 1413 } 1414 return pair<const_iterator, const_iterator>(const_iterator(__y), 1415 const_iterator(__y)); 1416 } 1417 1418 template<typename _Key, typename _Val, typename _KeyOfValue, 1419 typename _Compare, typename _Alloc> 1420 void 1421 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1422 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 1423 #if __cplusplus >= 201103L 1424 noexcept(_Alloc_traits::_S_nothrow_swap()) 1425 #endif 1426 { 1427 if (_M_root() == 0) 1428 { 1429 if (__t._M_root() != 0) 1430 { 1431 _M_root() = __t._M_root(); 1432 _M_leftmost() = __t._M_leftmost(); 1433 _M_rightmost() = __t._M_rightmost(); 1434 _M_root()->_M_parent = _M_end(); 1435 1436 __t._M_root() = 0; 1437 __t._M_leftmost() = __t._M_end(); 1438 __t._M_rightmost() = __t._M_end(); 1439 } 1440 } 1441 else if (__t._M_root() == 0) 1442 { 1443 __t._M_root() = _M_root(); 1444 __t._M_leftmost() = _M_leftmost(); 1445 __t._M_rightmost() = _M_rightmost(); 1446 __t._M_root()->_M_parent = __t._M_end(); 1447 1448 _M_root() = 0; 1449 _M_leftmost() = _M_end(); 1450 _M_rightmost() = _M_end(); 1451 } 1452 else 1453 { 1454 std::swap(_M_root(),__t._M_root()); 1455 std::swap(_M_leftmost(),__t._M_leftmost()); 1456 std::swap(_M_rightmost(),__t._M_rightmost()); 1457 1458 _M_root()->_M_parent = _M_end(); 1459 __t._M_root()->_M_parent = __t._M_end(); 1460 } 1461 // No need to swap header's color as it does not change. 1462 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 1463 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 1464 1465 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), 1466 __t._M_get_Node_allocator()); 1467 } 1468 1469 template<typename _Key, typename _Val, typename _KeyOfValue, 1470 typename _Compare, typename _Alloc> 1471 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1472 _Compare, _Alloc>::_Base_ptr, 1473 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1474 _Compare, _Alloc>::_Base_ptr> 1475 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1476 _M_get_insert_unique_pos(const key_type& __k) 1477 { 1478 typedef pair<_Base_ptr, _Base_ptr> _Res; 1479 _Link_type __x = _M_begin(); 1480 _Link_type __y = _M_end(); 1481 bool __comp = true; 1482 while (__x != 0) 1483 { 1484 __y = __x; 1485 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 1486 __x = __comp ? _S_left(__x) : _S_right(__x); 1487 } 1488 iterator __j = iterator(__y); 1489 if (__comp) 1490 { 1491 if (__j == begin()) 1492 return _Res(__x, __y); 1493 else 1494 --__j; 1495 } 1496 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 1497 return _Res(__x, __y); 1498 return _Res(__j._M_node, 0); 1499 } 1500 1501 template<typename _Key, typename _Val, typename _KeyOfValue, 1502 typename _Compare, typename _Alloc> 1503 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1504 _Compare, _Alloc>::_Base_ptr, 1505 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1506 _Compare, _Alloc>::_Base_ptr> 1507 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1508 _M_get_insert_equal_pos(const key_type& __k) 1509 { 1510 typedef pair<_Base_ptr, _Base_ptr> _Res; 1511 _Link_type __x = _M_begin(); 1512 _Link_type __y = _M_end(); 1513 while (__x != 0) 1514 { 1515 __y = __x; 1516 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 1517 _S_left(__x) : _S_right(__x); 1518 } 1519 return _Res(__x, __y); 1520 } 1521 1522 template<typename _Key, typename _Val, typename _KeyOfValue, 1523 typename _Compare, typename _Alloc> 1524 #if __cplusplus >= 201103L 1525 template<typename _Arg> 1526 #endif 1527 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1528 _Compare, _Alloc>::iterator, bool> 1529 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1530 #if __cplusplus >= 201103L 1531 _M_insert_unique(_Arg&& __v) 1532 #else 1533 _M_insert_unique(const _Val& __v) 1534 #endif 1535 { 1536 typedef pair<iterator, bool> _Res; 1537 pair<_Base_ptr, _Base_ptr> __res 1538 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 1539 1540 if (__res.second) 1541 return _Res(_M_insert_(__res.first, __res.second, 1542 _GLIBCXX_FORWARD(_Arg, __v)), 1543 true); 1544 1545 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 1546 } 1547 1548 template<typename _Key, typename _Val, typename _KeyOfValue, 1549 typename _Compare, typename _Alloc> 1550 #if __cplusplus >= 201103L 1551 template<typename _Arg> 1552 #endif 1553 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1554 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1555 #if __cplusplus >= 201103L 1556 _M_insert_equal(_Arg&& __v) 1557 #else 1558 _M_insert_equal(const _Val& __v) 1559 #endif 1560 { 1561 pair<_Base_ptr, _Base_ptr> __res 1562 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 1563 return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v)); 1564 } 1565 1566 template<typename _Key, typename _Val, typename _KeyOfValue, 1567 typename _Compare, typename _Alloc> 1568 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1569 _Compare, _Alloc>::_Base_ptr, 1570 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1571 _Compare, _Alloc>::_Base_ptr> 1572 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1573 _M_get_insert_hint_unique_pos(const_iterator __position, 1574 const key_type& __k) 1575 { 1576 iterator __pos = __position._M_const_cast(); 1577 typedef pair<_Base_ptr, _Base_ptr> _Res; 1578 1579 // end() 1580 if (__pos._M_node == _M_end()) 1581 { 1582 if (size() > 0 1583 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 1584 return _Res(0, _M_rightmost()); 1585 else 1586 return _M_get_insert_unique_pos(__k); 1587 } 1588 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 1589 { 1590 // First, try before... 1591 iterator __before = __pos; 1592 if (__pos._M_node == _M_leftmost()) // begin() 1593 return _Res(_M_leftmost(), _M_leftmost()); 1594 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 1595 { 1596 if (_S_right(__before._M_node) == 0) 1597 return _Res(0, __before._M_node); 1598 else 1599 return _Res(__pos._M_node, __pos._M_node); 1600 } 1601 else 1602 return _M_get_insert_unique_pos(__k); 1603 } 1604 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 1605 { 1606 // ... then try after. 1607 iterator __after = __pos; 1608 if (__pos._M_node == _M_rightmost()) 1609 return _Res(0, _M_rightmost()); 1610 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 1611 { 1612 if (_S_right(__pos._M_node) == 0) 1613 return _Res(0, __pos._M_node); 1614 else 1615 return _Res(__after._M_node, __after._M_node); 1616 } 1617 else 1618 return _M_get_insert_unique_pos(__k); 1619 } 1620 else 1621 // Equivalent keys. 1622 return _Res(__pos._M_node, 0); 1623 } 1624 1625 template<typename _Key, typename _Val, typename _KeyOfValue, 1626 typename _Compare, typename _Alloc> 1627 #if __cplusplus >= 201103L 1628 template<typename _Arg> 1629 #endif 1630 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1631 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1632 #if __cplusplus >= 201103L 1633 _M_insert_unique_(const_iterator __position, _Arg&& __v) 1634 #else 1635 _M_insert_unique_(const_iterator __position, const _Val& __v) 1636 #endif 1637 { 1638 pair<_Base_ptr, _Base_ptr> __res 1639 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 1640 1641 if (__res.second) 1642 return _M_insert_(__res.first, __res.second, 1643 _GLIBCXX_FORWARD(_Arg, __v)); 1644 return iterator(static_cast<_Link_type>(__res.first)); 1645 } 1646 1647 template<typename _Key, typename _Val, typename _KeyOfValue, 1648 typename _Compare, typename _Alloc> 1649 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1650 _Compare, _Alloc>::_Base_ptr, 1651 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1652 _Compare, _Alloc>::_Base_ptr> 1653 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1654 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 1655 { 1656 iterator __pos = __position._M_const_cast(); 1657 typedef pair<_Base_ptr, _Base_ptr> _Res; 1658 1659 // end() 1660 if (__pos._M_node == _M_end()) 1661 { 1662 if (size() > 0 1663 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 1664 return _Res(0, _M_rightmost()); 1665 else 1666 return _M_get_insert_equal_pos(__k); 1667 } 1668 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 1669 { 1670 // First, try before... 1671 iterator __before = __pos; 1672 if (__pos._M_node == _M_leftmost()) // begin() 1673 return _Res(_M_leftmost(), _M_leftmost()); 1674 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 1675 { 1676 if (_S_right(__before._M_node) == 0) 1677 return _Res(0, __before._M_node); 1678 else 1679 return _Res(__pos._M_node, __pos._M_node); 1680 } 1681 else 1682 return _M_get_insert_equal_pos(__k); 1683 } 1684 else 1685 { 1686 // ... then try after. 1687 iterator __after = __pos; 1688 if (__pos._M_node == _M_rightmost()) 1689 return _Res(0, _M_rightmost()); 1690 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 1691 { 1692 if (_S_right(__pos._M_node) == 0) 1693 return _Res(0, __pos._M_node); 1694 else 1695 return _Res(__after._M_node, __after._M_node); 1696 } 1697 else 1698 return _Res(0, 0); 1699 } 1700 } 1701 1702 template<typename _Key, typename _Val, typename _KeyOfValue, 1703 typename _Compare, typename _Alloc> 1704 #if __cplusplus >= 201103L 1705 template<typename _Arg> 1706 #endif 1707 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1708 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1709 #if __cplusplus >= 201103L 1710 _M_insert_equal_(const_iterator __position, _Arg&& __v) 1711 #else 1712 _M_insert_equal_(const_iterator __position, const _Val& __v) 1713 #endif 1714 { 1715 pair<_Base_ptr, _Base_ptr> __res 1716 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 1717 1718 if (__res.second) 1719 return _M_insert_(__res.first, __res.second, 1720 _GLIBCXX_FORWARD(_Arg, __v)); 1721 1722 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 1723 } 1724 1725 #if __cplusplus >= 201103L 1726 template<typename _Key, typename _Val, typename _KeyOfValue, 1727 typename _Compare, typename _Alloc> 1728 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1729 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1730 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 1731 { 1732 bool __insert_left = (__x != 0 || __p == _M_end() 1733 || _M_impl._M_key_compare(_S_key(__z), 1734 _S_key(__p))); 1735 1736 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1737 this->_M_impl._M_header); 1738 ++_M_impl._M_node_count; 1739 return iterator(__z); 1740 } 1741 1742 template<typename _Key, typename _Val, typename _KeyOfValue, 1743 typename _Compare, typename _Alloc> 1744 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1745 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1746 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 1747 { 1748 bool __insert_left = (__p == _M_end() 1749 || !_M_impl._M_key_compare(_S_key(__p), 1750 _S_key(__z))); 1751 1752 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1753 this->_M_impl._M_header); 1754 ++_M_impl._M_node_count; 1755 return iterator(__z); 1756 } 1757 1758 template<typename _Key, typename _Val, typename _KeyOfValue, 1759 typename _Compare, typename _Alloc> 1760 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1761 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1762 _M_insert_equal_lower_node(_Link_type __z) 1763 { 1764 _Link_type __x = _M_begin(); 1765 _Link_type __y = _M_end(); 1766 while (__x != 0) 1767 { 1768 __y = __x; 1769 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 1770 _S_left(__x) : _S_right(__x); 1771 } 1772 return _M_insert_lower_node(__y, __z); 1773 } 1774 1775 template<typename _Key, typename _Val, typename _KeyOfValue, 1776 typename _Compare, typename _Alloc> 1777 template<typename... _Args> 1778 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1779 _Compare, _Alloc>::iterator, bool> 1780 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1781 _M_emplace_unique(_Args&&... __args) 1782 { 1783 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 1784 1785 __try 1786 { 1787 typedef pair<iterator, bool> _Res; 1788 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 1789 if (__res.second) 1790 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 1791 1792 _M_destroy_node(__z); 1793 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 1794 } 1795 __catch(...) 1796 { 1797 _M_destroy_node(__z); 1798 __throw_exception_again; 1799 } 1800 } 1801 1802 template<typename _Key, typename _Val, typename _KeyOfValue, 1803 typename _Compare, typename _Alloc> 1804 template<typename... _Args> 1805 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1806 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1807 _M_emplace_equal(_Args&&... __args) 1808 { 1809 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 1810 1811 __try 1812 { 1813 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 1814 return _M_insert_node(__res.first, __res.second, __z); 1815 } 1816 __catch(...) 1817 { 1818 _M_destroy_node(__z); 1819 __throw_exception_again; 1820 } 1821 } 1822 1823 template<typename _Key, typename _Val, typename _KeyOfValue, 1824 typename _Compare, typename _Alloc> 1825 template<typename... _Args> 1826 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1827 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1828 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 1829 { 1830 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 1831 1832 __try 1833 { 1834 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 1835 1836 if (__res.second) 1837 return _M_insert_node(__res.first, __res.second, __z); 1838 1839 _M_destroy_node(__z); 1840 return iterator(static_cast<_Link_type>(__res.first)); 1841 } 1842 __catch(...) 1843 { 1844 _M_destroy_node(__z); 1845 __throw_exception_again; 1846 } 1847 } 1848 1849 template<typename _Key, typename _Val, typename _KeyOfValue, 1850 typename _Compare, typename _Alloc> 1851 template<typename... _Args> 1852 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1853 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1854 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 1855 { 1856 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 1857 1858 __try 1859 { 1860 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 1861 1862 if (__res.second) 1863 return _M_insert_node(__res.first, __res.second, __z); 1864 1865 return _M_insert_equal_lower_node(__z); 1866 } 1867 __catch(...) 1868 { 1869 _M_destroy_node(__z); 1870 __throw_exception_again; 1871 } 1872 } 1873 #endif 1874 1875 template<typename _Key, typename _Val, typename _KoV, 1876 typename _Cmp, typename _Alloc> 1877 template<class _II> 1878 void 1879 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1880 _M_insert_unique(_II __first, _II __last) 1881 { 1882 for (; __first != __last; ++__first) 1883 _M_insert_unique_(end(), *__first); 1884 } 1885 1886 template<typename _Key, typename _Val, typename _KoV, 1887 typename _Cmp, typename _Alloc> 1888 template<class _II> 1889 void 1890 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1891 _M_insert_equal(_II __first, _II __last) 1892 { 1893 for (; __first != __last; ++__first) 1894 _M_insert_equal_(end(), *__first); 1895 } 1896 1897 template<typename _Key, typename _Val, typename _KeyOfValue, 1898 typename _Compare, typename _Alloc> 1899 void 1900 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1901 _M_erase_aux(const_iterator __position) 1902 { 1903 _Link_type __y = 1904 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1905 (const_cast<_Base_ptr>(__position._M_node), 1906 this->_M_impl._M_header)); 1907 _M_destroy_node(__y); 1908 --_M_impl._M_node_count; 1909 } 1910 1911 template<typename _Key, typename _Val, typename _KeyOfValue, 1912 typename _Compare, typename _Alloc> 1913 void 1914 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1915 _M_erase_aux(const_iterator __first, const_iterator __last) 1916 { 1917 if (__first == begin() && __last == end()) 1918 clear(); 1919 else 1920 while (__first != __last) 1921 erase(__first++); 1922 } 1923 1924 template<typename _Key, typename _Val, typename _KeyOfValue, 1925 typename _Compare, typename _Alloc> 1926 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1927 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1928 erase(const _Key& __x) 1929 { 1930 pair<iterator, iterator> __p = equal_range(__x); 1931 const size_type __old_size = size(); 1932 erase(__p.first, __p.second); 1933 return __old_size - size(); 1934 } 1935 1936 template<typename _Key, typename _Val, typename _KeyOfValue, 1937 typename _Compare, typename _Alloc> 1938 void 1939 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1940 erase(const _Key* __first, const _Key* __last) 1941 { 1942 while (__first != __last) 1943 erase(*__first++); 1944 } 1945 1946 template<typename _Key, typename _Val, typename _KeyOfValue, 1947 typename _Compare, typename _Alloc> 1948 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1949 _Compare, _Alloc>::iterator 1950 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1951 find(const _Key& __k) 1952 { 1953 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1954 return (__j == end() 1955 || _M_impl._M_key_compare(__k, 1956 _S_key(__j._M_node))) ? end() : __j; 1957 } 1958 1959 template<typename _Key, typename _Val, typename _KeyOfValue, 1960 typename _Compare, typename _Alloc> 1961 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1962 _Compare, _Alloc>::const_iterator 1963 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1964 find(const _Key& __k) const 1965 { 1966 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1967 return (__j == end() 1968 || _M_impl._M_key_compare(__k, 1969 _S_key(__j._M_node))) ? end() : __j; 1970 } 1971 1972 template<typename _Key, typename _Val, typename _KeyOfValue, 1973 typename _Compare, typename _Alloc> 1974 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1975 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1976 count(const _Key& __k) const 1977 { 1978 pair<const_iterator, const_iterator> __p = equal_range(__k); 1979 const size_type __n = std::distance(__p.first, __p.second); 1980 return __n; 1981 } 1982 1983 _GLIBCXX_PURE unsigned int 1984 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 1985 const _Rb_tree_node_base* __root) throw (); 1986 1987 template<typename _Key, typename _Val, typename _KeyOfValue, 1988 typename _Compare, typename _Alloc> 1989 bool 1990 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 1991 { 1992 if (_M_impl._M_node_count == 0 || begin() == end()) 1993 return _M_impl._M_node_count == 0 && begin() == end() 1994 && this->_M_impl._M_header._M_left == _M_end() 1995 && this->_M_impl._M_header._M_right == _M_end(); 1996 1997 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 1998 for (const_iterator __it = begin(); __it != end(); ++__it) 1999 { 2000 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 2001 _Const_Link_type __L = _S_left(__x); 2002 _Const_Link_type __R = _S_right(__x); 2003 2004 if (__x->_M_color == _S_red) 2005 if ((__L && __L->_M_color == _S_red) 2006 || (__R && __R->_M_color == _S_red)) 2007 return false; 2008 2009 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 2010 return false; 2011 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 2012 return false; 2013 2014 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 2015 return false; 2016 } 2017 2018 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 2019 return false; 2020 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 2021 return false; 2022 return true; 2023 } 2024 2025 _GLIBCXX_END_NAMESPACE_VERSION 2026 } // namespace 2027 2028 #endif 2029
