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