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