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