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