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