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