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 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 719 swap(_Rb_tree&& __t); 720 #else 721 swap(_Rb_tree& __t); 722 #endif 723 724 // Insert/erase. 725 pair<iterator, bool> 726 _M_insert_unique(const value_type& __x); 727 728 iterator 729 _M_insert_equal(const value_type& __x); 730 731 iterator 732 _M_insert_unique_(const_iterator __position, const value_type& __x); 733 734 iterator 735 _M_insert_equal_(const_iterator __position, const value_type& __x); 736 737 template<typename _InputIterator> 738 void 739 _M_insert_unique(_InputIterator __first, _InputIterator __last); 740 741 template<typename _InputIterator> 742 void 743 _M_insert_equal(_InputIterator __first, _InputIterator __last); 744 745 void 746 erase(iterator __position); 747 748 void 749 erase(const_iterator __position); 750 751 size_type 752 erase(const key_type& __x); 753 754 void 755 erase(iterator __first, iterator __last); 756 757 void 758 erase(const_iterator __first, const_iterator __last); 759 760 void 761 erase(const key_type* __first, const key_type* __last); 762 763 void 764 clear() 765 { 766 _M_erase(_M_begin()); 767 _M_leftmost() = _M_end(); 768 _M_root() = 0; 769 _M_rightmost() = _M_end(); 770 _M_impl._M_node_count = 0; 771 } 772 773 // Set operations. 774 iterator 775 find(const key_type& __k); 776 777 const_iterator 778 find(const key_type& __k) const; 779 780 size_type 781 count(const key_type& __k) const; 782 783 iterator 784 lower_bound(const key_type& __k) 785 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 786 787 const_iterator 788 lower_bound(const key_type& __k) const 789 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 790 791 iterator 792 upper_bound(const key_type& __k) 793 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 794 795 const_iterator 796 upper_bound(const key_type& __k) const 797 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 798 799 pair<iterator, iterator> 800 equal_range(const key_type& __k); 801 802 pair<const_iterator, const_iterator> 803 equal_range(const key_type& __k) const; 804 805 // Debugging. 806 bool 807 __rb_verify() const; 808 }; 809 810 template<typename _Key, typename _Val, typename _KeyOfValue, 811 typename _Compare, typename _Alloc> 812 inline bool 813 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 814 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 815 { 816 return __x.size() == __y.size() 817 && std::equal(__x.begin(), __x.end(), __y.begin()); 818 } 819 820 template<typename _Key, typename _Val, typename _KeyOfValue, 821 typename _Compare, typename _Alloc> 822 inline bool 823 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 824 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 825 { 826 return std::lexicographical_compare(__x.begin(), __x.end(), 827 __y.begin(), __y.end()); 828 } 829 830 template<typename _Key, typename _Val, typename _KeyOfValue, 831 typename _Compare, typename _Alloc> 832 inline bool 833 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 834 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 835 { return !(__x == __y); } 836 837 template<typename _Key, typename _Val, typename _KeyOfValue, 838 typename _Compare, typename _Alloc> 839 inline bool 840 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 841 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 842 { return __y < __x; } 843 844 template<typename _Key, typename _Val, typename _KeyOfValue, 845 typename _Compare, typename _Alloc> 846 inline bool 847 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 848 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 849 { return !(__y < __x); } 850 851 template<typename _Key, typename _Val, typename _KeyOfValue, 852 typename _Compare, typename _Alloc> 853 inline bool 854 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 855 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 856 { return !(__x < __y); } 857 858 template<typename _Key, typename _Val, typename _KeyOfValue, 859 typename _Compare, typename _Alloc> 860 inline void 861 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 862 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 863 { __x.swap(__y); } 864 865 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 866 template<typename _Key, typename _Val, typename _KeyOfValue, 867 typename _Compare, typename _Alloc> 868 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 869 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x) 870 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) 871 { 872 if (__x._M_root() != 0) 873 { 874 _M_root() = __x._M_root(); 875 _M_leftmost() = __x._M_leftmost(); 876 _M_rightmost() = __x._M_rightmost(); 877 _M_root()->_M_parent = _M_end(); 878 879 __x._M_root() = 0; 880 __x._M_leftmost() = __x._M_end(); 881 __x._M_rightmost() = __x._M_end(); 882 883 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 884 __x._M_impl._M_node_count = 0; 885 } 886 } 887 #endif 888 889 template<typename _Key, typename _Val, typename _KeyOfValue, 890 typename _Compare, typename _Alloc> 891 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 892 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 893 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) 894 { 895 if (this != &__x) 896 { 897 // Note that _Key may be a constant type. 898 clear(); 899 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 900 if (__x._M_root() != 0) 901 { 902 _M_root() = _M_copy(__x._M_begin(), _M_end()); 903 _M_leftmost() = _S_minimum(_M_root()); 904 _M_rightmost() = _S_maximum(_M_root()); 905 _M_impl._M_node_count = __x._M_impl._M_node_count; 906 } 907 } 908 return *this; 909 } 910 911 template<typename _Key, typename _Val, typename _KeyOfValue, 912 typename _Compare, typename _Alloc> 913 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 914 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 915 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) 916 { 917 bool __insert_left = (__x != 0 || __p == _M_end() 918 || _M_impl._M_key_compare(_KeyOfValue()(__v), 919 _S_key(__p))); 920 921 _Link_type __z = _M_create_node(__v); 922 923 _Rb_tree_insert_and_rebalance(__insert_left, __z, 924 const_cast<_Base_ptr>(__p), 925 this->_M_impl._M_header); 926 ++_M_impl._M_node_count; 927 return iterator(__z); 928 } 929 930 template<typename _Key, typename _Val, typename _KeyOfValue, 931 typename _Compare, typename _Alloc> 932 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 933 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 934 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 935 { 936 bool __insert_left = (__x != 0 || __p == _M_end() 937 || !_M_impl._M_key_compare(_S_key(__p), 938 _KeyOfValue()(__v))); 939 940 _Link_type __z = _M_create_node(__v); 941 942 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 943 this->_M_impl._M_header); 944 ++_M_impl._M_node_count; 945 return iterator(__z); 946 } 947 948 template<typename _Key, typename _Val, typename _KeyOfValue, 949 typename _Compare, typename _Alloc> 950 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 951 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 952 _M_insert_equal_lower(const _Val& __v) 953 { 954 _Link_type __x = _M_begin(); 955 _Link_type __y = _M_end(); 956 while (__x != 0) 957 { 958 __y = __x; 959 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 960 _S_left(__x) : _S_right(__x); 961 } 962 return _M_insert_lower(__x, __y, __v); 963 } 964 965 template<typename _Key, typename _Val, typename _KoV, 966 typename _Compare, typename _Alloc> 967 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 968 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 969 _M_copy(_Const_Link_type __x, _Link_type __p) 970 { 971 // Structural copy. __x and __p must be non-null. 972 _Link_type __top = _M_clone_node(__x); 973 __top->_M_parent = __p; 974 975 __try 976 { 977 if (__x->_M_right) 978 __top->_M_right = _M_copy(_S_right(__x), __top); 979 __p = __top; 980 __x = _S_left(__x); 981 982 while (__x != 0) 983 { 984 _Link_type __y = _M_clone_node(__x); 985 __p->_M_left = __y; 986 __y->_M_parent = __p; 987 if (__x->_M_right) 988 __y->_M_right = _M_copy(_S_right(__x), __y); 989 __p = __y; 990 __x = _S_left(__x); 991 } 992 } 993 __catch(...) 994 { 995 _M_erase(__top); 996 __throw_exception_again; 997 } 998 return __top; 999 } 1000 1001 template<typename _Key, typename _Val, typename _KeyOfValue, 1002 typename _Compare, typename _Alloc> 1003 void 1004 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1005 _M_erase(_Link_type __x) 1006 { 1007 // Erase without rebalancing. 1008 while (__x != 0) 1009 { 1010 _M_erase(_S_right(__x)); 1011 _Link_type __y = _S_left(__x); 1012 _M_destroy_node(__x); 1013 __x = __y; 1014 } 1015 } 1016 1017 template<typename _Key, typename _Val, typename _KeyOfValue, 1018 typename _Compare, typename _Alloc> 1019 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1020 _Compare, _Alloc>::iterator 1021 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1022 _M_lower_bound(_Link_type __x, _Link_type __y, 1023 const _Key& __k) 1024 { 1025 while (__x != 0) 1026 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1027 __y = __x, __x = _S_left(__x); 1028 else 1029 __x = _S_right(__x); 1030 return iterator(__y); 1031 } 1032 1033 template<typename _Key, typename _Val, typename _KeyOfValue, 1034 typename _Compare, typename _Alloc> 1035 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1036 _Compare, _Alloc>::const_iterator 1037 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1038 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 1039 const _Key& __k) const 1040 { 1041 while (__x != 0) 1042 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1043 __y = __x, __x = _S_left(__x); 1044 else 1045 __x = _S_right(__x); 1046 return const_iterator(__y); 1047 } 1048 1049 template<typename _Key, typename _Val, typename _KeyOfValue, 1050 typename _Compare, typename _Alloc> 1051 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1052 _Compare, _Alloc>::iterator 1053 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1054 _M_upper_bound(_Link_type __x, _Link_type __y, 1055 const _Key& __k) 1056 { 1057 while (__x != 0) 1058 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1059 __y = __x, __x = _S_left(__x); 1060 else 1061 __x = _S_right(__x); 1062 return iterator(__y); 1063 } 1064 1065 template<typename _Key, typename _Val, typename _KeyOfValue, 1066 typename _Compare, typename _Alloc> 1067 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1068 _Compare, _Alloc>::const_iterator 1069 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1070 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 1071 const _Key& __k) const 1072 { 1073 while (__x != 0) 1074 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1075 __y = __x, __x = _S_left(__x); 1076 else 1077 __x = _S_right(__x); 1078 return const_iterator(__y); 1079 } 1080 1081 template<typename _Key, typename _Val, typename _KeyOfValue, 1082 typename _Compare, typename _Alloc> 1083 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1084 _Compare, _Alloc>::iterator, 1085 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1086 _Compare, _Alloc>::iterator> 1087 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1088 equal_range(const _Key& __k) 1089 { 1090 _Link_type __x = _M_begin(); 1091 _Link_type __y = _M_end(); 1092 while (__x != 0) 1093 { 1094 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1095 __x = _S_right(__x); 1096 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1097 __y = __x, __x = _S_left(__x); 1098 else 1099 { 1100 _Link_type __xu(__x), __yu(__y); 1101 __y = __x, __x = _S_left(__x); 1102 __xu = _S_right(__xu); 1103 return pair<iterator, 1104 iterator>(_M_lower_bound(__x, __y, __k), 1105 _M_upper_bound(__xu, __yu, __k)); 1106 } 1107 } 1108 return pair<iterator, iterator>(iterator(__y), 1109 iterator(__y)); 1110 } 1111 1112 template<typename _Key, typename _Val, typename _KeyOfValue, 1113 typename _Compare, typename _Alloc> 1114 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1115 _Compare, _Alloc>::const_iterator, 1116 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1117 _Compare, _Alloc>::const_iterator> 1118 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1119 equal_range(const _Key& __k) const 1120 { 1121 _Const_Link_type __x = _M_begin(); 1122 _Const_Link_type __y = _M_end(); 1123 while (__x != 0) 1124 { 1125 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1126 __x = _S_right(__x); 1127 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1128 __y = __x, __x = _S_left(__x); 1129 else 1130 { 1131 _Const_Link_type __xu(__x), __yu(__y); 1132 __y = __x, __x = _S_left(__x); 1133 __xu = _S_right(__xu); 1134 return pair<const_iterator, 1135 const_iterator>(_M_lower_bound(__x, __y, __k), 1136 _M_upper_bound(__xu, __yu, __k)); 1137 } 1138 } 1139 return pair<const_iterator, const_iterator>(const_iterator(__y), 1140 const_iterator(__y)); 1141 } 1142 1143 template<typename _Key, typename _Val, typename _KeyOfValue, 1144 typename _Compare, typename _Alloc> 1145 void 1146 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1147 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1148 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __t) 1149 #else 1150 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 1151 #endif 1152 { 1153 if (_M_root() == 0) 1154 { 1155 if (__t._M_root() != 0) 1156 { 1157 _M_root() = __t._M_root(); 1158 _M_leftmost() = __t._M_leftmost(); 1159 _M_rightmost() = __t._M_rightmost(); 1160 _M_root()->_M_parent = _M_end(); 1161 1162 __t._M_root() = 0; 1163 __t._M_leftmost() = __t._M_end(); 1164 __t._M_rightmost() = __t._M_end(); 1165 } 1166 } 1167 else if (__t._M_root() == 0) 1168 { 1169 __t._M_root() = _M_root(); 1170 __t._M_leftmost() = _M_leftmost(); 1171 __t._M_rightmost() = _M_rightmost(); 1172 __t._M_root()->_M_parent = __t._M_end(); 1173 1174 _M_root() = 0; 1175 _M_leftmost() = _M_end(); 1176 _M_rightmost() = _M_end(); 1177 } 1178 else 1179 { 1180 std::swap(_M_root(),__t._M_root()); 1181 std::swap(_M_leftmost(),__t._M_leftmost()); 1182 std::swap(_M_rightmost(),__t._M_rightmost()); 1183 1184 _M_root()->_M_parent = _M_end(); 1185 __t._M_root()->_M_parent = __t._M_end(); 1186 } 1187 // No need to swap header's color as it does not change. 1188 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 1189 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 1190 1191 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1192 // 431. Swapping containers with unequal allocators. 1193 std::__alloc_swap<_Node_allocator>:: 1194 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); 1195 } 1196 1197 template<typename _Key, typename _Val, typename _KeyOfValue, 1198 typename _Compare, typename _Alloc> 1199 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1200 _Compare, _Alloc>::iterator, bool> 1201 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1202 _M_insert_unique(const _Val& __v) 1203 { 1204 _Link_type __x = _M_begin(); 1205 _Link_type __y = _M_end(); 1206 bool __comp = true; 1207 while (__x != 0) 1208 { 1209 __y = __x; 1210 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 1211 __x = __comp ? _S_left(__x) : _S_right(__x); 1212 } 1213 iterator __j = iterator(__y); 1214 if (__comp) 1215 { 1216 if (__j == begin()) 1217 return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); 1218 else 1219 --__j; 1220 } 1221 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 1222 return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); 1223 return pair<iterator, bool>(__j, false); 1224 } 1225 1226 template<typename _Key, typename _Val, typename _KeyOfValue, 1227 typename _Compare, typename _Alloc> 1228 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1229 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1230 _M_insert_equal(const _Val& __v) 1231 { 1232 _Link_type __x = _M_begin(); 1233 _Link_type __y = _M_end(); 1234 while (__x != 0) 1235 { 1236 __y = __x; 1237 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 1238 _S_left(__x) : _S_right(__x); 1239 } 1240 return _M_insert_(__x, __y, __v); 1241 } 1242 1243 template<typename _Key, typename _Val, typename _KeyOfValue, 1244 typename _Compare, typename _Alloc> 1245 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1246 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1247 _M_insert_unique_(const_iterator __position, const _Val& __v) 1248 { 1249 // end() 1250 if (__position._M_node == _M_end()) 1251 { 1252 if (size() > 0 1253 && _M_impl._M_key_compare(_S_key(_M_rightmost()), 1254 _KeyOfValue()(__v))) 1255 return _M_insert_(0, _M_rightmost(), __v); 1256 else 1257 return _M_insert_unique(__v).first; 1258 } 1259 else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1260 _S_key(__position._M_node))) 1261 { 1262 // First, try before... 1263 const_iterator __before = __position; 1264 if (__position._M_node == _M_leftmost()) // begin() 1265 return _M_insert_(_M_leftmost(), _M_leftmost(), __v); 1266 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 1267 _KeyOfValue()(__v))) 1268 { 1269 if (_S_right(__before._M_node) == 0) 1270 return _M_insert_(0, __before._M_node, __v); 1271 else 1272 return _M_insert_(__position._M_node, 1273 __position._M_node, __v); 1274 } 1275 else 1276 return _M_insert_unique(__v).first; 1277 } 1278 else if (_M_impl._M_key_compare(_S_key(__position._M_node), 1279 _KeyOfValue()(__v))) 1280 { 1281 // ... then try after. 1282 const_iterator __after = __position; 1283 if (__position._M_node == _M_rightmost()) 1284 return _M_insert_(0, _M_rightmost(), __v); 1285 else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 1286 _S_key((++__after)._M_node))) 1287 { 1288 if (_S_right(__position._M_node) == 0) 1289 return _M_insert_(0, __position._M_node, __v); 1290 else 1291 return _M_insert_(__after._M_node, __after._M_node, __v); 1292 } 1293 else 1294 return _M_insert_unique(__v).first; 1295 } 1296 else 1297 // Equivalent keys. 1298 return iterator(static_cast<_Link_type> 1299 (const_cast<_Base_ptr>(__position._M_node))); 1300 } 1301 1302 template<typename _Key, typename _Val, typename _KeyOfValue, 1303 typename _Compare, typename _Alloc> 1304 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1305 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1306 _M_insert_equal_(const_iterator __position, const _Val& __v) 1307 { 1308 // end() 1309 if (__position._M_node == _M_end()) 1310 { 1311 if (size() > 0 1312 && !_M_impl._M_key_compare(_KeyOfValue()(__v), 1313 _S_key(_M_rightmost()))) 1314 return _M_insert_(0, _M_rightmost(), __v); 1315 else 1316 return _M_insert_equal(__v); 1317 } 1318 else if (!_M_impl._M_key_compare(_S_key(__position._M_node), 1319 _KeyOfValue()(__v))) 1320 { 1321 // First, try before... 1322 const_iterator __before = __position; 1323 if (__position._M_node == _M_leftmost()) // begin() 1324 return _M_insert_(_M_leftmost(), _M_leftmost(), __v); 1325 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 1326 _S_key((--__before)._M_node))) 1327 { 1328 if (_S_right(__before._M_node) == 0) 1329 return _M_insert_(0, __before._M_node, __v); 1330 else 1331 return _M_insert_(__position._M_node, 1332 __position._M_node, __v); 1333 } 1334 else 1335 return _M_insert_equal(__v); 1336 } 1337 else 1338 { 1339 // ... then try after. 1340 const_iterator __after = __position; 1341 if (__position._M_node == _M_rightmost()) 1342 return _M_insert_(0, _M_rightmost(), __v); 1343 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), 1344 _KeyOfValue()(__v))) 1345 { 1346 if (_S_right(__position._M_node) == 0) 1347 return _M_insert_(0, __position._M_node, __v); 1348 else 1349 return _M_insert_(__after._M_node, __after._M_node, __v); 1350 } 1351 else 1352 return _M_insert_equal_lower(__v); 1353 } 1354 } 1355 1356 template<typename _Key, typename _Val, typename _KoV, 1357 typename _Cmp, typename _Alloc> 1358 template<class _II> 1359 void 1360 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1361 _M_insert_unique(_II __first, _II __last) 1362 { 1363 for (; __first != __last; ++__first) 1364 _M_insert_unique_(end(), *__first); 1365 } 1366 1367 template<typename _Key, typename _Val, typename _KoV, 1368 typename _Cmp, typename _Alloc> 1369 template<class _II> 1370 void 1371 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1372 _M_insert_equal(_II __first, _II __last) 1373 { 1374 for (; __first != __last; ++__first) 1375 _M_insert_equal_(end(), *__first); 1376 } 1377 1378 template<typename _Key, typename _Val, typename _KeyOfValue, 1379 typename _Compare, typename _Alloc> 1380 inline void 1381 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1382 erase(iterator __position) 1383 { 1384 _Link_type __y = 1385 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1386 (__position._M_node, 1387 this->_M_impl._M_header)); 1388 _M_destroy_node(__y); 1389 --_M_impl._M_node_count; 1390 } 1391 1392 template<typename _Key, typename _Val, typename _KeyOfValue, 1393 typename _Compare, typename _Alloc> 1394 inline void 1395 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1396 erase(const_iterator __position) 1397 { 1398 _Link_type __y = 1399 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1400 (const_cast<_Base_ptr>(__position._M_node), 1401 this->_M_impl._M_header)); 1402 _M_destroy_node(__y); 1403 --_M_impl._M_node_count; 1404 } 1405 1406 template<typename _Key, typename _Val, typename _KeyOfValue, 1407 typename _Compare, typename _Alloc> 1408 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1409 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1410 erase(const _Key& __x) 1411 { 1412 pair<iterator, iterator> __p = equal_range(__x); 1413 const size_type __old_size = size(); 1414 erase(__p.first, __p.second); 1415 return __old_size - size(); 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 erase(iterator __first, iterator __last) 1423 { 1424 if (__first == begin() && __last == end()) 1425 clear(); 1426 else 1427 while (__first != __last) 1428 erase(__first++); 1429 } 1430 1431 template<typename _Key, typename _Val, typename _KeyOfValue, 1432 typename _Compare, typename _Alloc> 1433 void 1434 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1435 erase(const_iterator __first, const_iterator __last) 1436 { 1437 if (__first == begin() && __last == end()) 1438 clear(); 1439 else 1440 while (__first != __last) 1441 erase(__first++); 1442 } 1443 1444 template<typename _Key, typename _Val, typename _KeyOfValue, 1445 typename _Compare, typename _Alloc> 1446 void 1447 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1448 erase(const _Key* __first, const _Key* __last) 1449 { 1450 while (__first != __last) 1451 erase(*__first++); 1452 } 1453 1454 template<typename _Key, typename _Val, typename _KeyOfValue, 1455 typename _Compare, typename _Alloc> 1456 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1457 _Compare, _Alloc>::iterator 1458 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1459 find(const _Key& __k) 1460 { 1461 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1462 return (__j == end() 1463 || _M_impl._M_key_compare(__k, 1464 _S_key(__j._M_node))) ? end() : __j; 1465 } 1466 1467 template<typename _Key, typename _Val, typename _KeyOfValue, 1468 typename _Compare, typename _Alloc> 1469 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1470 _Compare, _Alloc>::const_iterator 1471 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1472 find(const _Key& __k) const 1473 { 1474 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1475 return (__j == end() 1476 || _M_impl._M_key_compare(__k, 1477 _S_key(__j._M_node))) ? end() : __j; 1478 } 1479 1480 template<typename _Key, typename _Val, typename _KeyOfValue, 1481 typename _Compare, typename _Alloc> 1482 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1483 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1484 count(const _Key& __k) const 1485 { 1486 pair<const_iterator, const_iterator> __p = equal_range(__k); 1487 const size_type __n = std::distance(__p.first, __p.second); 1488 return __n; 1489 } 1490 1491 unsigned int 1492 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 1493 const _Rb_tree_node_base* __root); 1494 1495 template<typename _Key, typename _Val, typename _KeyOfValue, 1496 typename _Compare, typename _Alloc> 1497 bool 1498 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 1499 { 1500 if (_M_impl._M_node_count == 0 || begin() == end()) 1501 return _M_impl._M_node_count == 0 && begin() == end() 1502 && this->_M_impl._M_header._M_left == _M_end() 1503 && this->_M_impl._M_header._M_right == _M_end(); 1504 1505 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 1506 for (const_iterator __it = begin(); __it != end(); ++__it) 1507 { 1508 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 1509 _Const_Link_type __L = _S_left(__x); 1510 _Const_Link_type __R = _S_right(__x); 1511 1512 if (__x->_M_color == _S_red) 1513 if ((__L && __L->_M_color == _S_red) 1514 || (__R && __R->_M_color == _S_red)) 1515 return false; 1516 1517 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 1518 return false; 1519 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 1520 return false; 1521 1522 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 1523 return false; 1524 } 1525 1526 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 1527 return false; 1528 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 1529 return false; 1530 return true; 1531 } 1532 1533 _GLIBCXX_END_NAMESPACE 1534 1535 #endif 1536
