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