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 iterator 804 erase(const_iterator __position) 805 { 806 const_iterator __result = __position; 807 ++__result; 808 _M_erase_aux(__position); 809 return __result._M_const_cast(); 810 } 811 812 // LWG 2059. 813 iterator 814 erase(iterator __position) 815 { 816 iterator __result = __position; 817 ++__result; 818 _M_erase_aux(__position); 819 return __result; 820 } 821#else 822 void 823 erase(iterator __position) 824 { _M_erase_aux(__position); } 825 826 void 827 erase(const_iterator __position) 828 { _M_erase_aux(__position); } 829#endif 830 size_type 831 erase(const key_type& __x); 832 833#if __cplusplus >= 201103L 834 // _GLIBCXX_RESOLVE_LIB_DEFECTS 835 // DR 130. Associative erase should return an iterator. 836 iterator 837 erase(const_iterator __first, const_iterator __last) 838 { 839 _M_erase_aux(__first, __last); 840 return __last._M_const_cast(); 841 } 842#else 843 void 844 erase(iterator __first, iterator __last) 845 { _M_erase_aux(__first, __last); } 846 847 void 848 erase(const_iterator __first, const_iterator __last) 849 { _M_erase_aux(__first, __last); } 850#endif 851 void 852 erase(const key_type* __first, const key_type* __last); 853 854 void 855 clear() _GLIBCXX_NOEXCEPT 856 { 857 _M_erase(_M_begin()); 858 _M_leftmost() = _M_end(); 859 _M_root() = 0; 860 _M_rightmost() = _M_end(); 861 _M_impl._M_node_count = 0; 862 } 863 864 // Set operations. 865 iterator 866 find(const key_type& __k); 867 868 const_iterator 869 find(const key_type& __k) const; 870 871 size_type 872 count(const key_type& __k) const; 873 874 iterator 875 lower_bound(const key_type& __k) 876 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 877 878 const_iterator 879 lower_bound(const key_type& __k) const 880 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 881 882 iterator 883 upper_bound(const key_type& __k) 884 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 885 886 const_iterator 887 upper_bound(const key_type& __k) const 888 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 889 890 pair<iterator, iterator> 891 equal_range(const key_type& __k); 892 893 pair<const_iterator, const_iterator> 894 equal_range(const key_type& __k) const; 895 896 // Debugging. 897 bool 898 __rb_verify() const; 899 }; 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 { 907 return __x.size() == __y.size() 908 && std::equal(__x.begin(), __x.end(), __y.begin()); 909 } 910 911 template<typename _Key, typename _Val, typename _KeyOfValue, 912 typename _Compare, typename _Alloc> 913 inline bool 914 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 915 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 916 { 917 return std::lexicographical_compare(__x.begin(), __x.end(), 918 __y.begin(), __y.end()); 919 } 920 921 template<typename _Key, typename _Val, typename _KeyOfValue, 922 typename _Compare, typename _Alloc> 923 inline bool 924 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 925 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 926 { return !(__x == __y); } 927 928 template<typename _Key, typename _Val, typename _KeyOfValue, 929 typename _Compare, typename _Alloc> 930 inline bool 931 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 932 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 933 { return __y < __x; } 934 935 template<typename _Key, typename _Val, typename _KeyOfValue, 936 typename _Compare, typename _Alloc> 937 inline bool 938 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 939 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 940 { return !(__y < __x); } 941 942 template<typename _Key, typename _Val, typename _KeyOfValue, 943 typename _Compare, typename _Alloc> 944 inline bool 945 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 946 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 947 { return !(__x < __y); } 948 949 template<typename _Key, typename _Val, typename _KeyOfValue, 950 typename _Compare, typename _Alloc> 951 inline void 952 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 953 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 954 { __x.swap(__y); } 955 956#if __cplusplus >= 201103L 957 template<typename _Key, typename _Val, typename _KeyOfValue, 958 typename _Compare, typename _Alloc> 959 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 960 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x) 961 : _M_impl(__x._M_impl._M_key_compare, 962 std::move(__x._M_get_Node_allocator())) 963 { 964 if (__x._M_root() != 0) 965 { 966 _M_root() = __x._M_root(); 967 _M_leftmost() = __x._M_leftmost(); 968 _M_rightmost() = __x._M_rightmost(); 969 _M_root()->_M_parent = _M_end(); 970 971 __x._M_root() = 0; 972 __x._M_leftmost() = __x._M_end(); 973 __x._M_rightmost() = __x._M_end(); 974 975 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 976 __x._M_impl._M_node_count = 0; 977 } 978 } 979#endif 980 981 template<typename _Key, typename _Val, typename _KeyOfValue, 982 typename _Compare, typename _Alloc> 983 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 984 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 985 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) 986 { 987 if (this != &__x) 988 { 989 // Note that _Key may be a constant type. 990 clear(); 991 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 992 if (__x._M_root() != 0) 993 { 994 _M_root() = _M_copy(__x._M_begin(), _M_end()); 995 _M_leftmost() = _S_minimum(_M_root()); 996 _M_rightmost() = _S_maximum(_M_root()); 997 _M_impl._M_node_count = __x._M_impl._M_node_count; 998 } 999 } 1000 return *this; 1001 } 1002 1003 template<typename _Key, typename _Val, typename _KeyOfValue, 1004 typename _Compare, typename _Alloc> 1005#if __cplusplus >= 201103L 1006 template<typename _Arg> 1007#endif 1008 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1009 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1010#if __cplusplus >= 201103L 1011 _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) 1012#else 1013 _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 1014#endif 1015 { 1016 bool __insert_left = (__x != 0 || __p == _M_end() 1017 || _M_impl._M_key_compare(_KeyOfValue()(__v), 1018 _S_key(__p))); 1019 1020 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 1021 1022 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1023 this->_M_impl._M_header); 1024 ++_M_impl._M_node_count; 1025 return iterator(__z); 1026 } 1027 1028 template<typename _Key, typename _Val, typename _KeyOfValue, 1029 typename _Compare, typename _Alloc> 1030#if __cplusplus >= 201103L 1031 template<typename _Arg> 1032#endif 1033 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1034 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1035#if __cplusplus >= 201103L 1036 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 1037#else 1038 _M_insert_lower(_Base_ptr __p, const _Val& __v) 1039#endif 1040 { 1041 bool __insert_left = (__p == _M_end() 1042 || !_M_impl._M_key_compare(_S_key(__p), 1043 _KeyOfValue()(__v))); 1044 1045 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 1046 1047 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1048 this->_M_impl._M_header); 1049 ++_M_impl._M_node_count; 1050 return iterator(__z); 1051 } 1052 1053 template<typename _Key, typename _Val, typename _KeyOfValue, 1054 typename _Compare, typename _Alloc> 1055#if __cplusplus >= 201103L 1056 template<typename _Arg> 1057#endif 1058 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1059 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1060#if __cplusplus >= 201103L 1061 _M_insert_equal_lower(_Arg&& __v) 1062#else 1063 _M_insert_equal_lower(const _Val& __v) 1064#endif 1065 { 1066 _Link_type __x = _M_begin(); 1067 _Link_type __y = _M_end(); 1068 while (__x != 0) 1069 { 1070 __y = __x; 1071 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 1072 _S_left(__x) : _S_right(__x); 1073 } 1074 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 1075 } 1076 1077 template<typename _Key, typename _Val, typename _KoV, 1078 typename _Compare, typename _Alloc> 1079 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 1080 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 1081 _M_copy(_Const_Link_type __x, _Link_type __p) 1082 { 1083 // Structural copy. __x and __p must be non-null. 1084 _Link_type __top = _M_clone_node(__x); 1085 __top->_M_parent = __p; 1086 1087 __try 1088 { 1089 if (__x->_M_right) 1090 __top->_M_right = _M_copy(_S_right(__x), __top); 1091 __p = __top; 1092 __x = _S_left(__x); 1093 1094 while (__x != 0) 1095 { 1096 _Link_type __y = _M_clone_node(__x); 1097 __p->_M_left = __y; 1098 __y->_M_parent = __p; 1099 if (__x->_M_right) 1100 __y->_M_right = _M_copy(_S_right(__x), __y); 1101 __p = __y; 1102 __x = _S_left(__x); 1103 } 1104 } 1105 __catch(...) 1106 { 1107 _M_erase(__top); 1108 __throw_exception_again; 1109 } 1110 return __top; 1111 } 1112 1113 template<typename _Key, typename _Val, typename _KeyOfValue, 1114 typename _Compare, typename _Alloc> 1115 void 1116 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1117 _M_erase(_Link_type __x) 1118 { 1119 // Erase without rebalancing. 1120 while (__x != 0) 1121 { 1122 _M_erase(_S_right(__x)); 1123 _Link_type __y = _S_left(__x); 1124 _M_destroy_node(__x); 1125 __x = __y; 1126 } 1127 } 1128 1129 template<typename _Key, typename _Val, typename _KeyOfValue, 1130 typename _Compare, typename _Alloc> 1131 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1132 _Compare, _Alloc>::iterator 1133 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1134 _M_lower_bound(_Link_type __x, _Link_type __y, 1135 const _Key& __k) 1136 { 1137 while (__x != 0) 1138 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1139 __y = __x, __x = _S_left(__x); 1140 else 1141 __x = _S_right(__x); 1142 return iterator(__y); 1143 } 1144 1145 template<typename _Key, typename _Val, typename _KeyOfValue, 1146 typename _Compare, typename _Alloc> 1147 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1148 _Compare, _Alloc>::const_iterator 1149 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1150 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 1151 const _Key& __k) const 1152 { 1153 while (__x != 0) 1154 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1155 __y = __x, __x = _S_left(__x); 1156 else 1157 __x = _S_right(__x); 1158 return const_iterator(__y); 1159 } 1160 1161 template<typename _Key, typename _Val, typename _KeyOfValue, 1162 typename _Compare, typename _Alloc> 1163 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1164 _Compare, _Alloc>::iterator 1165 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1166 _M_upper_bound(_Link_type __x, _Link_type __y, 1167 const _Key& __k) 1168 { 1169 while (__x != 0) 1170 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1171 __y = __x, __x = _S_left(__x); 1172 else 1173 __x = _S_right(__x); 1174 return iterator(__y); 1175 } 1176 1177 template<typename _Key, typename _Val, typename _KeyOfValue, 1178 typename _Compare, typename _Alloc> 1179 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1180 _Compare, _Alloc>::const_iterator 1181 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1182 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 1183 const _Key& __k) const 1184 { 1185 while (__x != 0) 1186 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1187 __y = __x, __x = _S_left(__x); 1188 else 1189 __x = _S_right(__x); 1190 return const_iterator(__y); 1191 } 1192 1193 template<typename _Key, typename _Val, typename _KeyOfValue, 1194 typename _Compare, typename _Alloc> 1195 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1196 _Compare, _Alloc>::iterator, 1197 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1198 _Compare, _Alloc>::iterator> 1199 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1200 equal_range(const _Key& __k) 1201 { 1202 _Link_type __x = _M_begin(); 1203 _Link_type __y = _M_end(); 1204 while (__x != 0) 1205 { 1206 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1207 __x = _S_right(__x); 1208 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1209 __y = __x, __x = _S_left(__x); 1210 else 1211 { 1212 _Link_type __xu(__x), __yu(__y); 1213 __y = __x, __x = _S_left(__x); 1214 __xu = _S_right(__xu); 1215 return pair<iterator, 1216 iterator>(_M_lower_bound(__x, __y, __k), 1217 _M_upper_bound(__xu, __yu, __k)); 1218 } 1219 } 1220 return pair<iterator, iterator>(iterator(__y), 1221 iterator(__y)); 1222 } 1223 1224 template<typename _Key, typename _Val, typename _KeyOfValue, 1225 typename _Compare, typename _Alloc> 1226 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1227 _Compare, _Alloc>::const_iterator, 1228 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1229 _Compare, _Alloc>::const_iterator> 1230 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1231 equal_range(const _Key& __k) const 1232 { 1233 _Const_Link_type __x = _M_begin(); 1234 _Const_Link_type __y = _M_end(); 1235 while (__x != 0) 1236 { 1237 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1238 __x = _S_right(__x); 1239 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1240 __y = __x, __x = _S_left(__x); 1241 else 1242 { 1243 _Const_Link_type __xu(__x), __yu(__y); 1244 __y = __x, __x = _S_left(__x); 1245 __xu = _S_right(__xu); 1246 return pair<const_iterator, 1247 const_iterator>(_M_lower_bound(__x, __y, __k), 1248 _M_upper_bound(__xu, __yu, __k)); 1249 } 1250 } 1251 return pair<const_iterator, const_iterator>(const_iterator(__y), 1252 const_iterator(__y)); 1253 } 1254 1255 template<typename _Key, typename _Val, typename _KeyOfValue, 1256 typename _Compare, typename _Alloc> 1257 void 1258 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1259 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 1260 { 1261 if (_M_root() == 0) 1262 { 1263 if (__t._M_root() != 0) 1264 { 1265 _M_root() = __t._M_root(); 1266 _M_leftmost() = __t._M_leftmost(); 1267 _M_rightmost() = __t._M_rightmost(); 1268 _M_root()->_M_parent = _M_end(); 1269 1270 __t._M_root() = 0; 1271 __t._M_leftmost() = __t._M_end(); 1272 __t._M_rightmost() = __t._M_end(); 1273 } 1274 } 1275 else if (__t._M_root() == 0) 1276 { 1277 __t._M_root() = _M_root(); 1278 __t._M_leftmost() = _M_leftmost(); 1279 __t._M_rightmost() = _M_rightmost(); 1280 __t._M_root()->_M_parent = __t._M_end(); 1281 1282 _M_root() = 0; 1283 _M_leftmost() = _M_end(); 1284 _M_rightmost() = _M_end(); 1285 } 1286 else 1287 { 1288 std::swap(_M_root(),__t._M_root()); 1289 std::swap(_M_leftmost(),__t._M_leftmost()); 1290 std::swap(_M_rightmost(),__t._M_rightmost()); 1291 1292 _M_root()->_M_parent = _M_end(); 1293 __t._M_root()->_M_parent = __t._M_end(); 1294 } 1295 // No need to swap header's color as it does not change. 1296 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 1297 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 1298 1299 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1300 // 431. Swapping containers with unequal allocators. 1301 std::__alloc_swap<_Node_allocator>:: 1302 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); 1303 } 1304 1305 template<typename _Key, typename _Val, typename _KeyOfValue, 1306 typename _Compare, typename _Alloc> 1307 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1308 _Compare, _Alloc>::_Base_ptr, 1309 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1310 _Compare, _Alloc>::_Base_ptr> 1311 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1312 _M_get_insert_unique_pos(const key_type& __k) 1313 { 1314 typedef pair<_Base_ptr, _Base_ptr> _Res; 1315 _Link_type __x = _M_begin(); 1316 _Link_type __y = _M_end(); 1317 bool __comp = true; 1318 while (__x != 0) 1319 { 1320 __y = __x; 1321 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 1322 __x = __comp ? _S_left(__x) : _S_right(__x); 1323 } 1324 iterator __j = iterator(__y); 1325 if (__comp) 1326 { 1327 if (__j == begin()) 1328 return _Res(__x, __y); 1329 else 1330 --__j; 1331 } 1332 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 1333 return _Res(__x, __y); 1334 return _Res(__j._M_node, 0); 1335 } 1336 1337 template<typename _Key, typename _Val, typename _KeyOfValue, 1338 typename _Compare, typename _Alloc> 1339 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1340 _Compare, _Alloc>::_Base_ptr, 1341 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1342 _Compare, _Alloc>::_Base_ptr> 1343 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1344 _M_get_insert_equal_pos(const key_type& __k) 1345 { 1346 typedef pair<_Base_ptr, _Base_ptr> _Res; 1347 _Link_type __x = _M_begin(); 1348 _Link_type __y = _M_end(); 1349 while (__x != 0) 1350 { 1351 __y = __x; 1352 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 1353 _S_left(__x) : _S_right(__x); 1354 } 1355 return _Res(__x, __y); 1356 } 1357 1358 template<typename _Key, typename _Val, typename _KeyOfValue, 1359 typename _Compare, typename _Alloc> 1360#if __cplusplus >= 201103L 1361 template<typename _Arg> 1362#endif 1363 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1364 _Compare, _Alloc>::iterator, bool> 1365 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1366#if __cplusplus >= 201103L 1367 _M_insert_unique(_Arg&& __v) 1368#else 1369 _M_insert_unique(const _Val& __v) 1370#endif 1371 { 1372 typedef pair<iterator, bool> _Res; 1373 pair<_Base_ptr, _Base_ptr> __res 1374 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 1375 1376 if (__res.second) 1377 return _Res(_M_insert_(__res.first, __res.second, 1378 _GLIBCXX_FORWARD(_Arg, __v)), 1379 true); 1380 1381 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 1382 } 1383 1384 template<typename _Key, typename _Val, typename _KeyOfValue, 1385 typename _Compare, typename _Alloc> 1386#if __cplusplus >= 201103L 1387 template<typename _Arg> 1388#endif 1389 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1390 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1391#if __cplusplus >= 201103L 1392 _M_insert_equal(_Arg&& __v) 1393#else 1394 _M_insert_equal(const _Val& __v) 1395#endif 1396 { 1397 pair<_Base_ptr, _Base_ptr> __res 1398 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 1399 return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v)); 1400 } 1401 1402 template<typename _Key, typename _Val, typename _KeyOfValue, 1403 typename _Compare, typename _Alloc> 1404 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1405 _Compare, _Alloc>::_Base_ptr, 1406 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1407 _Compare, _Alloc>::_Base_ptr> 1408 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1409 _M_get_insert_hint_unique_pos(const_iterator __position, 1410 const key_type& __k) 1411 { 1412 iterator __pos = __position._M_const_cast(); 1413 typedef pair<_Base_ptr, _Base_ptr> _Res; 1414 1415 // end() 1416 if (__pos._M_node == _M_end()) 1417 { 1418 if (size() > 0 1419 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 1420 return _Res(0, _M_rightmost()); 1421 else 1422 return _M_get_insert_unique_pos(__k); 1423 } 1424 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 1425 { 1426 // First, try before... 1427 iterator __before = __pos; 1428 if (__pos._M_node == _M_leftmost()) // begin() 1429 return _Res(_M_leftmost(), _M_leftmost()); 1430 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 1431 { 1432 if (_S_right(__before._M_node) == 0) 1433 return _Res(0, __before._M_node); 1434 else 1435 return _Res(__pos._M_node, __pos._M_node); 1436 } 1437 else 1438 return _M_get_insert_unique_pos(__k); 1439 } 1440 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 1441 { 1442 // ... then try after. 1443 iterator __after = __pos; 1444 if (__pos._M_node == _M_rightmost()) 1445 return _Res(0, _M_rightmost()); 1446 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 1447 { 1448 if (_S_right(__pos._M_node) == 0) 1449 return _Res(0, __pos._M_node); 1450 else 1451 return _Res(__after._M_node, __after._M_node); 1452 } 1453 else 1454 return _M_get_insert_unique_pos(__k); 1455 } 1456 else 1457 // Equivalent keys. 1458 return _Res(__pos._M_node, 0); 1459 } 1460 1461 template<typename _Key, typename _Val, typename _KeyOfValue, 1462 typename _Compare, typename _Alloc> 1463#if __cplusplus >= 201103L 1464 template<typename _Arg> 1465#endif 1466 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1467 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1468#if __cplusplus >= 201103L 1469 _M_insert_unique_(const_iterator __position, _Arg&& __v) 1470#else 1471 _M_insert_unique_(const_iterator __position, const _Val& __v) 1472#endif 1473 { 1474 pair<_Base_ptr, _Base_ptr> __res 1475 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 1476 1477 if (__res.second) 1478 return _M_insert_(__res.first, __res.second, 1479 _GLIBCXX_FORWARD(_Arg, __v)); 1480 return iterator(static_cast<_Link_type>(__res.first)); 1481 } 1482 1483 template<typename _Key, typename _Val, typename _KeyOfValue, 1484 typename _Compare, typename _Alloc> 1485 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1486 _Compare, _Alloc>::_Base_ptr, 1487 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1488 _Compare, _Alloc>::_Base_ptr> 1489 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1490 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 1491 { 1492 iterator __pos = __position._M_const_cast(); 1493 typedef pair<_Base_ptr, _Base_ptr> _Res; 1494 1495 // end() 1496 if (__pos._M_node == _M_end()) 1497 { 1498 if (size() > 0 1499 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 1500 return _Res(0, _M_rightmost()); 1501 else 1502 return _M_get_insert_equal_pos(__k); 1503 } 1504 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 1505 { 1506 // First, try before... 1507 iterator __before = __pos; 1508 if (__pos._M_node == _M_leftmost()) // begin() 1509 return _Res(_M_leftmost(), _M_leftmost()); 1510 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 1511 { 1512 if (_S_right(__before._M_node) == 0) 1513 return _Res(0, __before._M_node); 1514 else 1515 return _Res(__pos._M_node, __pos._M_node); 1516 } 1517 else 1518 return _M_get_insert_equal_pos(__k); 1519 } 1520 else 1521 { 1522 // ... then try after. 1523 iterator __after = __pos; 1524 if (__pos._M_node == _M_rightmost()) 1525 return _Res(0, _M_rightmost()); 1526 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 1527 { 1528 if (_S_right(__pos._M_node) == 0) 1529 return _Res(0, __pos._M_node); 1530 else 1531 return _Res(__after._M_node, __after._M_node); 1532 } 1533 else 1534 return _Res(0, 0); 1535 } 1536 } 1537 1538 template<typename _Key, typename _Val, typename _KeyOfValue, 1539 typename _Compare, typename _Alloc> 1540#if __cplusplus >= 201103L 1541 template<typename _Arg> 1542#endif 1543 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1544 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1545#if __cplusplus >= 201103L 1546 _M_insert_equal_(const_iterator __position, _Arg&& __v) 1547#else 1548 _M_insert_equal_(const_iterator __position, const _Val& __v) 1549#endif 1550 { 1551 pair<_Base_ptr, _Base_ptr> __res 1552 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 1553 1554 if (__res.second) 1555 return _M_insert_(__res.first, __res.second, 1556 _GLIBCXX_FORWARD(_Arg, __v)); 1557 1558 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 1559 } 1560 1561#if __cplusplus >= 201103L 1562 template<typename _Key, typename _Val, typename _KeyOfValue, 1563 typename _Compare, typename _Alloc> 1564 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1565 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1566 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 1567 { 1568 bool __insert_left = (__x != 0 || __p == _M_end() 1569 || _M_impl._M_key_compare(_S_key(__z), 1570 _S_key(__p))); 1571 1572 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1573 this->_M_impl._M_header); 1574 ++_M_impl._M_node_count; 1575 return iterator(__z); 1576 } 1577 1578 template<typename _Key, typename _Val, typename _KeyOfValue, 1579 typename _Compare, typename _Alloc> 1580 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1581 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1582 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 1583 { 1584 bool __insert_left = (__p == _M_end() 1585 || !_M_impl._M_key_compare(_S_key(__p), 1586 _S_key(__z))); 1587 1588 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1589 this->_M_impl._M_header); 1590 ++_M_impl._M_node_count; 1591 return iterator(__z); 1592 } 1593 1594 template<typename _Key, typename _Val, typename _KeyOfValue, 1595 typename _Compare, typename _Alloc> 1596 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1597 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1598 _M_insert_equal_lower_node(_Link_type __z) 1599 { 1600 _Link_type __x = _M_begin(); 1601 _Link_type __y = _M_end(); 1602 while (__x != 0) 1603 { 1604 __y = __x; 1605 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 1606 _S_left(__x) : _S_right(__x); 1607 } 1608 return _M_insert_lower_node(__y, __z); 1609 } 1610 1611 template<typename _Key, typename _Val, typename _KeyOfValue, 1612 typename _Compare, typename _Alloc> 1613 template<typename... _Args> 1614 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1615 _Compare, _Alloc>::iterator, bool> 1616 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1617 _M_emplace_unique(_Args&&... __args) 1618 { 1619 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 1620 1621 __try 1622 { 1623 typedef pair<iterator, bool> _Res; 1624 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 1625 if (__res.second) 1626 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 1627 1628 _M_destroy_node(__z); 1629 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 1630 } 1631 __catch(...) 1632 { 1633 _M_destroy_node(__z); 1634 __throw_exception_again; 1635 } 1636 } 1637 1638 template<typename _Key, typename _Val, typename _KeyOfValue, 1639 typename _Compare, typename _Alloc> 1640 template<typename... _Args> 1641 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1642 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1643 _M_emplace_equal(_Args&&... __args) 1644 { 1645 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 1646 1647 __try 1648 { 1649 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 1650 return _M_insert_node(__res.first, __res.second, __z); 1651 } 1652 __catch(...) 1653 { 1654 _M_destroy_node(__z); 1655 __throw_exception_again; 1656 } 1657 } 1658 1659 template<typename _Key, typename _Val, typename _KeyOfValue, 1660 typename _Compare, typename _Alloc> 1661 template<typename... _Args> 1662 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1663 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1664 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 1665 { 1666 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 1667 1668 __try 1669 { 1670 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 1671 1672 if (__res.second) 1673 return _M_insert_node(__res.first, __res.second, __z); 1674 1675 _M_destroy_node(__z); 1676 return iterator(static_cast<_Link_type>(__res.first)); 1677 } 1678 __catch(...) 1679 { 1680 _M_destroy_node(__z); 1681 __throw_exception_again; 1682 } 1683 } 1684 1685 template<typename _Key, typename _Val, typename _KeyOfValue, 1686 typename _Compare, typename _Alloc> 1687 template<typename... _Args> 1688 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1689 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1690 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 1691 { 1692 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 1693 1694 __try 1695 { 1696 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 1697 1698 if (__res.second) 1699 return _M_insert_node(__res.first, __res.second, __z); 1700 1701 return _M_insert_equal_lower_node(__z); 1702 } 1703 __catch(...) 1704 { 1705 _M_destroy_node(__z); 1706 __throw_exception_again; 1707 } 1708 } 1709#endif 1710 1711 template<typename _Key, typename _Val, typename _KoV, 1712 typename _Cmp, typename _Alloc> 1713 template<class _II> 1714 void 1715 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1716 _M_insert_unique(_II __first, _II __last) 1717 { 1718 for (; __first != __last; ++__first) 1719 _M_insert_unique_(end(), *__first); 1720 } 1721 1722 template<typename _Key, typename _Val, typename _KoV, 1723 typename _Cmp, typename _Alloc> 1724 template<class _II> 1725 void 1726 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 1727 _M_insert_equal(_II __first, _II __last) 1728 { 1729 for (; __first != __last; ++__first) 1730 _M_insert_equal_(end(), *__first); 1731 } 1732 1733 template<typename _Key, typename _Val, typename _KeyOfValue, 1734 typename _Compare, typename _Alloc> 1735 void 1736 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1737 _M_erase_aux(const_iterator __position) 1738 { 1739 _Link_type __y = 1740 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 1741 (const_cast<_Base_ptr>(__position._M_node), 1742 this->_M_impl._M_header)); 1743 _M_destroy_node(__y); 1744 --_M_impl._M_node_count; 1745 } 1746 1747 template<typename _Key, typename _Val, typename _KeyOfValue, 1748 typename _Compare, typename _Alloc> 1749 void 1750 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1751 _M_erase_aux(const_iterator __first, const_iterator __last) 1752 { 1753 if (__first == begin() && __last == end()) 1754 clear(); 1755 else 1756 while (__first != __last) 1757 erase(__first++); 1758 } 1759 1760 template<typename _Key, typename _Val, typename _KeyOfValue, 1761 typename _Compare, typename _Alloc> 1762 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1763 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1764 erase(const _Key& __x) 1765 { 1766 pair<iterator, iterator> __p = equal_range(__x); 1767 const size_type __old_size = size(); 1768 erase(__p.first, __p.second); 1769 return __old_size - size(); 1770 } 1771 1772 template<typename _Key, typename _Val, typename _KeyOfValue, 1773 typename _Compare, typename _Alloc> 1774 void 1775 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1776 erase(const _Key* __first, const _Key* __last) 1777 { 1778 while (__first != __last) 1779 erase(*__first++); 1780 } 1781 1782 template<typename _Key, typename _Val, typename _KeyOfValue, 1783 typename _Compare, typename _Alloc> 1784 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1785 _Compare, _Alloc>::iterator 1786 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1787 find(const _Key& __k) 1788 { 1789 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1790 return (__j == end() 1791 || _M_impl._M_key_compare(__k, 1792 _S_key(__j._M_node))) ? end() : __j; 1793 } 1794 1795 template<typename _Key, typename _Val, typename _KeyOfValue, 1796 typename _Compare, typename _Alloc> 1797 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1798 _Compare, _Alloc>::const_iterator 1799 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1800 find(const _Key& __k) const 1801 { 1802 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 1803 return (__j == end() 1804 || _M_impl._M_key_compare(__k, 1805 _S_key(__j._M_node))) ? end() : __j; 1806 } 1807 1808 template<typename _Key, typename _Val, typename _KeyOfValue, 1809 typename _Compare, typename _Alloc> 1810 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 1811 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1812 count(const _Key& __k) const 1813 { 1814 pair<const_iterator, const_iterator> __p = equal_range(__k); 1815 const size_type __n = std::distance(__p.first, __p.second); 1816 return __n; 1817 } 1818 1819 _GLIBCXX_PURE unsigned int 1820 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 1821 const _Rb_tree_node_base* __root) throw (); 1822 1823 template<typename _Key, typename _Val, typename _KeyOfValue, 1824 typename _Compare, typename _Alloc> 1825 bool 1826 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 1827 { 1828 if (_M_impl._M_node_count == 0 || begin() == end()) 1829 return _M_impl._M_node_count == 0 && begin() == end() 1830 && this->_M_impl._M_header._M_left == _M_end() 1831 && this->_M_impl._M_header._M_right == _M_end(); 1832 1833 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 1834 for (const_iterator __it = begin(); __it != end(); ++__it) 1835 { 1836 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 1837 _Const_Link_type __L = _S_left(__x); 1838 _Const_Link_type __R = _S_right(__x); 1839 1840 if (__x->_M_color == _S_red) 1841 if ((__L && __L->_M_color == _S_red) 1842 || (__R && __R->_M_color == _S_red)) 1843 return false; 1844 1845 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 1846 return false; 1847 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 1848 return false; 1849 1850 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 1851 return false; 1852 } 1853 1854 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 1855 return false; 1856 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 1857 return false; 1858 return true; 1859 } 1860 1861_GLIBCXX_END_NAMESPACE_VERSION 1862} // namespace 1863 1864#endif 1865