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 _KeyCompare _M_key_compare; 460 461 _CheckedCompare(): _M_key_compare() { } 462 _CheckedCompare(const _KeyCompare & __comp): _M_key_compare(__comp) { } 463 464 // Template arg required to avoid duplicating code in the two op() 465 // operators below. User-provided _M_key_compare may not be const, 466 // but needs to be callable from our const op(). 467 // See http://b/1731200 for details. 468 template <typename _KeyCompareT> 469 static bool _M_compare_with(_KeyCompareT& __comp, const _Key& __x, const _Key& __y) { 470 if (__comp(__x, __x)) 471 __throw_runtime_error("strict weak ordering: (__x LT __x) != false"); 472 if (__comp(__y, __y)) 473 __throw_runtime_error("strict weak ordering: (__y LT __y) != false"); 474 bool lt = __comp(__x, __y); 475 if (lt && __comp(__y, __x)) 476 __throw_runtime_error("strict weak ordering: ((__x LT __y) && (__y LT __x)) != false"); 477 return lt; 478 } 479 bool operator()(const _Key& __x, const _Key& __y) const { 480 return _M_compare_with(_M_key_compare, __x, __y); 481 } 482 483 bool operator()(const _Key& __x, const _Key& __y) { 484 return _M_compare_with(_M_key_compare, __x, __y); 485 } 486 487 operator _KeyCompare() const { return _M_key_compare; } 488 }; 489 490 _Rb_tree_impl<_CheckedCompare<_Compare> > _M_impl; 491 #else 492 _Rb_tree_impl<_Compare> _M_impl; 493 #endif 494 495 protected: 496 _Base_ptr& 497 _M_root() 498 { return this->_M_impl._M_header._M_parent; } 499 500 _Const_Base_ptr 501 _M_root() const 502 { return this->_M_impl._M_header._M_parent; } 503 504 _Base_ptr& 505 _M_leftmost() 506 { return this->_M_impl._M_header._M_left; } 507 508 _Const_Base_ptr 509 _M_leftmost() const 510 { return this->_M_impl._M_header._M_left; } 511 512 _Base_ptr& 513 _M_rightmost() 514 { return this->_M_impl._M_header._M_right; } 515 516 _Const_Base_ptr 517 _M_rightmost() const 518 { return this->_M_impl._M_header._M_right; } 519 520 _Link_type 521 _M_begin() 522 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 523 524 _Const_Link_type 525 _M_begin() const 526 { 527 return static_cast<_Const_Link_type> 528 (this->_M_impl._M_header._M_parent); 529 } 530 531 _Link_type 532 _M_end() 533 { return static_cast<_Link_type>(&this->_M_impl._M_header); } 534 535 _Const_Link_type 536 _M_end() const 537 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 538 539 static const_reference 540 _S_value(_Const_Link_type __x) 541 { return __x->_M_value_field; } 542 543 static const _Key& 544 _S_key(_Const_Link_type __x) 545 { return _KeyOfValue()(_S_value(__x)); } 546 547 static _Link_type 548 _S_left(_Base_ptr __x) 549 { return static_cast<_Link_type>(__x->_M_left); } 550 551 static _Const_Link_type 552 _S_left(_Const_Base_ptr __x) 553 { return static_cast<_Const_Link_type>(__x->_M_left); } 554 555 static _Link_type 556 _S_right(_Base_ptr __x) 557 { return static_cast<_Link_type>(__x->_M_right); } 558 559 static _Const_Link_type 560 _S_right(_Const_Base_ptr __x) 561 { return static_cast<_Const_Link_type>(__x->_M_right); } 562 563 static const_reference 564 _S_value(_Const_Base_ptr __x) 565 { return static_cast<_Const_Link_type>(__x)->_M_value_field; } 566 567 static const _Key& 568 _S_key(_Const_Base_ptr __x) 569 { return _KeyOfValue()(_S_value(__x)); } 570 571 static _Base_ptr 572 _S_minimum(_Base_ptr __x) 573 { return _Rb_tree_node_base::_S_minimum(__x); } 574 575 static _Const_Base_ptr 576 _S_minimum(_Const_Base_ptr __x) 577 { return _Rb_tree_node_base::_S_minimum(__x); } 578 579 static _Base_ptr 580 _S_maximum(_Base_ptr __x) 581 { return _Rb_tree_node_base::_S_maximum(__x); } 582 583 static _Const_Base_ptr 584 _S_maximum(_Const_Base_ptr __x) 585 { return _Rb_tree_node_base::_S_maximum(__x); } 586 587 public: 588 typedef _Rb_tree_iterator<value_type> iterator; 589 typedef _Rb_tree_const_iterator<value_type> const_iterator; 590 591 typedef std::reverse_iterator<iterator> reverse_iterator; 592 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 593 594 private: 595 iterator 596 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, 597 const value_type& __v); 598 599 // _GLIBCXX_RESOLVE_LIB_DEFECTS 600 // 233. Insertion hints in associative containers. 601 iterator 602 _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 603 604 iterator 605 _M_insert_equal_lower(const value_type& __x); 606 607 _Link_type 608 _M_copy(_Const_Link_type __x, _Link_type __p); 609 610 void 611 _M_erase(_Link_type __x); 612 613 iterator 614 _M_lower_bound(_Link_type __x, _Link_type __y, 615 const _Key& __k); 616 617 const_iterator 618 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 619 const _Key& __k) const; 620 621 iterator 622 _M_upper_bound(_Link_type __x, _Link_type __y, 623 const _Key& __k); 624 625 const_iterator 626 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 627 const _Key& __k) const; 628 629 public: 630 // allocation/deallocation 631 _Rb_tree() { } 632 633 _Rb_tree(const _Compare& __comp, 634 const allocator_type& __a = allocator_type()) 635 : _M_impl(__comp, __a) { } 636 637 _Rb_tree(const _Rb_tree& __x) 638 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) 639 { 640 if (__x._M_root() != 0) 641 { 642 _M_root() = _M_copy(__x._M_begin(), _M_end()); 643 _M_leftmost() = _S_minimum(_M_root()); 644 _M_rightmost() = _S_maximum(_M_root()); 645 _M_impl._M_node_count = __x._M_impl._M_node_count; 646 } 647 } 648 649 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 650 _Rb_tree(_Rb_tree&& __x); 651 #endif 652 653 ~_Rb_tree() 654 { _M_erase(_M_begin()); } 655 656 _Rb_tree& 657 operator=(const _Rb_tree& __x); 658 659 // Accessors. 660 _Compare 661 key_comp() const 662 { return _M_impl._M_key_compare; } 663 664 iterator 665 begin() 666 { 667 return iterator(static_cast<_Link_type> 668 (this->_M_impl._M_header._M_left)); 669 } 670 671 const_iterator 672 begin() const 673 { 674 return const_iterator(static_cast<_Const_Link_type> 675 (this->_M_impl._M_header._M_left)); 676 } 677 678 iterator 679 end() 680 { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); } 681 682 const_iterator 683 end() const 684 { 685 return const_iterator(static_cast<_Const_Link_type> 686 (&this->_M_impl._M_header)); 687 } 688 689 reverse_iterator 690 rbegin() 691 { return reverse_iterator(end()); } 692 693 const_reverse_iterator 694 rbegin() const 695 { return const_reverse_iterator(end()); } 696 697 reverse_iterator 698 rend() 699 { return reverse_iterator(begin()); } 700 701 const_reverse_iterator 702 rend() const 703 { return const_reverse_iterator(begin()); } 704 705 bool 706 empty() const 707 { return _M_impl._M_node_count == 0; } 708 709 size_type 710 size() const 711 { return _M_impl._M_node_count; } 712 713 size_type 714 max_size() const 715 { return _M_get_Node_allocator().max_size(); } 716 717 void 718 swap(_Rb_tree& __t); 719 720 // Insert/erase. 721 pair<iterator, bool> 722 _M_insert_unique(const value_type& __x); 723 724 iterator 725 _M_insert_equal(const value_type& __x); 726 727 iterator 728 _M_insert_unique_(const_iterator __position, const value_type& __x); 729 730 iterator 731 _M_insert_equal_(const_iterator __position, const value_type& __x); 732 733 template<typename _InputIterator> 734 void 735 _M_insert_unique(_InputIterator __first, _InputIterator __last); 736 737 template<typename _InputIterator> 738 void 739 _M_insert_equal(_InputIterator __first, _InputIterator __last); 740 741 void 742 erase(iterator __position); 743 744 void 745 erase(const_iterator __position); 746 747 size_type 748 erase(const key_type& __x); 749 750 void 751 erase(iterator __first, iterator __last); 752 753 void 754 erase(const_iterator __first, const_iterator __last); 755 756 void 757 erase(const key_type* __first, const key_type* __last); 758 759 void 760 clear() 761 { 762 _M_erase(_M_begin()); 763 _M_leftmost() = _M_end(); 764 _M_root() = 0; 765 _M_rightmost() = _M_end(); 766 _M_impl._M_node_count = 0; 767 } 768 769 // Set operations. 770 iterator 771 find(const key_type& __k); 772 773 const_iterator 774 find(const key_type& __k) const; 775 776 size_type 777 count(const key_type& __k) const; 778 779 iterator 780 lower_bound(const key_type& __k) 781 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 782 783 const_iterator 784 lower_bound(const key_type& __k) const 785 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 786 787 iterator 788 upper_bound(const key_type& __k) 789 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 790 791 const_iterator 792 upper_bound(const key_type& __k) const 793 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 794 795 pair<iterator, iterator> 796 equal_range(const key_type& __k); 797 798 pair<const_iterator, const_iterator> 799 equal_range(const key_type& __k) const; 800 801 // Debugging. 802 bool 803 __rb_verify() const; 804 }; 805 806 template<typename _Key, typename _Val, typename _KeyOfValue, 807 typename _Compare, typename _Alloc> 808 inline bool 809 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 810 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 811 { 812 return __x.size() == __y.size() 813 && std::equal(__x.begin(), __x.end(), __y.begin()); 814 } 815 816 template<typename _Key, typename _Val, typename _KeyOfValue, 817 typename _Compare, typename _Alloc> 818 inline bool 819 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 820 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 821 { 822 return std::lexicographical_compare(__x.begin(), __x.end(), 823 __y.begin(), __y.end()); 824 } 825 826 template<typename _Key, typename _Val, typename _KeyOfValue, 827 typename _Compare, typename _Alloc> 828 inline bool 829 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 830 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 831 { return !(__x == __y); } 832 833 template<typename _Key, typename _Val, typename _KeyOfValue, 834 typename _Compare, typename _Alloc> 835 inline bool 836 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 837 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 838 { return __y < __x; } 839 840 template<typename _Key, typename _Val, typename _KeyOfValue, 841 typename _Compare, typename _Alloc> 842 inline bool 843 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 844 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 845 { return !(__y < __x); } 846 847 template<typename _Key, typename _Val, typename _KeyOfValue, 848 typename _Compare, typename _Alloc> 849 inline bool 850 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 851 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 852 { return !(__x < __y); } 853 854 template<typename _Key, typename _Val, typename _KeyOfValue, 855 typename _Compare, typename _Alloc> 856 inline void 857 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 858 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 859 { __x.swap(__y); } 860 861 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 862 template<typename _Key, typename _Val, typename _KeyOfValue, 863 typename _Compare, typename _Alloc> 864 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 865 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x) 866 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) 867 { 868 if (__x._M_root() != 0) 869 { 870 _M_root() = __x._M_root(); 871 _M_leftmost() = __x._M_leftmost(); 872 _M_rightmost() = __x._M_rightmost(); 873 _M_root()->_M_parent = _M_end(); 874 875 __x._M_root() = 0; 876 __x._M_leftmost() = __x._M_end(); 877 __x._M_rightmost() = __x._M_end(); 878 879 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 880 __x._M_impl._M_node_count = 0; 881 } 882 } 883 #endif 884 885 template<typename _Key, typename _Val, typename _KeyOfValue, 886 typename _Compare, typename _Alloc> 887 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 888 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 889 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) 890 { 891 if (this != &__x) 892 { 893 // Note that _Key may be a constant type. 894 clear(); 895 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 896 if (__x._M_root() != 0) 897 { 898 _M_root() = _M_copy(__x._M_begin(), _M_end()); 899 _M_leftmost() = _S_minimum(_M_root()); 900 _M_rightmost() = _S_maximum(_M_root()); 901 _M_impl._M_node_count = __x._M_impl._M_node_count; 902 } 903 } 904 return *this; 905 } 906 907 template<typename _Key, typename _Val, typename _KeyOfValue, 908 typename _Compare, typename _Alloc> 909 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 910 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 911 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) 912 { 913 bool __insert_left = (__x != 0 || __p == _M_end() 914 || _M_impl._M_key_compare(_KeyOfValue()(__v), 915 _S_key(__p))); 916 917 _Link_type __z = _M_create_node(__v); 918 919 _Rb_tree_insert_and_rebalance(__insert_left, __z, 920 const_cast<_Base_ptr>(__p), 921 this->_M_impl._M_header); 922 ++_M_impl._M_node_count; 923 return iterator(__z); 924 } 925 926 template<typename _Key, typename _Val, typename _KeyOfValue, 927 typename _Compare, typename _Alloc> 928 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 929 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 930 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 931 { 932 bool __insert_left = (__x != 0 || __p == _M_end() 933 || !_M_impl._M_key_compare(_S_key(__p), 934 _KeyOfValue()(__v))); 935 936 _Link_type __z = _M_create_node(__v); 937 938 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 939 this->_M_impl._M_header); 940 ++_M_impl._M_node_count; 941 return iterator(__z); 942 } 943 944 template<typename _Key, typename _Val, typename _KeyOfValue, 945 typename _Compare, typename _Alloc> 946 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 947 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 948 _M_insert_equal_lower(const _Val& __v) 949 { 950 _Link_type __x = _M_begin(); 951 _Link_type __y = _M_end(); 952 while (__x != 0) 953 { 954 __y = __x; 955 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 956 _S_left(__x) : _S_right(__x); 957 } 958 return _M_insert_lower(__x, __y, __v); 959 } 960 961 template<typename _Key, typename _Val, typename _KoV, 962 typename _Compare, typename _Alloc> 963 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 964 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 965 _M_copy(_Const_Link_type __x, _Link_type __p) 966 { 967 // Structural copy. __x and __p must be non-null. 968 _Link_type __top = _M_clone_node(__x); 969 __top->_M_parent = __p; 970 971 __try 972 { 973 if (__x->_M_right) 974 __top->_M_right = _M_copy(_S_right(__x), __top); 975 __p = __top; 976 __x = _S_left(__x); 977 978 while (__x != 0) 979 { 980 _Link_type __y = _M_clone_node(__x); 981 __p->_M_left = __y; 982 __y->_M_parent = __p; 983 if (__x->_M_right) 984 __y->_M_right = _M_copy(_S_right(__x), __y); 985 __p = __y; 986 __x = _S_left(__x); 987 } 988 } 989 __catch(...) 990 { 991 _M_erase(__top); 992 __throw_exception_again; 993 } 994 return __top; 995 } 996 997 template<typename _Key, typename _Val, typename _KeyOfValue, 998 typename _Compare, typename _Alloc> 999 void 1000 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1001 _M_erase(_Link_type __x) 1002 { 1003 // Erase without rebalancing. 1004 while (__x != 0) 1005 { 1006 _M_erase(_S_right(__x)); 1007 _Link_type __y = _S_left(__x); 1008 _M_destroy_node(__x); 1009 __x = __y; 1010 } 1011 } 1012 1013 template<typename _Key, typename _Val, typename _KeyOfValue, 1014 typename _Compare, typename _Alloc> 1015 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1016 _Compare, _Alloc>::iterator 1017 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1018 _M_lower_bound(_Link_type __x, _Link_type __y, 1019 const _Key& __k) 1020 { 1021 while (__x != 0) 1022 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1023 __y = __x, __x = _S_left(__x); 1024 else 1025 __x = _S_right(__x); 1026 return iterator(__y); 1027 } 1028 1029 template<typename _Key, typename _Val, typename _KeyOfValue, 1030 typename _Compare, typename _Alloc> 1031 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1032 _Compare, _Alloc>::const_iterator 1033 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1034 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 1035 const _Key& __k) const 1036 { 1037 while (__x != 0) 1038 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1039 __y = __x, __x = _S_left(__x); 1040 else 1041 __x = _S_right(__x); 1042 return const_iterator(__y); 1043 } 1044 1045 template<typename _Key, typename _Val, typename _KeyOfValue, 1046 typename _Compare, typename _Alloc> 1047 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1048 _Compare, _Alloc>::iterator 1049 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1050 _M_upper_bound(_Link_type __x, _Link_type __y, 1051 const _Key& __k) 1052 { 1053 while (__x != 0) 1054 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1055 __y = __x, __x = _S_left(__x); 1056 else 1057 __x = _S_right(__x); 1058 return iterator(__y); 1059 } 1060 1061 template<typename _Key, typename _Val, typename _KeyOfValue, 1062 typename _Compare, typename _Alloc> 1063 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1064 _Compare, _Alloc>::const_iterator 1065 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1066 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 1067 const _Key& __k) const 1068 { 1069 while (__x != 0) 1070 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1071 __y = __x, __x = _S_left(__x); 1072 else 1073 __x = _S_right(__x); 1074 return const_iterator(__y); 1075 } 1076 1077 template<typename _Key, typename _Val, typename _KeyOfValue, 1078 typename _Compare, typename _Alloc> 1079 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1080 _Compare, _Alloc>::iterator, 1081 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1082 _Compare, _Alloc>::iterator> 1083 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1084 equal_range(const _Key& __k) 1085 { 1086 _Link_type __x = _M_begin(); 1087 _Link_type __y = _M_end(); 1088 while (__x != 0) 1089 { 1090 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1091 __x = _S_right(__x); 1092 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1093 __y = __x, __x = _S_left(__x); 1094 else 1095 { 1096 _Link_type __xu(__x), __yu(__y); 1097 __y = __x, __x = _S_left(__x); 1098 __xu = _S_right(__xu); 1099 return pair<iterator, 1100 iterator>(_M_lower_bound(__x, __y, __k), 1101 _M_upper_bound(__xu, __yu, __k)); 1102 } 1103 } 1104 return pair<iterator, iterator>(iterator(__y), 1105 iterator(__y)); 1106 } 1107 1108 template<typename _Key, typename _Val, typename _KeyOfValue, 1109 typename _Compare, typename _Alloc> 1110 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1111 _Compare, _Alloc>::const_iterator, 1112 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1113 _Compare, _Alloc>::const_iterator> 1114 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1115 equal_range(const _Key& __k) const 1116 { 1117 _Const_Link_type __x = _M_begin(); 1118 _Const_Link_type __y = _M_end(); 1119 while (__x != 0) 1120 { 1121 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1122 __x = _S_right(__x); 1123 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1124 __y = __x, __x = _S_left(__x); 1125 else 1126 { 1127 _Const_Link_type __xu(__x), __yu(__y); 1128 __y = __x, __x = _S_left(__x); 1129 __xu = _S_right(__xu); 1130 return pair<const_iterator, 1131 const_iterator>(_M_lower_bound(__x, __y, __k), 1132 _M_upper_bound(__xu, __yu, __k)); 1133 } 1134 } 1135 return pair<const_iterator, const_iterator>(const_iterator(__y), 1136 const_iterator(__y)); 1137 } 1138 1139 template<typename _Key, typename _Val, typename _KeyOfValue, 1140 typename _Compare, typename _Alloc> 1141 void 1142 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1143 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 1144 { 1145 if (_M_root() == 0) 1146 { 1147 if (__t._M_root() != 0) 1148 { 1149 _M_root() = __t._M_root(); 1150 _M_leftmost() = __t._M_leftmost(); 1151 _M_rightmost() = __t._M_rightmost(); 1152 _M_root()->_M_parent = _M_end(); 1153 1154 __t._M_root() = 0; 1155 __t._M_leftmost() = __t._M_end(); 1156 __t._M_rightmost() = __t._M_end(); 1157 } 1158 } 1159 else if (__t._M_root() == 0) 1160 { 1161 __t._M_root() = _M_root(); 1162 __t._M_leftmost() = _M_leftmost(); 1163 __t._M_rightmost() = _M_rightmost(); 1164 __t._M_root()->_M_parent = __t._M_end(); 1165 1166 _M_root() = 0; 1167 _M_leftmost() = _M_end(); 1168 _M_rightmost() = _M_end(); 1169 } 1170 else 1171 { 1172 std::swap(_M_root(),__t._M_root()); 1173 std::swap(_M_leftmost(),__t._M_leftmost()); 1174 std::swap(_M_rightmost(),__t._M_rightmost()); 1175 1176 _M_root()->_M_parent = _M_end(); 1177 __t._M_root()->_M_parent = __t._M_end(); 1178 } 1179 // No need to swap header's color as it does not change. 1180 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 1181 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 1182 1183 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1184 // 431. Swapping containers with unequal allocators. 1185 std::__alloc_swap<_Node_allocator>:: 1186 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); 1187 } 1188 1189 template<typename _Key, typename _Val, typename _KeyOfValue, 1190 typename _Compare, typename _Alloc> 1191 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1192 _Compare, _Alloc>::iterator, bool> 1193 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1194 _M_insert_unique(const _Val& __v) 1195 { 1196 _Link_type __x = _M_begin(); 1197 _Link_type __y = _M_end(); 1198 bool __comp = true; 1199 while (__x != 0) 1200 { 1201 __y = __x; 1202 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 1203 __x = __comp ? _S_left(__x) : _S_right(__x); 1204 } 1205 iterator __j = iterator(__y); 1206 if (__comp) 1207 { 1208 if (__j == begin()) 1209 return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); 1210 else 1211 --__j; 1212 } 1213 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 1214 return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); 1215 return pair<iterator, bool>(__j, false); 1216 } 1217 1218 template<typename _Key, typename _Val, typename _KeyOfValue, 1219 typename _Compare, typename _Alloc> 1220 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1221 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1222 _M_insert_equal(const _Val& __v) 1223 { 1224 _Link_type __x = _M_begin(); 1225 _Link_type __y = _M_end(); 1226 while (__x != 0) 1227 { 1228 __y = __x; 1229 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 1230 _S_left(__x) : _S_right(__x); 1231 } 1232 return _M_insert_(__x, __y, __v); 1233 } 1234 1235 template<typename _Key, typename _Val, typename _KeyOfValue, 1236 typename _Compare, typename _Alloc> 1237 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1238 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1239 _M_insert_unique_(const_iterator __position, const _Val& __v) 1240 { 1241 // end() 1242 if (__position._M_node == _M_end()) 1243 { 1244 if (size() > 0 1245 && _M_impl._M_key_compare(_S_key(_M_rightmost()), 1246 _KeyOfValue()(__v))) 1247 return _M_insert_(0, _M_rightmost(), __v); 1248 else 1249 return _M_insert_unique(__v).first; 1250 } 1251 else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1252 _S_key(__position._M_node))) 1253 { 1254 // First, try before... 1255 const_iterator __before = __position; 1256 if (__position._M_node == _M_leftmost()) // begin() 1257 return _M_insert_(_M_leftmost(), _M_leftmost(), __v); 1258 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 1259 _KeyOfValue()(__v))) 1260 { 1261 if (_S_right(__before._M_node) == 0) 1262 return _M_insert_(0, __before._M_node, __v); 1263 else 1264 return _M_insert_(__position._M_node, 1265 __position._M_node, __v); 1266 } 1267 else 1268 return _M_insert_unique(__v).first; 1269 } 1270 else if (_M_impl._M_key_compare(_S_key(__position._M_node), 1271 _KeyOfValue()(__v))) 1272 { 1273 // ... then try after. 1274 const_iterator __after = __position; 1275 if (__position._M_node == _M_rightmost()) 1276 return _M_insert_(0, _M_rightmost(), __v); 1277 else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1278 _S_key((++__after)._M_node))) 1279 { 1280 if (_S_right(__position._M_node) == 0) 1281 return _M_insert_(0, __position._M_node, __v); 1282 else 1283 return _M_insert_(__after._M_node, __after._M_node, __v); 1284 } 1285 else 1286 return _M_insert_unique(__v).first; 1287 } 1288 else 1289 // Equivalent keys. 1290 return iterator(static_cast<_Link_type> 1291 (const_cast<_Base_ptr>(__position._M_node))); 1292 } 1293 1294 template<typename _Key, typename _Val, typename _KeyOfValue, 1295 typename _Compare, typename _Alloc> 1296 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1297 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1298 _M_insert_equal_(const_iterator __position, const _Val& __v) 1299 { 1300 // end() 1301 if (__position._M_node == _M_end()) 1302 { 1303 if (size() > 0 1304 && !_M_impl._M_key_compare(_KeyOfValue()(__v), 1305 _S_key(_M_rightmost()))) 1306 return _M_insert_(0, _M_rightmost(), __v); 1307 else 1308 return _M_insert_equal(__v); 1309 } 1310 else if (!_M_impl._M_key_compare(_S_key(__position._M_node), 1311 _KeyOfValue()(__v))) 1312 { 1313 // First, try before... 1314 const_iterator __before = __position; 1315 if (__position._M_node == _M_leftmost()) // begin() 1316 return _M_insert_(_M_leftmost(), _M_leftmost(), __v); 1317 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 1318 _S_key((--__before)._M_node))) 1319 { 1320 if (_S_right(__before._M_node) == 0) 1321 return _M_insert_(0, __before._M_node, __v); 1322 else 1323 return _M_insert_(__position._M_node, 1324 __position._M_node, __v); 1325 } 1326 else 1327 return _M_insert_equal(__v); 1328 } 1329 else 1330 { 1331 // ... then try after. 1332 const_iterator __after = __position; 1333 if (__position._M_node == _M_rightmost()) 1334 return _M_insert_(0, _M_rightmost(), __v); 1335 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), 1336 _KeyOfValue()(__v))) 1337 { 1338 if (_S_right(__position._M_node) == 0) 1339 return _M_insert_(0, __position._M_node, __v); 1340 else 1341 return _M_insert_(__after._M_node, __after._M_node, __v); 1342 } 1343 else 1344 return _M_insert_equal_lower(__v); 1345 } 1346 } 1347 1348 template<typename _Key, typename _Val, typename _KoV, 1349 typename _Cmp, typename _Alloc> 1350 template<class _II> 1351 void 1352 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1353 _M_insert_unique(_II __first, _II __last) 1354 { 1355 for (; __first != __last; ++__first) 1356 _M_insert_unique_(end(), *__first); 1357 } 1358 1359 template<typename _Key, typename _Val, typename _KoV, 1360 typename _Cmp, typename _Alloc> 1361 template<class _II> 1362 void 1363 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1364 _M_insert_equal(_II __first, _II __last) 1365 { 1366 for (; __first != __last; ++__first) 1367 _M_insert_equal_(end(), *__first); 1368 } 1369 1370 template<typename _Key, typename _Val, typename _KeyOfValue, 1371 typename _Compare, typename _Alloc> 1372 inline void 1373 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1374 erase(iterator __position) 1375 { 1376 _Link_type __y = 1377 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1378 (__position._M_node, 1379 this->_M_impl._M_header)); 1380 _M_destroy_node(__y); 1381 --_M_impl._M_node_count; 1382 } 1383 1384 template<typename _Key, typename _Val, typename _KeyOfValue, 1385 typename _Compare, typename _Alloc> 1386 inline void 1387 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1388 erase(const_iterator __position) 1389 { 1390 _Link_type __y = 1391 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1392 (const_cast<_Base_ptr>(__position._M_node), 1393 this->_M_impl._M_header)); 1394 _M_destroy_node(__y); 1395 --_M_impl._M_node_count; 1396 } 1397 1398 template<typename _Key, typename _Val, typename _KeyOfValue, 1399 typename _Compare, typename _Alloc> 1400 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1401 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1402 erase(const _Key& __x) 1403 { 1404 pair<iterator, iterator> __p = equal_range(__x); 1405 const size_type __old_size = size(); 1406 erase(__p.first, __p.second); 1407 return __old_size - size(); 1408 } 1409 1410 template<typename _Key, typename _Val, typename _KeyOfValue, 1411 typename _Compare, typename _Alloc> 1412 void 1413 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1414 erase(iterator __first, iterator __last) 1415 { 1416 if (__first == begin() && __last == end()) 1417 clear(); 1418 else 1419 while (__first != __last) 1420 erase(__first++); 1421 } 1422 1423 template<typename _Key, typename _Val, typename _KeyOfValue, 1424 typename _Compare, typename _Alloc> 1425 void 1426 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1427 erase(const_iterator __first, const_iterator __last) 1428 { 1429 if (__first == begin() && __last == end()) 1430 clear(); 1431 else 1432 while (__first != __last) 1433 erase(__first++); 1434 } 1435 1436 template<typename _Key, typename _Val, typename _KeyOfValue, 1437 typename _Compare, typename _Alloc> 1438 void 1439 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1440 erase(const _Key* __first, const _Key* __last) 1441 { 1442 while (__first != __last) 1443 erase(*__first++); 1444 } 1445 1446 template<typename _Key, typename _Val, typename _KeyOfValue, 1447 typename _Compare, typename _Alloc> 1448 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1449 _Compare, _Alloc>::iterator 1450 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1451 find(const _Key& __k) 1452 { 1453 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1454 return (__j == end() 1455 || _M_impl._M_key_compare(__k, 1456 _S_key(__j._M_node))) ? end() : __j; 1457 } 1458 1459 template<typename _Key, typename _Val, typename _KeyOfValue, 1460 typename _Compare, typename _Alloc> 1461 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1462 _Compare, _Alloc>::const_iterator 1463 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1464 find(const _Key& __k) const 1465 { 1466 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1467 return (__j == end() 1468 || _M_impl._M_key_compare(__k, 1469 _S_key(__j._M_node))) ? end() : __j; 1470 } 1471 1472 template<typename _Key, typename _Val, typename _KeyOfValue, 1473 typename _Compare, typename _Alloc> 1474 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1475 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1476 count(const _Key& __k) const 1477 { 1478 pair<const_iterator, const_iterator> __p = equal_range(__k); 1479 const size_type __n = std::distance(__p.first, __p.second); 1480 return __n; 1481 } 1482 1483 unsigned int 1484 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 1485 const _Rb_tree_node_base* __root); 1486 1487 template<typename _Key, typename _Val, typename _KeyOfValue, 1488 typename _Compare, typename _Alloc> 1489 bool 1490 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 1491 { 1492 if (_M_impl._M_node_count == 0 || begin() == end()) 1493 return _M_impl._M_node_count == 0 && begin() == end() 1494 && this->_M_impl._M_header._M_left == _M_end() 1495 && this->_M_impl._M_header._M_right == _M_end(); 1496 1497 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 1498 for (const_iterator __it = begin(); __it != end(); ++__it) 1499 { 1500 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 1501 _Const_Link_type __L = _S_left(__x); 1502 _Const_Link_type __R = _S_right(__x); 1503 1504 if (__x->_M_color == _S_red) 1505 if ((__L && __L->_M_color == _S_red) 1506 || (__R && __R->_M_color == _S_red)) 1507 return false; 1508 1509 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 1510 return false; 1511 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 1512 return false; 1513 1514 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 1515 return false; 1516 } 1517 1518 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 1519 return false; 1520 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 1521 return false; 1522 return true; 1523 } 1524 1525 _GLIBCXX_END_NAMESPACE 1526 1527 #endif 1528
