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