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, 845 std::move(__x._M_get_Node_allocator())) 846 { 847 if (__x._M_root() != 0) 848 _M_move_data(__x, std::true_type()); 849 } 850 851 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a) 852 : _Rb_tree(std::move(__x), _Node_allocator(__a)) 853 { } 854 855 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a); 856 #endif 857 858 ~_Rb_tree() _GLIBCXX_NOEXCEPT 859 { _M_erase(_M_begin()); } 860 861 _Rb_tree& 862 operator=(const _Rb_tree& __x); 863 864 // Accessors. 865 _Compare 866 key_comp() const 867 { return _M_impl._M_key_compare; } 868 869 iterator 870 begin() _GLIBCXX_NOEXCEPT 871 { return iterator(this->_M_impl._M_header._M_left); } 872 873 const_iterator 874 begin() const _GLIBCXX_NOEXCEPT 875 { return const_iterator(this->_M_impl._M_header._M_left); } 876 877 iterator 878 end() _GLIBCXX_NOEXCEPT 879 { return iterator(&this->_M_impl._M_header); } 880 881 const_iterator 882 end() const _GLIBCXX_NOEXCEPT 883 { return const_iterator(&this->_M_impl._M_header); } 884 885 reverse_iterator 886 rbegin() _GLIBCXX_NOEXCEPT 887 { return reverse_iterator(end()); } 888 889 const_reverse_iterator 890 rbegin() const _GLIBCXX_NOEXCEPT 891 { return const_reverse_iterator(end()); } 892 893 reverse_iterator 894 rend() _GLIBCXX_NOEXCEPT 895 { return reverse_iterator(begin()); } 896 897 const_reverse_iterator 898 rend() const _GLIBCXX_NOEXCEPT 899 { return const_reverse_iterator(begin()); } 900 901 bool 902 empty() const _GLIBCXX_NOEXCEPT 903 { return _M_impl._M_node_count == 0; } 904 905 size_type 906 size() const _GLIBCXX_NOEXCEPT 907 { return _M_impl._M_node_count; } 908 909 size_type 910 max_size() const _GLIBCXX_NOEXCEPT 911 { return _Alloc_traits::max_size(_M_get_Node_allocator()); } 912 913 void 914 #if __cplusplus >= 201103L 915 swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap()); 916 #else 917 swap(_Rb_tree& __t); 918 #endif 919 920 // Insert/erase. 921 #if __cplusplus >= 201103L 922 template<typename _Arg> 923 pair<iterator, bool> 924 _M_insert_unique(_Arg&& __x); 925 926 template<typename _Arg> 927 iterator 928 _M_insert_equal(_Arg&& __x); 929 930 template<typename _Arg, typename _NodeGen> 931 iterator 932 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&); 933 934 template<typename _Arg> 935 iterator 936 _M_insert_unique_(const_iterator __pos, _Arg&& __x) 937 { 938 _Alloc_node __an(*this); 939 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an); 940 } 941 942 template<typename _Arg, typename _NodeGen> 943 iterator 944 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&); 945 946 template<typename _Arg> 947 iterator 948 _M_insert_equal_(const_iterator __pos, _Arg&& __x) 949 { 950 _Alloc_node __an(*this); 951 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); 952 } 953 954 template<typename... _Args> 955 pair<iterator, bool> 956 _M_emplace_unique(_Args&&... __args); 957 958 template<typename... _Args> 959 iterator 960 _M_emplace_equal(_Args&&... __args); 961 962 template<typename... _Args> 963 iterator 964 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); 965 966 template<typename... _Args> 967 iterator 968 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); 969 #else 970 pair<iterator, bool> 971 _M_insert_unique(const value_type& __x); 972 973 iterator 974 _M_insert_equal(const value_type& __x); 975 976 template<typename _NodeGen> 977 iterator 978 _M_insert_unique_(const_iterator __pos, const value_type& __x, 979 _NodeGen&); 980 981 iterator 982 _M_insert_unique_(const_iterator __pos, const value_type& __x) 983 { 984 _Alloc_node __an(*this); 985 return _M_insert_unique_(__pos, __x, __an); 986 } 987 988 template<typename _NodeGen> 989 iterator 990 _M_insert_equal_(const_iterator __pos, const value_type& __x, 991 _NodeGen&); 992 iterator 993 _M_insert_equal_(const_iterator __pos, const value_type& __x) 994 { 995 _Alloc_node __an(*this); 996 return _M_insert_equal_(__pos, __x, __an); 997 } 998 #endif 999 1000 template<typename _InputIterator> 1001 void 1002 _M_insert_unique(_InputIterator __first, _InputIterator __last); 1003 1004 template<typename _InputIterator> 1005 void 1006 _M_insert_equal(_InputIterator __first, _InputIterator __last); 1007 1008 private: 1009 void 1010 _M_erase_aux(const_iterator __position); 1011 1012 void 1013 _M_erase_aux(const_iterator __first, const_iterator __last); 1014 1015 public: 1016 #if __cplusplus >= 201103L 1017 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1018 // DR 130. Associative erase should return an iterator. 1019 _GLIBCXX_ABI_TAG_CXX11 1020 iterator 1021 erase(const_iterator __position) 1022 { 1023 const_iterator __result = __position; 1024 ++__result; 1025 _M_erase_aux(__position); 1026 return __result._M_const_cast(); 1027 } 1028 1029 // LWG 2059. 1030 _GLIBCXX_ABI_TAG_CXX11 1031 iterator 1032 erase(iterator __position) 1033 { 1034 iterator __result = __position; 1035 ++__result; 1036 _M_erase_aux(__position); 1037 return __result; 1038 } 1039 #else 1040 void 1041 erase(iterator __position) 1042 { _M_erase_aux(__position); } 1043 1044 void 1045 erase(const_iterator __position) 1046 { _M_erase_aux(__position); } 1047 #endif 1048 size_type 1049 erase(const key_type& __x); 1050 1051 #if __cplusplus >= 201103L 1052 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1053 // DR 130. Associative erase should return an iterator. 1054 _GLIBCXX_ABI_TAG_CXX11 1055 iterator 1056 erase(const_iterator __first, const_iterator __last) 1057 { 1058 _M_erase_aux(__first, __last); 1059 return __last._M_const_cast(); 1060 } 1061 #else 1062 void 1063 erase(iterator __first, iterator __last) 1064 { _M_erase_aux(__first, __last); } 1065 1066 void 1067 erase(const_iterator __first, const_iterator __last) 1068 { _M_erase_aux(__first, __last); } 1069 #endif 1070 void 1071 erase(const key_type* __first, const key_type* __last); 1072 1073 void 1074 clear() _GLIBCXX_NOEXCEPT 1075 { 1076 _M_erase(_M_begin()); 1077 _M_impl._M_reset(); 1078 } 1079 1080 // Set operations. 1081 iterator 1082 find(const key_type& __k); 1083 1084 const_iterator 1085 find(const key_type& __k) const; 1086 1087 size_type 1088 count(const key_type& __k) const; 1089 1090 iterator 1091 lower_bound(const key_type& __k) 1092 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 1093 1094 const_iterator 1095 lower_bound(const key_type& __k) const 1096 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 1097 1098 iterator 1099 upper_bound(const key_type& __k) 1100 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 1101 1102 const_iterator 1103 upper_bound(const key_type& __k) const 1104 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 1105 1106 pair<iterator, iterator> 1107 equal_range(const key_type& __k); 1108 1109 pair<const_iterator, const_iterator> 1110 equal_range(const key_type& __k) const; 1111 1112 #if __cplusplus > 201103L 1113 template<typename _Cmp, typename _Kt, typename = __void_t<>> 1114 struct __is_transparent { }; 1115 1116 template<typename _Cmp, typename _Kt> 1117 struct 1118 __is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>> 1119 { typedef void type; }; 1120 1121 static auto _S_iter(_Link_type __x) { return iterator(__x); } 1122 1123 static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); } 1124 1125 template<typename _Cmp, typename _Link, typename _Kt> 1126 static auto 1127 _S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k) 1128 { 1129 while (__x != 0) 1130 if (!__cmp(_S_key(__x), __k)) 1131 __y = __x, __x = _S_left(__x); 1132 else 1133 __x = _S_right(__x); 1134 return _S_iter(__y); 1135 } 1136 1137 template<typename _Cmp, typename _Link, typename _Kt> 1138 static auto 1139 _S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k) 1140 { 1141 while (__x != 0) 1142 if (__cmp(__k, _S_key(__x))) 1143 __y = __x, __x = _S_left(__x); 1144 else 1145 __x = _S_right(__x); 1146 return _S_iter(__y); 1147 } 1148 1149 template<typename _Kt, 1150 typename _Req = typename __is_transparent<_Compare, _Kt>::type> 1151 iterator 1152 _M_find_tr(const _Kt& __k) 1153 { 1154 auto& __cmp = _M_impl._M_key_compare; 1155 auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); 1156 return (__j == end() || __cmp(__k, _S_key(__j._M_node))) 1157 ? end() : __j; 1158 } 1159 1160 template<typename _Kt, 1161 typename _Req = typename __is_transparent<_Compare, _Kt>::type> 1162 const_iterator 1163 _M_find_tr(const _Kt& __k) const 1164 { 1165 auto& __cmp = _M_impl._M_key_compare; 1166 auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); 1167 return (__j == end() || __cmp(__k, _S_key(__j._M_node))) 1168 ? end() : __j; 1169 } 1170 1171 template<typename _Kt, 1172 typename _Req = typename __is_transparent<_Compare, _Kt>::type> 1173 size_type 1174 _M_count_tr(const _Kt& __k) const 1175 { 1176 auto __p = _M_equal_range_tr(__k); 1177 return std::distance(__p.first, __p.second); 1178 } 1179 1180 template<typename _Kt, 1181 typename _Req = typename __is_transparent<_Compare, _Kt>::type> 1182 iterator 1183 _M_lower_bound_tr(const _Kt& __k) 1184 { 1185 auto& __cmp = _M_impl._M_key_compare; 1186 return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); 1187 } 1188 1189 template<typename _Kt, 1190 typename _Req = typename __is_transparent<_Compare, _Kt>::type> 1191 const_iterator 1192 _M_lower_bound_tr(const _Kt& __k) const 1193 { 1194 auto& __cmp = _M_impl._M_key_compare; 1195 return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); 1196 } 1197 1198 template<typename _Kt, 1199 typename _Req = typename __is_transparent<_Compare, _Kt>::type> 1200 iterator 1201 _M_upper_bound_tr(const _Kt& __k) 1202 { 1203 auto& __cmp = _M_impl._M_key_compare; 1204 return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k); 1205 } 1206 1207 template<typename _Kt, 1208 typename _Req = typename __is_transparent<_Compare, _Kt>::type> 1209 const_iterator 1210 _M_upper_bound_tr(const _Kt& __k) const 1211 { 1212 auto& __cmp = _M_impl._M_key_compare; 1213 return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k); 1214 } 1215 1216 template<typename _Kt, 1217 typename _Req = typename __is_transparent<_Compare, _Kt>::type> 1218 pair<iterator, iterator> 1219 _M_equal_range_tr(const _Kt& __k) 1220 { 1221 auto __low = _M_lower_bound_tr(__k); 1222 auto __high = __low; 1223 auto& __cmp = _M_impl._M_key_compare; 1224 while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) 1225 ++__high; 1226 return { __low, __high }; 1227 } 1228 1229 template<typename _Kt, 1230 typename _Req = typename __is_transparent<_Compare, _Kt>::type> 1231 pair<const_iterator, const_iterator> 1232 _M_equal_range_tr(const _Kt& __k) const 1233 { 1234 auto __low = _M_lower_bound_tr(__k); 1235 auto __high = __low; 1236 auto& __cmp = _M_impl._M_key_compare; 1237 while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) 1238 ++__high; 1239 return { __low, __high }; 1240 } 1241 #endif 1242 1243 // Debugging. 1244 bool 1245 __rb_verify() const; 1246 1247 #if __cplusplus >= 201103L 1248 _Rb_tree& 1249 operator=(_Rb_tree&&) 1250 noexcept(_Alloc_traits::_S_nothrow_move() 1251 && is_nothrow_move_assignable<_Compare>::value); 1252 1253 template<typename _Iterator> 1254 void 1255 _M_assign_unique(_Iterator, _Iterator); 1256 1257 template<typename _Iterator> 1258 void 1259 _M_assign_equal(_Iterator, _Iterator); 1260 1261 private: 1262 // Move elements from container with equal allocator. 1263 void 1264 _M_move_data(_Rb_tree&, std::true_type); 1265 1266 // Move elements from container with possibly non-equal allocator, 1267 // which might result in a copy not a move. 1268 void 1269 _M_move_data(_Rb_tree&, std::false_type); 1270 1271 // Move assignment from container with equal allocator. 1272 void 1273 _M_move_assign(_Rb_tree&, std::true_type); 1274 1275 // Move assignment from container with possibly non-equal allocator, 1276 // which might result in a copy not a move. 1277 void 1278 _M_move_assign(_Rb_tree&, std::false_type); 1279 #endif 1280 }; 1281 1282 template<typename _Key, typename _Val, typename _KeyOfValue, 1283 typename _Compare, typename _Alloc> 1284 inline bool 1285 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1286 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1287 { 1288 return __x.size() == __y.size() 1289 && std::equal(__x.begin(), __x.end(), __y.begin()); 1290 } 1291 1292 template<typename _Key, typename _Val, typename _KeyOfValue, 1293 typename _Compare, typename _Alloc> 1294 inline bool 1295 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1296 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1297 { 1298 return std::lexicographical_compare(__x.begin(), __x.end(), 1299 __y.begin(), __y.end()); 1300 } 1301 1302 template<typename _Key, typename _Val, typename _KeyOfValue, 1303 typename _Compare, typename _Alloc> 1304 inline bool 1305 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1306 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1307 { return !(__x == __y); } 1308 1309 template<typename _Key, typename _Val, typename _KeyOfValue, 1310 typename _Compare, typename _Alloc> 1311 inline bool 1312 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1313 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1314 { return __y < __x; } 1315 1316 template<typename _Key, typename _Val, typename _KeyOfValue, 1317 typename _Compare, typename _Alloc> 1318 inline bool 1319 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1320 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1321 { return !(__y < __x); } 1322 1323 template<typename _Key, typename _Val, typename _KeyOfValue, 1324 typename _Compare, typename _Alloc> 1325 inline bool 1326 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1327 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1328 { return !(__x < __y); } 1329 1330 template<typename _Key, typename _Val, typename _KeyOfValue, 1331 typename _Compare, typename _Alloc> 1332 inline void 1333 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1334 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1335 { __x.swap(__y); } 1336 1337 #if __cplusplus >= 201103L 1338 template<typename _Key, typename _Val, typename _KeyOfValue, 1339 typename _Compare, typename _Alloc> 1340 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1341 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) 1342 : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) 1343 { 1344 using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>; 1345 if (__x._M_root() != nullptr) 1346 _M_move_data(__x, __eq()); 1347 } 1348 1349 template<typename _Key, typename _Val, typename _KeyOfValue, 1350 typename _Compare, typename _Alloc> 1351 void 1352 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1353 _M_move_data(_Rb_tree& __x, std::true_type) 1354 { 1355 _M_root() = __x._M_root(); 1356 _M_leftmost() = __x._M_leftmost(); 1357 _M_rightmost() = __x._M_rightmost(); 1358 _M_root()->_M_parent = _M_end(); 1359 1360 __x._M_root() = 0; 1361 __x._M_leftmost() = __x._M_end(); 1362 __x._M_rightmost() = __x._M_end(); 1363 1364 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 1365 __x._M_impl._M_node_count = 0; 1366 } 1367 1368 template<typename _Key, typename _Val, typename _KeyOfValue, 1369 typename _Compare, typename _Alloc> 1370 void 1371 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1372 _M_move_data(_Rb_tree& __x, std::false_type) 1373 { 1374 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 1375 _M_move_data(__x, std::true_type()); 1376 else 1377 { 1378 _Alloc_node __an(*this); 1379 auto __lbd = 1380 [&__an](const value_type& __cval) 1381 { 1382 auto& __val = const_cast<value_type&>(__cval); 1383 return __an(std::move_if_noexcept(__val)); 1384 }; 1385 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); 1386 _M_leftmost() = _S_minimum(_M_root()); 1387 _M_rightmost() = _S_maximum(_M_root()); 1388 _M_impl._M_node_count = __x._M_impl._M_node_count; 1389 } 1390 } 1391 1392 template<typename _Key, typename _Val, typename _KeyOfValue, 1393 typename _Compare, typename _Alloc> 1394 inline void 1395 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1396 _M_move_assign(_Rb_tree& __x, true_type) 1397 { 1398 clear(); 1399 if (__x._M_root() != nullptr) 1400 _M_move_data(__x, std::true_type()); 1401 std::__alloc_on_move(_M_get_Node_allocator(), 1402 __x._M_get_Node_allocator()); 1403 } 1404 1405 template<typename _Key, typename _Val, typename _KeyOfValue, 1406 typename _Compare, typename _Alloc> 1407 void 1408 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1409 _M_move_assign(_Rb_tree& __x, false_type) 1410 { 1411 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 1412 return _M_move_assign(__x, true_type{}); 1413 1414 // Try to move each node reusing existing nodes and copying __x nodes 1415 // structure. 1416 _Reuse_or_alloc_node __roan(*this); 1417 _M_impl._M_reset(); 1418 if (__x._M_root() != nullptr) 1419 { 1420 auto __lbd = 1421 [&__roan](const value_type& __cval) 1422 { 1423 auto& __val = const_cast<value_type&>(__cval); 1424 return __roan(std::move_if_noexcept(__val)); 1425 }; 1426 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); 1427 _M_leftmost() = _S_minimum(_M_root()); 1428 _M_rightmost() = _S_maximum(_M_root()); 1429 _M_impl._M_node_count = __x._M_impl._M_node_count; 1430 __x.clear(); 1431 } 1432 } 1433 1434 template<typename _Key, typename _Val, typename _KeyOfValue, 1435 typename _Compare, typename _Alloc> 1436 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 1437 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1438 operator=(_Rb_tree&& __x) 1439 noexcept(_Alloc_traits::_S_nothrow_move() 1440 && is_nothrow_move_assignable<_Compare>::value) 1441 { 1442 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 1443 constexpr bool __move_storage = 1444 _Alloc_traits::_S_propagate_on_move_assign() 1445 || _Alloc_traits::_S_always_equal(); 1446 _M_move_assign(__x, __bool_constant<__move_storage>()); 1447 return *this; 1448 } 1449 1450 template<typename _Key, typename _Val, typename _KeyOfValue, 1451 typename _Compare, typename _Alloc> 1452 template<typename _Iterator> 1453 void 1454 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1455 _M_assign_unique(_Iterator __first, _Iterator __last) 1456 { 1457 _Reuse_or_alloc_node __roan(*this); 1458 _M_impl._M_reset(); 1459 for (; __first != __last; ++__first) 1460 _M_insert_unique_(end(), *__first, __roan); 1461 } 1462 1463 template<typename _Key, typename _Val, typename _KeyOfValue, 1464 typename _Compare, typename _Alloc> 1465 template<typename _Iterator> 1466 void 1467 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1468 _M_assign_equal(_Iterator __first, _Iterator __last) 1469 { 1470 _Reuse_or_alloc_node __roan(*this); 1471 _M_impl._M_reset(); 1472 for (; __first != __last; ++__first) 1473 _M_insert_equal_(end(), *__first, __roan); 1474 } 1475 #endif 1476 1477 template<typename _Key, typename _Val, typename _KeyOfValue, 1478 typename _Compare, typename _Alloc> 1479 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 1480 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1481 operator=(const _Rb_tree& __x) 1482 { 1483 if (this != &__x) 1484 { 1485 // Note that _Key may be a constant type. 1486 #if __cplusplus >= 201103L 1487 if (_Alloc_traits::_S_propagate_on_copy_assign()) 1488 { 1489 auto& __this_alloc = this->_M_get_Node_allocator(); 1490 auto& __that_alloc = __x._M_get_Node_allocator(); 1491 if (!_Alloc_traits::_S_always_equal() 1492 && __this_alloc != __that_alloc) 1493 { 1494 // Replacement allocator cannot free existing storage, we need 1495 // to erase nodes first. 1496 clear(); 1497 std::__alloc_on_copy(__this_alloc, __that_alloc); 1498 } 1499 } 1500 #endif 1501 1502 _Reuse_or_alloc_node __roan(*this); 1503 _M_impl._M_reset(); 1504 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 1505 if (__x._M_root() != 0) 1506 { 1507 _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan); 1508 _M_leftmost() = _S_minimum(_M_root()); 1509 _M_rightmost() = _S_maximum(_M_root()); 1510 _M_impl._M_node_count = __x._M_impl._M_node_count; 1511 } 1512 } 1513 1514 return *this; 1515 } 1516 1517 template<typename _Key, typename _Val, typename _KeyOfValue, 1518 typename _Compare, typename _Alloc> 1519 #if __cplusplus >= 201103L 1520 template<typename _Arg, typename _NodeGen> 1521 #else 1522 template<typename _NodeGen> 1523 #endif 1524 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1525 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1526 _M_insert_(_Base_ptr __x, _Base_ptr __p, 1527 #if __cplusplus >= 201103L 1528 _Arg&& __v, 1529 #else 1530 const _Val& __v, 1531 #endif 1532 _NodeGen& __node_gen) 1533 { 1534 bool __insert_left = (__x != 0 || __p == _M_end() 1535 || _M_impl._M_key_compare(_KeyOfValue()(__v), 1536 _S_key(__p))); 1537 1538 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); 1539 1540 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1541 this->_M_impl._M_header); 1542 ++_M_impl._M_node_count; 1543 return iterator(__z); 1544 } 1545 1546 template<typename _Key, typename _Val, typename _KeyOfValue, 1547 typename _Compare, typename _Alloc> 1548 #if __cplusplus >= 201103L 1549 template<typename _Arg> 1550 #endif 1551 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1552 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1553 #if __cplusplus >= 201103L 1554 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 1555 #else 1556 _M_insert_lower(_Base_ptr __p, const _Val& __v) 1557 #endif 1558 { 1559 bool __insert_left = (__p == _M_end() 1560 || !_M_impl._M_key_compare(_S_key(__p), 1561 _KeyOfValue()(__v))); 1562 1563 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 1564 1565 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1566 this->_M_impl._M_header); 1567 ++_M_impl._M_node_count; 1568 return iterator(__z); 1569 } 1570 1571 template<typename _Key, typename _Val, typename _KeyOfValue, 1572 typename _Compare, typename _Alloc> 1573 #if __cplusplus >= 201103L 1574 template<typename _Arg> 1575 #endif 1576 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1577 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1578 #if __cplusplus >= 201103L 1579 _M_insert_equal_lower(_Arg&& __v) 1580 #else 1581 _M_insert_equal_lower(const _Val& __v) 1582 #endif 1583 { 1584 _Link_type __x = _M_begin(); 1585 _Link_type __y = _M_end(); 1586 while (__x != 0) 1587 { 1588 __y = __x; 1589 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 1590 _S_left(__x) : _S_right(__x); 1591 } 1592 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 1593 } 1594 1595 template<typename _Key, typename _Val, typename _KoV, 1596 typename _Compare, typename _Alloc> 1597 template<typename _NodeGen> 1598 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 1599 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 1600 _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen& __node_gen) 1601 { 1602 // Structural copy. __x and __p must be non-null. 1603 _Link_type __top = _M_clone_node(__x, __node_gen); 1604 __top->_M_parent = __p; 1605 1606 __try 1607 { 1608 if (__x->_M_right) 1609 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen); 1610 __p = __top; 1611 __x = _S_left(__x); 1612 1613 while (__x != 0) 1614 { 1615 _Link_type __y = _M_clone_node(__x, __node_gen); 1616 __p->_M_left = __y; 1617 __y->_M_parent = __p; 1618 if (__x->_M_right) 1619 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen); 1620 __p = __y; 1621 __x = _S_left(__x); 1622 } 1623 } 1624 __catch(...) 1625 { 1626 _M_erase(__top); 1627 __throw_exception_again; 1628 } 1629 return __top; 1630 } 1631 1632 template<typename _Key, typename _Val, typename _KeyOfValue, 1633 typename _Compare, typename _Alloc> 1634 void 1635 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1636 _M_erase(_Link_type __x) 1637 { 1638 // Erase without rebalancing. 1639 while (__x != 0) 1640 { 1641 _M_erase(_S_right(__x)); 1642 _Link_type __y = _S_left(__x); 1643 _M_drop_node(__x); 1644 __x = __y; 1645 } 1646 } 1647 1648 template<typename _Key, typename _Val, typename _KeyOfValue, 1649 typename _Compare, typename _Alloc> 1650 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1651 _Compare, _Alloc>::iterator 1652 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1653 _M_lower_bound(_Link_type __x, _Link_type __y, 1654 const _Key& __k) 1655 { 1656 while (__x != 0) 1657 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1658 __y = __x, __x = _S_left(__x); 1659 else 1660 __x = _S_right(__x); 1661 return iterator(__y); 1662 } 1663 1664 template<typename _Key, typename _Val, typename _KeyOfValue, 1665 typename _Compare, typename _Alloc> 1666 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1667 _Compare, _Alloc>::const_iterator 1668 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1669 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 1670 const _Key& __k) const 1671 { 1672 while (__x != 0) 1673 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1674 __y = __x, __x = _S_left(__x); 1675 else 1676 __x = _S_right(__x); 1677 return const_iterator(__y); 1678 } 1679 1680 template<typename _Key, typename _Val, typename _KeyOfValue, 1681 typename _Compare, typename _Alloc> 1682 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1683 _Compare, _Alloc>::iterator 1684 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1685 _M_upper_bound(_Link_type __x, _Link_type __y, 1686 const _Key& __k) 1687 { 1688 while (__x != 0) 1689 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1690 __y = __x, __x = _S_left(__x); 1691 else 1692 __x = _S_right(__x); 1693 return iterator(__y); 1694 } 1695 1696 template<typename _Key, typename _Val, typename _KeyOfValue, 1697 typename _Compare, typename _Alloc> 1698 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1699 _Compare, _Alloc>::const_iterator 1700 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1701 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 1702 const _Key& __k) const 1703 { 1704 while (__x != 0) 1705 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1706 __y = __x, __x = _S_left(__x); 1707 else 1708 __x = _S_right(__x); 1709 return const_iterator(__y); 1710 } 1711 1712 template<typename _Key, typename _Val, typename _KeyOfValue, 1713 typename _Compare, typename _Alloc> 1714 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1715 _Compare, _Alloc>::iterator, 1716 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1717 _Compare, _Alloc>::iterator> 1718 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1719 equal_range(const _Key& __k) 1720 { 1721 _Link_type __x = _M_begin(); 1722 _Link_type __y = _M_end(); 1723 while (__x != 0) 1724 { 1725 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1726 __x = _S_right(__x); 1727 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1728 __y = __x, __x = _S_left(__x); 1729 else 1730 { 1731 _Link_type __xu(__x), __yu(__y); 1732 __y = __x, __x = _S_left(__x); 1733 __xu = _S_right(__xu); 1734 return pair<iterator, 1735 iterator>(_M_lower_bound(__x, __y, __k), 1736 _M_upper_bound(__xu, __yu, __k)); 1737 } 1738 } 1739 return pair<iterator, iterator>(iterator(__y), 1740 iterator(__y)); 1741 } 1742 1743 template<typename _Key, typename _Val, typename _KeyOfValue, 1744 typename _Compare, typename _Alloc> 1745 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1746 _Compare, _Alloc>::const_iterator, 1747 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1748 _Compare, _Alloc>::const_iterator> 1749 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1750 equal_range(const _Key& __k) const 1751 { 1752 _Const_Link_type __x = _M_begin(); 1753 _Const_Link_type __y = _M_end(); 1754 while (__x != 0) 1755 { 1756 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1757 __x = _S_right(__x); 1758 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1759 __y = __x, __x = _S_left(__x); 1760 else 1761 { 1762 _Const_Link_type __xu(__x), __yu(__y); 1763 __y = __x, __x = _S_left(__x); 1764 __xu = _S_right(__xu); 1765 return pair<const_iterator, 1766 const_iterator>(_M_lower_bound(__x, __y, __k), 1767 _M_upper_bound(__xu, __yu, __k)); 1768 } 1769 } 1770 return pair<const_iterator, const_iterator>(const_iterator(__y), 1771 const_iterator(__y)); 1772 } 1773 1774 template<typename _Key, typename _Val, typename _KeyOfValue, 1775 typename _Compare, typename _Alloc> 1776 void 1777 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1778 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 1779 #if __cplusplus >= 201103L 1780 noexcept(_Alloc_traits::_S_nothrow_swap()) 1781 #endif 1782 { 1783 if (_M_root() == 0) 1784 { 1785 if (__t._M_root() != 0) 1786 { 1787 _M_root() = __t._M_root(); 1788 _M_leftmost() = __t._M_leftmost(); 1789 _M_rightmost() = __t._M_rightmost(); 1790 _M_root()->_M_parent = _M_end(); 1791 _M_impl._M_node_count = __t._M_impl._M_node_count; 1792 1793 __t._M_impl._M_reset(); 1794 } 1795 } 1796 else if (__t._M_root() == 0) 1797 { 1798 __t._M_root() = _M_root(); 1799 __t._M_leftmost() = _M_leftmost(); 1800 __t._M_rightmost() = _M_rightmost(); 1801 __t._M_root()->_M_parent = __t._M_end(); 1802 __t._M_impl._M_node_count = _M_impl._M_node_count; 1803 1804 _M_impl._M_reset(); 1805 } 1806 else 1807 { 1808 std::swap(_M_root(),__t._M_root()); 1809 std::swap(_M_leftmost(),__t._M_leftmost()); 1810 std::swap(_M_rightmost(),__t._M_rightmost()); 1811 1812 _M_root()->_M_parent = _M_end(); 1813 __t._M_root()->_M_parent = __t._M_end(); 1814 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 1815 } 1816 // No need to swap header's color as it does not change. 1817 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 1818 1819 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), 1820 __t._M_get_Node_allocator()); 1821 } 1822 1823 template<typename _Key, typename _Val, typename _KeyOfValue, 1824 typename _Compare, typename _Alloc> 1825 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1826 _Compare, _Alloc>::_Base_ptr, 1827 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1828 _Compare, _Alloc>::_Base_ptr> 1829 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1830 _M_get_insert_unique_pos(const key_type& __k) 1831 { 1832 typedef pair<_Base_ptr, _Base_ptr> _Res; 1833 _Link_type __x = _M_begin(); 1834 _Link_type __y = _M_end(); 1835 bool __comp = true; 1836 while (__x != 0) 1837 { 1838 __y = __x; 1839 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 1840 __x = __comp ? _S_left(__x) : _S_right(__x); 1841 } 1842 iterator __j = iterator(__y); 1843 if (__comp) 1844 { 1845 if (__j == begin()) 1846 return _Res(__x, __y); 1847 else 1848 --__j; 1849 } 1850 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 1851 return _Res(__x, __y); 1852 return _Res(__j._M_node, 0); 1853 } 1854 1855 template<typename _Key, typename _Val, typename _KeyOfValue, 1856 typename _Compare, typename _Alloc> 1857 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1858 _Compare, _Alloc>::_Base_ptr, 1859 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1860 _Compare, _Alloc>::_Base_ptr> 1861 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1862 _M_get_insert_equal_pos(const key_type& __k) 1863 { 1864 typedef pair<_Base_ptr, _Base_ptr> _Res; 1865 _Link_type __x = _M_begin(); 1866 _Link_type __y = _M_end(); 1867 while (__x != 0) 1868 { 1869 __y = __x; 1870 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 1871 _S_left(__x) : _S_right(__x); 1872 } 1873 return _Res(__x, __y); 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 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1882 _Compare, _Alloc>::iterator, bool> 1883 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1884 #if __cplusplus >= 201103L 1885 _M_insert_unique(_Arg&& __v) 1886 #else 1887 _M_insert_unique(const _Val& __v) 1888 #endif 1889 { 1890 typedef pair<iterator, bool> _Res; 1891 pair<_Base_ptr, _Base_ptr> __res 1892 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 1893 1894 if (__res.second) 1895 { 1896 _Alloc_node __an(*this); 1897 return _Res(_M_insert_(__res.first, __res.second, 1898 _GLIBCXX_FORWARD(_Arg, __v), __an), 1899 true); 1900 } 1901 1902 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 1903 } 1904 1905 template<typename _Key, typename _Val, typename _KeyOfValue, 1906 typename _Compare, typename _Alloc> 1907 #if __cplusplus >= 201103L 1908 template<typename _Arg> 1909 #endif 1910 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1911 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1912 #if __cplusplus >= 201103L 1913 _M_insert_equal(_Arg&& __v) 1914 #else 1915 _M_insert_equal(const _Val& __v) 1916 #endif 1917 { 1918 pair<_Base_ptr, _Base_ptr> __res 1919 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 1920 _Alloc_node __an(*this); 1921 return _M_insert_(__res.first, __res.second, 1922 _GLIBCXX_FORWARD(_Arg, __v), __an); 1923 } 1924 1925 template<typename _Key, typename _Val, typename _KeyOfValue, 1926 typename _Compare, typename _Alloc> 1927 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1928 _Compare, _Alloc>::_Base_ptr, 1929 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1930 _Compare, _Alloc>::_Base_ptr> 1931 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1932 _M_get_insert_hint_unique_pos(const_iterator __position, 1933 const key_type& __k) 1934 { 1935 iterator __pos = __position._M_const_cast(); 1936 typedef pair<_Base_ptr, _Base_ptr> _Res; 1937 1938 // end() 1939 if (__pos._M_node == _M_end()) 1940 { 1941 if (size() > 0 1942 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 1943 return _Res(0, _M_rightmost()); 1944 else 1945 return _M_get_insert_unique_pos(__k); 1946 } 1947 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 1948 { 1949 // First, try before... 1950 iterator __before = __pos; 1951 if (__pos._M_node == _M_leftmost()) // begin() 1952 return _Res(_M_leftmost(), _M_leftmost()); 1953 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 1954 { 1955 if (_S_right(__before._M_node) == 0) 1956 return _Res(0, __before._M_node); 1957 else 1958 return _Res(__pos._M_node, __pos._M_node); 1959 } 1960 else 1961 return _M_get_insert_unique_pos(__k); 1962 } 1963 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 1964 { 1965 // ... then try after. 1966 iterator __after = __pos; 1967 if (__pos._M_node == _M_rightmost()) 1968 return _Res(0, _M_rightmost()); 1969 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 1970 { 1971 if (_S_right(__pos._M_node) == 0) 1972 return _Res(0, __pos._M_node); 1973 else 1974 return _Res(__after._M_node, __after._M_node); 1975 } 1976 else 1977 return _M_get_insert_unique_pos(__k); 1978 } 1979 else 1980 // Equivalent keys. 1981 return _Res(__pos._M_node, 0); 1982 } 1983 1984 template<typename _Key, typename _Val, typename _KeyOfValue, 1985 typename _Compare, typename _Alloc> 1986 #if __cplusplus >= 201103L 1987 template<typename _Arg, typename _NodeGen> 1988 #else 1989 template<typename _NodeGen> 1990 #endif 1991 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1992 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1993 _M_insert_unique_(const_iterator __position, 1994 #if __cplusplus >= 201103L 1995 _Arg&& __v, 1996 #else 1997 const _Val& __v, 1998 #endif 1999 _NodeGen& __node_gen) 2000 { 2001 pair<_Base_ptr, _Base_ptr> __res 2002 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 2003 2004 if (__res.second) 2005 return _M_insert_(__res.first, __res.second, 2006 _GLIBCXX_FORWARD(_Arg, __v), 2007 __node_gen); 2008 return iterator(static_cast<_Link_type>(__res.first)); 2009 } 2010 2011 template<typename _Key, typename _Val, typename _KeyOfValue, 2012 typename _Compare, typename _Alloc> 2013 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2014 _Compare, _Alloc>::_Base_ptr, 2015 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2016 _Compare, _Alloc>::_Base_ptr> 2017 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2018 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 2019 { 2020 iterator __pos = __position._M_const_cast(); 2021 typedef pair<_Base_ptr, _Base_ptr> _Res; 2022 2023 // end() 2024 if (__pos._M_node == _M_end()) 2025 { 2026 if (size() > 0 2027 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 2028 return _Res(0, _M_rightmost()); 2029 else 2030 return _M_get_insert_equal_pos(__k); 2031 } 2032 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 2033 { 2034 // First, try before... 2035 iterator __before = __pos; 2036 if (__pos._M_node == _M_leftmost()) // begin() 2037 return _Res(_M_leftmost(), _M_leftmost()); 2038 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 2039 { 2040 if (_S_right(__before._M_node) == 0) 2041 return _Res(0, __before._M_node); 2042 else 2043 return _Res(__pos._M_node, __pos._M_node); 2044 } 2045 else 2046 return _M_get_insert_equal_pos(__k); 2047 } 2048 else 2049 { 2050 // ... then try after. 2051 iterator __after = __pos; 2052 if (__pos._M_node == _M_rightmost()) 2053 return _Res(0, _M_rightmost()); 2054 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 2055 { 2056 if (_S_right(__pos._M_node) == 0) 2057 return _Res(0, __pos._M_node); 2058 else 2059 return _Res(__after._M_node, __after._M_node); 2060 } 2061 else 2062 return _Res(0, 0); 2063 } 2064 } 2065 2066 template<typename _Key, typename _Val, typename _KeyOfValue, 2067 typename _Compare, typename _Alloc> 2068 #if __cplusplus >= 201103L 2069 template<typename _Arg, typename _NodeGen> 2070 #else 2071 template<typename _NodeGen> 2072 #endif 2073 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2074 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2075 _M_insert_equal_(const_iterator __position, 2076 #if __cplusplus >= 201103L 2077 _Arg&& __v, 2078 #else 2079 const _Val& __v, 2080 #endif 2081 _NodeGen& __node_gen) 2082 { 2083 pair<_Base_ptr, _Base_ptr> __res 2084 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 2085 2086 if (__res.second) 2087 return _M_insert_(__res.first, __res.second, 2088 _GLIBCXX_FORWARD(_Arg, __v), 2089 __node_gen); 2090 2091 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 2092 } 2093 2094 #if __cplusplus >= 201103L 2095 template<typename _Key, typename _Val, typename _KeyOfValue, 2096 typename _Compare, typename _Alloc> 2097 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2098 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2099 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 2100 { 2101 bool __insert_left = (__x != 0 || __p == _M_end() 2102 || _M_impl._M_key_compare(_S_key(__z), 2103 _S_key(__p))); 2104 2105 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 2106 this->_M_impl._M_header); 2107 ++_M_impl._M_node_count; 2108 return iterator(__z); 2109 } 2110 2111 template<typename _Key, typename _Val, typename _KeyOfValue, 2112 typename _Compare, typename _Alloc> 2113 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2114 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2115 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 2116 { 2117 bool __insert_left = (__p == _M_end() 2118 || !_M_impl._M_key_compare(_S_key(__p), 2119 _S_key(__z))); 2120 2121 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 2122 this->_M_impl._M_header); 2123 ++_M_impl._M_node_count; 2124 return iterator(__z); 2125 } 2126 2127 template<typename _Key, typename _Val, typename _KeyOfValue, 2128 typename _Compare, typename _Alloc> 2129 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2130 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2131 _M_insert_equal_lower_node(_Link_type __z) 2132 { 2133 _Link_type __x = _M_begin(); 2134 _Link_type __y = _M_end(); 2135 while (__x != 0) 2136 { 2137 __y = __x; 2138 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 2139 _S_left(__x) : _S_right(__x); 2140 } 2141 return _M_insert_lower_node(__y, __z); 2142 } 2143 2144 template<typename _Key, typename _Val, typename _KeyOfValue, 2145 typename _Compare, typename _Alloc> 2146 template<typename... _Args> 2147 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2148 _Compare, _Alloc>::iterator, bool> 2149 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2150 _M_emplace_unique(_Args&&... __args) 2151 { 2152 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2153 2154 __try 2155 { 2156 typedef pair<iterator, bool> _Res; 2157 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 2158 if (__res.second) 2159 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 2160 2161 _M_drop_node(__z); 2162 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 2163 } 2164 __catch(...) 2165 { 2166 _M_drop_node(__z); 2167 __throw_exception_again; 2168 } 2169 } 2170 2171 template<typename _Key, typename _Val, typename _KeyOfValue, 2172 typename _Compare, typename _Alloc> 2173 template<typename... _Args> 2174 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2175 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2176 _M_emplace_equal(_Args&&... __args) 2177 { 2178 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2179 2180 __try 2181 { 2182 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 2183 return _M_insert_node(__res.first, __res.second, __z); 2184 } 2185 __catch(...) 2186 { 2187 _M_drop_node(__z); 2188 __throw_exception_again; 2189 } 2190 } 2191 2192 template<typename _Key, typename _Val, typename _KeyOfValue, 2193 typename _Compare, typename _Alloc> 2194 template<typename... _Args> 2195 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2196 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2197 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 2198 { 2199 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2200 2201 __try 2202 { 2203 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 2204 2205 if (__res.second) 2206 return _M_insert_node(__res.first, __res.second, __z); 2207 2208 _M_drop_node(__z); 2209 return iterator(static_cast<_Link_type>(__res.first)); 2210 } 2211 __catch(...) 2212 { 2213 _M_drop_node(__z); 2214 __throw_exception_again; 2215 } 2216 } 2217 2218 template<typename _Key, typename _Val, typename _KeyOfValue, 2219 typename _Compare, typename _Alloc> 2220 template<typename... _Args> 2221 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2222 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2223 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 2224 { 2225 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2226 2227 __try 2228 { 2229 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 2230 2231 if (__res.second) 2232 return _M_insert_node(__res.first, __res.second, __z); 2233 2234 return _M_insert_equal_lower_node(__z); 2235 } 2236 __catch(...) 2237 { 2238 _M_drop_node(__z); 2239 __throw_exception_again; 2240 } 2241 } 2242 #endif 2243 2244 template<typename _Key, typename _Val, typename _KoV, 2245 typename _Cmp, typename _Alloc> 2246 template<class _II> 2247 void 2248 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 2249 _M_insert_unique(_II __first, _II __last) 2250 { 2251 _Alloc_node __an(*this); 2252 for (; __first != __last; ++__first) 2253 _M_insert_unique_(end(), *__first, __an); 2254 } 2255 2256 template<typename _Key, typename _Val, typename _KoV, 2257 typename _Cmp, typename _Alloc> 2258 template<class _II> 2259 void 2260 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 2261 _M_insert_equal(_II __first, _II __last) 2262 { 2263 _Alloc_node __an(*this); 2264 for (; __first != __last; ++__first) 2265 _M_insert_equal_(end(), *__first, __an); 2266 } 2267 2268 template<typename _Key, typename _Val, typename _KeyOfValue, 2269 typename _Compare, typename _Alloc> 2270 void 2271 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2272 _M_erase_aux(const_iterator __position) 2273 { 2274 _Link_type __y = 2275 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 2276 (const_cast<_Base_ptr>(__position._M_node), 2277 this->_M_impl._M_header)); 2278 _M_drop_node(__y); 2279 --_M_impl._M_node_count; 2280 } 2281 2282 template<typename _Key, typename _Val, typename _KeyOfValue, 2283 typename _Compare, typename _Alloc> 2284 void 2285 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2286 _M_erase_aux(const_iterator __first, const_iterator __last) 2287 { 2288 if (__first == begin() && __last == end()) 2289 clear(); 2290 else 2291 while (__first != __last) 2292 erase(__first++); 2293 } 2294 2295 template<typename _Key, typename _Val, typename _KeyOfValue, 2296 typename _Compare, typename _Alloc> 2297 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 2298 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2299 erase(const _Key& __x) 2300 { 2301 pair<iterator, iterator> __p = equal_range(__x); 2302 const size_type __old_size = size(); 2303 erase(__p.first, __p.second); 2304 return __old_size - size(); 2305 } 2306 2307 template<typename _Key, typename _Val, typename _KeyOfValue, 2308 typename _Compare, typename _Alloc> 2309 void 2310 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2311 erase(const _Key* __first, const _Key* __last) 2312 { 2313 while (__first != __last) 2314 erase(*__first++); 2315 } 2316 2317 template<typename _Key, typename _Val, typename _KeyOfValue, 2318 typename _Compare, typename _Alloc> 2319 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2320 _Compare, _Alloc>::iterator 2321 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2322 find(const _Key& __k) 2323 { 2324 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 2325 return (__j == end() 2326 || _M_impl._M_key_compare(__k, 2327 _S_key(__j._M_node))) ? end() : __j; 2328 } 2329 2330 template<typename _Key, typename _Val, typename _KeyOfValue, 2331 typename _Compare, typename _Alloc> 2332 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2333 _Compare, _Alloc>::const_iterator 2334 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2335 find(const _Key& __k) const 2336 { 2337 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 2338 return (__j == end() 2339 || _M_impl._M_key_compare(__k, 2340 _S_key(__j._M_node))) ? end() : __j; 2341 } 2342 2343 template<typename _Key, typename _Val, typename _KeyOfValue, 2344 typename _Compare, typename _Alloc> 2345 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 2346 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2347 count(const _Key& __k) const 2348 { 2349 pair<const_iterator, const_iterator> __p = equal_range(__k); 2350 const size_type __n = std::distance(__p.first, __p.second); 2351 return __n; 2352 } 2353 2354 _GLIBCXX_PURE unsigned int 2355 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 2356 const _Rb_tree_node_base* __root) throw (); 2357 2358 template<typename _Key, typename _Val, typename _KeyOfValue, 2359 typename _Compare, typename _Alloc> 2360 bool 2361 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 2362 { 2363 if (_M_impl._M_node_count == 0 || begin() == end()) 2364 return _M_impl._M_node_count == 0 && begin() == end() 2365 && this->_M_impl._M_header._M_left == _M_end() 2366 && this->_M_impl._M_header._M_right == _M_end(); 2367 2368 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 2369 for (const_iterator __it = begin(); __it != end(); ++__it) 2370 { 2371 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 2372 _Const_Link_type __L = _S_left(__x); 2373 _Const_Link_type __R = _S_right(__x); 2374 2375 if (__x->_M_color == _S_red) 2376 if ((__L && __L->_M_color == _S_red) 2377 || (__R && __R->_M_color == _S_red)) 2378 return false; 2379 2380 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 2381 return false; 2382 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 2383 return false; 2384 2385 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 2386 return false; 2387 } 2388 2389 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 2390 return false; 2391 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 2392 return false; 2393 return true; 2394 } 2395 2396 _GLIBCXX_END_NAMESPACE_VERSION 2397 } // namespace 2398 2399 #endif 2400