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