stl_tree.h revision 146897
1// RB tree implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005 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 : _M_node() { } 166 167 _Rb_tree_iterator(_Link_type __x) 168 : _M_node(__x) { } 169 170 reference 171 operator*() const 172 { return static_cast<_Link_type>(_M_node)->_M_value_field; } 173 174 pointer 175 operator->() const 176 { return &static_cast<_Link_type>(_M_node)->_M_value_field; } 177 178 _Self& 179 operator++() 180 { 181 _M_node = _Rb_tree_increment(_M_node); 182 return *this; 183 } 184 185 _Self 186 operator++(int) 187 { 188 _Self __tmp = *this; 189 _M_node = _Rb_tree_increment(_M_node); 190 return __tmp; 191 } 192 193 _Self& 194 operator--() 195 { 196 _M_node = _Rb_tree_decrement(_M_node); 197 return *this; 198 } 199 200 _Self 201 operator--(int) 202 { 203 _Self __tmp = *this; 204 _M_node = _Rb_tree_decrement(_M_node); 205 return __tmp; 206 } 207 208 bool 209 operator==(const _Self& __x) const 210 { return _M_node == __x._M_node; } 211 212 bool 213 operator!=(const _Self& __x) const 214 { return _M_node != __x._M_node; } 215 216 _Base_ptr _M_node; 217 }; 218 219 template<typename _Tp> 220 struct _Rb_tree_const_iterator 221 { 222 typedef _Tp value_type; 223 typedef const _Tp& reference; 224 typedef const _Tp* pointer; 225 226 typedef _Rb_tree_iterator<_Tp> iterator; 227 228 typedef bidirectional_iterator_tag iterator_category; 229 typedef ptrdiff_t difference_type; 230 231 typedef _Rb_tree_const_iterator<_Tp> _Self; 232 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 233 typedef const _Rb_tree_node<_Tp>* _Link_type; 234 235 _Rb_tree_const_iterator() 236 : _M_node() { } 237 238 _Rb_tree_const_iterator(_Link_type __x) 239 : _M_node(__x) { } 240 241 _Rb_tree_const_iterator(const iterator& __it) 242 : _M_node(__it._M_node) { } 243 244 reference 245 operator*() const 246 { return static_cast<_Link_type>(_M_node)->_M_value_field; } 247 248 pointer 249 operator->() const 250 { return &static_cast<_Link_type>(_M_node)->_M_value_field; } 251 252 _Self& 253 operator++() 254 { 255 _M_node = _Rb_tree_increment(_M_node); 256 return *this; 257 } 258 259 _Self 260 operator++(int) 261 { 262 _Self __tmp = *this; 263 _M_node = _Rb_tree_increment(_M_node); 264 return __tmp; 265 } 266 267 _Self& 268 operator--() 269 { 270 _M_node = _Rb_tree_decrement(_M_node); 271 return *this; 272 } 273 274 _Self 275 operator--(int) 276 { 277 _Self __tmp = *this; 278 _M_node = _Rb_tree_decrement(_M_node); 279 return __tmp; 280 } 281 282 bool 283 operator==(const _Self& __x) const 284 { return _M_node == __x._M_node; } 285 286 bool 287 operator!=(const _Self& __x) const 288 { return _M_node != __x._M_node; } 289 290 _Base_ptr _M_node; 291 }; 292 293 template<typename _Val> 294 inline bool 295 operator==(const _Rb_tree_iterator<_Val>& __x, 296 const _Rb_tree_const_iterator<_Val>& __y) 297 { return __x._M_node == __y._M_node; } 298 299 template<typename _Val> 300 inline bool 301 operator!=(const _Rb_tree_iterator<_Val>& __x, 302 const _Rb_tree_const_iterator<_Val>& __y) 303 { return __x._M_node != __y._M_node; } 304 305 void 306 _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 307 _Rb_tree_node_base*& __root); 308 309 void 310 _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 311 _Rb_tree_node_base*& __root); 312 313 void 314 _Rb_tree_insert_and_rebalance(const bool __insert_left, 315 _Rb_tree_node_base* __x, 316 _Rb_tree_node_base* __p, 317 _Rb_tree_node_base& __header); 318 319 _Rb_tree_node_base* 320 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 321 _Rb_tree_node_base& __header); 322 323 324 template<typename _Key, typename _Val, typename _KeyOfValue, 325 typename _Compare, typename _Alloc = allocator<_Val> > 326 class _Rb_tree 327 { 328 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other 329 _Node_allocator; 330 331 protected: 332 typedef _Rb_tree_node_base* _Base_ptr; 333 typedef const _Rb_tree_node_base* _Const_Base_ptr; 334 typedef _Rb_tree_node<_Val> _Rb_tree_node; 335 336 public: 337 typedef _Key key_type; 338 typedef _Val value_type; 339 typedef value_type* pointer; 340 typedef const value_type* const_pointer; 341 typedef value_type& reference; 342 typedef const value_type& const_reference; 343 typedef _Rb_tree_node* _Link_type; 344 typedef const _Rb_tree_node* _Const_Link_type; 345 typedef size_t size_type; 346 typedef ptrdiff_t difference_type; 347 typedef _Alloc allocator_type; 348 349 allocator_type 350 get_allocator() const 351 { return *static_cast<const _Node_allocator*>(&this->_M_impl); } 352 353 protected: 354 _Rb_tree_node* 355 _M_get_node() 356 { return _M_impl._Node_allocator::allocate(1); } 357 358 void 359 _M_put_node(_Rb_tree_node* __p) 360 { _M_impl._Node_allocator::deallocate(__p, 1); } 361 362 _Link_type 363 _M_create_node(const value_type& __x) 364 { 365 _Link_type __tmp = _M_get_node(); 366 try 367 { std::_Construct(&__tmp->_M_value_field, __x); } 368 catch(...) 369 { 370 _M_put_node(__tmp); 371 __throw_exception_again; 372 } 373 return __tmp; 374 } 375 376 _Link_type 377 _M_clone_node(_Const_Link_type __x) 378 { 379 _Link_type __tmp = _M_create_node(__x->_M_value_field); 380 __tmp->_M_color = __x->_M_color; 381 __tmp->_M_left = 0; 382 __tmp->_M_right = 0; 383 return __tmp; 384 } 385 386 void 387 destroy_node(_Link_type __p) 388 { 389 std::_Destroy(&__p->_M_value_field); 390 _M_put_node(__p); 391 } 392 393 protected: 394 template<typename _Key_compare, 395 bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type> 396 struct _Rb_tree_impl : public _Node_allocator 397 { 398 _Key_compare _M_key_compare; 399 _Rb_tree_node_base _M_header; 400 size_type _M_node_count; // Keeps track of size of tree. 401 402 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), 403 const _Key_compare& __comp = _Key_compare()) 404 : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0) 405 { 406 this->_M_header._M_color = _S_red; 407 this->_M_header._M_parent = 0; 408 this->_M_header._M_left = &this->_M_header; 409 this->_M_header._M_right = &this->_M_header; 410 } 411 }; 412 413 // Specialization for _Comparison types that are not capable of 414 // being base classes / super classes. 415 template<typename _Key_compare> 416 struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator 417 { 418 _Key_compare _M_key_compare; 419 _Rb_tree_node_base _M_header; 420 size_type _M_node_count; // Keeps track of size of tree. 421 422 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), 423 const _Key_compare& __comp = _Key_compare()) 424 : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0) 425 { 426 this->_M_header._M_color = _S_red; 427 this->_M_header._M_parent = 0; 428 this->_M_header._M_left = &this->_M_header; 429 this->_M_header._M_right = &this->_M_header; 430 } 431 }; 432 433 _Rb_tree_impl<_Compare> _M_impl; 434 435 protected: 436 _Base_ptr& 437 _M_root() 438 { return this->_M_impl._M_header._M_parent; } 439 440 _Const_Base_ptr 441 _M_root() const 442 { return this->_M_impl._M_header._M_parent; } 443 444 _Base_ptr& 445 _M_leftmost() 446 { return this->_M_impl._M_header._M_left; } 447 448 _Const_Base_ptr 449 _M_leftmost() const 450 { return this->_M_impl._M_header._M_left; } 451 452 _Base_ptr& 453 _M_rightmost() 454 { return this->_M_impl._M_header._M_right; } 455 456 _Const_Base_ptr 457 _M_rightmost() const 458 { return this->_M_impl._M_header._M_right; } 459 460 _Link_type 461 _M_begin() 462 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 463 464 _Const_Link_type 465 _M_begin() const 466 { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_parent); } 467 468 _Link_type 469 _M_end() 470 { return static_cast<_Link_type>(&this->_M_impl._M_header); } 471 472 _Const_Link_type 473 _M_end() const 474 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 475 476 static const_reference 477 _S_value(_Const_Link_type __x) 478 { return __x->_M_value_field; } 479 480 static const _Key& 481 _S_key(_Const_Link_type __x) 482 { return _KeyOfValue()(_S_value(__x)); } 483 484 static _Link_type 485 _S_left(_Base_ptr __x) 486 { return static_cast<_Link_type>(__x->_M_left); } 487 488 static _Const_Link_type 489 _S_left(_Const_Base_ptr __x) 490 { return static_cast<_Const_Link_type>(__x->_M_left); } 491 492 static _Link_type 493 _S_right(_Base_ptr __x) 494 { return static_cast<_Link_type>(__x->_M_right); } 495 496 static _Const_Link_type 497 _S_right(_Const_Base_ptr __x) 498 { return static_cast<_Const_Link_type>(__x->_M_right); } 499 500 static const_reference 501 _S_value(_Const_Base_ptr __x) 502 { return static_cast<_Const_Link_type>(__x)->_M_value_field; } 503 504 static const _Key& 505 _S_key(_Const_Base_ptr __x) 506 { return _KeyOfValue()(_S_value(__x)); } 507 508 static _Base_ptr 509 _S_minimum(_Base_ptr __x) 510 { return _Rb_tree_node_base::_S_minimum(__x); } 511 512 static _Const_Base_ptr 513 _S_minimum(_Const_Base_ptr __x) 514 { return _Rb_tree_node_base::_S_minimum(__x); } 515 516 static _Base_ptr 517 _S_maximum(_Base_ptr __x) 518 { return _Rb_tree_node_base::_S_maximum(__x); } 519 520 static _Const_Base_ptr 521 _S_maximum(_Const_Base_ptr __x) 522 { return _Rb_tree_node_base::_S_maximum(__x); } 523 524 public: 525 typedef _Rb_tree_iterator<value_type> iterator; 526 typedef _Rb_tree_const_iterator<value_type> const_iterator; 527 528 typedef std::reverse_iterator<iterator> reverse_iterator; 529 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 530 531 private: 532 iterator 533 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 534 535 _Link_type 536 _M_copy(_Const_Link_type __x, _Link_type __p); 537 538 void 539 _M_erase(_Link_type __x); 540 541 public: 542 // allocation/deallocation 543 _Rb_tree() 544 { } 545 546 _Rb_tree(const _Compare& __comp) 547 : _M_impl(allocator_type(), __comp) 548 { } 549 550 _Rb_tree(const _Compare& __comp, const allocator_type& __a) 551 : _M_impl(__a, __comp) 552 { } 553 554 _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) 555 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare) 556 { 557 if (__x._M_root() != 0) 558 { 559 _M_root() = _M_copy(__x._M_begin(), _M_end()); 560 _M_leftmost() = _S_minimum(_M_root()); 561 _M_rightmost() = _S_maximum(_M_root()); 562 _M_impl._M_node_count = __x._M_impl._M_node_count; 563 } 564 } 565 566 ~_Rb_tree() 567 { _M_erase(_M_begin()); } 568 569 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 570 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x); 571 572 // Accessors. 573 _Compare 574 key_comp() const 575 { return _M_impl._M_key_compare; } 576 577 iterator 578 begin() 579 { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); } 580 581 const_iterator 582 begin() const 583 { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); } 584 585 iterator 586 end() 587 { return static_cast<_Link_type>(&this->_M_impl._M_header); } 588 589 const_iterator 590 end() const 591 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 592 593 reverse_iterator 594 rbegin() 595 { return reverse_iterator(end()); } 596 597 const_reverse_iterator 598 rbegin() const 599 { return const_reverse_iterator(end()); } 600 601 reverse_iterator 602 rend() 603 { return reverse_iterator(begin()); } 604 605 const_reverse_iterator 606 rend() const 607 { return const_reverse_iterator(begin()); } 608 609 bool 610 empty() const 611 { return _M_impl._M_node_count == 0; } 612 613 size_type 614 size() const 615 { return _M_impl._M_node_count; } 616 617 size_type 618 max_size() const 619 { return size_type(-1); } 620 621 void 622 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t); 623 624 // Insert/erase. 625 pair<iterator,bool> 626 insert_unique(const value_type& __x); 627 628 iterator 629 insert_equal(const value_type& __x); 630 631 iterator 632 insert_unique(iterator __position, const value_type& __x); 633 634 iterator 635 insert_equal(iterator __position, const value_type& __x); 636 637 template<typename _InputIterator> 638 void 639 insert_unique(_InputIterator __first, _InputIterator __last); 640 641 template<typename _InputIterator> 642 void 643 insert_equal(_InputIterator __first, _InputIterator __last); 644 645 void 646 erase(iterator __position); 647 648 size_type 649 erase(const key_type& __x); 650 651 void 652 erase(iterator __first, iterator __last); 653 654 void 655 erase(const key_type* __first, const key_type* __last); 656 657 void 658 clear() 659 { 660 _M_erase(_M_begin()); 661 _M_leftmost() = _M_end(); 662 _M_root() = 0; 663 _M_rightmost() = _M_end(); 664 _M_impl._M_node_count = 0; 665 } 666 667 // Set operations. 668 iterator 669 find(const key_type& __x); 670 671 const_iterator 672 find(const key_type& __x) const; 673 674 size_type 675 count(const key_type& __x) const; 676 677 iterator 678 lower_bound(const key_type& __x); 679 680 const_iterator 681 lower_bound(const key_type& __x) const; 682 683 iterator 684 upper_bound(const key_type& __x); 685 686 const_iterator 687 upper_bound(const key_type& __x) const; 688 689 pair<iterator,iterator> 690 equal_range(const key_type& __x); 691 692 pair<const_iterator, const_iterator> 693 equal_range(const key_type& __x) const; 694 695 // Debugging. 696 bool 697 __rb_verify() const; 698 }; 699 700 template<typename _Key, typename _Val, typename _KeyOfValue, 701 typename _Compare, typename _Alloc> 702 inline bool 703 operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 704 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 705 { 706 return __x.size() == __y.size() 707 && std::equal(__x.begin(), __x.end(), __y.begin()); 708 } 709 710 template<typename _Key, typename _Val, typename _KeyOfValue, 711 typename _Compare, typename _Alloc> 712 inline bool 713 operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 714 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 715 { 716 return std::lexicographical_compare(__x.begin(), __x.end(), 717 __y.begin(), __y.end()); 718 } 719 720 template<typename _Key, typename _Val, typename _KeyOfValue, 721 typename _Compare, typename _Alloc> 722 inline bool 723 operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 724 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 725 { return !(__x == __y); } 726 727 template<typename _Key, typename _Val, typename _KeyOfValue, 728 typename _Compare, typename _Alloc> 729 inline bool 730 operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 731 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 732 { return __y < __x; } 733 734 template<typename _Key, typename _Val, typename _KeyOfValue, 735 typename _Compare, typename _Alloc> 736 inline bool 737 operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 738 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 739 { return !(__y < __x); } 740 741 template<typename _Key, typename _Val, typename _KeyOfValue, 742 typename _Compare, typename _Alloc> 743 inline bool 744 operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 745 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 746 { return !(__x < __y); } 747 748 template<typename _Key, typename _Val, typename _KeyOfValue, 749 typename _Compare, typename _Alloc> 750 inline void 751 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 752 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 753 { __x.swap(__y); } 754 755 template<typename _Key, typename _Val, typename _KeyOfValue, 756 typename _Compare, typename _Alloc> 757 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 758 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 759 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) 760 { 761 if (this != &__x) 762 { 763 // Note that _Key may be a constant type. 764 clear(); 765 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 766 if (__x._M_root() != 0) 767 { 768 _M_root() = _M_copy(__x._M_begin(), _M_end()); 769 _M_leftmost() = _S_minimum(_M_root()); 770 _M_rightmost() = _S_maximum(_M_root()); 771 _M_impl._M_node_count = __x._M_impl._M_node_count; 772 } 773 } 774 return *this; 775 } 776 777 template<typename _Key, typename _Val, typename _KeyOfValue, 778 typename _Compare, typename _Alloc> 779 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 780 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 781 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 782 { 783 _Link_type __z = _M_create_node(__v); 784 bool __insert_left; 785 786 __insert_left = __x != 0 || __p == _M_end() 787 || _M_impl._M_key_compare(_KeyOfValue()(__v), 788 _S_key(__p)); 789 790 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 791 this->_M_impl._M_header); 792 ++_M_impl._M_node_count; 793 return iterator(__z); 794 } 795 796 template<typename _Key, typename _Val, typename _KeyOfValue, 797 typename _Compare, typename _Alloc> 798 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 799 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 800 insert_equal(const _Val& __v) 801 { 802 _Link_type __x = _M_begin(); 803 _Link_type __y = _M_end(); 804 while (__x != 0) 805 { 806 __y = __x; 807 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 808 _S_left(__x) : _S_right(__x); 809 } 810 return _M_insert(__x, __y, __v); 811 } 812 813 template<typename _Key, typename _Val, typename _KeyOfValue, 814 typename _Compare, typename _Alloc> 815 void 816 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 817 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) 818 { 819 if (_M_root() == 0) 820 { 821 if (__t._M_root() != 0) 822 { 823 _M_root() = __t._M_root(); 824 _M_leftmost() = __t._M_leftmost(); 825 _M_rightmost() = __t._M_rightmost(); 826 _M_root()->_M_parent = _M_end(); 827 828 __t._M_root() = 0; 829 __t._M_leftmost() = __t._M_end(); 830 __t._M_rightmost() = __t._M_end(); 831 } 832 } 833 else if (__t._M_root() == 0) 834 { 835 __t._M_root() = _M_root(); 836 __t._M_leftmost() = _M_leftmost(); 837 __t._M_rightmost() = _M_rightmost(); 838 __t._M_root()->_M_parent = __t._M_end(); 839 840 _M_root() = 0; 841 _M_leftmost() = _M_end(); 842 _M_rightmost() = _M_end(); 843 } 844 else 845 { 846 std::swap(_M_root(),__t._M_root()); 847 std::swap(_M_leftmost(),__t._M_leftmost()); 848 std::swap(_M_rightmost(),__t._M_rightmost()); 849 850 _M_root()->_M_parent = _M_end(); 851 __t._M_root()->_M_parent = __t._M_end(); 852 } 853 // No need to swap header's color as it does not change. 854 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 855 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 856 } 857 858 template<typename _Key, typename _Val, typename _KeyOfValue, 859 typename _Compare, typename _Alloc> 860 pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, 861 bool> 862 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 863 insert_unique(const _Val& __v) 864 { 865 _Link_type __x = _M_begin(); 866 _Link_type __y = _M_end(); 867 bool __comp = true; 868 while (__x != 0) 869 { 870 __y = __x; 871 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 872 __x = __comp ? _S_left(__x) : _S_right(__x); 873 } 874 iterator __j = iterator(__y); 875 if (__comp) 876 if (__j == begin()) 877 return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 878 else 879 --__j; 880 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 881 return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 882 return pair<iterator,bool>(__j, false); 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 insert_unique(iterator __position, const _Val& __v) 890 { 891 if (__position._M_node == _M_leftmost()) 892 { 893 // begin() 894 if (size() > 0 895 && _M_impl._M_key_compare(_KeyOfValue()(__v), 896 _S_key(__position._M_node))) 897 return _M_insert(__position._M_node, __position._M_node, __v); 898 // First argument just needs to be non-null. 899 else 900 return insert_unique(__v).first; 901 } 902 else if (__position._M_node == _M_end()) 903 { 904 // end() 905 if (_M_impl._M_key_compare(_S_key(_M_rightmost()), 906 _KeyOfValue()(__v))) 907 return _M_insert(0, _M_rightmost(), __v); 908 else 909 return insert_unique(__v).first; 910 } 911 else 912 { 913 iterator __before = __position; 914 --__before; 915 if (_M_impl._M_key_compare(_S_key(__before._M_node), 916 _KeyOfValue()(__v)) 917 && _M_impl._M_key_compare(_KeyOfValue()(__v), 918 _S_key(__position._M_node))) 919 { 920 if (_S_right(__before._M_node) == 0) 921 return _M_insert(0, __before._M_node, __v); 922 else 923 return _M_insert(__position._M_node, __position._M_node, __v); 924 // First argument just needs to be non-null. 925 } 926 else 927 return insert_unique(__v).first; 928 } 929 } 930 931 template<typename _Key, typename _Val, typename _KeyOfValue, 932 typename _Compare, typename _Alloc> 933 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 934 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 935 insert_equal(iterator __position, const _Val& __v) 936 { 937 if (__position._M_node == _M_leftmost()) 938 { 939 // begin() 940 if (size() > 0 941 && !_M_impl._M_key_compare(_S_key(__position._M_node), 942 _KeyOfValue()(__v))) 943 return _M_insert(__position._M_node, __position._M_node, __v); 944 // first argument just needs to be non-null 945 else 946 return insert_equal(__v); 947 } 948 else if (__position._M_node == _M_end()) 949 { 950 // end() 951 if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 952 _S_key(_M_rightmost()))) 953 return _M_insert(0, _M_rightmost(), __v); 954 else 955 return insert_equal(__v); 956 } 957 else 958 { 959 iterator __before = __position; 960 --__before; 961 if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 962 _S_key(__before._M_node)) 963 && !_M_impl._M_key_compare(_S_key(__position._M_node), 964 _KeyOfValue()(__v))) 965 { 966 if (_S_right(__before._M_node) == 0) 967 return _M_insert(0, __before._M_node, __v); 968 else 969 return _M_insert(__position._M_node, __position._M_node, __v); 970 // First argument just needs to be non-null. 971 } 972 else 973 return insert_equal(__v); 974 } 975 } 976 977 template<typename _Key, typename _Val, typename _KoV, 978 typename _Cmp, typename _Alloc> 979 template<class _II> 980 void 981 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: 982 insert_equal(_II __first, _II __last) 983 { 984 for ( ; __first != __last; ++__first) 985 insert_equal(*__first); 986 } 987 988 template<typename _Key, typename _Val, typename _KoV, 989 typename _Cmp, typename _Alloc> 990 template<class _II> 991 void 992 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: 993 insert_unique(_II __first, _II __last) 994 { 995 for ( ; __first != __last; ++__first) 996 insert_unique(*__first); 997 } 998 999 template<typename _Key, typename _Val, typename _KeyOfValue, 1000 typename _Compare, typename _Alloc> 1001 inline void 1002 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position) 1003 { 1004 _Link_type __y = 1005 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node, 1006 this->_M_impl._M_header)); 1007 destroy_node(__y); 1008 --_M_impl._M_node_count; 1009 } 1010 1011 template<typename _Key, typename _Val, typename _KeyOfValue, 1012 typename _Compare, typename _Alloc> 1013 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 1014 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x) 1015 { 1016 pair<iterator,iterator> __p = equal_range(__x); 1017 size_type __n = std::distance(__p.first, __p.second); 1018 erase(__p.first, __p.second); 1019 return __n; 1020 } 1021 1022 template<typename _Key, typename _Val, typename _KoV, 1023 typename _Compare, typename _Alloc> 1024 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 1025 _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>:: 1026 _M_copy(_Const_Link_type __x, _Link_type __p) 1027 { 1028 // Structural copy. __x and __p must be non-null. 1029 _Link_type __top = _M_clone_node(__x); 1030 __top->_M_parent = __p; 1031 1032 try 1033 { 1034 if (__x->_M_right) 1035 __top->_M_right = _M_copy(_S_right(__x), __top); 1036 __p = __top; 1037 __x = _S_left(__x); 1038 1039 while (__x != 0) 1040 { 1041 _Link_type __y = _M_clone_node(__x); 1042 __p->_M_left = __y; 1043 __y->_M_parent = __p; 1044 if (__x->_M_right) 1045 __y->_M_right = _M_copy(_S_right(__x), __y); 1046 __p = __y; 1047 __x = _S_left(__x); 1048 } 1049 } 1050 catch(...) 1051 { 1052 _M_erase(__top); 1053 __throw_exception_again; 1054 } 1055 return __top; 1056 } 1057 1058 template<typename _Key, typename _Val, typename _KeyOfValue, 1059 typename _Compare, typename _Alloc> 1060 void 1061 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x) 1062 { 1063 // Erase without rebalancing. 1064 while (__x != 0) 1065 { 1066 _M_erase(_S_right(__x)); 1067 _Link_type __y = _S_left(__x); 1068 destroy_node(__x); 1069 __x = __y; 1070 } 1071 } 1072 1073 template<typename _Key, typename _Val, typename _KeyOfValue, 1074 typename _Compare, typename _Alloc> 1075 void 1076 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1077 erase(iterator __first, iterator __last) 1078 { 1079 if (__first == begin() && __last == end()) 1080 clear(); 1081 else 1082 while (__first != __last) erase(__first++); 1083 } 1084 1085 template<typename _Key, typename _Val, typename _KeyOfValue, 1086 typename _Compare, typename _Alloc> 1087 void 1088 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1089 erase(const _Key* __first, const _Key* __last) 1090 { 1091 while (__first != __last) 1092 erase(*__first++); 1093 } 1094 1095 template<typename _Key, typename _Val, typename _KeyOfValue, 1096 typename _Compare, typename _Alloc> 1097 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 1098 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) 1099 { 1100 _Link_type __x = _M_begin(); // Current node. 1101 _Link_type __y = _M_end(); // Last node which is not less than __k. 1102 1103 while (__x != 0) 1104 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1105 __y = __x, __x = _S_left(__x); 1106 else 1107 __x = _S_right(__x); 1108 1109 iterator __j = iterator(__y); 1110 return (__j == end() 1111 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; 1112 } 1113 1114 template<typename _Key, typename _Val, typename _KeyOfValue, 1115 typename _Compare, typename _Alloc> 1116 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 1117 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1118 find(const _Key& __k) const 1119 { 1120 _Const_Link_type __x = _M_begin(); // Current node. 1121 _Const_Link_type __y = _M_end(); // Last node which is not less than __k. 1122 1123 while (__x != 0) 1124 { 1125 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1126 __y = __x, __x = _S_left(__x); 1127 else 1128 __x = _S_right(__x); 1129 } 1130 const_iterator __j = const_iterator(__y); 1131 return (__j == end() 1132 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; 1133 } 1134 1135 template<typename _Key, typename _Val, typename _KeyOfValue, 1136 typename _Compare, typename _Alloc> 1137 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 1138 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1139 count(const _Key& __k) const 1140 { 1141 pair<const_iterator, const_iterator> __p = equal_range(__k); 1142 const size_type __n = std::distance(__p.first, __p.second); 1143 return __n; 1144 } 1145 1146 template<typename _Key, typename _Val, typename _KeyOfValue, 1147 typename _Compare, typename _Alloc> 1148 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 1149 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1150 lower_bound(const _Key& __k) 1151 { 1152 _Link_type __x = _M_begin(); // Current node. 1153 _Link_type __y = _M_end(); // Last node which is not less than __k. 1154 1155 while (__x != 0) 1156 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1157 __y = __x, __x = _S_left(__x); 1158 else 1159 __x = _S_right(__x); 1160 1161 return iterator(__y); 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 lower_bound(const _Key& __k) const 1169 { 1170 _Const_Link_type __x = _M_begin(); // Current node. 1171 _Const_Link_type __y = _M_end(); // Last node which is not less than __k. 1172 1173 while (__x != 0) 1174 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1175 __y = __x, __x = _S_left(__x); 1176 else 1177 __x = _S_right(__x); 1178 1179 return const_iterator(__y); 1180 } 1181 1182 template<typename _Key, typename _Val, typename _KeyOfValue, 1183 typename _Compare, typename _Alloc> 1184 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 1185 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1186 upper_bound(const _Key& __k) 1187 { 1188 _Link_type __x = _M_begin(); // Current node. 1189 _Link_type __y = _M_end(); // Last node which is greater than __k. 1190 1191 while (__x != 0) 1192 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1193 __y = __x, __x = _S_left(__x); 1194 else 1195 __x = _S_right(__x); 1196 1197 return iterator(__y); 1198 } 1199 1200 template<typename _Key, typename _Val, typename _KeyOfValue, 1201 typename _Compare, typename _Alloc> 1202 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 1203 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1204 upper_bound(const _Key& __k) const 1205 { 1206 _Const_Link_type __x = _M_begin(); // Current node. 1207 _Const_Link_type __y = _M_end(); // Last node which is greater than __k. 1208 1209 while (__x != 0) 1210 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1211 __y = __x, __x = _S_left(__x); 1212 else 1213 __x = _S_right(__x); 1214 1215 return const_iterator(__y); 1216 } 1217 1218 template<typename _Key, typename _Val, typename _KeyOfValue, 1219 typename _Compare, typename _Alloc> 1220 inline 1221 pair<typename _Rb_tree<_Key,_Val,_KeyOfValue, 1222 _Compare,_Alloc>::iterator, 1223 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator> 1224 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1225 equal_range(const _Key& __k) 1226 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); } 1227 1228 template<typename _Key, typename _Val, typename _KoV, 1229 typename _Compare, typename _Alloc> 1230 inline 1231 pair<typename _Rb_tree<_Key, _Val, _KoV, 1232 _Compare, _Alloc>::const_iterator, 1233 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator> 1234 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 1235 equal_range(const _Key& __k) const 1236 { return pair<const_iterator, const_iterator>(lower_bound(__k), 1237 upper_bound(__k)); } 1238 1239 unsigned int 1240 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 1241 const _Rb_tree_node_base* __root); 1242 1243 template<typename _Key, typename _Val, typename _KeyOfValue, 1244 typename _Compare, typename _Alloc> 1245 bool 1246 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 1247 { 1248 if (_M_impl._M_node_count == 0 || begin() == end()) 1249 return _M_impl._M_node_count == 0 && begin() == end() 1250 && this->_M_impl._M_header._M_left == _M_end() 1251 && this->_M_impl._M_header._M_right == _M_end(); 1252 1253 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 1254 for (const_iterator __it = begin(); __it != end(); ++__it) 1255 { 1256 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 1257 _Const_Link_type __L = _S_left(__x); 1258 _Const_Link_type __R = _S_right(__x); 1259 1260 if (__x->_M_color == _S_red) 1261 if ((__L && __L->_M_color == _S_red) 1262 || (__R && __R->_M_color == _S_red)) 1263 return false; 1264 1265 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 1266 return false; 1267 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 1268 return false; 1269 1270 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 1271 return false; 1272 } 1273 1274 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 1275 return false; 1276 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 1277 return false; 1278 return true; 1279 } 1280} // namespace std 1281 1282#endif 1283 1284