1 // RB tree implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2016 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 #pragma GCC system_header 62 63 #include <bits/stl_algobase.h> 64 #include <bits/allocator.h> 65 #include <bits/stl_function.h> 66 #include <bits/cpp_type_traits.h> 67 #include <ext/alloc_traits.h> 68 #if __cplusplus >= 201103L 69 #include <ext/aligned_buffer.h> 70 #endif 71 72 namespace std _GLIBCXX_VISIBILITY(default) 73 { 74 _GLIBCXX_BEGIN_NAMESPACE_VERSION 75 76 #if __cplusplus > 201103L 77 # define __cpp_lib_generic_associative_lookup 201304 78 #endif 79 80 // Red-black tree class, designed for use in implementing STL 81 // associative containers (set, multiset, map, and multimap). The 82 // insertion and deletion algorithms are based on those in Cormen, 83 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 84 // 1990), except that 85 // 86 // (1) the header cell is maintained with links not only to the root 87 // but also to the leftmost node of the tree, to enable constant 88 // time begin(), and to the rightmost node of the tree, to enable 89 // linear time performance when used with the generic set algorithms 90 // (set_union, etc.) 91 // 92 // (2) when a node being deleted has two children its successor node 93 // is relinked into its place, rather than copied, so that the only 94 // iterators invalidated are those referring to the deleted node. 95 96 enum _Rb_tree_color { _S_red = false, _S_black = true }; 97 98 struct _Rb_tree_node_base 99 { 100 typedef _Rb_tree_node_base* _Base_ptr; 101 typedef const _Rb_tree_node_base* _Const_Base_ptr; 102 103 _Rb_tree_color _M_color; 104 _Base_ptr _M_parent; 105 _Base_ptr _M_left; 106 _Base_ptr _M_right; 107 108 static _Base_ptr 109 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 110 { 111 while (__x->_M_left != 0) __x = __x->_M_left; 112 return __x; 113 } 114 115 static _Const_Base_ptr 116 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 117 { 118 while (__x->_M_left != 0) __x = __x->_M_left; 119 return __x; 120 } 121 122 static _Base_ptr 123 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 124 { 125 while (__x->_M_right != 0) __x = __x->_M_right; 126 return __x; 127 } 128 129 static _Const_Base_ptr 130 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 131 { 132 while (__x->_M_right != 0) __x = __x->_M_right; 133 return __x; 134 } 135 }; 136 137 template<typename _Val> 138 struct _Rb_tree_node : public _Rb_tree_node_base 139 { 140 typedef _Rb_tree_node<_Val>* _Link_type; 141 142 #if __cplusplus < 201103L 143 _Val _M_value_field; 144 145 _Val* 146 _M_valptr() 147 { return std::__addressof(_M_value_field); } 148 149 const _Val* 150 _M_valptr() const 151 { return std::__addressof(_M_value_field); } 152 #else 153 __gnu_cxx::__aligned_membuf<_Val> _M_storage; 154 155 _Val* 156 _M_valptr() 157 { return _M_storage._M_ptr(); } 158 159 const _Val* 160 _M_valptr() const 161 { return _M_storage._M_ptr(); } 162 #endif 163 }; 164 165 _GLIBCXX_PURE _Rb_tree_node_base* 166 _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); 167 168 _GLIBCXX_PURE const _Rb_tree_node_base* 169 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw (); 170 171 _GLIBCXX_PURE _Rb_tree_node_base* 172 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw (); 173 174 _GLIBCXX_PURE const _Rb_tree_node_base* 175 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw (); 176 177 template<typename _Tp> 178 struct _Rb_tree_iterator 179 { 180 typedef _Tp value_type; 181 typedef _Tp& reference; 182 typedef _Tp* pointer; 183 184 typedef bidirectional_iterator_tag iterator_category; 185 typedef ptrdiff_t difference_type; 186 187 typedef _Rb_tree_iterator<_Tp> _Self; 188 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 189 typedef _Rb_tree_node<_Tp>* _Link_type; 190 191 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT 192 : _M_node() { } 193 194 explicit 195 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 196 : _M_node(__x) { } 197 198 reference 199 operator*() const _GLIBCXX_NOEXCEPT 200 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 201 202 pointer 203 operator->() const _GLIBCXX_NOEXCEPT 204 { return static_cast<_Link_type> (_M_node)->_M_valptr(); } 205 206 _Self& 207 operator++() _GLIBCXX_NOEXCEPT 208 { 209 _M_node = _Rb_tree_increment(_M_node); 210 return *this; 211 } 212 213 _Self 214 operator++(int) _GLIBCXX_NOEXCEPT 215 { 216 _Self __tmp = *this; 217 _M_node = _Rb_tree_increment(_M_node); 218 return __tmp; 219 } 220 221 _Self& 222 operator--() _GLIBCXX_NOEXCEPT 223 { 224 _M_node = _Rb_tree_decrement(_M_node); 225 return *this; 226 } 227 228 _Self 229 operator--(int) _GLIBCXX_NOEXCEPT 230 { 231 _Self __tmp = *this; 232 _M_node = _Rb_tree_decrement(_M_node); 233 return __tmp; 234 } 235 236 bool 237 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 238 { return _M_node == __x._M_node; } 239 240 bool 241 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 242 { return _M_node != __x._M_node; } 243 244 _Base_ptr _M_node; 245 }; 246 247 template<typename _Tp> 248 struct _Rb_tree_const_iterator 249 { 250 typedef _Tp value_type; 251 typedef const _Tp& reference; 252 typedef const _Tp* pointer; 253 254 typedef _Rb_tree_iterator<_Tp> iterator; 255 256 typedef bidirectional_iterator_tag iterator_category; 257 typedef ptrdiff_t difference_type; 258 259 typedef _Rb_tree_const_iterator<_Tp> _Self; 260 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 261 typedef const _Rb_tree_node<_Tp>* _Link_type; 262 263 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT 264 : _M_node() { } 265 266 explicit 267 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 268 : _M_node(__x) { } 269 270 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT 271 : _M_node(__it._M_node) { } 272 273 iterator 274 _M_const_cast() const _GLIBCXX_NOEXCEPT 275 { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); } 276 277 reference 278 operator*() const _GLIBCXX_NOEXCEPT 279 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 280 281 pointer 282 operator->() const _GLIBCXX_NOEXCEPT 283 { return static_cast<_Link_type>(_M_node)->_M_valptr(); } 284 285 _Self& 286 operator++() _GLIBCXX_NOEXCEPT 287 { 288 _M_node = _Rb_tree_increment(_M_node); 289 return *this; 290 } 291 292 _Self 293 operator++(int) _GLIBCXX_NOEXCEPT 294 { 295 _Self __tmp = *this; 296 _M_node = _Rb_tree_increment(_M_node); 297 return __tmp; 298 } 299 300 _Self& 301 operator--() _GLIBCXX_NOEXCEPT 302 { 303 _M_node = _Rb_tree_decrement(_M_node); 304 return *this; 305 } 306 307 _Self 308 operator--(int) _GLIBCXX_NOEXCEPT 309 { 310 _Self __tmp = *this; 311 _M_node = _Rb_tree_decrement(_M_node); 312 return __tmp; 313 } 314 315 bool 316 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 317 { return _M_node == __x._M_node; } 318 319 bool 320 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 321 { return _M_node != __x._M_node; } 322 323 _Base_ptr _M_node; 324 }; 325 326 template<typename _Val> 327 inline bool 328 operator==(const _Rb_tree_iterator<_Val>& __x, 329 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 330 { return __x._M_node == __y._M_node; } 331 332 template<typename _Val> 333 inline bool 334 operator!=(const _Rb_tree_iterator<_Val>& __x, 335 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 336 { return __x._M_node != __y._M_node; } 337 338 void 339 _Rb_tree_insert_and_rebalance(const bool __insert_left, 340 _Rb_tree_node_base* __x, 341 _Rb_tree_node_base* __p, 342 _Rb_tree_node_base& __header) throw (); 343 344 _Rb_tree_node_base* 345 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 346 _Rb_tree_node_base& __header) throw (); 347 348 #if __cplusplus > 201103L 349 template<typename _Cmp, typename _SfinaeType, typename = __void_t<>> 350 struct __has_is_transparent 351 { }; 352 353 template<typename _Cmp, typename _SfinaeType> 354 struct __has_is_transparent<_Cmp, _SfinaeType, 355 __void_t<typename _Cmp::is_transparent>> 356 { typedef void type; }; 357 #endif 358 359 template<typename _Key, typename _Val, typename _KeyOfValue, 360 typename _Compare, typename _Alloc = allocator<_Val> > 361 class _Rb_tree 362 { 363 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 364 rebind<_Rb_tree_node<_Val> >::other _Node_allocator; 365 366 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits; 367 368 protected: 369 typedef _Rb_tree_node_base* _Base_ptr; 370 typedef const _Rb_tree_node_base* _Const_Base_ptr; 371 typedef _Rb_tree_node<_Val>* _Link_type; 372 typedef const _Rb_tree_node<_Val>* _Const_Link_type; 373 374 private: 375 // Functor recycling a pool of nodes and using allocation once the pool 376 // is empty. 377 struct _Reuse_or_alloc_node 378 { 379 _Reuse_or_alloc_node(_Rb_tree& __t) 380 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t) 381 { 382 if (_M_root) 383 { 384 _M_root->_M_parent = 0; 385 386 if (_M_nodes->_M_left) 387 _M_nodes = _M_nodes->_M_left; 388 } 389 else 390 _M_nodes = 0; 391 } 392 393 #if __cplusplus >= 201103L 394 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete; 395 #endif 396 397 ~_Reuse_or_alloc_node() 398 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); } 399 400 template<typename _Arg> 401 _Link_type 402 #if __cplusplus < 201103L 403 operator()(const _Arg& __arg) 404 #else 405 operator()(_Arg&& __arg) 406 #endif 407 { 408 _Link_type __node = static_cast<_Link_type>(_M_extract()); 409 if (__node) 410 { 411 _M_t._M_destroy_node(__node); 412 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg)); 413 return __node; 414 } 415 416 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); 417 } 418 419 private: 420 _Base_ptr 421 _M_extract() 422 { 423 if (!_M_nodes) 424 return _M_nodes; 425 426 _Base_ptr __node = _M_nodes; 427 _M_nodes = _M_nodes->_M_parent; 428 if (_M_nodes) 429 { 430 if (_M_nodes->_M_right == __node) 431 { 432 _M_nodes->_M_right = 0; 433 434 if (_M_nodes->_M_left) 435 { 436 _M_nodes = _M_nodes->_M_left; 437 438 while (_M_nodes->_M_right) 439 _M_nodes = _M_nodes->_M_right; 440 441 if (_M_nodes->_M_left) 442 _M_nodes = _M_nodes->_M_left; 443 } 444 } 445 else // __node is on the left. 446 _M_nodes->_M_left = 0; 447 } 448 else 449 _M_root = 0; 450 451 return __node; 452 } 453 454 _Base_ptr _M_root; 455 _Base_ptr _M_nodes; 456 _Rb_tree& _M_t; 457 }; 458 459 // Functor similar to the previous one but without any pool of nodes to 460 // recycle. 461 struct _Alloc_node 462 { 463 _Alloc_node(_Rb_tree& __t) 464 : _M_t(__t) { } 465 466 template<typename _Arg> 467 _Link_type 468 #if __cplusplus < 201103L 469 operator()(const _Arg& __arg) const 470 #else 471 operator()(_Arg&& __arg) const 472 #endif 473 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); } 474 475 private: 476 _Rb_tree& _M_t; 477 }; 478 479 public: 480 typedef _Key key_type; 481 typedef _Val value_type; 482 typedef value_type* pointer; 483 typedef const value_type* const_pointer; 484 typedef value_type& reference; 485 typedef const value_type& const_reference; 486 typedef size_t size_type; 487 typedef ptrdiff_t difference_type; 488 typedef _Alloc allocator_type; 489 490 _Node_allocator& 491 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT 492 { return *static_cast<_Node_allocator*>(&this->_M_impl); } 493 494 const _Node_allocator& 495 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT 496 { return *static_cast<const _Node_allocator*>(&this->_M_impl); } 497 498 allocator_type 499 get_allocator() const _GLIBCXX_NOEXCEPT 500 { return allocator_type(_M_get_Node_allocator()); } 501 502 protected: 503 _Link_type 504 _M_get_node() 505 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); } 506 507 void 508 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT 509 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); } 510 511 #if __cplusplus < 201103L 512 void 513 _M_construct_node(_Link_type __node, const value_type& __x) 514 { 515 __try 516 { get_allocator().construct(__node->_M_valptr(), __x); } 517 __catch(...) 518 { 519 _M_put_node(__node); 520 __throw_exception_again; 521 } 522 } 523 524 _Link_type 525 _M_create_node(const value_type& __x) 526 { 527 _Link_type __tmp = _M_get_node(); 528 _M_construct_node(__tmp, __x); 529 return __tmp; 530 } 531 532 void 533 _M_destroy_node(_Link_type __p) 534 { get_allocator().destroy(__p->_M_valptr()); } 535 #else 536 template<typename... _Args> 537 void 538 _M_construct_node(_Link_type __node, _Args&&... __args) 539 { 540 __try 541 { 542 ::new(__node) _Rb_tree_node<_Val>; 543 _Alloc_traits::construct(_M_get_Node_allocator(), 544 __node->_M_valptr(), 545 std::forward<_Args>(__args)...); 546 } 547 __catch(...) 548 { 549 __node->~_Rb_tree_node<_Val>(); 550 _M_put_node(__node); 551 __throw_exception_again; 552 } 553 } 554 555 template<typename... _Args> 556 _Link_type 557 _M_create_node(_Args&&... __args) 558 { 559 _Link_type __tmp = _M_get_node(); 560 _M_construct_node(__tmp, std::forward<_Args>(__args)...); 561 return __tmp; 562 } 563 564 void 565 _M_destroy_node(_Link_type __p) noexcept 566 { 567 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr()); 568 __p->~_Rb_tree_node<_Val>(); 569 } 570 #endif 571 572 void 573 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT 574 { 575 _M_destroy_node(__p); 576 _M_put_node(__p); 577 } 578 579 template<typename _NodeGen> 580 _Link_type 581 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen) 582 { 583 _Link_type __tmp = __node_gen(*__x->_M_valptr()); 584 __tmp->_M_color = __x->_M_color; 585 __tmp->_M_left = 0; 586 __tmp->_M_right = 0; 587 return __tmp; 588 } 589 590 protected: 591 // Unused _Is_pod_comparator is kept as it is part of mangled name. 592 template<typename _Key_compare, 593 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)> 594 struct _Rb_tree_impl : public _Node_allocator 595 { 596 _Key_compare _M_key_compare; 597 _Rb_tree_node_base _M_header; 598 size_type _M_node_count; // Keeps track of size of tree. 599 600 _Rb_tree_impl() 601 : _Node_allocator(), _M_key_compare(), _M_header(), 602 _M_node_count(0) 603 { _M_initialize(); } 604 605 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 606 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), 607 _M_node_count(0) 608 { _M_initialize(); } 609 610 #if __cplusplus >= 201103L 611 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) 612 : _Node_allocator(std::move(__a)), _M_key_compare(__comp), 613 _M_header(), _M_node_count(0) 614 { _M_initialize(); } 615 #endif 616 617 void 618 _M_reset() 619 { 620 this->_M_header._M_parent = 0; 621 this->_M_header._M_left = &this->_M_header; 622 this->_M_header._M_right = &this->_M_header; 623 this->_M_node_count = 0; 624 } 625 626 private: 627 void 628 _M_initialize() 629 { 630 this->_M_header._M_color = _S_red; 631 this->_M_header._M_parent = 0; 632 this->_M_header._M_left = &this->_M_header; 633 this->_M_header._M_right = &this->_M_header; 634 } 635 }; 636 637 _Rb_tree_impl<_Compare> _M_impl; 638 639 protected: 640 _Base_ptr& 641 _M_root() _GLIBCXX_NOEXCEPT 642 { return this->_M_impl._M_header._M_parent; } 643 644 _Const_Base_ptr 645 _M_root() const _GLIBCXX_NOEXCEPT 646 { return this->_M_impl._M_header._M_parent; } 647 648 _Base_ptr& 649 _M_leftmost() _GLIBCXX_NOEXCEPT 650 { return this->_M_impl._M_header._M_left; } 651 652 _Const_Base_ptr 653 _M_leftmost() const _GLIBCXX_NOEXCEPT 654 { return this->_M_impl._M_header._M_left; } 655 656 _Base_ptr& 657 _M_rightmost() _GLIBCXX_NOEXCEPT 658 { return this->_M_impl._M_header._M_right; } 659 660 _Const_Base_ptr 661 _M_rightmost() const _GLIBCXX_NOEXCEPT 662 { return this->_M_impl._M_header._M_right; } 663 664 _Link_type 665 _M_begin() _GLIBCXX_NOEXCEPT 666 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 667 668 _Const_Link_type 669 _M_begin() const _GLIBCXX_NOEXCEPT 670 { 671 return static_cast<_Const_Link_type> 672 (this->_M_impl._M_header._M_parent); 673 } 674 675 _Base_ptr 676 _M_end() _GLIBCXX_NOEXCEPT 677 { return &this->_M_impl._M_header; } 678 679 _Const_Base_ptr 680 _M_end() const _GLIBCXX_NOEXCEPT 681 { return &this->_M_impl._M_header; } 682 683 static const_reference 684 _S_value(_Const_Link_type __x) 685 { return *__x->_M_valptr(); } 686 687 static const _Key& 688 _S_key(_Const_Link_type __x) 689 { return _KeyOfValue()(_S_value(__x)); } 690 691 static _Link_type 692 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT 693 { return static_cast<_Link_type>(__x->_M_left); } 694 695 static _Const_Link_type 696 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 697 { return static_cast<_Const_Link_type>(__x->_M_left); } 698 699 static _Link_type 700 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT 701 { return static_cast<_Link_type>(__x->_M_right); } 702 703 static _Const_Link_type 704 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 705 { return static_cast<_Const_Link_type>(__x->_M_right); } 706 707 static const_reference 708 _S_value(_Const_Base_ptr __x) 709 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); } 710 711 static const _Key& 712 _S_key(_Const_Base_ptr __x) 713 { return _KeyOfValue()(_S_value(__x)); } 714 715 static _Base_ptr 716 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 717 { return _Rb_tree_node_base::_S_minimum(__x); } 718 719 static _Const_Base_ptr 720 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 721 { return _Rb_tree_node_base::_S_minimum(__x); } 722 723 static _Base_ptr 724 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 725 { return _Rb_tree_node_base::_S_maximum(__x); } 726 727 static _Const_Base_ptr 728 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 729 { return _Rb_tree_node_base::_S_maximum(__x); } 730 731 public: 732 typedef _Rb_tree_iterator<value_type> iterator; 733 typedef _Rb_tree_const_iterator<value_type> const_iterator; 734 735 typedef std::reverse_iterator<iterator> reverse_iterator; 736 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 737 738 pair<_Base_ptr, _Base_ptr> 739 _M_get_insert_unique_pos(const key_type& __k); 740 741 pair<_Base_ptr, _Base_ptr> 742 _M_get_insert_equal_pos(const key_type& __k); 743 744 pair<_Base_ptr, _Base_ptr> 745 _M_get_insert_hint_unique_pos(const_iterator __pos, 746 const key_type& __k); 747 748 pair<_Base_ptr, _Base_ptr> 749 _M_get_insert_hint_equal_pos(const_iterator __pos, 750 const key_type& __k); 751 752 private: 753 #if __cplusplus >= 201103L 754 template<typename _Arg, typename _NodeGen> 755 iterator 756 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&); 757 758 iterator 759 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); 760 761 template<typename _Arg> 762 iterator 763 _M_insert_lower(_Base_ptr __y, _Arg&& __v); 764 765 template<typename _Arg> 766 iterator 767 _M_insert_equal_lower(_Arg&& __x); 768 769 iterator 770 _M_insert_lower_node(_Base_ptr __p, _Link_type __z); 771 772 iterator 773 _M_insert_equal_lower_node(_Link_type __z); 774 #else 775 template<typename _NodeGen> 776 iterator 777 _M_insert_(_Base_ptr __x, _Base_ptr __y, 778 const value_type& __v, _NodeGen&); 779 780 // _GLIBCXX_RESOLVE_LIB_DEFECTS 781 // 233. Insertion hints in associative containers. 782 iterator 783 _M_insert_lower(_Base_ptr __y, const value_type& __v); 784 785 iterator 786 _M_insert_equal_lower(const value_type& __x); 787 #endif 788 789 template<typename _NodeGen> 790 _Link_type 791 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&); 792 793 _Link_type 794 _M_copy(_Const_Link_type __x, _Base_ptr __p) 795 { 796 _Alloc_node __an(*this); 797 return _M_copy(__x, __p, __an); 798 } 799 800 void 801 _M_erase(_Link_type __x); 802 803 iterator 804 _M_lower_bound(_Link_type __x, _Base_ptr __y, 805 const _Key& __k); 806 807 const_iterator 808 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, 809 const _Key& __k) const; 810 811 iterator 812 _M_upper_bound(_Link_type __x, _Base_ptr __y, 813 const _Key& __k); 814 815 const_iterator 816 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, 817 const _Key& __k) const; 818 819 public: 820 // allocation/deallocation 821 _Rb_tree() { } 822 823 _Rb_tree(const _Compare& __comp, 824 const allocator_type& __a = allocator_type()) 825 : _M_impl(__comp, _Node_allocator(__a)) { } 826 827 _Rb_tree(const _Rb_tree& __x) 828 : _M_impl(__x._M_impl._M_key_compare, 829 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator())) 830 { 831 if (__x._M_root() != 0) 832 { 833 _M_root() = _M_copy(__x._M_begin(), _M_end()); 834 _M_leftmost() = _S_minimum(_M_root()); 835 _M_rightmost() = _S_maximum(_M_root()); 836 _M_impl._M_node_count = __x._M_impl._M_node_count; 837 } 838 } 839 840 #if __cplusplus >= 201103L 841 _Rb_tree(const allocator_type& __a) 842 : _M_impl(_Compare(), _Node_allocator(__a)) 843 { } 844 845 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a) 846 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) 847 { 848 if (__x._M_root() != nullptr) 849 { 850 _M_root() = _M_copy(__x._M_begin(), _M_end()); 851 _M_leftmost() = _S_minimum(_M_root()); 852 _M_rightmost() = _S_maximum(_M_root()); 853 _M_impl._M_node_count = __x._M_impl._M_node_count; 854 } 855 } 856 857 _Rb_tree(_Rb_tree&& __x) 858 : _M_impl(__x._M_impl._M_key_compare, 859 std::move(__x._M_get_Node_allocator())) 860 { 861 if (__x._M_root() != 0) 862 _M_move_data(__x, std::true_type()); 863 } 864 865 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a) 866 : _Rb_tree(std::move(__x), _Node_allocator(__a)) 867 { } 868 869 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a); 870 #endif 871 872 ~_Rb_tree() _GLIBCXX_NOEXCEPT 873 { _M_erase(_M_begin()); } 874 875 _Rb_tree& 876 operator=(const _Rb_tree& __x); 877 878 // Accessors. 879 _Compare 880 key_comp() const 881 { return _M_impl._M_key_compare; } 882 883 iterator 884 begin() _GLIBCXX_NOEXCEPT 885 { return iterator(this->_M_impl._M_header._M_left); } 886 887 const_iterator 888 begin() const _GLIBCXX_NOEXCEPT 889 { return const_iterator(this->_M_impl._M_header._M_left); } 890 891 iterator 892 end() _GLIBCXX_NOEXCEPT 893 { return iterator(&this->_M_impl._M_header); } 894 895 const_iterator 896 end() const _GLIBCXX_NOEXCEPT 897 { return const_iterator(&this->_M_impl._M_header); } 898 899 reverse_iterator 900 rbegin() _GLIBCXX_NOEXCEPT 901 { return reverse_iterator(end()); } 902 903 const_reverse_iterator 904 rbegin() const _GLIBCXX_NOEXCEPT 905 { return const_reverse_iterator(end()); } 906 907 reverse_iterator 908 rend() _GLIBCXX_NOEXCEPT 909 { return reverse_iterator(begin()); } 910 911 const_reverse_iterator 912 rend() const _GLIBCXX_NOEXCEPT 913 { return const_reverse_iterator(begin()); } 914 915 bool 916 empty() const _GLIBCXX_NOEXCEPT 917 { return _M_impl._M_node_count == 0; } 918 919 size_type 920 size() const _GLIBCXX_NOEXCEPT 921 { return _M_impl._M_node_count; } 922 923 size_type 924 max_size() const _GLIBCXX_NOEXCEPT 925 { return _Alloc_traits::max_size(_M_get_Node_allocator()); } 926 927 void 928 swap(_Rb_tree& __t) 929 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value); 930 931 // Insert/erase. 932 #if __cplusplus >= 201103L 933 template<typename _Arg> 934 pair<iterator, bool> 935 _M_insert_unique(_Arg&& __x); 936 937 template<typename _Arg> 938 iterator 939 _M_insert_equal(_Arg&& __x); 940 941 template<typename _Arg, typename _NodeGen> 942 iterator 943 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&); 944 945 template<typename _Arg> 946 iterator 947 _M_insert_unique_(const_iterator __pos, _Arg&& __x) 948 { 949 _Alloc_node __an(*this); 950 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an); 951 } 952 953 template<typename _Arg, typename _NodeGen> 954 iterator 955 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&); 956 957 template<typename _Arg> 958 iterator 959 _M_insert_equal_(const_iterator __pos, _Arg&& __x) 960 { 961 _Alloc_node __an(*this); 962 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); 963 } 964 965 template<typename... _Args> 966 pair<iterator, bool> 967 _M_emplace_unique(_Args&&... __args); 968 969 template<typename... _Args> 970 iterator 971 _M_emplace_equal(_Args&&... __args); 972 973 template<typename... _Args> 974 iterator 975 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); 976 977 template<typename... _Args> 978 iterator 979 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); 980 #else 981 pair<iterator, bool> 982 _M_insert_unique(const value_type& __x); 983 984 iterator 985 _M_insert_equal(const value_type& __x); 986 987 template<typename _NodeGen> 988 iterator 989 _M_insert_unique_(const_iterator __pos, const value_type& __x, 990 _NodeGen&); 991 992 iterator 993 _M_insert_unique_(const_iterator __pos, const value_type& __x) 994 { 995 _Alloc_node __an(*this); 996 return _M_insert_unique_(__pos, __x, __an); 997 } 998 999 template<typename _NodeGen> 1000 iterator 1001 _M_insert_equal_(const_iterator __pos, const value_type& __x, 1002 _NodeGen&); 1003 iterator 1004 _M_insert_equal_(const_iterator __pos, const value_type& __x) 1005 { 1006 _Alloc_node __an(*this); 1007 return _M_insert_equal_(__pos, __x, __an); 1008 } 1009 #endif 1010 1011 template<typename _InputIterator> 1012 void 1013 _M_insert_unique(_InputIterator __first, _InputIterator __last); 1014 1015 template<typename _InputIterator> 1016 void 1017 _M_insert_equal(_InputIterator __first, _InputIterator __last); 1018 1019 private: 1020 void 1021 _M_erase_aux(const_iterator __position); 1022 1023 void 1024 _M_erase_aux(const_iterator __first, const_iterator __last); 1025 1026 public: 1027 #if __cplusplus >= 201103L 1028 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1029 // DR 130. Associative erase should return an iterator. 1030 _GLIBCXX_ABI_TAG_CXX11 1031 iterator 1032 erase(const_iterator __position) 1033 { 1034 const_iterator __result = __position; 1035 ++__result; 1036 _M_erase_aux(__position); 1037 return __result._M_const_cast(); 1038 } 1039 1040 // LWG 2059. 1041 _GLIBCXX_ABI_TAG_CXX11 1042 iterator 1043 erase(iterator __position) 1044 { 1045 iterator __result = __position; 1046 ++__result; 1047 _M_erase_aux(__position); 1048 return __result; 1049 } 1050 #else 1051 void 1052 erase(iterator __position) 1053 { _M_erase_aux(__position); } 1054 1055 void 1056 erase(const_iterator __position) 1057 { _M_erase_aux(__position); } 1058 #endif 1059 size_type 1060 erase(const key_type& __x); 1061 1062 #if __cplusplus >= 201103L 1063 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1064 // DR 130. Associative erase should return an iterator. 1065 _GLIBCXX_ABI_TAG_CXX11 1066 iterator 1067 erase(const_iterator __first, const_iterator __last) 1068 { 1069 _M_erase_aux(__first, __last); 1070 return __last._M_const_cast(); 1071 } 1072 #else 1073 void 1074 erase(iterator __first, iterator __last) 1075 { _M_erase_aux(__first, __last); } 1076 1077 void 1078 erase(const_iterator __first, const_iterator __last) 1079 { _M_erase_aux(__first, __last); } 1080 #endif 1081 void 1082 erase(const key_type* __first, const key_type* __last); 1083 1084 void 1085 clear() _GLIBCXX_NOEXCEPT 1086 { 1087 _M_erase(_M_begin()); 1088 _M_impl._M_reset(); 1089 } 1090 1091 // Set operations. 1092 iterator 1093 find(const key_type& __k); 1094 1095 const_iterator 1096 find(const key_type& __k) const; 1097 1098 size_type 1099 count(const key_type& __k) const; 1100 1101 iterator 1102 lower_bound(const key_type& __k) 1103 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 1104 1105 const_iterator 1106 lower_bound(const key_type& __k) const 1107 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 1108 1109 iterator 1110 upper_bound(const key_type& __k) 1111 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 1112 1113 const_iterator 1114 upper_bound(const key_type& __k) const 1115 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 1116 1117 pair<iterator, iterator> 1118 equal_range(const key_type& __k); 1119 1120 pair<const_iterator, const_iterator> 1121 equal_range(const key_type& __k) const; 1122 1123 #if __cplusplus > 201103L 1124 template<typename _Kt, 1125 typename _Req = 1126 typename __has_is_transparent<_Compare, _Kt>::type> 1127 iterator 1128 _M_find_tr(const _Kt& __k) 1129 { 1130 const _Rb_tree* __const_this = this; 1131 return __const_this->_M_find_tr(__k)._M_const_cast(); 1132 } 1133 1134 template<typename _Kt, 1135 typename _Req = 1136 typename __has_is_transparent<_Compare, _Kt>::type> 1137 const_iterator 1138 _M_find_tr(const _Kt& __k) const 1139 { 1140 auto __j = _M_lower_bound_tr(__k); 1141 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node))) 1142 __j = end(); 1143 return __j; 1144 } 1145 1146 template<typename _Kt, 1147 typename _Req = 1148 typename __has_is_transparent<_Compare, _Kt>::type> 1149 size_type 1150 _M_count_tr(const _Kt& __k) const 1151 { 1152 auto __p = _M_equal_range_tr(__k); 1153 return std::distance(__p.first, __p.second); 1154 } 1155 1156 template<typename _Kt, 1157 typename _Req = 1158 typename __has_is_transparent<_Compare, _Kt>::type> 1159 iterator 1160 _M_lower_bound_tr(const _Kt& __k) 1161 { 1162 const _Rb_tree* __const_this = this; 1163 return __const_this->_M_lower_bound_tr(__k)._M_const_cast(); 1164 } 1165 1166 template<typename _Kt, 1167 typename _Req = 1168 typename __has_is_transparent<_Compare, _Kt>::type> 1169 const_iterator 1170 _M_lower_bound_tr(const _Kt& __k) const 1171 { 1172 auto __x = _M_begin(); 1173 auto __y = _M_end(); 1174 while (__x != 0) 1175 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1176 { 1177 __y = __x; 1178 __x = _S_left(__x); 1179 } 1180 else 1181 __x = _S_right(__x); 1182 return const_iterator(__y); 1183 } 1184 1185 template<typename _Kt, 1186 typename _Req = 1187 typename __has_is_transparent<_Compare, _Kt>::type> 1188 iterator 1189 _M_upper_bound_tr(const _Kt& __k) 1190 { 1191 const _Rb_tree* __const_this = this; 1192 return __const_this->_M_upper_bound_tr(__k)._M_const_cast(); 1193 } 1194 1195 template<typename _Kt, 1196 typename _Req = 1197 typename __has_is_transparent<_Compare, _Kt>::type> 1198 const_iterator 1199 _M_upper_bound_tr(const _Kt& __k) const 1200 { 1201 auto __x = _M_begin(); 1202 auto __y = _M_end(); 1203 while (__x != 0) 1204 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1205 { 1206 __y = __x; 1207 __x = _S_left(__x); 1208 } 1209 else 1210 __x = _S_right(__x); 1211 return const_iterator(__y); 1212 } 1213 1214 template<typename _Kt, 1215 typename _Req = 1216 typename __has_is_transparent<_Compare, _Kt>::type> 1217 pair<iterator, iterator> 1218 _M_equal_range_tr(const _Kt& __k) 1219 { 1220 const _Rb_tree* __const_this = this; 1221 auto __ret = __const_this->_M_equal_range_tr(__k); 1222 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() }; 1223 } 1224 1225 template<typename _Kt, 1226 typename _Req = 1227 typename __has_is_transparent<_Compare, _Kt>::type> 1228 pair<const_iterator, const_iterator> 1229 _M_equal_range_tr(const _Kt& __k) const 1230 { 1231 auto __low = _M_lower_bound_tr(__k); 1232 auto __high = __low; 1233 auto& __cmp = _M_impl._M_key_compare; 1234 while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) 1235 ++__high; 1236 return { __low, __high }; 1237 } 1238 #endif 1239 1240 // Debugging. 1241 bool 1242 __rb_verify() const; 1243 1244 #if __cplusplus >= 201103L 1245 _Rb_tree& 1246 operator=(_Rb_tree&&) 1247 noexcept(_Alloc_traits::_S_nothrow_move() 1248 && is_nothrow_move_assignable<_Compare>::value); 1249 1250 template<typename _Iterator> 1251 void 1252 _M_assign_unique(_Iterator, _Iterator); 1253 1254 template<typename _Iterator> 1255 void 1256 _M_assign_equal(_Iterator, _Iterator); 1257 1258 private: 1259 // Move elements from container with equal allocator. 1260 void 1261 _M_move_data(_Rb_tree&, std::true_type); 1262 1263 // Move elements from container with possibly non-equal allocator, 1264 // which might result in a copy not a move. 1265 void 1266 _M_move_data(_Rb_tree&, std::false_type); 1267 1268 // Move assignment from container with equal allocator. 1269 void 1270 _M_move_assign(_Rb_tree&, std::true_type); 1271 1272 // Move assignment from container with possibly non-equal allocator, 1273 // which might result in a copy not a move. 1274 void 1275 _M_move_assign(_Rb_tree&, std::false_type); 1276 #endif 1277 }; 1278 1279 template<typename _Key, typename _Val, typename _KeyOfValue, 1280 typename _Compare, typename _Alloc> 1281 inline bool 1282 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1283 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1284 { 1285 return __x.size() == __y.size() 1286 && std::equal(__x.begin(), __x.end(), __y.begin()); 1287 } 1288 1289 template<typename _Key, typename _Val, typename _KeyOfValue, 1290 typename _Compare, typename _Alloc> 1291 inline bool 1292 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1293 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1294 { 1295 return std::lexicographical_compare(__x.begin(), __x.end(), 1296 __y.begin(), __y.end()); 1297 } 1298 1299 template<typename _Key, typename _Val, typename _KeyOfValue, 1300 typename _Compare, typename _Alloc> 1301 inline bool 1302 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1303 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1304 { return !(__x == __y); } 1305 1306 template<typename _Key, typename _Val, typename _KeyOfValue, 1307 typename _Compare, typename _Alloc> 1308 inline bool 1309 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1310 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1311 { return __y < __x; } 1312 1313 template<typename _Key, typename _Val, typename _KeyOfValue, 1314 typename _Compare, typename _Alloc> 1315 inline bool 1316 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1317 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1318 { return !(__y < __x); } 1319 1320 template<typename _Key, typename _Val, typename _KeyOfValue, 1321 typename _Compare, typename _Alloc> 1322 inline bool 1323 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1324 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1325 { return !(__x < __y); } 1326 1327 template<typename _Key, typename _Val, typename _KeyOfValue, 1328 typename _Compare, typename _Alloc> 1329 inline void 1330 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1331 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1332 { __x.swap(__y); } 1333 1334 #if __cplusplus >= 201103L 1335 template<typename _Key, typename _Val, typename _KeyOfValue, 1336 typename _Compare, typename _Alloc> 1337 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1338 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) 1339 : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) 1340 { 1341 using __eq = typename _Alloc_traits::is_always_equal; 1342 if (__x._M_root() != nullptr) 1343 _M_move_data(__x, __eq()); 1344 } 1345 1346 template<typename _Key, typename _Val, typename _KeyOfValue, 1347 typename _Compare, typename _Alloc> 1348 void 1349 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1350 _M_move_data(_Rb_tree& __x, std::true_type) 1351 { 1352 _M_root() = __x._M_root(); 1353 _M_leftmost() = __x._M_leftmost(); 1354 _M_rightmost() = __x._M_rightmost(); 1355 _M_root()->_M_parent = _M_end(); 1356 1357 __x._M_root() = 0; 1358 __x._M_leftmost() = __x._M_end(); 1359 __x._M_rightmost() = __x._M_end(); 1360 1361 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 1362 __x._M_impl._M_node_count = 0; 1363 } 1364 1365 template<typename _Key, typename _Val, typename _KeyOfValue, 1366 typename _Compare, typename _Alloc> 1367 void 1368 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1369 _M_move_data(_Rb_tree& __x, std::false_type) 1370 { 1371 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 1372 _M_move_data(__x, std::true_type()); 1373 else 1374 { 1375 _Alloc_node __an(*this); 1376 auto __lbd = 1377 [&__an](const value_type& __cval) 1378 { 1379 auto& __val = const_cast<value_type&>(__cval); 1380 return __an(std::move_if_noexcept(__val)); 1381 }; 1382 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); 1383 _M_leftmost() = _S_minimum(_M_root()); 1384 _M_rightmost() = _S_maximum(_M_root()); 1385 _M_impl._M_node_count = __x._M_impl._M_node_count; 1386 } 1387 } 1388 1389 template<typename _Key, typename _Val, typename _KeyOfValue, 1390 typename _Compare, typename _Alloc> 1391 inline void 1392 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1393 _M_move_assign(_Rb_tree& __x, true_type) 1394 { 1395 clear(); 1396 if (__x._M_root() != nullptr) 1397 _M_move_data(__x, std::true_type()); 1398 std::__alloc_on_move(_M_get_Node_allocator(), 1399 __x._M_get_Node_allocator()); 1400 } 1401 1402 template<typename _Key, typename _Val, typename _KeyOfValue, 1403 typename _Compare, typename _Alloc> 1404 void 1405 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1406 _M_move_assign(_Rb_tree& __x, false_type) 1407 { 1408 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 1409 return _M_move_assign(__x, true_type{}); 1410 1411 // Try to move each node reusing existing nodes and copying __x nodes 1412 // structure. 1413 _Reuse_or_alloc_node __roan(*this); 1414 _M_impl._M_reset(); 1415 if (__x._M_root() != nullptr) 1416 { 1417 auto __lbd = 1418 [&__roan](const value_type& __cval) 1419 { 1420 auto& __val = const_cast<value_type&>(__cval); 1421 return __roan(std::move_if_noexcept(__val)); 1422 }; 1423 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); 1424 _M_leftmost() = _S_minimum(_M_root()); 1425 _M_rightmost() = _S_maximum(_M_root()); 1426 _M_impl._M_node_count = __x._M_impl._M_node_count; 1427 __x.clear(); 1428 } 1429 } 1430 1431 template<typename _Key, typename _Val, typename _KeyOfValue, 1432 typename _Compare, typename _Alloc> 1433 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 1434 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1435 operator=(_Rb_tree&& __x) 1436 noexcept(_Alloc_traits::_S_nothrow_move() 1437 && is_nothrow_move_assignable<_Compare>::value) 1438 { 1439 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 1440 constexpr bool __move_storage = 1441 _Alloc_traits::_S_propagate_on_move_assign() 1442 || _Alloc_traits::_S_always_equal(); 1443 _M_move_assign(__x, __bool_constant<__move_storage>()); 1444 return *this; 1445 } 1446 1447 template<typename _Key, typename _Val, typename _KeyOfValue, 1448 typename _Compare, typename _Alloc> 1449 template<typename _Iterator> 1450 void 1451 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1452 _M_assign_unique(_Iterator __first, _Iterator __last) 1453 { 1454 _Reuse_or_alloc_node __roan(*this); 1455 _M_impl._M_reset(); 1456 for (; __first != __last; ++__first) 1457 _M_insert_unique_(end(), *__first, __roan); 1458 } 1459 1460 template<typename _Key, typename _Val, typename _KeyOfValue, 1461 typename _Compare, typename _Alloc> 1462 template<typename _Iterator> 1463 void 1464 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1465 _M_assign_equal(_Iterator __first, _Iterator __last) 1466 { 1467 _Reuse_or_alloc_node __roan(*this); 1468 _M_impl._M_reset(); 1469 for (; __first != __last; ++__first) 1470 _M_insert_equal_(end(), *__first, __roan); 1471 } 1472 #endif 1473 1474 template<typename _Key, typename _Val, typename _KeyOfValue, 1475 typename _Compare, typename _Alloc> 1476 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 1477 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1478 operator=(const _Rb_tree& __x) 1479 { 1480 if (this != &__x) 1481 { 1482 // Note that _Key may be a constant type. 1483 #if __cplusplus >= 201103L 1484 if (_Alloc_traits::_S_propagate_on_copy_assign()) 1485 { 1486 auto& __this_alloc = this->_M_get_Node_allocator(); 1487 auto& __that_alloc = __x._M_get_Node_allocator(); 1488 if (!_Alloc_traits::_S_always_equal() 1489 && __this_alloc != __that_alloc) 1490 { 1491 // Replacement allocator cannot free existing storage, we need 1492 // to erase nodes first. 1493 clear(); 1494 std::__alloc_on_copy(__this_alloc, __that_alloc); 1495 } 1496 } 1497 #endif 1498 1499 _Reuse_or_alloc_node __roan(*this); 1500 _M_impl._M_reset(); 1501 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 1502 if (__x._M_root() != 0) 1503 { 1504 _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan); 1505 _M_leftmost() = _S_minimum(_M_root()); 1506 _M_rightmost() = _S_maximum(_M_root()); 1507 _M_impl._M_node_count = __x._M_impl._M_node_count; 1508 } 1509 } 1510 1511 return *this; 1512 } 1513 1514 template<typename _Key, typename _Val, typename _KeyOfValue, 1515 typename _Compare, typename _Alloc> 1516 #if __cplusplus >= 201103L 1517 template<typename _Arg, typename _NodeGen> 1518 #else 1519 template<typename _NodeGen> 1520 #endif 1521 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1522 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1523 _M_insert_(_Base_ptr __x, _Base_ptr __p, 1524 #if __cplusplus >= 201103L 1525 _Arg&& __v, 1526 #else 1527 const _Val& __v, 1528 #endif 1529 _NodeGen& __node_gen) 1530 { 1531 bool __insert_left = (__x != 0 || __p == _M_end() 1532 || _M_impl._M_key_compare(_KeyOfValue()(__v), 1533 _S_key(__p))); 1534 1535 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); 1536 1537 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1538 this->_M_impl._M_header); 1539 ++_M_impl._M_node_count; 1540 return iterator(__z); 1541 } 1542 1543 template<typename _Key, typename _Val, typename _KeyOfValue, 1544 typename _Compare, typename _Alloc> 1545 #if __cplusplus >= 201103L 1546 template<typename _Arg> 1547 #endif 1548 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1549 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1550 #if __cplusplus >= 201103L 1551 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 1552 #else 1553 _M_insert_lower(_Base_ptr __p, const _Val& __v) 1554 #endif 1555 { 1556 bool __insert_left = (__p == _M_end() 1557 || !_M_impl._M_key_compare(_S_key(__p), 1558 _KeyOfValue()(__v))); 1559 1560 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 1561 1562 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1563 this->_M_impl._M_header); 1564 ++_M_impl._M_node_count; 1565 return iterator(__z); 1566 } 1567 1568 template<typename _Key, typename _Val, typename _KeyOfValue, 1569 typename _Compare, typename _Alloc> 1570 #if __cplusplus >= 201103L 1571 template<typename _Arg> 1572 #endif 1573 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1574 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1575 #if __cplusplus >= 201103L 1576 _M_insert_equal_lower(_Arg&& __v) 1577 #else 1578 _M_insert_equal_lower(const _Val& __v) 1579 #endif 1580 { 1581 _Link_type __x = _M_begin(); 1582 _Base_ptr __y = _M_end(); 1583 while (__x != 0) 1584 { 1585 __y = __x; 1586 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 1587 _S_left(__x) : _S_right(__x); 1588 } 1589 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 1590 } 1591 1592 template<typename _Key, typename _Val, typename _KoV, 1593 typename _Compare, typename _Alloc> 1594 template<typename _NodeGen> 1595 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 1596 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 1597 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) 1598 { 1599 // Structural copy. __x and __p must be non-null. 1600 _Link_type __top = _M_clone_node(__x, __node_gen); 1601 __top->_M_parent = __p; 1602 1603 __try 1604 { 1605 if (__x->_M_right) 1606 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen); 1607 __p = __top; 1608 __x = _S_left(__x); 1609 1610 while (__x != 0) 1611 { 1612 _Link_type __y = _M_clone_node(__x, __node_gen); 1613 __p->_M_left = __y; 1614 __y->_M_parent = __p; 1615 if (__x->_M_right) 1616 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen); 1617 __p = __y; 1618 __x = _S_left(__x); 1619 } 1620 } 1621 __catch(...) 1622 { 1623 _M_erase(__top); 1624 __throw_exception_again; 1625 } 1626 return __top; 1627 } 1628 1629 template<typename _Key, typename _Val, typename _KeyOfValue, 1630 typename _Compare, typename _Alloc> 1631 void 1632 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1633 _M_erase(_Link_type __x) 1634 { 1635 // Erase without rebalancing. 1636 while (__x != 0) 1637 { 1638 _M_erase(_S_right(__x)); 1639 _Link_type __y = _S_left(__x); 1640 _M_drop_node(__x); 1641 __x = __y; 1642 } 1643 } 1644 1645 template<typename _Key, typename _Val, typename _KeyOfValue, 1646 typename _Compare, typename _Alloc> 1647 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1648 _Compare, _Alloc>::iterator 1649 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1650 _M_lower_bound(_Link_type __x, _Base_ptr __y, 1651 const _Key& __k) 1652 { 1653 while (__x != 0) 1654 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1655 __y = __x, __x = _S_left(__x); 1656 else 1657 __x = _S_right(__x); 1658 return iterator(__y); 1659 } 1660 1661 template<typename _Key, typename _Val, typename _KeyOfValue, 1662 typename _Compare, typename _Alloc> 1663 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1664 _Compare, _Alloc>::const_iterator 1665 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1666 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, 1667 const _Key& __k) const 1668 { 1669 while (__x != 0) 1670 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1671 __y = __x, __x = _S_left(__x); 1672 else 1673 __x = _S_right(__x); 1674 return const_iterator(__y); 1675 } 1676 1677 template<typename _Key, typename _Val, typename _KeyOfValue, 1678 typename _Compare, typename _Alloc> 1679 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1680 _Compare, _Alloc>::iterator 1681 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1682 _M_upper_bound(_Link_type __x, _Base_ptr __y, 1683 const _Key& __k) 1684 { 1685 while (__x != 0) 1686 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1687 __y = __x, __x = _S_left(__x); 1688 else 1689 __x = _S_right(__x); 1690 return iterator(__y); 1691 } 1692 1693 template<typename _Key, typename _Val, typename _KeyOfValue, 1694 typename _Compare, typename _Alloc> 1695 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1696 _Compare, _Alloc>::const_iterator 1697 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1698 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, 1699 const _Key& __k) const 1700 { 1701 while (__x != 0) 1702 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1703 __y = __x, __x = _S_left(__x); 1704 else 1705 __x = _S_right(__x); 1706 return const_iterator(__y); 1707 } 1708 1709 template<typename _Key, typename _Val, typename _KeyOfValue, 1710 typename _Compare, typename _Alloc> 1711 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1712 _Compare, _Alloc>::iterator, 1713 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1714 _Compare, _Alloc>::iterator> 1715 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1716 equal_range(const _Key& __k) 1717 { 1718 _Link_type __x = _M_begin(); 1719 _Base_ptr __y = _M_end(); 1720 while (__x != 0) 1721 { 1722 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1723 __x = _S_right(__x); 1724 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1725 __y = __x, __x = _S_left(__x); 1726 else 1727 { 1728 _Link_type __xu(__x); 1729 _Base_ptr __yu(__y); 1730 __y = __x, __x = _S_left(__x); 1731 __xu = _S_right(__xu); 1732 return pair<iterator, 1733 iterator>(_M_lower_bound(__x, __y, __k), 1734 _M_upper_bound(__xu, __yu, __k)); 1735 } 1736 } 1737 return pair<iterator, iterator>(iterator(__y), 1738 iterator(__y)); 1739 } 1740 1741 template<typename _Key, typename _Val, typename _KeyOfValue, 1742 typename _Compare, typename _Alloc> 1743 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1744 _Compare, _Alloc>::const_iterator, 1745 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1746 _Compare, _Alloc>::const_iterator> 1747 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1748 equal_range(const _Key& __k) const 1749 { 1750 _Const_Link_type __x = _M_begin(); 1751 _Const_Base_ptr __y = _M_end(); 1752 while (__x != 0) 1753 { 1754 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1755 __x = _S_right(__x); 1756 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1757 __y = __x, __x = _S_left(__x); 1758 else 1759 { 1760 _Const_Link_type __xu(__x); 1761 _Const_Base_ptr __yu(__y); 1762 __y = __x, __x = _S_left(__x); 1763 __xu = _S_right(__xu); 1764 return pair<const_iterator, 1765 const_iterator>(_M_lower_bound(__x, __y, __k), 1766 _M_upper_bound(__xu, __yu, __k)); 1767 } 1768 } 1769 return pair<const_iterator, const_iterator>(const_iterator(__y), 1770 const_iterator(__y)); 1771 } 1772 1773 template<typename _Key, typename _Val, typename _KeyOfValue, 1774 typename _Compare, typename _Alloc> 1775 void 1776 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1777 swap(_Rb_tree& __t) 1778 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 1779 { 1780 if (_M_root() == 0) 1781 { 1782 if (__t._M_root() != 0) 1783 { 1784 _M_root() = __t._M_root(); 1785 _M_leftmost() = __t._M_leftmost(); 1786 _M_rightmost() = __t._M_rightmost(); 1787 _M_root()->_M_parent = _M_end(); 1788 _M_impl._M_node_count = __t._M_impl._M_node_count; 1789 1790 __t._M_impl._M_reset(); 1791 } 1792 } 1793 else if (__t._M_root() == 0) 1794 { 1795 __t._M_root() = _M_root(); 1796 __t._M_leftmost() = _M_leftmost(); 1797 __t._M_rightmost() = _M_rightmost(); 1798 __t._M_root()->_M_parent = __t._M_end(); 1799 __t._M_impl._M_node_count = _M_impl._M_node_count; 1800 1801 _M_impl._M_reset(); 1802 } 1803 else 1804 { 1805 std::swap(_M_root(),__t._M_root()); 1806 std::swap(_M_leftmost(),__t._M_leftmost()); 1807 std::swap(_M_rightmost(),__t._M_rightmost()); 1808 1809 _M_root()->_M_parent = _M_end(); 1810 __t._M_root()->_M_parent = __t._M_end(); 1811 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 1812 } 1813 // No need to swap header's color as it does not change. 1814 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 1815 1816 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), 1817 __t._M_get_Node_allocator()); 1818 } 1819 1820 template<typename _Key, typename _Val, typename _KeyOfValue, 1821 typename _Compare, typename _Alloc> 1822 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1823 _Compare, _Alloc>::_Base_ptr, 1824 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1825 _Compare, _Alloc>::_Base_ptr> 1826 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1827 _M_get_insert_unique_pos(const key_type& __k) 1828 { 1829 typedef pair<_Base_ptr, _Base_ptr> _Res; 1830 _Link_type __x = _M_begin(); 1831 _Base_ptr __y = _M_end(); 1832 bool __comp = true; 1833 while (__x != 0) 1834 { 1835 __y = __x; 1836 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 1837 __x = __comp ? _S_left(__x) : _S_right(__x); 1838 } 1839 iterator __j = iterator(__y); 1840 if (__comp) 1841 { 1842 if (__j == begin()) 1843 return _Res(__x, __y); 1844 else 1845 --__j; 1846 } 1847 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 1848 return _Res(__x, __y); 1849 return _Res(__j._M_node, 0); 1850 } 1851 1852 template<typename _Key, typename _Val, typename _KeyOfValue, 1853 typename _Compare, typename _Alloc> 1854 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1855 _Compare, _Alloc>::_Base_ptr, 1856 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1857 _Compare, _Alloc>::_Base_ptr> 1858 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1859 _M_get_insert_equal_pos(const key_type& __k) 1860 { 1861 typedef pair<_Base_ptr, _Base_ptr> _Res; 1862 _Link_type __x = _M_begin(); 1863 _Base_ptr __y = _M_end(); 1864 while (__x != 0) 1865 { 1866 __y = __x; 1867 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 1868 _S_left(__x) : _S_right(__x); 1869 } 1870 return _Res(__x, __y); 1871 } 1872 1873 template<typename _Key, typename _Val, typename _KeyOfValue, 1874 typename _Compare, typename _Alloc> 1875 #if __cplusplus >= 201103L 1876 template<typename _Arg> 1877 #endif 1878 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1879 _Compare, _Alloc>::iterator, bool> 1880 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1881 #if __cplusplus >= 201103L 1882 _M_insert_unique(_Arg&& __v) 1883 #else 1884 _M_insert_unique(const _Val& __v) 1885 #endif 1886 { 1887 typedef pair<iterator, bool> _Res; 1888 pair<_Base_ptr, _Base_ptr> __res 1889 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 1890 1891 if (__res.second) 1892 { 1893 _Alloc_node __an(*this); 1894 return _Res(_M_insert_(__res.first, __res.second, 1895 _GLIBCXX_FORWARD(_Arg, __v), __an), 1896 true); 1897 } 1898 1899 return _Res(iterator(__res.first), false); 1900 } 1901 1902 template<typename _Key, typename _Val, typename _KeyOfValue, 1903 typename _Compare, typename _Alloc> 1904 #if __cplusplus >= 201103L 1905 template<typename _Arg> 1906 #endif 1907 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1908 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1909 #if __cplusplus >= 201103L 1910 _M_insert_equal(_Arg&& __v) 1911 #else 1912 _M_insert_equal(const _Val& __v) 1913 #endif 1914 { 1915 pair<_Base_ptr, _Base_ptr> __res 1916 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 1917 _Alloc_node __an(*this); 1918 return _M_insert_(__res.first, __res.second, 1919 _GLIBCXX_FORWARD(_Arg, __v), __an); 1920 } 1921 1922 template<typename _Key, typename _Val, typename _KeyOfValue, 1923 typename _Compare, typename _Alloc> 1924 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1925 _Compare, _Alloc>::_Base_ptr, 1926 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1927 _Compare, _Alloc>::_Base_ptr> 1928 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1929 _M_get_insert_hint_unique_pos(const_iterator __position, 1930 const key_type& __k) 1931 { 1932 iterator __pos = __position._M_const_cast(); 1933 typedef pair<_Base_ptr, _Base_ptr> _Res; 1934 1935 // end() 1936 if (__pos._M_node == _M_end()) 1937 { 1938 if (size() > 0 1939 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 1940 return _Res(0, _M_rightmost()); 1941 else 1942 return _M_get_insert_unique_pos(__k); 1943 } 1944 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 1945 { 1946 // First, try before... 1947 iterator __before = __pos; 1948 if (__pos._M_node == _M_leftmost()) // begin() 1949 return _Res(_M_leftmost(), _M_leftmost()); 1950 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 1951 { 1952 if (_S_right(__before._M_node) == 0) 1953 return _Res(0, __before._M_node); 1954 else 1955 return _Res(__pos._M_node, __pos._M_node); 1956 } 1957 else 1958 return _M_get_insert_unique_pos(__k); 1959 } 1960 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 1961 { 1962 // ... then try after. 1963 iterator __after = __pos; 1964 if (__pos._M_node == _M_rightmost()) 1965 return _Res(0, _M_rightmost()); 1966 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 1967 { 1968 if (_S_right(__pos._M_node) == 0) 1969 return _Res(0, __pos._M_node); 1970 else 1971 return _Res(__after._M_node, __after._M_node); 1972 } 1973 else 1974 return _M_get_insert_unique_pos(__k); 1975 } 1976 else 1977 // Equivalent keys. 1978 return _Res(__pos._M_node, 0); 1979 } 1980 1981 template<typename _Key, typename _Val, typename _KeyOfValue, 1982 typename _Compare, typename _Alloc> 1983 #if __cplusplus >= 201103L 1984 template<typename _Arg, typename _NodeGen> 1985 #else 1986 template<typename _NodeGen> 1987 #endif 1988 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1989 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1990 _M_insert_unique_(const_iterator __position, 1991 #if __cplusplus >= 201103L 1992 _Arg&& __v, 1993 #else 1994 const _Val& __v, 1995 #endif 1996 _NodeGen& __node_gen) 1997 { 1998 pair<_Base_ptr, _Base_ptr> __res 1999 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 2000 2001 if (__res.second) 2002 return _M_insert_(__res.first, __res.second, 2003 _GLIBCXX_FORWARD(_Arg, __v), 2004 __node_gen); 2005 return iterator(__res.first); 2006 } 2007 2008 template<typename _Key, typename _Val, typename _KeyOfValue, 2009 typename _Compare, typename _Alloc> 2010 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2011 _Compare, _Alloc>::_Base_ptr, 2012 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2013 _Compare, _Alloc>::_Base_ptr> 2014 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2015 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 2016 { 2017 iterator __pos = __position._M_const_cast(); 2018 typedef pair<_Base_ptr, _Base_ptr> _Res; 2019 2020 // end() 2021 if (__pos._M_node == _M_end()) 2022 { 2023 if (size() > 0 2024 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 2025 return _Res(0, _M_rightmost()); 2026 else 2027 return _M_get_insert_equal_pos(__k); 2028 } 2029 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 2030 { 2031 // First, try before... 2032 iterator __before = __pos; 2033 if (__pos._M_node == _M_leftmost()) // begin() 2034 return _Res(_M_leftmost(), _M_leftmost()); 2035 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 2036 { 2037 if (_S_right(__before._M_node) == 0) 2038 return _Res(0, __before._M_node); 2039 else 2040 return _Res(__pos._M_node, __pos._M_node); 2041 } 2042 else 2043 return _M_get_insert_equal_pos(__k); 2044 } 2045 else 2046 { 2047 // ... then try after. 2048 iterator __after = __pos; 2049 if (__pos._M_node == _M_rightmost()) 2050 return _Res(0, _M_rightmost()); 2051 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 2052 { 2053 if (_S_right(__pos._M_node) == 0) 2054 return _Res(0, __pos._M_node); 2055 else 2056 return _Res(__after._M_node, __after._M_node); 2057 } 2058 else 2059 return _Res(0, 0); 2060 } 2061 } 2062 2063 template<typename _Key, typename _Val, typename _KeyOfValue, 2064 typename _Compare, typename _Alloc> 2065 #if __cplusplus >= 201103L 2066 template<typename _Arg, typename _NodeGen> 2067 #else 2068 template<typename _NodeGen> 2069 #endif 2070 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2071 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2072 _M_insert_equal_(const_iterator __position, 2073 #if __cplusplus >= 201103L 2074 _Arg&& __v, 2075 #else 2076 const _Val& __v, 2077 #endif 2078 _NodeGen& __node_gen) 2079 { 2080 pair<_Base_ptr, _Base_ptr> __res 2081 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 2082 2083 if (__res.second) 2084 return _M_insert_(__res.first, __res.second, 2085 _GLIBCXX_FORWARD(_Arg, __v), 2086 __node_gen); 2087 2088 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 2089 } 2090 2091 #if __cplusplus >= 201103L 2092 template<typename _Key, typename _Val, typename _KeyOfValue, 2093 typename _Compare, typename _Alloc> 2094 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2095 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2096 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 2097 { 2098 bool __insert_left = (__x != 0 || __p == _M_end() 2099 || _M_impl._M_key_compare(_S_key(__z), 2100 _S_key(__p))); 2101 2102 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 2103 this->_M_impl._M_header); 2104 ++_M_impl._M_node_count; 2105 return iterator(__z); 2106 } 2107 2108 template<typename _Key, typename _Val, typename _KeyOfValue, 2109 typename _Compare, typename _Alloc> 2110 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2111 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2112 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 2113 { 2114 bool __insert_left = (__p == _M_end() 2115 || !_M_impl._M_key_compare(_S_key(__p), 2116 _S_key(__z))); 2117 2118 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 2119 this->_M_impl._M_header); 2120 ++_M_impl._M_node_count; 2121 return iterator(__z); 2122 } 2123 2124 template<typename _Key, typename _Val, typename _KeyOfValue, 2125 typename _Compare, typename _Alloc> 2126 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2127 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2128 _M_insert_equal_lower_node(_Link_type __z) 2129 { 2130 _Link_type __x = _M_begin(); 2131 _Base_ptr __y = _M_end(); 2132 while (__x != 0) 2133 { 2134 __y = __x; 2135 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 2136 _S_left(__x) : _S_right(__x); 2137 } 2138 return _M_insert_lower_node(__y, __z); 2139 } 2140 2141 template<typename _Key, typename _Val, typename _KeyOfValue, 2142 typename _Compare, typename _Alloc> 2143 template<typename... _Args> 2144 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2145 _Compare, _Alloc>::iterator, bool> 2146 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2147 _M_emplace_unique(_Args&&... __args) 2148 { 2149 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2150 2151 __try 2152 { 2153 typedef pair<iterator, bool> _Res; 2154 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 2155 if (__res.second) 2156 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 2157 2158 _M_drop_node(__z); 2159 return _Res(iterator(__res.first), false); 2160 } 2161 __catch(...) 2162 { 2163 _M_drop_node(__z); 2164 __throw_exception_again; 2165 } 2166 } 2167 2168 template<typename _Key, typename _Val, typename _KeyOfValue, 2169 typename _Compare, typename _Alloc> 2170 template<typename... _Args> 2171 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2172 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2173 _M_emplace_equal(_Args&&... __args) 2174 { 2175 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2176 2177 __try 2178 { 2179 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 2180 return _M_insert_node(__res.first, __res.second, __z); 2181 } 2182 __catch(...) 2183 { 2184 _M_drop_node(__z); 2185 __throw_exception_again; 2186 } 2187 } 2188 2189 template<typename _Key, typename _Val, typename _KeyOfValue, 2190 typename _Compare, typename _Alloc> 2191 template<typename... _Args> 2192 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2193 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2194 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 2195 { 2196 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2197 2198 __try 2199 { 2200 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 2201 2202 if (__res.second) 2203 return _M_insert_node(__res.first, __res.second, __z); 2204 2205 _M_drop_node(__z); 2206 return iterator(__res.first); 2207 } 2208 __catch(...) 2209 { 2210 _M_drop_node(__z); 2211 __throw_exception_again; 2212 } 2213 } 2214 2215 template<typename _Key, typename _Val, typename _KeyOfValue, 2216 typename _Compare, typename _Alloc> 2217 template<typename... _Args> 2218 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2219 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2220 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 2221 { 2222 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2223 2224 __try 2225 { 2226 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 2227 2228 if (__res.second) 2229 return _M_insert_node(__res.first, __res.second, __z); 2230 2231 return _M_insert_equal_lower_node(__z); 2232 } 2233 __catch(...) 2234 { 2235 _M_drop_node(__z); 2236 __throw_exception_again; 2237 } 2238 } 2239 #endif 2240 2241 template<typename _Key, typename _Val, typename _KoV, 2242 typename _Cmp, typename _Alloc> 2243 template<class _II> 2244 void 2245 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 2246 _M_insert_unique(_II __first, _II __last) 2247 { 2248 _Alloc_node __an(*this); 2249 for (; __first != __last; ++__first) 2250 _M_insert_unique_(end(), *__first, __an); 2251 } 2252 2253 template<typename _Key, typename _Val, typename _KoV, 2254 typename _Cmp, typename _Alloc> 2255 template<class _II> 2256 void 2257 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 2258 _M_insert_equal(_II __first, _II __last) 2259 { 2260 _Alloc_node __an(*this); 2261 for (; __first != __last; ++__first) 2262 _M_insert_equal_(end(), *__first, __an); 2263 } 2264 2265 template<typename _Key, typename _Val, typename _KeyOfValue, 2266 typename _Compare, typename _Alloc> 2267 void 2268 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2269 _M_erase_aux(const_iterator __position) 2270 { 2271 _Link_type __y = 2272 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 2273 (const_cast<_Base_ptr>(__position._M_node), 2274 this->_M_impl._M_header)); 2275 _M_drop_node(__y); 2276 --_M_impl._M_node_count; 2277 } 2278 2279 template<typename _Key, typename _Val, typename _KeyOfValue, 2280 typename _Compare, typename _Alloc> 2281 void 2282 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2283 _M_erase_aux(const_iterator __first, const_iterator __last) 2284 { 2285 if (__first == begin() && __last == end()) 2286 clear(); 2287 else 2288 while (__first != __last) 2289 erase(__first++); 2290 } 2291 2292 template<typename _Key, typename _Val, typename _KeyOfValue, 2293 typename _Compare, typename _Alloc> 2294 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 2295 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2296 erase(const _Key& __x) 2297 { 2298 pair<iterator, iterator> __p = equal_range(__x); 2299 const size_type __old_size = size(); 2300 erase(__p.first, __p.second); 2301 return __old_size - size(); 2302 } 2303 2304 template<typename _Key, typename _Val, typename _KeyOfValue, 2305 typename _Compare, typename _Alloc> 2306 void 2307 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2308 erase(const _Key* __first, const _Key* __last) 2309 { 2310 while (__first != __last) 2311 erase(*__first++); 2312 } 2313 2314 template<typename _Key, typename _Val, typename _KeyOfValue, 2315 typename _Compare, typename _Alloc> 2316 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2317 _Compare, _Alloc>::iterator 2318 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2319 find(const _Key& __k) 2320 { 2321 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 2322 return (__j == end() 2323 || _M_impl._M_key_compare(__k, 2324 _S_key(__j._M_node))) ? end() : __j; 2325 } 2326 2327 template<typename _Key, typename _Val, typename _KeyOfValue, 2328 typename _Compare, typename _Alloc> 2329 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2330 _Compare, _Alloc>::const_iterator 2331 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2332 find(const _Key& __k) const 2333 { 2334 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 2335 return (__j == end() 2336 || _M_impl._M_key_compare(__k, 2337 _S_key(__j._M_node))) ? end() : __j; 2338 } 2339 2340 template<typename _Key, typename _Val, typename _KeyOfValue, 2341 typename _Compare, typename _Alloc> 2342 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 2343 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2344 count(const _Key& __k) const 2345 { 2346 pair<const_iterator, const_iterator> __p = equal_range(__k); 2347 const size_type __n = std::distance(__p.first, __p.second); 2348 return __n; 2349 } 2350 2351 _GLIBCXX_PURE unsigned int 2352 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 2353 const _Rb_tree_node_base* __root) throw (); 2354 2355 template<typename _Key, typename _Val, typename _KeyOfValue, 2356 typename _Compare, typename _Alloc> 2357 bool 2358 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 2359 { 2360 if (_M_impl._M_node_count == 0 || begin() == end()) 2361 return _M_impl._M_node_count == 0 && begin() == end() 2362 && this->_M_impl._M_header._M_left == _M_end() 2363 && this->_M_impl._M_header._M_right == _M_end(); 2364 2365 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 2366 for (const_iterator __it = begin(); __it != end(); ++__it) 2367 { 2368 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 2369 _Const_Link_type __L = _S_left(__x); 2370 _Const_Link_type __R = _S_right(__x); 2371 2372 if (__x->_M_color == _S_red) 2373 if ((__L && __L->_M_color == _S_red) 2374 || (__R && __R->_M_color == _S_red)) 2375 return false; 2376 2377 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 2378 return false; 2379 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 2380 return false; 2381 2382 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 2383 return false; 2384 } 2385 2386 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 2387 return false; 2388 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 2389 return false; 2390 return true; 2391 } 2392 2393 _GLIBCXX_END_NAMESPACE_VERSION 2394 } // namespace 2395 2396 #endif 2397