1 // RB tree implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /* 27 * 28 * Copyright (c) 1996,1997 29 * Silicon Graphics Computer Systems, Inc. 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Silicon Graphics makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1994 41 * Hewlett-Packard Company 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Hewlett-Packard Company makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 * 51 * 52 */ 53 54 /** @file stl_tree.h 55 * This is an internal header file, included by other library headers. 56 * You should not attempt to use it directly. 57 */ 58 59 #ifndef _STL_TREE_H 60 #define _STL_TREE_H 1 61 62 #include <bits/stl_algobase.h> 63 #include <bits/allocator.h> 64 #include <bits/stl_function.h> 65 #include <bits/cpp_type_traits.h> 66 67 _GLIBCXX_BEGIN_NAMESPACE(std) 68 69 // Red-black tree class, designed for use in implementing STL 70 // associative containers (set, multiset, map, and multimap). The 71 // insertion and deletion algorithms are based on those in Cormen, 72 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 73 // 1990), except that 74 // 75 // (1) the header cell is maintained with links not only to the root 76 // but also to the leftmost node of the tree, to enable constant 77 // time begin(), and to the rightmost node of the tree, to enable 78 // linear time performance when used with the generic set algorithms 79 // (set_union, etc.) 80 // 81 // (2) when a node being deleted has two children its successor node 82 // is relinked into its place, rather than copied, so that the only 83 // iterators invalidated are those referring to the deleted node. 84 85 enum _Rb_tree_color { _S_red = false, _S_black = true }; 86 87 struct _Rb_tree_node_base 88 { 89 typedef _Rb_tree_node_base* _Base_ptr; 90 typedef const _Rb_tree_node_base* _Const_Base_ptr; 91 92 _Rb_tree_color _M_color; 93 _Base_ptr _M_parent; 94 _Base_ptr _M_left; 95 _Base_ptr _M_right; 96 97 static _Base_ptr 98 _S_minimum(_Base_ptr __x) 99 { 100 while (__x->_M_left != 0) __x = __x->_M_left; 101 return __x; 102 } 103 104 static _Const_Base_ptr 105 _S_minimum(_Const_Base_ptr __x) 106 { 107 while (__x->_M_left != 0) __x = __x->_M_left; 108 return __x; 109 } 110 111 static _Base_ptr 112 _S_maximum(_Base_ptr __x) 113 { 114 while (__x->_M_right != 0) __x = __x->_M_right; 115 return __x; 116 } 117 118 static _Const_Base_ptr 119 _S_maximum(_Const_Base_ptr __x) 120 { 121 while (__x->_M_right != 0) __x = __x->_M_right; 122 return __x; 123 } 124 }; 125 126 template<typename _Val> 127 struct _Rb_tree_node : public _Rb_tree_node_base 128 { 129 typedef _Rb_tree_node<_Val>* _Link_type; 130 _Val _M_value_field; 131 132 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 133 template<typename... _Args> 134 _Rb_tree_node(_Args&&... __args) 135 : _Rb_tree_node_base(), 136 _M_value_field(std::forward<_Args>(__args)...) { } 137 #endif 138 }; 139 140 _Rb_tree_node_base* 141 _Rb_tree_increment(_Rb_tree_node_base* __x); 142 143 const _Rb_tree_node_base* 144 _Rb_tree_increment(const _Rb_tree_node_base* __x); 145 146 _Rb_tree_node_base* 147 _Rb_tree_decrement(_Rb_tree_node_base* __x); 148 149 const _Rb_tree_node_base* 150 _Rb_tree_decrement(const _Rb_tree_node_base* __x); 151 152 template<typename _Tp> 153 struct _Rb_tree_iterator 154 { 155 typedef _Tp value_type; 156 typedef _Tp& reference; 157 typedef _Tp* pointer; 158 159 typedef bidirectional_iterator_tag iterator_category; 160 typedef ptrdiff_t difference_type; 161 162 typedef _Rb_tree_iterator<_Tp> _Self; 163 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 164 typedef _Rb_tree_node<_Tp>* _Link_type; 165 166 _Rb_tree_iterator() 167 : _M_node() { } 168 169 explicit 170 _Rb_tree_iterator(_Link_type __x) 171 : _M_node(__x) { } 172 173 reference 174 operator*() const 175 { return static_cast<_Link_type>(_M_node)->_M_value_field; } 176 177 pointer 178 operator->() const 179 { return &static_cast<_Link_type>(_M_node)->_M_value_field; } 180 181 _Self& 182 operator++() 183 { 184 _M_node = _Rb_tree_increment(_M_node); 185 return *this; 186 } 187 188 _Self 189 operator++(int) 190 { 191 _Self __tmp = *this; 192 _M_node = _Rb_tree_increment(_M_node); 193 return __tmp; 194 } 195 196 _Self& 197 operator--() 198 { 199 _M_node = _Rb_tree_decrement(_M_node); 200 return *this; 201 } 202 203 _Self 204 operator--(int) 205 { 206 _Self __tmp = *this; 207 _M_node = _Rb_tree_decrement(_M_node); 208 return __tmp; 209 } 210 211 bool 212 operator==(const _Self& __x) const 213 { return _M_node == __x._M_node; } 214 215 bool 216 operator!=(const _Self& __x) const 217 { return _M_node != __x._M_node; } 218 219 _Base_ptr _M_node; 220 }; 221 222 template<typename _Tp> 223 struct _Rb_tree_const_iterator 224 { 225 typedef _Tp value_type; 226 typedef const _Tp& reference; 227 typedef const _Tp* pointer; 228 229 typedef _Rb_tree_iterator<_Tp> iterator; 230 231 typedef bidirectional_iterator_tag iterator_category; 232 typedef ptrdiff_t difference_type; 233 234 typedef _Rb_tree_const_iterator<_Tp> _Self; 235 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 236 typedef const _Rb_tree_node<_Tp>* _Link_type; 237 238 _Rb_tree_const_iterator() 239 : _M_node() { } 240 241 explicit 242 _Rb_tree_const_iterator(_Link_type __x) 243 : _M_node(__x) { } 244 245 _Rb_tree_const_iterator(const iterator& __it) 246 : _M_node(__it._M_node) { } 247 248 reference 249 operator*() const 250 { return static_cast<_Link_type>(_M_node)->_M_value_field; } 251 252 pointer 253 operator->() const 254 { return &static_cast<_Link_type>(_M_node)->_M_value_field; } 255 256 _Self& 257 operator++() 258 { 259 _M_node = _Rb_tree_increment(_M_node); 260 return *this; 261 } 262 263 _Self 264 operator++(int) 265 { 266 _Self __tmp = *this; 267 _M_node = _Rb_tree_increment(_M_node); 268 return __tmp; 269 } 270 271 _Self& 272 operator--() 273 { 274 _M_node = _Rb_tree_decrement(_M_node); 275 return *this; 276 } 277 278 _Self 279 operator--(int) 280 { 281 _Self __tmp = *this; 282 _M_node = _Rb_tree_decrement(_M_node); 283 return __tmp; 284 } 285 286 bool 287 operator==(const _Self& __x) const 288 { return _M_node == __x._M_node; } 289 290 bool 291 operator!=(const _Self& __x) const 292 { return _M_node != __x._M_node; } 293 294 _Base_ptr _M_node; 295 }; 296 297 template<typename _Val> 298 inline bool 299 operator==(const _Rb_tree_iterator<_Val>& __x, 300 const _Rb_tree_const_iterator<_Val>& __y) 301 { return __x._M_node == __y._M_node; } 302 303 template<typename _Val> 304 inline bool 305 operator!=(const _Rb_tree_iterator<_Val>& __x, 306 const _Rb_tree_const_iterator<_Val>& __y) 307 { return __x._M_node != __y._M_node; } 308 309 void 310 _Rb_tree_insert_and_rebalance(const bool __insert_left, 311 _Rb_tree_node_base* __x, 312 _Rb_tree_node_base* __p, 313 _Rb_tree_node_base& __header); 314 315 _Rb_tree_node_base* 316 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 317 _Rb_tree_node_base& __header); 318 319 320 template<typename _Key, typename _Val, typename _KeyOfValue, 321 typename _Compare, typename _Alloc = allocator<_Val> > 322 class _Rb_tree 323 { 324 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other 325 _Node_allocator; 326 327 protected: 328 typedef _Rb_tree_node_base* _Base_ptr; 329 typedef const _Rb_tree_node_base* _Const_Base_ptr; 330 331 public: 332 typedef _Key key_type; 333 typedef _Val value_type; 334 typedef value_type* pointer; 335 typedef const value_type* const_pointer; 336 typedef value_type& reference; 337 typedef const value_type& const_reference; 338 typedef _Rb_tree_node<_Val>* _Link_type; 339 typedef const _Rb_tree_node<_Val>* _Const_Link_type; 340 typedef size_t size_type; 341 typedef ptrdiff_t difference_type; 342 typedef _Alloc allocator_type; 343 344 _Node_allocator& 345 _M_get_Node_allocator() 346 { return *static_cast<_Node_allocator*>(&this->_M_impl); } 347 348 const _Node_allocator& 349 _M_get_Node_allocator() const 350 { return *static_cast<const _Node_allocator*>(&this->_M_impl); } 351 352 allocator_type 353 get_allocator() const 354 { return allocator_type(_M_get_Node_allocator()); } 355 356 protected: 357 _Link_type 358 _M_get_node() 359 { return _M_impl._Node_allocator::allocate(1); } 360 361 void 362 _M_put_node(_Link_type __p) 363 { _M_impl._Node_allocator::deallocate(__p, 1); } 364 365 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 366 _Link_type 367 _M_create_node(const value_type& __x) 368 { 369 _Link_type __tmp = _M_get_node(); 370 __try 371 { get_allocator().construct(&__tmp->_M_value_field, __x); } 372 __catch(...) 373 { 374 _M_put_node(__tmp); 375 __throw_exception_again; 376 } 377 return __tmp; 378 } 379 380 void 381 _M_destroy_node(_Link_type __p) 382 { 383 get_allocator().destroy(&__p->_M_value_field); 384 _M_put_node(__p); 385 } 386 #else 387 template<typename... _Args> 388 _Link_type 389 _M_create_node(_Args&&... __args) 390 { 391 _Link_type __tmp = _M_get_node(); 392 __try 393 { 394 _M_get_Node_allocator().construct(__tmp, 395 std::forward<_Args>(__args)...); 396 } 397 __catch(...) 398 { 399 _M_put_node(__tmp); 400 __throw_exception_again; 401 } 402 return __tmp; 403 } 404 405 void 406 _M_destroy_node(_Link_type __p) 407 { 408 _M_get_Node_allocator().destroy(__p); 409 _M_put_node(__p); 410 } 411 #endif 412 413 _Link_type 414 _M_clone_node(_Const_Link_type __x) 415 { 416 _Link_type __tmp = _M_create_node(__x->_M_value_field); 417 __tmp->_M_color = __x->_M_color; 418 __tmp->_M_left = 0; 419 __tmp->_M_right = 0; 420 return __tmp; 421 } 422 423 protected: 424 template<typename _Key_compare, 425 bool _Is_pod_comparator = __is_pod(_Key_compare)> 426 struct _Rb_tree_impl : public _Node_allocator 427 { 428 _Key_compare _M_key_compare; 429 _Rb_tree_node_base _M_header; 430 size_type _M_node_count; // Keeps track of size of tree. 431 432 _Rb_tree_impl() 433 : _Node_allocator(), _M_key_compare(), _M_header(), 434 _M_node_count(0) 435 { _M_initialize(); } 436 437 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 438 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), 439 _M_node_count(0) 440 { _M_initialize(); } 441 442 private: 443 void 444 _M_initialize() 445 { 446 this->_M_header._M_color = _S_red; 447 this->_M_header._M_parent = 0; 448 this->_M_header._M_left = &this->_M_header; 449 this->_M_header._M_right = &this->_M_header; 450 } 451 }; 452 453 // Local modification: if __google_stl_debug_rbtree is defined to 454 // non-zero value, check sort predicate for strict weak ordering. 455 // See http://b/1731200. 456 #if __google_stl_debug_rbtree 457 template<typename _KeyCompare> 458 struct _CheckedCompare { 459 // Mutable because some clients use non-const operator(). 460 mutable _KeyCompare _M_key_compare; 461 462 _CheckedCompare(): _M_key_compare() { } 463 _CheckedCompare(const _KeyCompare & __comp): _M_key_compare(__comp) { } 464 465 bool operator()(const _Key& __x, const _Key& __y) const { 466 if (_M_key_compare(__x, __x)) 467 __throw_runtime_error("strict weak ordering: (__x LT __x) != false"); 468 if (_M_key_compare(__y, __y)) 469 __throw_runtime_error("strict weak ordering: (__y LT __y) != false"); 470 bool lt = _M_key_compare(__x, __y); 471 if (lt && _M_key_compare(__y, __x)) 472 __throw_runtime_error("strict weak ordering: ((__x LT __y) && (__y LT __x)) != false"); 473 return lt; 474 } 475 operator _KeyCompare() const { return _M_key_compare; } 476 }; 477 478 _Rb_tree_impl<_CheckedCompare<_Compare> > _M_impl; 479 #else 480 _Rb_tree_impl<_Compare> _M_impl; 481 #endif 482 483 protected: 484 _Base_ptr& 485 _M_root() 486 { return this->_M_impl._M_header._M_parent; } 487 488 _Const_Base_ptr 489 _M_root() const 490 { return this->_M_impl._M_header._M_parent; } 491 492 _Base_ptr& 493 _M_leftmost() 494 { return this->_M_impl._M_header._M_left; } 495 496 _Const_Base_ptr 497 _M_leftmost() const 498 { return this->_M_impl._M_header._M_left; } 499 500 _Base_ptr& 501 _M_rightmost() 502 { return this->_M_impl._M_header._M_right; } 503 504 _Const_Base_ptr 505 _M_rightmost() const 506 { return this->_M_impl._M_header._M_right; } 507 508 _Link_type 509 _M_begin() 510 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 511 512 _Const_Link_type 513 _M_begin() const 514 { 515 return static_cast<_Const_Link_type> 516 (this->_M_impl._M_header._M_parent); 517 } 518 519 _Link_type 520 _M_end() 521 { return static_cast<_Link_type>(&this->_M_impl._M_header); } 522 523 _Const_Link_type 524 _M_end() const 525 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 526 527 static const_reference 528 _S_value(_Const_Link_type __x) 529 { return __x->_M_value_field; } 530 531 static const _Key& 532 _S_key(_Const_Link_type __x) 533 { return _KeyOfValue()(_S_value(__x)); } 534 535 static _Link_type 536 _S_left(_Base_ptr __x) 537 { return static_cast<_Link_type>(__x->_M_left); } 538 539 static _Const_Link_type 540 _S_left(_Const_Base_ptr __x) 541 { return static_cast<_Const_Link_type>(__x->_M_left); } 542 543 static _Link_type 544 _S_right(_Base_ptr __x) 545 { return static_cast<_Link_type>(__x->_M_right); } 546 547 static _Const_Link_type 548 _S_right(_Const_Base_ptr __x) 549 { return static_cast<_Const_Link_type>(__x->_M_right); } 550 551 static const_reference 552 _S_value(_Const_Base_ptr __x) 553 { return static_cast<_Const_Link_type>(__x)->_M_value_field; } 554 555 static const _Key& 556 _S_key(_Const_Base_ptr __x) 557 { return _KeyOfValue()(_S_value(__x)); } 558 559 static _Base_ptr 560 _S_minimum(_Base_ptr __x) 561 { return _Rb_tree_node_base::_S_minimum(__x); } 562 563 static _Const_Base_ptr 564 _S_minimum(_Const_Base_ptr __x) 565 { return _Rb_tree_node_base::_S_minimum(__x); } 566 567 static _Base_ptr 568 _S_maximum(_Base_ptr __x) 569 { return _Rb_tree_node_base::_S_maximum(__x); } 570 571 static _Const_Base_ptr 572 _S_maximum(_Const_Base_ptr __x) 573 { return _Rb_tree_node_base::_S_maximum(__x); } 574 575 public: 576 typedef _Rb_tree_iterator<value_type> iterator; 577 typedef _Rb_tree_const_iterator<value_type> const_iterator; 578 579 typedef std::reverse_iterator<iterator> reverse_iterator; 580 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 581 582 private: 583 iterator 584 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, 585 const value_type& __v); 586 587 // _GLIBCXX_RESOLVE_LIB_DEFECTS 588 // 233. Insertion hints in associative containers. 589 iterator 590 _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 591 592 iterator 593 _M_insert_equal_lower(const value_type& __x); 594 595 _Link_type 596 _M_copy(_Const_Link_type __x, _Link_type __p); 597 598 void 599 _M_erase(_Link_type __x); 600 601 iterator 602 _M_lower_bound(_Link_type __x, _Link_type __y, 603 const _Key& __k); 604 605 const_iterator 606 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 607 const _Key& __k) const; 608 609 iterator 610 _M_upper_bound(_Link_type __x, _Link_type __y, 611 const _Key& __k); 612 613 const_iterator 614 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 615 const _Key& __k) const; 616 617 public: 618 // allocation/deallocation 619 _Rb_tree() { } 620 621 _Rb_tree(const _Compare& __comp, 622 const allocator_type& __a = allocator_type()) 623 : _M_impl(__comp, __a) { } 624 625 _Rb_tree(const _Rb_tree& __x) 626 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) 627 { 628 if (__x._M_root() != 0) 629 { 630 _M_root() = _M_copy(__x._M_begin(), _M_end()); 631 _M_leftmost() = _S_minimum(_M_root()); 632 _M_rightmost() = _S_maximum(_M_root()); 633 _M_impl._M_node_count = __x._M_impl._M_node_count; 634 } 635 } 636 637 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 638 _Rb_tree(_Rb_tree&& __x); 639 #endif 640 641 ~_Rb_tree() 642 { _M_erase(_M_begin()); } 643 644 _Rb_tree& 645 operator=(const _Rb_tree& __x); 646 647 // Accessors. 648 _Compare 649 key_comp() const 650 { return _M_impl._M_key_compare; } 651 652 iterator 653 begin() 654 { 655 return iterator(static_cast<_Link_type> 656 (this->_M_impl._M_header._M_left)); 657 } 658 659 const_iterator 660 begin() const 661 { 662 return const_iterator(static_cast<_Const_Link_type> 663 (this->_M_impl._M_header._M_left)); 664 } 665 666 iterator 667 end() 668 { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); } 669 670 const_iterator 671 end() const 672 { 673 return const_iterator(static_cast<_Const_Link_type> 674 (&this->_M_impl._M_header)); 675 } 676 677 reverse_iterator 678 rbegin() 679 { return reverse_iterator(end()); } 680 681 const_reverse_iterator 682 rbegin() const 683 { return const_reverse_iterator(end()); } 684 685 reverse_iterator 686 rend() 687 { return reverse_iterator(begin()); } 688 689 const_reverse_iterator 690 rend() const 691 { return const_reverse_iterator(begin()); } 692 693 bool 694 empty() const 695 { return _M_impl._M_node_count == 0; } 696 697 size_type 698 size() const 699 { return _M_impl._M_node_count; } 700 701 size_type 702 max_size() const 703 { return _M_get_Node_allocator().max_size(); } 704 705 void 706 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 707 swap(_Rb_tree&& __t); 708 #else 709 swap(_Rb_tree& __t); 710 #endif 711 712 // Insert/erase. 713 pair<iterator, bool> 714 _M_insert_unique(const value_type& __x); 715 716 iterator 717 _M_insert_equal(const value_type& __x); 718 719 iterator 720 _M_insert_unique_(const_iterator __position, const value_type& __x); 721 722 iterator 723 _M_insert_equal_(const_iterator __position, const value_type& __x); 724 725 template<typename _InputIterator> 726 void 727 _M_insert_unique(_InputIterator __first, _InputIterator __last); 728 729 template<typename _InputIterator> 730 void 731 _M_insert_equal(_InputIterator __first, _InputIterator __last); 732 733 void 734 erase(iterator __position); 735 736 void 737 erase(const_iterator __position); 738 739 size_type 740 erase(const key_type& __x); 741 742 void 743 erase(iterator __first, iterator __last); 744 745 void 746 erase(const_iterator __first, const_iterator __last); 747 748 void 749 erase(const key_type* __first, const key_type* __last); 750 751 void 752 clear() 753 { 754 _M_erase(_M_begin()); 755 _M_leftmost() = _M_end(); 756 _M_root() = 0; 757 _M_rightmost() = _M_end(); 758 _M_impl._M_node_count = 0; 759 } 760 761 // Set operations. 762 iterator 763 find(const key_type& __k); 764 765 const_iterator 766 find(const key_type& __k) const; 767 768 size_type 769 count(const key_type& __k) const; 770 771 iterator 772 lower_bound(const key_type& __k) 773 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 774 775 const_iterator 776 lower_bound(const key_type& __k) const 777 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 778 779 iterator 780 upper_bound(const key_type& __k) 781 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 782 783 const_iterator 784 upper_bound(const key_type& __k) const 785 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 786 787 pair<iterator, iterator> 788 equal_range(const key_type& __k); 789 790 pair<const_iterator, const_iterator> 791 equal_range(const key_type& __k) const; 792 793 // Debugging. 794 bool 795 __rb_verify() const; 796 }; 797 798 template<typename _Key, typename _Val, typename _KeyOfValue, 799 typename _Compare, typename _Alloc> 800 inline bool 801 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 802 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 803 { 804 return __x.size() == __y.size() 805 && std::equal(__x.begin(), __x.end(), __y.begin()); 806 } 807 808 template<typename _Key, typename _Val, typename _KeyOfValue, 809 typename _Compare, typename _Alloc> 810 inline bool 811 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 812 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 813 { 814 return std::lexicographical_compare(__x.begin(), __x.end(), 815 __y.begin(), __y.end()); 816 } 817 818 template<typename _Key, typename _Val, typename _KeyOfValue, 819 typename _Compare, typename _Alloc> 820 inline bool 821 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 822 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 823 { return !(__x == __y); } 824 825 template<typename _Key, typename _Val, typename _KeyOfValue, 826 typename _Compare, typename _Alloc> 827 inline bool 828 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 829 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 830 { return __y < __x; } 831 832 template<typename _Key, typename _Val, typename _KeyOfValue, 833 typename _Compare, typename _Alloc> 834 inline bool 835 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 836 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 837 { return !(__y < __x); } 838 839 template<typename _Key, typename _Val, typename _KeyOfValue, 840 typename _Compare, typename _Alloc> 841 inline bool 842 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 843 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 844 { return !(__x < __y); } 845 846 template<typename _Key, typename _Val, typename _KeyOfValue, 847 typename _Compare, typename _Alloc> 848 inline void 849 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 850 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 851 { __x.swap(__y); } 852 853 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 854 template<typename _Key, typename _Val, typename _KeyOfValue, 855 typename _Compare, typename _Alloc> 856 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 857 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x) 858 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) 859 { 860 if (__x._M_root() != 0) 861 { 862 _M_root() = __x._M_root(); 863 _M_leftmost() = __x._M_leftmost(); 864 _M_rightmost() = __x._M_rightmost(); 865 _M_root()->_M_parent = _M_end(); 866 867 __x._M_root() = 0; 868 __x._M_leftmost() = __x._M_end(); 869 __x._M_rightmost() = __x._M_end(); 870 871 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 872 __x._M_impl._M_node_count = 0; 873 } 874 } 875 #endif 876 877 template<typename _Key, typename _Val, typename _KeyOfValue, 878 typename _Compare, typename _Alloc> 879 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 880 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 881 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) 882 { 883 if (this != &__x) 884 { 885 // Note that _Key may be a constant type. 886 clear(); 887 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 888 if (__x._M_root() != 0) 889 { 890 _M_root() = _M_copy(__x._M_begin(), _M_end()); 891 _M_leftmost() = _S_minimum(_M_root()); 892 _M_rightmost() = _S_maximum(_M_root()); 893 _M_impl._M_node_count = __x._M_impl._M_node_count; 894 } 895 } 896 return *this; 897 } 898 899 template<typename _Key, typename _Val, typename _KeyOfValue, 900 typename _Compare, typename _Alloc> 901 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 902 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 903 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) 904 { 905 bool __insert_left = (__x != 0 || __p == _M_end() 906 || _M_impl._M_key_compare(_KeyOfValue()(__v), 907 _S_key(__p))); 908 909 _Link_type __z = _M_create_node(__v); 910 911 _Rb_tree_insert_and_rebalance(__insert_left, __z, 912 const_cast<_Base_ptr>(__p), 913 this->_M_impl._M_header); 914 ++_M_impl._M_node_count; 915 return iterator(__z); 916 } 917 918 template<typename _Key, typename _Val, typename _KeyOfValue, 919 typename _Compare, typename _Alloc> 920 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 921 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 922 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 923 { 924 bool __insert_left = (__x != 0 || __p == _M_end() 925 || !_M_impl._M_key_compare(_S_key(__p), 926 _KeyOfValue()(__v))); 927 928 _Link_type __z = _M_create_node(__v); 929 930 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 931 this->_M_impl._M_header); 932 ++_M_impl._M_node_count; 933 return iterator(__z); 934 } 935 936 template<typename _Key, typename _Val, typename _KeyOfValue, 937 typename _Compare, typename _Alloc> 938 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 939 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 940 _M_insert_equal_lower(const _Val& __v) 941 { 942 _Link_type __x = _M_begin(); 943 _Link_type __y = _M_end(); 944 while (__x != 0) 945 { 946 __y = __x; 947 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 948 _S_left(__x) : _S_right(__x); 949 } 950 return _M_insert_lower(__x, __y, __v); 951 } 952 953 template<typename _Key, typename _Val, typename _KoV, 954 typename _Compare, typename _Alloc> 955 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 956 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 957 _M_copy(_Const_Link_type __x, _Link_type __p) 958 { 959 // Structural copy. __x and __p must be non-null. 960 _Link_type __top = _M_clone_node(__x); 961 __top->_M_parent = __p; 962 963 __try 964 { 965 if (__x->_M_right) 966 __top->_M_right = _M_copy(_S_right(__x), __top); 967 __p = __top; 968 __x = _S_left(__x); 969 970 while (__x != 0) 971 { 972 _Link_type __y = _M_clone_node(__x); 973 __p->_M_left = __y; 974 __y->_M_parent = __p; 975 if (__x->_M_right) 976 __y->_M_right = _M_copy(_S_right(__x), __y); 977 __p = __y; 978 __x = _S_left(__x); 979 } 980 } 981 __catch(...) 982 { 983 _M_erase(__top); 984 __throw_exception_again; 985 } 986 return __top; 987 } 988 989 template<typename _Key, typename _Val, typename _KeyOfValue, 990 typename _Compare, typename _Alloc> 991 void 992 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 993 _M_erase(_Link_type __x) 994 { 995 // Erase without rebalancing. 996 while (__x != 0) 997 { 998 _M_erase(_S_right(__x)); 999 _Link_type __y = _S_left(__x); 1000 _M_destroy_node(__x); 1001 __x = __y; 1002 } 1003 } 1004 1005 template<typename _Key, typename _Val, typename _KeyOfValue, 1006 typename _Compare, typename _Alloc> 1007 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1008 _Compare, _Alloc>::iterator 1009 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1010 _M_lower_bound(_Link_type __x, _Link_type __y, 1011 const _Key& __k) 1012 { 1013 while (__x != 0) 1014 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1015 __y = __x, __x = _S_left(__x); 1016 else 1017 __x = _S_right(__x); 1018 return iterator(__y); 1019 } 1020 1021 template<typename _Key, typename _Val, typename _KeyOfValue, 1022 typename _Compare, typename _Alloc> 1023 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1024 _Compare, _Alloc>::const_iterator 1025 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1026 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 1027 const _Key& __k) const 1028 { 1029 while (__x != 0) 1030 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1031 __y = __x, __x = _S_left(__x); 1032 else 1033 __x = _S_right(__x); 1034 return const_iterator(__y); 1035 } 1036 1037 template<typename _Key, typename _Val, typename _KeyOfValue, 1038 typename _Compare, typename _Alloc> 1039 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1040 _Compare, _Alloc>::iterator 1041 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1042 _M_upper_bound(_Link_type __x, _Link_type __y, 1043 const _Key& __k) 1044 { 1045 while (__x != 0) 1046 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1047 __y = __x, __x = _S_left(__x); 1048 else 1049 __x = _S_right(__x); 1050 return iterator(__y); 1051 } 1052 1053 template<typename _Key, typename _Val, typename _KeyOfValue, 1054 typename _Compare, typename _Alloc> 1055 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1056 _Compare, _Alloc>::const_iterator 1057 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1058 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 1059 const _Key& __k) const 1060 { 1061 while (__x != 0) 1062 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1063 __y = __x, __x = _S_left(__x); 1064 else 1065 __x = _S_right(__x); 1066 return const_iterator(__y); 1067 } 1068 1069 template<typename _Key, typename _Val, typename _KeyOfValue, 1070 typename _Compare, typename _Alloc> 1071 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1072 _Compare, _Alloc>::iterator, 1073 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1074 _Compare, _Alloc>::iterator> 1075 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1076 equal_range(const _Key& __k) 1077 { 1078 _Link_type __x = _M_begin(); 1079 _Link_type __y = _M_end(); 1080 while (__x != 0) 1081 { 1082 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1083 __x = _S_right(__x); 1084 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1085 __y = __x, __x = _S_left(__x); 1086 else 1087 { 1088 _Link_type __xu(__x), __yu(__y); 1089 __y = __x, __x = _S_left(__x); 1090 __xu = _S_right(__xu); 1091 return pair<iterator, 1092 iterator>(_M_lower_bound(__x, __y, __k), 1093 _M_upper_bound(__xu, __yu, __k)); 1094 } 1095 } 1096 return pair<iterator, iterator>(iterator(__y), 1097 iterator(__y)); 1098 } 1099 1100 template<typename _Key, typename _Val, typename _KeyOfValue, 1101 typename _Compare, typename _Alloc> 1102 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1103 _Compare, _Alloc>::const_iterator, 1104 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1105 _Compare, _Alloc>::const_iterator> 1106 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1107 equal_range(const _Key& __k) const 1108 { 1109 _Const_Link_type __x = _M_begin(); 1110 _Const_Link_type __y = _M_end(); 1111 while (__x != 0) 1112 { 1113 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1114 __x = _S_right(__x); 1115 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1116 __y = __x, __x = _S_left(__x); 1117 else 1118 { 1119 _Const_Link_type __xu(__x), __yu(__y); 1120 __y = __x, __x = _S_left(__x); 1121 __xu = _S_right(__xu); 1122 return pair<const_iterator, 1123 const_iterator>(_M_lower_bound(__x, __y, __k), 1124 _M_upper_bound(__xu, __yu, __k)); 1125 } 1126 } 1127 return pair<const_iterator, const_iterator>(const_iterator(__y), 1128 const_iterator(__y)); 1129 } 1130 1131 template<typename _Key, typename _Val, typename _KeyOfValue, 1132 typename _Compare, typename _Alloc> 1133 void 1134 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1135 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1136 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __t) 1137 #else 1138 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 1139 #endif 1140 { 1141 if (_M_root() == 0) 1142 { 1143 if (__t._M_root() != 0) 1144 { 1145 _M_root() = __t._M_root(); 1146 _M_leftmost() = __t._M_leftmost(); 1147 _M_rightmost() = __t._M_rightmost(); 1148 _M_root()->_M_parent = _M_end(); 1149 1150 __t._M_root() = 0; 1151 __t._M_leftmost() = __t._M_end(); 1152 __t._M_rightmost() = __t._M_end(); 1153 } 1154 } 1155 else if (__t._M_root() == 0) 1156 { 1157 __t._M_root() = _M_root(); 1158 __t._M_leftmost() = _M_leftmost(); 1159 __t._M_rightmost() = _M_rightmost(); 1160 __t._M_root()->_M_parent = __t._M_end(); 1161 1162 _M_root() = 0; 1163 _M_leftmost() = _M_end(); 1164 _M_rightmost() = _M_end(); 1165 } 1166 else 1167 { 1168 std::swap(_M_root(),__t._M_root()); 1169 std::swap(_M_leftmost(),__t._M_leftmost()); 1170 std::swap(_M_rightmost(),__t._M_rightmost()); 1171 1172 _M_root()->_M_parent = _M_end(); 1173 __t._M_root()->_M_parent = __t._M_end(); 1174 } 1175 // No need to swap header's color as it does not change. 1176 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 1177 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 1178 1179 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1180 // 431. Swapping containers with unequal allocators. 1181 std::__alloc_swap<_Node_allocator>:: 1182 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); 1183 } 1184 1185 template<typename _Key, typename _Val, typename _KeyOfValue, 1186 typename _Compare, typename _Alloc> 1187 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1188 _Compare, _Alloc>::iterator, bool> 1189 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1190 _M_insert_unique(const _Val& __v) 1191 { 1192 _Link_type __x = _M_begin(); 1193 _Link_type __y = _M_end(); 1194 bool __comp = true; 1195 while (__x != 0) 1196 { 1197 __y = __x; 1198 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 1199 __x = __comp ? _S_left(__x) : _S_right(__x); 1200 } 1201 iterator __j = iterator(__y); 1202 if (__comp) 1203 { 1204 if (__j == begin()) 1205 return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); 1206 else 1207 --__j; 1208 } 1209 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 1210 return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); 1211 return pair<iterator, bool>(__j, false); 1212 } 1213 1214 template<typename _Key, typename _Val, typename _KeyOfValue, 1215 typename _Compare, typename _Alloc> 1216 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1217 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1218 _M_insert_equal(const _Val& __v) 1219 { 1220 _Link_type __x = _M_begin(); 1221 _Link_type __y = _M_end(); 1222 while (__x != 0) 1223 { 1224 __y = __x; 1225 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 1226 _S_left(__x) : _S_right(__x); 1227 } 1228 return _M_insert_(__x, __y, __v); 1229 } 1230 1231 template<typename _Key, typename _Val, typename _KeyOfValue, 1232 typename _Compare, typename _Alloc> 1233 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1234 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1235 _M_insert_unique_(const_iterator __position, const _Val& __v) 1236 { 1237 // end() 1238 if (__position._M_node == _M_end()) 1239 { 1240 if (size() > 0 1241 && _M_impl._M_key_compare(_S_key(_M_rightmost()), 1242 _KeyOfValue()(__v))) 1243 return _M_insert_(0, _M_rightmost(), __v); 1244 else 1245 return _M_insert_unique(__v).first; 1246 } 1247 else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1248 _S_key(__position._M_node))) 1249 { 1250 // First, try before... 1251 const_iterator __before = __position; 1252 if (__position._M_node == _M_leftmost()) // begin() 1253 return _M_insert_(_M_leftmost(), _M_leftmost(), __v); 1254 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 1255 _KeyOfValue()(__v))) 1256 { 1257 if (_S_right(__before._M_node) == 0) 1258 return _M_insert_(0, __before._M_node, __v); 1259 else 1260 return _M_insert_(__position._M_node, 1261 __position._M_node, __v); 1262 } 1263 else 1264 return _M_insert_unique(__v).first; 1265 } 1266 else if (_M_impl._M_key_compare(_S_key(__position._M_node), 1267 _KeyOfValue()(__v))) 1268 { 1269 // ... then try after. 1270 const_iterator __after = __position; 1271 if (__position._M_node == _M_rightmost()) 1272 return _M_insert_(0, _M_rightmost(), __v); 1273 else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1274 _S_key((++__after)._M_node))) 1275 { 1276 if (_S_right(__position._M_node) == 0) 1277 return _M_insert_(0, __position._M_node, __v); 1278 else 1279 return _M_insert_(__after._M_node, __after._M_node, __v); 1280 } 1281 else 1282 return _M_insert_unique(__v).first; 1283 } 1284 else 1285 // Equivalent keys. 1286 return iterator(static_cast<_Link_type> 1287 (const_cast<_Base_ptr>(__position._M_node))); 1288 } 1289 1290 template<typename _Key, typename _Val, typename _KeyOfValue, 1291 typename _Compare, typename _Alloc> 1292 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1293 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1294 _M_insert_equal_(const_iterator __position, const _Val& __v) 1295 { 1296 // end() 1297 if (__position._M_node == _M_end()) 1298 { 1299 if (size() > 0 1300 && !_M_impl._M_key_compare(_KeyOfValue()(__v), 1301 _S_key(_M_rightmost()))) 1302 return _M_insert_(0, _M_rightmost(), __v); 1303 else 1304 return _M_insert_equal(__v); 1305 } 1306 else if (!_M_impl._M_key_compare(_S_key(__position._M_node), 1307 _KeyOfValue()(__v))) 1308 { 1309 // First, try before... 1310 const_iterator __before = __position; 1311 if (__position._M_node == _M_leftmost()) // begin() 1312 return _M_insert_(_M_leftmost(), _M_leftmost(), __v); 1313 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 1314 _S_key((--__before)._M_node))) 1315 { 1316 if (_S_right(__before._M_node) == 0) 1317 return _M_insert_(0, __before._M_node, __v); 1318 else 1319 return _M_insert_(__position._M_node, 1320 __position._M_node, __v); 1321 } 1322 else 1323 return _M_insert_equal(__v); 1324 } 1325 else 1326 { 1327 // ... then try after. 1328 const_iterator __after = __position; 1329 if (__position._M_node == _M_rightmost()) 1330 return _M_insert_(0, _M_rightmost(), __v); 1331 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), 1332 _KeyOfValue()(__v))) 1333 { 1334 if (_S_right(__position._M_node) == 0) 1335 return _M_insert_(0, __position._M_node, __v); 1336 else 1337 return _M_insert_(__after._M_node, __after._M_node, __v); 1338 } 1339 else 1340 return _M_insert_equal_lower(__v); 1341 } 1342 } 1343 1344 template<typename _Key, typename _Val, typename _KoV, 1345 typename _Cmp, typename _Alloc> 1346 template<class _II> 1347 void 1348 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1349 _M_insert_unique(_II __first, _II __last) 1350 { 1351 for (; __first != __last; ++__first) 1352 _M_insert_unique_(end(), *__first); 1353 } 1354 1355 template<typename _Key, typename _Val, typename _KoV, 1356 typename _Cmp, typename _Alloc> 1357 template<class _II> 1358 void 1359 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1360 _M_insert_equal(_II __first, _II __last) 1361 { 1362 for (; __first != __last; ++__first) 1363 _M_insert_equal_(end(), *__first); 1364 } 1365 1366 template<typename _Key, typename _Val, typename _KeyOfValue, 1367 typename _Compare, typename _Alloc> 1368 inline void 1369 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1370 erase(iterator __position) 1371 { 1372 _Link_type __y = 1373 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1374 (__position._M_node, 1375 this->_M_impl._M_header)); 1376 _M_destroy_node(__y); 1377 --_M_impl._M_node_count; 1378 } 1379 1380 template<typename _Key, typename _Val, typename _KeyOfValue, 1381 typename _Compare, typename _Alloc> 1382 inline void 1383 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1384 erase(const_iterator __position) 1385 { 1386 _Link_type __y = 1387 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1388 (const_cast<_Base_ptr>(__position._M_node), 1389 this->_M_impl._M_header)); 1390 _M_destroy_node(__y); 1391 --_M_impl._M_node_count; 1392 } 1393 1394 template<typename _Key, typename _Val, typename _KeyOfValue, 1395 typename _Compare, typename _Alloc> 1396 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1397 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1398 erase(const _Key& __x) 1399 { 1400 pair<iterator, iterator> __p = equal_range(__x); 1401 const size_type __old_size = size(); 1402 erase(__p.first, __p.second); 1403 return __old_size - size(); 1404 } 1405 1406 template<typename _Key, typename _Val, typename _KeyOfValue, 1407 typename _Compare, typename _Alloc> 1408 void 1409 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1410 erase(iterator __first, iterator __last) 1411 { 1412 if (__first == begin() && __last == end()) 1413 clear(); 1414 else 1415 while (__first != __last) 1416 erase(__first++); 1417 } 1418 1419 template<typename _Key, typename _Val, typename _KeyOfValue, 1420 typename _Compare, typename _Alloc> 1421 void 1422 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1423 erase(const_iterator __first, const_iterator __last) 1424 { 1425 if (__first == begin() && __last == end()) 1426 clear(); 1427 else 1428 while (__first != __last) 1429 erase(__first++); 1430 } 1431 1432 template<typename _Key, typename _Val, typename _KeyOfValue, 1433 typename _Compare, typename _Alloc> 1434 void 1435 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1436 erase(const _Key* __first, const _Key* __last) 1437 { 1438 while (__first != __last) 1439 erase(*__first++); 1440 } 1441 1442 template<typename _Key, typename _Val, typename _KeyOfValue, 1443 typename _Compare, typename _Alloc> 1444 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1445 _Compare, _Alloc>::iterator 1446 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1447 find(const _Key& __k) 1448 { 1449 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1450 return (__j == end() 1451 || _M_impl._M_key_compare(__k, 1452 _S_key(__j._M_node))) ? end() : __j; 1453 } 1454 1455 template<typename _Key, typename _Val, typename _KeyOfValue, 1456 typename _Compare, typename _Alloc> 1457 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1458 _Compare, _Alloc>::const_iterator 1459 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1460 find(const _Key& __k) const 1461 { 1462 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1463 return (__j == end() 1464 || _M_impl._M_key_compare(__k, 1465 _S_key(__j._M_node))) ? end() : __j; 1466 } 1467 1468 template<typename _Key, typename _Val, typename _KeyOfValue, 1469 typename _Compare, typename _Alloc> 1470 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1471 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1472 count(const _Key& __k) const 1473 { 1474 pair<const_iterator, const_iterator> __p = equal_range(__k); 1475 const size_type __n = std::distance(__p.first, __p.second); 1476 return __n; 1477 } 1478 1479 unsigned int 1480 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 1481 const _Rb_tree_node_base* __root); 1482 1483 template<typename _Key, typename _Val, typename _KeyOfValue, 1484 typename _Compare, typename _Alloc> 1485 bool 1486 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 1487 { 1488 if (_M_impl._M_node_count == 0 || begin() == end()) 1489 return _M_impl._M_node_count == 0 && begin() == end() 1490 && this->_M_impl._M_header._M_left == _M_end() 1491 && this->_M_impl._M_header._M_right == _M_end(); 1492 1493 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 1494 for (const_iterator __it = begin(); __it != end(); ++__it) 1495 { 1496 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 1497 _Const_Link_type __L = _S_left(__x); 1498 _Const_Link_type __R = _S_right(__x); 1499 1500 if (__x->_M_color == _S_red) 1501 if ((__L && __L->_M_color == _S_red) 1502 || (__R && __R->_M_color == _S_red)) 1503 return false; 1504 1505 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 1506 return false; 1507 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 1508 return false; 1509 1510 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 1511 return false; 1512 } 1513 1514 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 1515 return false; 1516 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 1517 return false; 1518 return true; 1519 } 1520 1521 _GLIBCXX_END_NAMESPACE 1522 1523 #endif 1524
