libstdc++
|
00001 // RB tree implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2016 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * 00027 * Copyright (c) 1996,1997 00028 * Silicon Graphics Computer Systems, Inc. 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Silicon Graphics makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1994 00040 * Hewlett-Packard Company 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Hewlett-Packard Company makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 * 00050 * 00051 */ 00052 00053 /** @file bits/stl_tree.h 00054 * This is an internal header file, included by other library headers. 00055 * Do not attempt to use it directly. @headername{map,set} 00056 */ 00057 00058 #ifndef _STL_TREE_H 00059 #define _STL_TREE_H 1 00060 00061 #pragma GCC system_header 00062 00063 #include <bits/stl_algobase.h> 00064 #include <bits/allocator.h> 00065 #include <bits/stl_function.h> 00066 #include <bits/cpp_type_traits.h> 00067 #include <ext/alloc_traits.h> 00068 #if __cplusplus >= 201103L 00069 #include <ext/aligned_buffer.h> 00070 #endif 00071 00072 namespace std _GLIBCXX_VISIBILITY(default) 00073 { 00074 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00075 00076 #if __cplusplus > 201103L 00077 # define __cpp_lib_generic_associative_lookup 201304 00078 #endif 00079 00080 // Red-black tree class, designed for use in implementing STL 00081 // associative containers (set, multiset, map, and multimap). The 00082 // insertion and deletion algorithms are based on those in Cormen, 00083 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 00084 // 1990), except that 00085 // 00086 // (1) the header cell is maintained with links not only to the root 00087 // but also to the leftmost node of the tree, to enable constant 00088 // time begin(), and to the rightmost node of the tree, to enable 00089 // linear time performance when used with the generic set algorithms 00090 // (set_union, etc.) 00091 // 00092 // (2) when a node being deleted has two children its successor node 00093 // is relinked into its place, rather than copied, so that the only 00094 // iterators invalidated are those referring to the deleted node. 00095 00096 enum _Rb_tree_color { _S_red = false, _S_black = true }; 00097 00098 struct _Rb_tree_node_base 00099 { 00100 typedef _Rb_tree_node_base* _Base_ptr; 00101 typedef const _Rb_tree_node_base* _Const_Base_ptr; 00102 00103 _Rb_tree_color _M_color; 00104 _Base_ptr _M_parent; 00105 _Base_ptr _M_left; 00106 _Base_ptr _M_right; 00107 00108 static _Base_ptr 00109 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00110 { 00111 while (__x->_M_left != 0) __x = __x->_M_left; 00112 return __x; 00113 } 00114 00115 static _Const_Base_ptr 00116 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00117 { 00118 while (__x->_M_left != 0) __x = __x->_M_left; 00119 return __x; 00120 } 00121 00122 static _Base_ptr 00123 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00124 { 00125 while (__x->_M_right != 0) __x = __x->_M_right; 00126 return __x; 00127 } 00128 00129 static _Const_Base_ptr 00130 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00131 { 00132 while (__x->_M_right != 0) __x = __x->_M_right; 00133 return __x; 00134 } 00135 }; 00136 00137 template<typename _Val> 00138 struct _Rb_tree_node : public _Rb_tree_node_base 00139 { 00140 typedef _Rb_tree_node<_Val>* _Link_type; 00141 00142 #if __cplusplus < 201103L 00143 _Val _M_value_field; 00144 00145 _Val* 00146 _M_valptr() 00147 { return std::__addressof(_M_value_field); } 00148 00149 const _Val* 00150 _M_valptr() const 00151 { return std::__addressof(_M_value_field); } 00152 #else 00153 __gnu_cxx::__aligned_membuf<_Val> _M_storage; 00154 00155 _Val* 00156 _M_valptr() 00157 { return _M_storage._M_ptr(); } 00158 00159 const _Val* 00160 _M_valptr() const 00161 { return _M_storage._M_ptr(); } 00162 #endif 00163 }; 00164 00165 _GLIBCXX_PURE _Rb_tree_node_base* 00166 _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); 00167 00168 _GLIBCXX_PURE const _Rb_tree_node_base* 00169 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw (); 00170 00171 _GLIBCXX_PURE _Rb_tree_node_base* 00172 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw (); 00173 00174 _GLIBCXX_PURE const _Rb_tree_node_base* 00175 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw (); 00176 00177 template<typename _Tp> 00178 struct _Rb_tree_iterator 00179 { 00180 typedef _Tp value_type; 00181 typedef _Tp& reference; 00182 typedef _Tp* pointer; 00183 00184 typedef bidirectional_iterator_tag iterator_category; 00185 typedef ptrdiff_t difference_type; 00186 00187 typedef _Rb_tree_iterator<_Tp> _Self; 00188 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 00189 typedef _Rb_tree_node<_Tp>* _Link_type; 00190 00191 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT 00192 : _M_node() { } 00193 00194 explicit 00195 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00196 : _M_node(__x) { } 00197 00198 reference 00199 operator*() const _GLIBCXX_NOEXCEPT 00200 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 00201 00202 pointer 00203 operator->() const _GLIBCXX_NOEXCEPT 00204 { return static_cast<_Link_type> (_M_node)->_M_valptr(); } 00205 00206 _Self& 00207 operator++() _GLIBCXX_NOEXCEPT 00208 { 00209 _M_node = _Rb_tree_increment(_M_node); 00210 return *this; 00211 } 00212 00213 _Self 00214 operator++(int) _GLIBCXX_NOEXCEPT 00215 { 00216 _Self __tmp = *this; 00217 _M_node = _Rb_tree_increment(_M_node); 00218 return __tmp; 00219 } 00220 00221 _Self& 00222 operator--() _GLIBCXX_NOEXCEPT 00223 { 00224 _M_node = _Rb_tree_decrement(_M_node); 00225 return *this; 00226 } 00227 00228 _Self 00229 operator--(int) _GLIBCXX_NOEXCEPT 00230 { 00231 _Self __tmp = *this; 00232 _M_node = _Rb_tree_decrement(_M_node); 00233 return __tmp; 00234 } 00235 00236 bool 00237 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 00238 { return _M_node == __x._M_node; } 00239 00240 bool 00241 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 00242 { return _M_node != __x._M_node; } 00243 00244 _Base_ptr _M_node; 00245 }; 00246 00247 template<typename _Tp> 00248 struct _Rb_tree_const_iterator 00249 { 00250 typedef _Tp value_type; 00251 typedef const _Tp& reference; 00252 typedef const _Tp* pointer; 00253 00254 typedef _Rb_tree_iterator<_Tp> iterator; 00255 00256 typedef bidirectional_iterator_tag iterator_category; 00257 typedef ptrdiff_t difference_type; 00258 00259 typedef _Rb_tree_const_iterator<_Tp> _Self; 00260 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 00261 typedef const _Rb_tree_node<_Tp>* _Link_type; 00262 00263 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT 00264 : _M_node() { } 00265 00266 explicit 00267 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00268 : _M_node(__x) { } 00269 00270 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT 00271 : _M_node(__it._M_node) { } 00272 00273 iterator 00274 _M_const_cast() const _GLIBCXX_NOEXCEPT 00275 { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); } 00276 00277 reference 00278 operator*() const _GLIBCXX_NOEXCEPT 00279 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 00280 00281 pointer 00282 operator->() const _GLIBCXX_NOEXCEPT 00283 { return static_cast<_Link_type>(_M_node)->_M_valptr(); } 00284 00285 _Self& 00286 operator++() _GLIBCXX_NOEXCEPT 00287 { 00288 _M_node = _Rb_tree_increment(_M_node); 00289 return *this; 00290 } 00291 00292 _Self 00293 operator++(int) _GLIBCXX_NOEXCEPT 00294 { 00295 _Self __tmp = *this; 00296 _M_node = _Rb_tree_increment(_M_node); 00297 return __tmp; 00298 } 00299 00300 _Self& 00301 operator--() _GLIBCXX_NOEXCEPT 00302 { 00303 _M_node = _Rb_tree_decrement(_M_node); 00304 return *this; 00305 } 00306 00307 _Self 00308 operator--(int) _GLIBCXX_NOEXCEPT 00309 { 00310 _Self __tmp = *this; 00311 _M_node = _Rb_tree_decrement(_M_node); 00312 return __tmp; 00313 } 00314 00315 bool 00316 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 00317 { return _M_node == __x._M_node; } 00318 00319 bool 00320 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 00321 { return _M_node != __x._M_node; } 00322 00323 _Base_ptr _M_node; 00324 }; 00325 00326 template<typename _Val> 00327 inline bool 00328 operator==(const _Rb_tree_iterator<_Val>& __x, 00329 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 00330 { return __x._M_node == __y._M_node; } 00331 00332 template<typename _Val> 00333 inline bool 00334 operator!=(const _Rb_tree_iterator<_Val>& __x, 00335 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 00336 { return __x._M_node != __y._M_node; } 00337 00338 void 00339 _Rb_tree_insert_and_rebalance(const bool __insert_left, 00340 _Rb_tree_node_base* __x, 00341 _Rb_tree_node_base* __p, 00342 _Rb_tree_node_base& __header) throw (); 00343 00344 _Rb_tree_node_base* 00345 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 00346 _Rb_tree_node_base& __header) throw (); 00347 00348 #if __cplusplus > 201103L 00349 template<typename _Cmp, typename _SfinaeType, typename = __void_t<>> 00350 struct __has_is_transparent 00351 { }; 00352 00353 template<typename _Cmp, typename _SfinaeType> 00354 struct __has_is_transparent<_Cmp, _SfinaeType, 00355 __void_t<typename _Cmp::is_transparent>> 00356 { typedef void type; }; 00357 #endif 00358 00359 template<typename _Key, typename _Val, typename _KeyOfValue, 00360 typename _Compare, typename _Alloc = allocator<_Val> > 00361 class _Rb_tree 00362 { 00363 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 00364 rebind<_Rb_tree_node<_Val> >::other _Node_allocator; 00365 00366 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits; 00367 00368 protected: 00369 typedef _Rb_tree_node_base* _Base_ptr; 00370 typedef const _Rb_tree_node_base* _Const_Base_ptr; 00371 typedef _Rb_tree_node<_Val>* _Link_type; 00372 typedef const _Rb_tree_node<_Val>* _Const_Link_type; 00373 00374 private: 00375 // Functor recycling a pool of nodes and using allocation once the pool 00376 // is empty. 00377 struct _Reuse_or_alloc_node 00378 { 00379 _Reuse_or_alloc_node(_Rb_tree& __t) 00380 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t) 00381 { 00382 if (_M_root) 00383 { 00384 _M_root->_M_parent = 0; 00385 00386 if (_M_nodes->_M_left) 00387 _M_nodes = _M_nodes->_M_left; 00388 } 00389 else 00390 _M_nodes = 0; 00391 } 00392 00393 #if __cplusplus >= 201103L 00394 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete; 00395 #endif 00396 00397 ~_Reuse_or_alloc_node() 00398 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); } 00399 00400 template<typename _Arg> 00401 _Link_type 00402 #if __cplusplus < 201103L 00403 operator()(const _Arg& __arg) 00404 #else 00405 operator()(_Arg&& __arg) 00406 #endif 00407 { 00408 _Link_type __node = static_cast<_Link_type>(_M_extract()); 00409 if (__node) 00410 { 00411 _M_t._M_destroy_node(__node); 00412 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg)); 00413 return __node; 00414 } 00415 00416 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); 00417 } 00418 00419 private: 00420 _Base_ptr 00421 _M_extract() 00422 { 00423 if (!_M_nodes) 00424 return _M_nodes; 00425 00426 _Base_ptr __node = _M_nodes; 00427 _M_nodes = _M_nodes->_M_parent; 00428 if (_M_nodes) 00429 { 00430 if (_M_nodes->_M_right == __node) 00431 { 00432 _M_nodes->_M_right = 0; 00433 00434 if (_M_nodes->_M_left) 00435 { 00436 _M_nodes = _M_nodes->_M_left; 00437 00438 while (_M_nodes->_M_right) 00439 _M_nodes = _M_nodes->_M_right; 00440 00441 if (_M_nodes->_M_left) 00442 _M_nodes = _M_nodes->_M_left; 00443 } 00444 } 00445 else // __node is on the left. 00446 _M_nodes->_M_left = 0; 00447 } 00448 else 00449 _M_root = 0; 00450 00451 return __node; 00452 } 00453 00454 _Base_ptr _M_root; 00455 _Base_ptr _M_nodes; 00456 _Rb_tree& _M_t; 00457 }; 00458 00459 // Functor similar to the previous one but without any pool of nodes to 00460 // recycle. 00461 struct _Alloc_node 00462 { 00463 _Alloc_node(_Rb_tree& __t) 00464 : _M_t(__t) { } 00465 00466 template<typename _Arg> 00467 _Link_type 00468 #if __cplusplus < 201103L 00469 operator()(const _Arg& __arg) const 00470 #else 00471 operator()(_Arg&& __arg) const 00472 #endif 00473 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); } 00474 00475 private: 00476 _Rb_tree& _M_t; 00477 }; 00478 00479 public: 00480 typedef _Key key_type; 00481 typedef _Val value_type; 00482 typedef value_type* pointer; 00483 typedef const value_type* const_pointer; 00484 typedef value_type& reference; 00485 typedef const value_type& const_reference; 00486 typedef size_t size_type; 00487 typedef ptrdiff_t difference_type; 00488 typedef _Alloc allocator_type; 00489 00490 _Node_allocator& 00491 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT 00492 { return *static_cast<_Node_allocator*>(&this->_M_impl); } 00493 00494 const _Node_allocator& 00495 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT 00496 { return *static_cast<const _Node_allocator*>(&this->_M_impl); } 00497 00498 allocator_type 00499 get_allocator() const _GLIBCXX_NOEXCEPT 00500 { return allocator_type(_M_get_Node_allocator()); } 00501 00502 protected: 00503 _Link_type 00504 _M_get_node() 00505 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); } 00506 00507 void 00508 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT 00509 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); } 00510 00511 #if __cplusplus < 201103L 00512 void 00513 _M_construct_node(_Link_type __node, const value_type& __x) 00514 { 00515 __try 00516 { get_allocator().construct(__node->_M_valptr(), __x); } 00517 __catch(...) 00518 { 00519 _M_put_node(__node); 00520 __throw_exception_again; 00521 } 00522 } 00523 00524 _Link_type 00525 _M_create_node(const value_type& __x) 00526 { 00527 _Link_type __tmp = _M_get_node(); 00528 _M_construct_node(__tmp, __x); 00529 return __tmp; 00530 } 00531 00532 void 00533 _M_destroy_node(_Link_type __p) 00534 { get_allocator().destroy(__p->_M_valptr()); } 00535 #else 00536 template<typename... _Args> 00537 void 00538 _M_construct_node(_Link_type __node, _Args&&... __args) 00539 { 00540 __try 00541 { 00542 ::new(__node) _Rb_tree_node<_Val>; 00543 _Alloc_traits::construct(_M_get_Node_allocator(), 00544 __node->_M_valptr(), 00545 std::forward<_Args>(__args)...); 00546 } 00547 __catch(...) 00548 { 00549 __node->~_Rb_tree_node<_Val>(); 00550 _M_put_node(__node); 00551 __throw_exception_again; 00552 } 00553 } 00554 00555 template<typename... _Args> 00556 _Link_type 00557 _M_create_node(_Args&&... __args) 00558 { 00559 _Link_type __tmp = _M_get_node(); 00560 _M_construct_node(__tmp, std::forward<_Args>(__args)...); 00561 return __tmp; 00562 } 00563 00564 void 00565 _M_destroy_node(_Link_type __p) noexcept 00566 { 00567 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr()); 00568 __p->~_Rb_tree_node<_Val>(); 00569 } 00570 #endif 00571 00572 void 00573 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT 00574 { 00575 _M_destroy_node(__p); 00576 _M_put_node(__p); 00577 } 00578 00579 template<typename _NodeGen> 00580 _Link_type 00581 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen) 00582 { 00583 _Link_type __tmp = __node_gen(*__x->_M_valptr()); 00584 __tmp->_M_color = __x->_M_color; 00585 __tmp->_M_left = 0; 00586 __tmp->_M_right = 0; 00587 return __tmp; 00588 } 00589 00590 protected: 00591 // Unused _Is_pod_comparator is kept as it is part of mangled name. 00592 template<typename _Key_compare, 00593 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)> 00594 struct _Rb_tree_impl : public _Node_allocator 00595 { 00596 _Key_compare _M_key_compare; 00597 _Rb_tree_node_base _M_header; 00598 size_type _M_node_count; // Keeps track of size of tree. 00599 00600 _Rb_tree_impl() 00601 : _Node_allocator(), _M_key_compare(), _M_header(), 00602 _M_node_count(0) 00603 { _M_initialize(); } 00604 00605 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 00606 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), 00607 _M_node_count(0) 00608 { _M_initialize(); } 00609 00610 #if __cplusplus >= 201103L 00611 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) 00612 : _Node_allocator(std::move(__a)), _M_key_compare(__comp), 00613 _M_header(), _M_node_count(0) 00614 { _M_initialize(); } 00615 #endif 00616 00617 void 00618 _M_reset() 00619 { 00620 this->_M_header._M_parent = 0; 00621 this->_M_header._M_left = &this->_M_header; 00622 this->_M_header._M_right = &this->_M_header; 00623 this->_M_node_count = 0; 00624 } 00625 00626 private: 00627 void 00628 _M_initialize() 00629 { 00630 this->_M_header._M_color = _S_red; 00631 this->_M_header._M_parent = 0; 00632 this->_M_header._M_left = &this->_M_header; 00633 this->_M_header._M_right = &this->_M_header; 00634 } 00635 }; 00636 00637 _Rb_tree_impl<_Compare> _M_impl; 00638 00639 protected: 00640 _Base_ptr& 00641 _M_root() _GLIBCXX_NOEXCEPT 00642 { return this->_M_impl._M_header._M_parent; } 00643 00644 _Const_Base_ptr 00645 _M_root() const _GLIBCXX_NOEXCEPT 00646 { return this->_M_impl._M_header._M_parent; } 00647 00648 _Base_ptr& 00649 _M_leftmost() _GLIBCXX_NOEXCEPT 00650 { return this->_M_impl._M_header._M_left; } 00651 00652 _Const_Base_ptr 00653 _M_leftmost() const _GLIBCXX_NOEXCEPT 00654 { return this->_M_impl._M_header._M_left; } 00655 00656 _Base_ptr& 00657 _M_rightmost() _GLIBCXX_NOEXCEPT 00658 { return this->_M_impl._M_header._M_right; } 00659 00660 _Const_Base_ptr 00661 _M_rightmost() const _GLIBCXX_NOEXCEPT 00662 { return this->_M_impl._M_header._M_right; } 00663 00664 _Link_type 00665 _M_begin() _GLIBCXX_NOEXCEPT 00666 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 00667 00668 _Const_Link_type 00669 _M_begin() const _GLIBCXX_NOEXCEPT 00670 { 00671 return static_cast<_Const_Link_type> 00672 (this->_M_impl._M_header._M_parent); 00673 } 00674 00675 _Base_ptr 00676 _M_end() _GLIBCXX_NOEXCEPT 00677 { return &this->_M_impl._M_header; } 00678 00679 _Const_Base_ptr 00680 _M_end() const _GLIBCXX_NOEXCEPT 00681 { return &this->_M_impl._M_header; } 00682 00683 static const_reference 00684 _S_value(_Const_Link_type __x) 00685 { return *__x->_M_valptr(); } 00686 00687 static const _Key& 00688 _S_key(_Const_Link_type __x) 00689 { return _KeyOfValue()(_S_value(__x)); } 00690 00691 static _Link_type 00692 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00693 { return static_cast<_Link_type>(__x->_M_left); } 00694 00695 static _Const_Link_type 00696 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00697 { return static_cast<_Const_Link_type>(__x->_M_left); } 00698 00699 static _Link_type 00700 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00701 { return static_cast<_Link_type>(__x->_M_right); } 00702 00703 static _Const_Link_type 00704 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00705 { return static_cast<_Const_Link_type>(__x->_M_right); } 00706 00707 static const_reference 00708 _S_value(_Const_Base_ptr __x) 00709 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); } 00710 00711 static const _Key& 00712 _S_key(_Const_Base_ptr __x) 00713 { return _KeyOfValue()(_S_value(__x)); } 00714 00715 static _Base_ptr 00716 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00717 { return _Rb_tree_node_base::_S_minimum(__x); } 00718 00719 static _Const_Base_ptr 00720 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00721 { return _Rb_tree_node_base::_S_minimum(__x); } 00722 00723 static _Base_ptr 00724 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00725 { return _Rb_tree_node_base::_S_maximum(__x); } 00726 00727 static _Const_Base_ptr 00728 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00729 { return _Rb_tree_node_base::_S_maximum(__x); } 00730 00731 public: 00732 typedef _Rb_tree_iterator<value_type> iterator; 00733 typedef _Rb_tree_const_iterator<value_type> const_iterator; 00734 00735 typedef std::reverse_iterator<iterator> reverse_iterator; 00736 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00737 00738 pair<_Base_ptr, _Base_ptr> 00739 _M_get_insert_unique_pos(const key_type& __k); 00740 00741 pair<_Base_ptr, _Base_ptr> 00742 _M_get_insert_equal_pos(const key_type& __k); 00743 00744 pair<_Base_ptr, _Base_ptr> 00745 _M_get_insert_hint_unique_pos(const_iterator __pos, 00746 const key_type& __k); 00747 00748 pair<_Base_ptr, _Base_ptr> 00749 _M_get_insert_hint_equal_pos(const_iterator __pos, 00750 const key_type& __k); 00751 00752 private: 00753 #if __cplusplus >= 201103L 00754 template<typename _Arg, typename _NodeGen> 00755 iterator 00756 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&); 00757 00758 iterator 00759 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); 00760 00761 template<typename _Arg> 00762 iterator 00763 _M_insert_lower(_Base_ptr __y, _Arg&& __v); 00764 00765 template<typename _Arg> 00766 iterator 00767 _M_insert_equal_lower(_Arg&& __x); 00768 00769 iterator 00770 _M_insert_lower_node(_Base_ptr __p, _Link_type __z); 00771 00772 iterator 00773 _M_insert_equal_lower_node(_Link_type __z); 00774 #else 00775 template<typename _NodeGen> 00776 iterator 00777 _M_insert_(_Base_ptr __x, _Base_ptr __y, 00778 const value_type& __v, _NodeGen&); 00779 00780 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00781 // 233. Insertion hints in associative containers. 00782 iterator 00783 _M_insert_lower(_Base_ptr __y, const value_type& __v); 00784 00785 iterator 00786 _M_insert_equal_lower(const value_type& __x); 00787 #endif 00788 00789 template<typename _NodeGen> 00790 _Link_type 00791 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&); 00792 00793 _Link_type 00794 _M_copy(_Const_Link_type __x, _Base_ptr __p) 00795 { 00796 _Alloc_node __an(*this); 00797 return _M_copy(__x, __p, __an); 00798 } 00799 00800 void 00801 _M_erase(_Link_type __x); 00802 00803 iterator 00804 _M_lower_bound(_Link_type __x, _Base_ptr __y, 00805 const _Key& __k); 00806 00807 const_iterator 00808 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, 00809 const _Key& __k) const; 00810 00811 iterator 00812 _M_upper_bound(_Link_type __x, _Base_ptr __y, 00813 const _Key& __k); 00814 00815 const_iterator 00816 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, 00817 const _Key& __k) const; 00818 00819 public: 00820 // allocation/deallocation 00821 _Rb_tree() { } 00822 00823 _Rb_tree(const _Compare& __comp, 00824 const allocator_type& __a = allocator_type()) 00825 : _M_impl(__comp, _Node_allocator(__a)) { } 00826 00827 _Rb_tree(const _Rb_tree& __x) 00828 : _M_impl(__x._M_impl._M_key_compare, 00829 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator())) 00830 { 00831 if (__x._M_root() != 0) 00832 { 00833 _M_root() = _M_copy(__x._M_begin(), _M_end()); 00834 _M_leftmost() = _S_minimum(_M_root()); 00835 _M_rightmost() = _S_maximum(_M_root()); 00836 _M_impl._M_node_count = __x._M_impl._M_node_count; 00837 } 00838 } 00839 00840 #if __cplusplus >= 201103L 00841 _Rb_tree(const allocator_type& __a) 00842 : _M_impl(_Compare(), _Node_allocator(__a)) 00843 { } 00844 00845 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a) 00846 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) 00847 { 00848 if (__x._M_root() != nullptr) 00849 { 00850 _M_root() = _M_copy(__x._M_begin(), _M_end()); 00851 _M_leftmost() = _S_minimum(_M_root()); 00852 _M_rightmost() = _S_maximum(_M_root()); 00853 _M_impl._M_node_count = __x._M_impl._M_node_count; 00854 } 00855 } 00856 00857 _Rb_tree(_Rb_tree&& __x) 00858 : _M_impl(__x._M_impl._M_key_compare, 00859 std::move(__x._M_get_Node_allocator())) 00860 { 00861 if (__x._M_root() != 0) 00862 _M_move_data(__x, std::true_type()); 00863 } 00864 00865 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a) 00866 : _Rb_tree(std::move(__x), _Node_allocator(__a)) 00867 { } 00868 00869 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a); 00870 #endif 00871 00872 ~_Rb_tree() _GLIBCXX_NOEXCEPT 00873 { _M_erase(_M_begin()); } 00874 00875 _Rb_tree& 00876 operator=(const _Rb_tree& __x); 00877 00878 // Accessors. 00879 _Compare 00880 key_comp() const 00881 { return _M_impl._M_key_compare; } 00882 00883 iterator 00884 begin() _GLIBCXX_NOEXCEPT 00885 { return iterator(this->_M_impl._M_header._M_left); } 00886 00887 const_iterator 00888 begin() const _GLIBCXX_NOEXCEPT 00889 { return const_iterator(this->_M_impl._M_header._M_left); } 00890 00891 iterator 00892 end() _GLIBCXX_NOEXCEPT 00893 { return iterator(&this->_M_impl._M_header); } 00894 00895 const_iterator 00896 end() const _GLIBCXX_NOEXCEPT 00897 { return const_iterator(&this->_M_impl._M_header); } 00898 00899 reverse_iterator 00900 rbegin() _GLIBCXX_NOEXCEPT 00901 { return reverse_iterator(end()); } 00902 00903 const_reverse_iterator 00904 rbegin() const _GLIBCXX_NOEXCEPT 00905 { return const_reverse_iterator(end()); } 00906 00907 reverse_iterator 00908 rend() _GLIBCXX_NOEXCEPT 00909 { return reverse_iterator(begin()); } 00910 00911 const_reverse_iterator 00912 rend() const _GLIBCXX_NOEXCEPT 00913 { return const_reverse_iterator(begin()); } 00914 00915 bool 00916 empty() const _GLIBCXX_NOEXCEPT 00917 { return _M_impl._M_node_count == 0; } 00918 00919 size_type 00920 size() const _GLIBCXX_NOEXCEPT 00921 { return _M_impl._M_node_count; } 00922 00923 size_type 00924 max_size() const _GLIBCXX_NOEXCEPT 00925 { return _Alloc_traits::max_size(_M_get_Node_allocator()); } 00926 00927 void 00928 swap(_Rb_tree& __t) 00929 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value); 00930 00931 // Insert/erase. 00932 #if __cplusplus >= 201103L 00933 template<typename _Arg> 00934 pair<iterator, bool> 00935 _M_insert_unique(_Arg&& __x); 00936 00937 template<typename _Arg> 00938 iterator 00939 _M_insert_equal(_Arg&& __x); 00940 00941 template<typename _Arg, typename _NodeGen> 00942 iterator 00943 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&); 00944 00945 template<typename _Arg> 00946 iterator 00947 _M_insert_unique_(const_iterator __pos, _Arg&& __x) 00948 { 00949 _Alloc_node __an(*this); 00950 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an); 00951 } 00952 00953 template<typename _Arg, typename _NodeGen> 00954 iterator 00955 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&); 00956 00957 template<typename _Arg> 00958 iterator 00959 _M_insert_equal_(const_iterator __pos, _Arg&& __x) 00960 { 00961 _Alloc_node __an(*this); 00962 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); 00963 } 00964 00965 template<typename... _Args> 00966 pair<iterator, bool> 00967 _M_emplace_unique(_Args&&... __args); 00968 00969 template<typename... _Args> 00970 iterator 00971 _M_emplace_equal(_Args&&... __args); 00972 00973 template<typename... _Args> 00974 iterator 00975 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); 00976 00977 template<typename... _Args> 00978 iterator 00979 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); 00980 #else 00981 pair<iterator, bool> 00982 _M_insert_unique(const value_type& __x); 00983 00984 iterator 00985 _M_insert_equal(const value_type& __x); 00986 00987 template<typename _NodeGen> 00988 iterator 00989 _M_insert_unique_(const_iterator __pos, const value_type& __x, 00990 _NodeGen&); 00991 00992 iterator 00993 _M_insert_unique_(const_iterator __pos, const value_type& __x) 00994 { 00995 _Alloc_node __an(*this); 00996 return _M_insert_unique_(__pos, __x, __an); 00997 } 00998 00999 template<typename _NodeGen> 01000 iterator 01001 _M_insert_equal_(const_iterator __pos, const value_type& __x, 01002 _NodeGen&); 01003 iterator 01004 _M_insert_equal_(const_iterator __pos, const value_type& __x) 01005 { 01006 _Alloc_node __an(*this); 01007 return _M_insert_equal_(__pos, __x, __an); 01008 } 01009 #endif 01010 01011 template<typename _InputIterator> 01012 void 01013 _M_insert_unique(_InputIterator __first, _InputIterator __last); 01014 01015 template<typename _InputIterator> 01016 void 01017 _M_insert_equal(_InputIterator __first, _InputIterator __last); 01018 01019 private: 01020 void 01021 _M_erase_aux(const_iterator __position); 01022 01023 void 01024 _M_erase_aux(const_iterator __first, const_iterator __last); 01025 01026 public: 01027 #if __cplusplus >= 201103L 01028 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01029 // DR 130. Associative erase should return an iterator. 01030 _GLIBCXX_ABI_TAG_CXX11 01031 iterator 01032 erase(const_iterator __position) 01033 { 01034 const_iterator __result = __position; 01035 ++__result; 01036 _M_erase_aux(__position); 01037 return __result._M_const_cast(); 01038 } 01039 01040 // LWG 2059. 01041 _GLIBCXX_ABI_TAG_CXX11 01042 iterator 01043 erase(iterator __position) 01044 { 01045 iterator __result = __position; 01046 ++__result; 01047 _M_erase_aux(__position); 01048 return __result; 01049 } 01050 #else 01051 void 01052 erase(iterator __position) 01053 { _M_erase_aux(__position); } 01054 01055 void 01056 erase(const_iterator __position) 01057 { _M_erase_aux(__position); } 01058 #endif 01059 size_type 01060 erase(const key_type& __x); 01061 01062 #if __cplusplus >= 201103L 01063 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01064 // DR 130. Associative erase should return an iterator. 01065 _GLIBCXX_ABI_TAG_CXX11 01066 iterator 01067 erase(const_iterator __first, const_iterator __last) 01068 { 01069 _M_erase_aux(__first, __last); 01070 return __last._M_const_cast(); 01071 } 01072 #else 01073 void 01074 erase(iterator __first, iterator __last) 01075 { _M_erase_aux(__first, __last); } 01076 01077 void 01078 erase(const_iterator __first, const_iterator __last) 01079 { _M_erase_aux(__first, __last); } 01080 #endif 01081 void 01082 erase(const key_type* __first, const key_type* __last); 01083 01084 void 01085 clear() _GLIBCXX_NOEXCEPT 01086 { 01087 _M_erase(_M_begin()); 01088 _M_impl._M_reset(); 01089 } 01090 01091 // Set operations. 01092 iterator 01093 find(const key_type& __k); 01094 01095 const_iterator 01096 find(const key_type& __k) const; 01097 01098 size_type 01099 count(const key_type& __k) const; 01100 01101 iterator 01102 lower_bound(const key_type& __k) 01103 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 01104 01105 const_iterator 01106 lower_bound(const key_type& __k) const 01107 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 01108 01109 iterator 01110 upper_bound(const key_type& __k) 01111 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 01112 01113 const_iterator 01114 upper_bound(const key_type& __k) const 01115 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 01116 01117 pair<iterator, iterator> 01118 equal_range(const key_type& __k); 01119 01120 pair<const_iterator, const_iterator> 01121 equal_range(const key_type& __k) const; 01122 01123 #if __cplusplus > 201103L 01124 template<typename _Kt, 01125 typename _Req = 01126 typename __has_is_transparent<_Compare, _Kt>::type> 01127 iterator 01128 _M_find_tr(const _Kt& __k) 01129 { 01130 const _Rb_tree* __const_this = this; 01131 return __const_this->_M_find_tr(__k)._M_const_cast(); 01132 } 01133 01134 template<typename _Kt, 01135 typename _Req = 01136 typename __has_is_transparent<_Compare, _Kt>::type> 01137 const_iterator 01138 _M_find_tr(const _Kt& __k) const 01139 { 01140 auto __j = _M_lower_bound_tr(__k); 01141 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node))) 01142 __j = end(); 01143 return __j; 01144 } 01145 01146 template<typename _Kt, 01147 typename _Req = 01148 typename __has_is_transparent<_Compare, _Kt>::type> 01149 size_type 01150 _M_count_tr(const _Kt& __k) const 01151 { 01152 auto __p = _M_equal_range_tr(__k); 01153 return std::distance(__p.first, __p.second); 01154 } 01155 01156 template<typename _Kt, 01157 typename _Req = 01158 typename __has_is_transparent<_Compare, _Kt>::type> 01159 iterator 01160 _M_lower_bound_tr(const _Kt& __k) 01161 { 01162 const _Rb_tree* __const_this = this; 01163 return __const_this->_M_lower_bound_tr(__k)._M_const_cast(); 01164 } 01165 01166 template<typename _Kt, 01167 typename _Req = 01168 typename __has_is_transparent<_Compare, _Kt>::type> 01169 const_iterator 01170 _M_lower_bound_tr(const _Kt& __k) const 01171 { 01172 auto __x = _M_begin(); 01173 auto __y = _M_end(); 01174 while (__x != 0) 01175 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01176 { 01177 __y = __x; 01178 __x = _S_left(__x); 01179 } 01180 else 01181 __x = _S_right(__x); 01182 return const_iterator(__y); 01183 } 01184 01185 template<typename _Kt, 01186 typename _Req = 01187 typename __has_is_transparent<_Compare, _Kt>::type> 01188 iterator 01189 _M_upper_bound_tr(const _Kt& __k) 01190 { 01191 const _Rb_tree* __const_this = this; 01192 return __const_this->_M_upper_bound_tr(__k)._M_const_cast(); 01193 } 01194 01195 template<typename _Kt, 01196 typename _Req = 01197 typename __has_is_transparent<_Compare, _Kt>::type> 01198 const_iterator 01199 _M_upper_bound_tr(const _Kt& __k) const 01200 { 01201 auto __x = _M_begin(); 01202 auto __y = _M_end(); 01203 while (__x != 0) 01204 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01205 { 01206 __y = __x; 01207 __x = _S_left(__x); 01208 } 01209 else 01210 __x = _S_right(__x); 01211 return const_iterator(__y); 01212 } 01213 01214 template<typename _Kt, 01215 typename _Req = 01216 typename __has_is_transparent<_Compare, _Kt>::type> 01217 pair<iterator, iterator> 01218 _M_equal_range_tr(const _Kt& __k) 01219 { 01220 const _Rb_tree* __const_this = this; 01221 auto __ret = __const_this->_M_equal_range_tr(__k); 01222 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() }; 01223 } 01224 01225 template<typename _Kt, 01226 typename _Req = 01227 typename __has_is_transparent<_Compare, _Kt>::type> 01228 pair<const_iterator, const_iterator> 01229 _M_equal_range_tr(const _Kt& __k) const 01230 { 01231 auto __low = _M_lower_bound_tr(__k); 01232 auto __high = __low; 01233 auto& __cmp = _M_impl._M_key_compare; 01234 while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) 01235 ++__high; 01236 return { __low, __high }; 01237 } 01238 #endif 01239 01240 // Debugging. 01241 bool 01242 __rb_verify() const; 01243 01244 #if __cplusplus >= 201103L 01245 _Rb_tree& 01246 operator=(_Rb_tree&&) 01247 noexcept(_Alloc_traits::_S_nothrow_move() 01248 && is_nothrow_move_assignable<_Compare>::value); 01249 01250 template<typename _Iterator> 01251 void 01252 _M_assign_unique(_Iterator, _Iterator); 01253 01254 template<typename _Iterator> 01255 void 01256 _M_assign_equal(_Iterator, _Iterator); 01257 01258 private: 01259 // Move elements from container with equal allocator. 01260 void 01261 _M_move_data(_Rb_tree&, std::true_type); 01262 01263 // Move elements from container with possibly non-equal allocator, 01264 // which might result in a copy not a move. 01265 void 01266 _M_move_data(_Rb_tree&, std::false_type); 01267 #endif 01268 }; 01269 01270 template<typename _Key, typename _Val, typename _KeyOfValue, 01271 typename _Compare, typename _Alloc> 01272 inline bool 01273 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01274 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01275 { 01276 return __x.size() == __y.size() 01277 && std::equal(__x.begin(), __x.end(), __y.begin()); 01278 } 01279 01280 template<typename _Key, typename _Val, typename _KeyOfValue, 01281 typename _Compare, typename _Alloc> 01282 inline bool 01283 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01284 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01285 { 01286 return std::lexicographical_compare(__x.begin(), __x.end(), 01287 __y.begin(), __y.end()); 01288 } 01289 01290 template<typename _Key, typename _Val, typename _KeyOfValue, 01291 typename _Compare, typename _Alloc> 01292 inline bool 01293 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01294 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01295 { return !(__x == __y); } 01296 01297 template<typename _Key, typename _Val, typename _KeyOfValue, 01298 typename _Compare, typename _Alloc> 01299 inline bool 01300 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01301 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01302 { return __y < __x; } 01303 01304 template<typename _Key, typename _Val, typename _KeyOfValue, 01305 typename _Compare, typename _Alloc> 01306 inline bool 01307 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01308 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01309 { return !(__y < __x); } 01310 01311 template<typename _Key, typename _Val, typename _KeyOfValue, 01312 typename _Compare, typename _Alloc> 01313 inline bool 01314 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01315 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01316 { return !(__x < __y); } 01317 01318 template<typename _Key, typename _Val, typename _KeyOfValue, 01319 typename _Compare, typename _Alloc> 01320 inline void 01321 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01322 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01323 { __x.swap(__y); } 01324 01325 #if __cplusplus >= 201103L 01326 template<typename _Key, typename _Val, typename _KeyOfValue, 01327 typename _Compare, typename _Alloc> 01328 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01329 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) 01330 : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) 01331 { 01332 using __eq = typename _Alloc_traits::is_always_equal; 01333 if (__x._M_root() != nullptr) 01334 _M_move_data(__x, __eq()); 01335 } 01336 01337 template<typename _Key, typename _Val, typename _KeyOfValue, 01338 typename _Compare, typename _Alloc> 01339 void 01340 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01341 _M_move_data(_Rb_tree& __x, std::true_type) 01342 { 01343 _M_root() = __x._M_root(); 01344 _M_leftmost() = __x._M_leftmost(); 01345 _M_rightmost() = __x._M_rightmost(); 01346 _M_root()->_M_parent = _M_end(); 01347 01348 __x._M_root() = 0; 01349 __x._M_leftmost() = __x._M_end(); 01350 __x._M_rightmost() = __x._M_end(); 01351 01352 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 01353 __x._M_impl._M_node_count = 0; 01354 } 01355 01356 template<typename _Key, typename _Val, typename _KeyOfValue, 01357 typename _Compare, typename _Alloc> 01358 void 01359 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01360 _M_move_data(_Rb_tree& __x, std::false_type) 01361 { 01362 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 01363 _M_move_data(__x, std::true_type()); 01364 else 01365 { 01366 _Alloc_node __an(*this); 01367 auto __lbd = 01368 [&__an](const value_type& __cval) 01369 { 01370 auto& __val = const_cast<value_type&>(__cval); 01371 return __an(std::move_if_noexcept(__val)); 01372 }; 01373 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); 01374 _M_leftmost() = _S_minimum(_M_root()); 01375 _M_rightmost() = _S_maximum(_M_root()); 01376 _M_impl._M_node_count = __x._M_impl._M_node_count; 01377 } 01378 } 01379 01380 template<typename _Key, typename _Val, typename _KeyOfValue, 01381 typename _Compare, typename _Alloc> 01382 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 01383 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01384 operator=(_Rb_tree&& __x) 01385 noexcept(_Alloc_traits::_S_nothrow_move() 01386 && is_nothrow_move_assignable<_Compare>::value) 01387 { 01388 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 01389 if (_Alloc_traits::_S_propagate_on_move_assign() 01390 || _Alloc_traits::_S_always_equal() 01391 || _M_get_Node_allocator() == __x._M_get_Node_allocator()) 01392 { 01393 clear(); 01394 if (__x._M_root() != nullptr) 01395 _M_move_data(__x, std::true_type()); 01396 std::__alloc_on_move(_M_get_Node_allocator(), 01397 __x._M_get_Node_allocator()); 01398 return *this; 01399 } 01400 01401 // Try to move each node reusing existing nodes and copying __x nodes 01402 // structure. 01403 _Reuse_or_alloc_node __roan(*this); 01404 _M_impl._M_reset(); 01405 if (__x._M_root() != nullptr) 01406 { 01407 auto __lbd = 01408 [&__roan](const value_type& __cval) 01409 { 01410 auto& __val = const_cast<value_type&>(__cval); 01411 return __roan(std::move_if_noexcept(__val)); 01412 }; 01413 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); 01414 _M_leftmost() = _S_minimum(_M_root()); 01415 _M_rightmost() = _S_maximum(_M_root()); 01416 _M_impl._M_node_count = __x._M_impl._M_node_count; 01417 __x.clear(); 01418 } 01419 return *this; 01420 } 01421 01422 template<typename _Key, typename _Val, typename _KeyOfValue, 01423 typename _Compare, typename _Alloc> 01424 template<typename _Iterator> 01425 void 01426 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01427 _M_assign_unique(_Iterator __first, _Iterator __last) 01428 { 01429 _Reuse_or_alloc_node __roan(*this); 01430 _M_impl._M_reset(); 01431 for (; __first != __last; ++__first) 01432 _M_insert_unique_(end(), *__first, __roan); 01433 } 01434 01435 template<typename _Key, typename _Val, typename _KeyOfValue, 01436 typename _Compare, typename _Alloc> 01437 template<typename _Iterator> 01438 void 01439 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01440 _M_assign_equal(_Iterator __first, _Iterator __last) 01441 { 01442 _Reuse_or_alloc_node __roan(*this); 01443 _M_impl._M_reset(); 01444 for (; __first != __last; ++__first) 01445 _M_insert_equal_(end(), *__first, __roan); 01446 } 01447 #endif 01448 01449 template<typename _Key, typename _Val, typename _KeyOfValue, 01450 typename _Compare, typename _Alloc> 01451 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 01452 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01453 operator=(const _Rb_tree& __x) 01454 { 01455 if (this != &__x) 01456 { 01457 // Note that _Key may be a constant type. 01458 #if __cplusplus >= 201103L 01459 if (_Alloc_traits::_S_propagate_on_copy_assign()) 01460 { 01461 auto& __this_alloc = this->_M_get_Node_allocator(); 01462 auto& __that_alloc = __x._M_get_Node_allocator(); 01463 if (!_Alloc_traits::_S_always_equal() 01464 && __this_alloc != __that_alloc) 01465 { 01466 // Replacement allocator cannot free existing storage, we need 01467 // to erase nodes first. 01468 clear(); 01469 std::__alloc_on_copy(__this_alloc, __that_alloc); 01470 } 01471 } 01472 #endif 01473 01474 _Reuse_or_alloc_node __roan(*this); 01475 _M_impl._M_reset(); 01476 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 01477 if (__x._M_root() != 0) 01478 { 01479 _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan); 01480 _M_leftmost() = _S_minimum(_M_root()); 01481 _M_rightmost() = _S_maximum(_M_root()); 01482 _M_impl._M_node_count = __x._M_impl._M_node_count; 01483 } 01484 } 01485 01486 return *this; 01487 } 01488 01489 template<typename _Key, typename _Val, typename _KeyOfValue, 01490 typename _Compare, typename _Alloc> 01491 #if __cplusplus >= 201103L 01492 template<typename _Arg, typename _NodeGen> 01493 #else 01494 template<typename _NodeGen> 01495 #endif 01496 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01497 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01498 _M_insert_(_Base_ptr __x, _Base_ptr __p, 01499 #if __cplusplus >= 201103L 01500 _Arg&& __v, 01501 #else 01502 const _Val& __v, 01503 #endif 01504 _NodeGen& __node_gen) 01505 { 01506 bool __insert_left = (__x != 0 || __p == _M_end() 01507 || _M_impl._M_key_compare(_KeyOfValue()(__v), 01508 _S_key(__p))); 01509 01510 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); 01511 01512 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01513 this->_M_impl._M_header); 01514 ++_M_impl._M_node_count; 01515 return iterator(__z); 01516 } 01517 01518 template<typename _Key, typename _Val, typename _KeyOfValue, 01519 typename _Compare, typename _Alloc> 01520 #if __cplusplus >= 201103L 01521 template<typename _Arg> 01522 #endif 01523 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01524 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01525 #if __cplusplus >= 201103L 01526 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 01527 #else 01528 _M_insert_lower(_Base_ptr __p, const _Val& __v) 01529 #endif 01530 { 01531 bool __insert_left = (__p == _M_end() 01532 || !_M_impl._M_key_compare(_S_key(__p), 01533 _KeyOfValue()(__v))); 01534 01535 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 01536 01537 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01538 this->_M_impl._M_header); 01539 ++_M_impl._M_node_count; 01540 return iterator(__z); 01541 } 01542 01543 template<typename _Key, typename _Val, typename _KeyOfValue, 01544 typename _Compare, typename _Alloc> 01545 #if __cplusplus >= 201103L 01546 template<typename _Arg> 01547 #endif 01548 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01549 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01550 #if __cplusplus >= 201103L 01551 _M_insert_equal_lower(_Arg&& __v) 01552 #else 01553 _M_insert_equal_lower(const _Val& __v) 01554 #endif 01555 { 01556 _Link_type __x = _M_begin(); 01557 _Base_ptr __y = _M_end(); 01558 while (__x != 0) 01559 { 01560 __y = __x; 01561 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 01562 _S_left(__x) : _S_right(__x); 01563 } 01564 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 01565 } 01566 01567 template<typename _Key, typename _Val, typename _KoV, 01568 typename _Compare, typename _Alloc> 01569 template<typename _NodeGen> 01570 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 01571 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 01572 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) 01573 { 01574 // Structural copy. __x and __p must be non-null. 01575 _Link_type __top = _M_clone_node(__x, __node_gen); 01576 __top->_M_parent = __p; 01577 01578 __try 01579 { 01580 if (__x->_M_right) 01581 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen); 01582 __p = __top; 01583 __x = _S_left(__x); 01584 01585 while (__x != 0) 01586 { 01587 _Link_type __y = _M_clone_node(__x, __node_gen); 01588 __p->_M_left = __y; 01589 __y->_M_parent = __p; 01590 if (__x->_M_right) 01591 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen); 01592 __p = __y; 01593 __x = _S_left(__x); 01594 } 01595 } 01596 __catch(...) 01597 { 01598 _M_erase(__top); 01599 __throw_exception_again; 01600 } 01601 return __top; 01602 } 01603 01604 template<typename _Key, typename _Val, typename _KeyOfValue, 01605 typename _Compare, typename _Alloc> 01606 void 01607 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01608 _M_erase(_Link_type __x) 01609 { 01610 // Erase without rebalancing. 01611 while (__x != 0) 01612 { 01613 _M_erase(_S_right(__x)); 01614 _Link_type __y = _S_left(__x); 01615 _M_drop_node(__x); 01616 __x = __y; 01617 } 01618 } 01619 01620 template<typename _Key, typename _Val, typename _KeyOfValue, 01621 typename _Compare, typename _Alloc> 01622 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01623 _Compare, _Alloc>::iterator 01624 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01625 _M_lower_bound(_Link_type __x, _Base_ptr __y, 01626 const _Key& __k) 01627 { 01628 while (__x != 0) 01629 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01630 __y = __x, __x = _S_left(__x); 01631 else 01632 __x = _S_right(__x); 01633 return iterator(__y); 01634 } 01635 01636 template<typename _Key, typename _Val, typename _KeyOfValue, 01637 typename _Compare, typename _Alloc> 01638 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01639 _Compare, _Alloc>::const_iterator 01640 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01641 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, 01642 const _Key& __k) const 01643 { 01644 while (__x != 0) 01645 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01646 __y = __x, __x = _S_left(__x); 01647 else 01648 __x = _S_right(__x); 01649 return const_iterator(__y); 01650 } 01651 01652 template<typename _Key, typename _Val, typename _KeyOfValue, 01653 typename _Compare, typename _Alloc> 01654 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01655 _Compare, _Alloc>::iterator 01656 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01657 _M_upper_bound(_Link_type __x, _Base_ptr __y, 01658 const _Key& __k) 01659 { 01660 while (__x != 0) 01661 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01662 __y = __x, __x = _S_left(__x); 01663 else 01664 __x = _S_right(__x); 01665 return iterator(__y); 01666 } 01667 01668 template<typename _Key, typename _Val, typename _KeyOfValue, 01669 typename _Compare, typename _Alloc> 01670 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01671 _Compare, _Alloc>::const_iterator 01672 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01673 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, 01674 const _Key& __k) const 01675 { 01676 while (__x != 0) 01677 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01678 __y = __x, __x = _S_left(__x); 01679 else 01680 __x = _S_right(__x); 01681 return const_iterator(__y); 01682 } 01683 01684 template<typename _Key, typename _Val, typename _KeyOfValue, 01685 typename _Compare, typename _Alloc> 01686 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01687 _Compare, _Alloc>::iterator, 01688 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01689 _Compare, _Alloc>::iterator> 01690 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01691 equal_range(const _Key& __k) 01692 { 01693 _Link_type __x = _M_begin(); 01694 _Base_ptr __y = _M_end(); 01695 while (__x != 0) 01696 { 01697 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01698 __x = _S_right(__x); 01699 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01700 __y = __x, __x = _S_left(__x); 01701 else 01702 { 01703 _Link_type __xu(__x); 01704 _Base_ptr __yu(__y); 01705 __y = __x, __x = _S_left(__x); 01706 __xu = _S_right(__xu); 01707 return pair<iterator, 01708 iterator>(_M_lower_bound(__x, __y, __k), 01709 _M_upper_bound(__xu, __yu, __k)); 01710 } 01711 } 01712 return pair<iterator, iterator>(iterator(__y), 01713 iterator(__y)); 01714 } 01715 01716 template<typename _Key, typename _Val, typename _KeyOfValue, 01717 typename _Compare, typename _Alloc> 01718 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01719 _Compare, _Alloc>::const_iterator, 01720 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01721 _Compare, _Alloc>::const_iterator> 01722 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01723 equal_range(const _Key& __k) const 01724 { 01725 _Const_Link_type __x = _M_begin(); 01726 _Const_Base_ptr __y = _M_end(); 01727 while (__x != 0) 01728 { 01729 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01730 __x = _S_right(__x); 01731 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01732 __y = __x, __x = _S_left(__x); 01733 else 01734 { 01735 _Const_Link_type __xu(__x); 01736 _Const_Base_ptr __yu(__y); 01737 __y = __x, __x = _S_left(__x); 01738 __xu = _S_right(__xu); 01739 return pair<const_iterator, 01740 const_iterator>(_M_lower_bound(__x, __y, __k), 01741 _M_upper_bound(__xu, __yu, __k)); 01742 } 01743 } 01744 return pair<const_iterator, const_iterator>(const_iterator(__y), 01745 const_iterator(__y)); 01746 } 01747 01748 template<typename _Key, typename _Val, typename _KeyOfValue, 01749 typename _Compare, typename _Alloc> 01750 void 01751 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01752 swap(_Rb_tree& __t) 01753 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 01754 { 01755 if (_M_root() == 0) 01756 { 01757 if (__t._M_root() != 0) 01758 { 01759 _M_root() = __t._M_root(); 01760 _M_leftmost() = __t._M_leftmost(); 01761 _M_rightmost() = __t._M_rightmost(); 01762 _M_root()->_M_parent = _M_end(); 01763 _M_impl._M_node_count = __t._M_impl._M_node_count; 01764 01765 __t._M_impl._M_reset(); 01766 } 01767 } 01768 else if (__t._M_root() == 0) 01769 { 01770 __t._M_root() = _M_root(); 01771 __t._M_leftmost() = _M_leftmost(); 01772 __t._M_rightmost() = _M_rightmost(); 01773 __t._M_root()->_M_parent = __t._M_end(); 01774 __t._M_impl._M_node_count = _M_impl._M_node_count; 01775 01776 _M_impl._M_reset(); 01777 } 01778 else 01779 { 01780 std::swap(_M_root(),__t._M_root()); 01781 std::swap(_M_leftmost(),__t._M_leftmost()); 01782 std::swap(_M_rightmost(),__t._M_rightmost()); 01783 01784 _M_root()->_M_parent = _M_end(); 01785 __t._M_root()->_M_parent = __t._M_end(); 01786 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 01787 } 01788 // No need to swap header's color as it does not change. 01789 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 01790 01791 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), 01792 __t._M_get_Node_allocator()); 01793 } 01794 01795 template<typename _Key, typename _Val, typename _KeyOfValue, 01796 typename _Compare, typename _Alloc> 01797 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01798 _Compare, _Alloc>::_Base_ptr, 01799 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01800 _Compare, _Alloc>::_Base_ptr> 01801 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01802 _M_get_insert_unique_pos(const key_type& __k) 01803 { 01804 typedef pair<_Base_ptr, _Base_ptr> _Res; 01805 _Link_type __x = _M_begin(); 01806 _Base_ptr __y = _M_end(); 01807 bool __comp = true; 01808 while (__x != 0) 01809 { 01810 __y = __x; 01811 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 01812 __x = __comp ? _S_left(__x) : _S_right(__x); 01813 } 01814 iterator __j = iterator(__y); 01815 if (__comp) 01816 { 01817 if (__j == begin()) 01818 return _Res(__x, __y); 01819 else 01820 --__j; 01821 } 01822 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 01823 return _Res(__x, __y); 01824 return _Res(__j._M_node, 0); 01825 } 01826 01827 template<typename _Key, typename _Val, typename _KeyOfValue, 01828 typename _Compare, typename _Alloc> 01829 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01830 _Compare, _Alloc>::_Base_ptr, 01831 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01832 _Compare, _Alloc>::_Base_ptr> 01833 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01834 _M_get_insert_equal_pos(const key_type& __k) 01835 { 01836 typedef pair<_Base_ptr, _Base_ptr> _Res; 01837 _Link_type __x = _M_begin(); 01838 _Base_ptr __y = _M_end(); 01839 while (__x != 0) 01840 { 01841 __y = __x; 01842 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 01843 _S_left(__x) : _S_right(__x); 01844 } 01845 return _Res(__x, __y); 01846 } 01847 01848 template<typename _Key, typename _Val, typename _KeyOfValue, 01849 typename _Compare, typename _Alloc> 01850 #if __cplusplus >= 201103L 01851 template<typename _Arg> 01852 #endif 01853 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01854 _Compare, _Alloc>::iterator, bool> 01855 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01856 #if __cplusplus >= 201103L 01857 _M_insert_unique(_Arg&& __v) 01858 #else 01859 _M_insert_unique(const _Val& __v) 01860 #endif 01861 { 01862 typedef pair<iterator, bool> _Res; 01863 pair<_Base_ptr, _Base_ptr> __res 01864 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 01865 01866 if (__res.second) 01867 { 01868 _Alloc_node __an(*this); 01869 return _Res(_M_insert_(__res.first, __res.second, 01870 _GLIBCXX_FORWARD(_Arg, __v), __an), 01871 true); 01872 } 01873 01874 return _Res(iterator(__res.first), false); 01875 } 01876 01877 template<typename _Key, typename _Val, typename _KeyOfValue, 01878 typename _Compare, typename _Alloc> 01879 #if __cplusplus >= 201103L 01880 template<typename _Arg> 01881 #endif 01882 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01883 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01884 #if __cplusplus >= 201103L 01885 _M_insert_equal(_Arg&& __v) 01886 #else 01887 _M_insert_equal(const _Val& __v) 01888 #endif 01889 { 01890 pair<_Base_ptr, _Base_ptr> __res 01891 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 01892 _Alloc_node __an(*this); 01893 return _M_insert_(__res.first, __res.second, 01894 _GLIBCXX_FORWARD(_Arg, __v), __an); 01895 } 01896 01897 template<typename _Key, typename _Val, typename _KeyOfValue, 01898 typename _Compare, typename _Alloc> 01899 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01900 _Compare, _Alloc>::_Base_ptr, 01901 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01902 _Compare, _Alloc>::_Base_ptr> 01903 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01904 _M_get_insert_hint_unique_pos(const_iterator __position, 01905 const key_type& __k) 01906 { 01907 iterator __pos = __position._M_const_cast(); 01908 typedef pair<_Base_ptr, _Base_ptr> _Res; 01909 01910 // end() 01911 if (__pos._M_node == _M_end()) 01912 { 01913 if (size() > 0 01914 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 01915 return _Res(0, _M_rightmost()); 01916 else 01917 return _M_get_insert_unique_pos(__k); 01918 } 01919 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 01920 { 01921 // First, try before... 01922 iterator __before = __pos; 01923 if (__pos._M_node == _M_leftmost()) // begin() 01924 return _Res(_M_leftmost(), _M_leftmost()); 01925 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 01926 { 01927 if (_S_right(__before._M_node) == 0) 01928 return _Res(0, __before._M_node); 01929 else 01930 return _Res(__pos._M_node, __pos._M_node); 01931 } 01932 else 01933 return _M_get_insert_unique_pos(__k); 01934 } 01935 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 01936 { 01937 // ... then try after. 01938 iterator __after = __pos; 01939 if (__pos._M_node == _M_rightmost()) 01940 return _Res(0, _M_rightmost()); 01941 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 01942 { 01943 if (_S_right(__pos._M_node) == 0) 01944 return _Res(0, __pos._M_node); 01945 else 01946 return _Res(__after._M_node, __after._M_node); 01947 } 01948 else 01949 return _M_get_insert_unique_pos(__k); 01950 } 01951 else 01952 // Equivalent keys. 01953 return _Res(__pos._M_node, 0); 01954 } 01955 01956 template<typename _Key, typename _Val, typename _KeyOfValue, 01957 typename _Compare, typename _Alloc> 01958 #if __cplusplus >= 201103L 01959 template<typename _Arg, typename _NodeGen> 01960 #else 01961 template<typename _NodeGen> 01962 #endif 01963 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01964 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01965 _M_insert_unique_(const_iterator __position, 01966 #if __cplusplus >= 201103L 01967 _Arg&& __v, 01968 #else 01969 const _Val& __v, 01970 #endif 01971 _NodeGen& __node_gen) 01972 { 01973 pair<_Base_ptr, _Base_ptr> __res 01974 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 01975 01976 if (__res.second) 01977 return _M_insert_(__res.first, __res.second, 01978 _GLIBCXX_FORWARD(_Arg, __v), 01979 __node_gen); 01980 return iterator(__res.first); 01981 } 01982 01983 template<typename _Key, typename _Val, typename _KeyOfValue, 01984 typename _Compare, typename _Alloc> 01985 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01986 _Compare, _Alloc>::_Base_ptr, 01987 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01988 _Compare, _Alloc>::_Base_ptr> 01989 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01990 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 01991 { 01992 iterator __pos = __position._M_const_cast(); 01993 typedef pair<_Base_ptr, _Base_ptr> _Res; 01994 01995 // end() 01996 if (__pos._M_node == _M_end()) 01997 { 01998 if (size() > 0 01999 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 02000 return _Res(0, _M_rightmost()); 02001 else 02002 return _M_get_insert_equal_pos(__k); 02003 } 02004 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 02005 { 02006 // First, try before... 02007 iterator __before = __pos; 02008 if (__pos._M_node == _M_leftmost()) // begin() 02009 return _Res(_M_leftmost(), _M_leftmost()); 02010 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 02011 { 02012 if (_S_right(__before._M_node) == 0) 02013 return _Res(0, __before._M_node); 02014 else 02015 return _Res(__pos._M_node, __pos._M_node); 02016 } 02017 else 02018 return _M_get_insert_equal_pos(__k); 02019 } 02020 else 02021 { 02022 // ... then try after. 02023 iterator __after = __pos; 02024 if (__pos._M_node == _M_rightmost()) 02025 return _Res(0, _M_rightmost()); 02026 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 02027 { 02028 if (_S_right(__pos._M_node) == 0) 02029 return _Res(0, __pos._M_node); 02030 else 02031 return _Res(__after._M_node, __after._M_node); 02032 } 02033 else 02034 return _Res(0, 0); 02035 } 02036 } 02037 02038 template<typename _Key, typename _Val, typename _KeyOfValue, 02039 typename _Compare, typename _Alloc> 02040 #if __cplusplus >= 201103L 02041 template<typename _Arg, typename _NodeGen> 02042 #else 02043 template<typename _NodeGen> 02044 #endif 02045 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02046 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02047 _M_insert_equal_(const_iterator __position, 02048 #if __cplusplus >= 201103L 02049 _Arg&& __v, 02050 #else 02051 const _Val& __v, 02052 #endif 02053 _NodeGen& __node_gen) 02054 { 02055 pair<_Base_ptr, _Base_ptr> __res 02056 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 02057 02058 if (__res.second) 02059 return _M_insert_(__res.first, __res.second, 02060 _GLIBCXX_FORWARD(_Arg, __v), 02061 __node_gen); 02062 02063 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 02064 } 02065 02066 #if __cplusplus >= 201103L 02067 template<typename _Key, typename _Val, typename _KeyOfValue, 02068 typename _Compare, typename _Alloc> 02069 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02070 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02071 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 02072 { 02073 bool __insert_left = (__x != 0 || __p == _M_end() 02074 || _M_impl._M_key_compare(_S_key(__z), 02075 _S_key(__p))); 02076 02077 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 02078 this->_M_impl._M_header); 02079 ++_M_impl._M_node_count; 02080 return iterator(__z); 02081 } 02082 02083 template<typename _Key, typename _Val, typename _KeyOfValue, 02084 typename _Compare, typename _Alloc> 02085 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02086 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02087 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 02088 { 02089 bool __insert_left = (__p == _M_end() 02090 || !_M_impl._M_key_compare(_S_key(__p), 02091 _S_key(__z))); 02092 02093 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 02094 this->_M_impl._M_header); 02095 ++_M_impl._M_node_count; 02096 return iterator(__z); 02097 } 02098 02099 template<typename _Key, typename _Val, typename _KeyOfValue, 02100 typename _Compare, typename _Alloc> 02101 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02102 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02103 _M_insert_equal_lower_node(_Link_type __z) 02104 { 02105 _Link_type __x = _M_begin(); 02106 _Base_ptr __y = _M_end(); 02107 while (__x != 0) 02108 { 02109 __y = __x; 02110 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 02111 _S_left(__x) : _S_right(__x); 02112 } 02113 return _M_insert_lower_node(__y, __z); 02114 } 02115 02116 template<typename _Key, typename _Val, typename _KeyOfValue, 02117 typename _Compare, typename _Alloc> 02118 template<typename... _Args> 02119 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02120 _Compare, _Alloc>::iterator, bool> 02121 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02122 _M_emplace_unique(_Args&&... __args) 02123 { 02124 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02125 02126 __try 02127 { 02128 typedef pair<iterator, bool> _Res; 02129 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 02130 if (__res.second) 02131 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 02132 02133 _M_drop_node(__z); 02134 return _Res(iterator(__res.first), false); 02135 } 02136 __catch(...) 02137 { 02138 _M_drop_node(__z); 02139 __throw_exception_again; 02140 } 02141 } 02142 02143 template<typename _Key, typename _Val, typename _KeyOfValue, 02144 typename _Compare, typename _Alloc> 02145 template<typename... _Args> 02146 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02147 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02148 _M_emplace_equal(_Args&&... __args) 02149 { 02150 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02151 02152 __try 02153 { 02154 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 02155 return _M_insert_node(__res.first, __res.second, __z); 02156 } 02157 __catch(...) 02158 { 02159 _M_drop_node(__z); 02160 __throw_exception_again; 02161 } 02162 } 02163 02164 template<typename _Key, typename _Val, typename _KeyOfValue, 02165 typename _Compare, typename _Alloc> 02166 template<typename... _Args> 02167 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02168 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02169 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 02170 { 02171 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02172 02173 __try 02174 { 02175 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 02176 02177 if (__res.second) 02178 return _M_insert_node(__res.first, __res.second, __z); 02179 02180 _M_drop_node(__z); 02181 return iterator(__res.first); 02182 } 02183 __catch(...) 02184 { 02185 _M_drop_node(__z); 02186 __throw_exception_again; 02187 } 02188 } 02189 02190 template<typename _Key, typename _Val, typename _KeyOfValue, 02191 typename _Compare, typename _Alloc> 02192 template<typename... _Args> 02193 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02194 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02195 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 02196 { 02197 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02198 02199 __try 02200 { 02201 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 02202 02203 if (__res.second) 02204 return _M_insert_node(__res.first, __res.second, __z); 02205 02206 return _M_insert_equal_lower_node(__z); 02207 } 02208 __catch(...) 02209 { 02210 _M_drop_node(__z); 02211 __throw_exception_again; 02212 } 02213 } 02214 #endif 02215 02216 template<typename _Key, typename _Val, typename _KoV, 02217 typename _Cmp, typename _Alloc> 02218 template<class _II> 02219 void 02220 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 02221 _M_insert_unique(_II __first, _II __last) 02222 { 02223 _Alloc_node __an(*this); 02224 for (; __first != __last; ++__first) 02225 _M_insert_unique_(end(), *__first, __an); 02226 } 02227 02228 template<typename _Key, typename _Val, typename _KoV, 02229 typename _Cmp, typename _Alloc> 02230 template<class _II> 02231 void 02232 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 02233 _M_insert_equal(_II __first, _II __last) 02234 { 02235 _Alloc_node __an(*this); 02236 for (; __first != __last; ++__first) 02237 _M_insert_equal_(end(), *__first, __an); 02238 } 02239 02240 template<typename _Key, typename _Val, typename _KeyOfValue, 02241 typename _Compare, typename _Alloc> 02242 void 02243 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02244 _M_erase_aux(const_iterator __position) 02245 { 02246 _Link_type __y = 02247 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 02248 (const_cast<_Base_ptr>(__position._M_node), 02249 this->_M_impl._M_header)); 02250 _M_drop_node(__y); 02251 --_M_impl._M_node_count; 02252 } 02253 02254 template<typename _Key, typename _Val, typename _KeyOfValue, 02255 typename _Compare, typename _Alloc> 02256 void 02257 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02258 _M_erase_aux(const_iterator __first, const_iterator __last) 02259 { 02260 if (__first == begin() && __last == end()) 02261 clear(); 02262 else 02263 while (__first != __last) 02264 erase(__first++); 02265 } 02266 02267 template<typename _Key, typename _Val, typename _KeyOfValue, 02268 typename _Compare, typename _Alloc> 02269 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 02270 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02271 erase(const _Key& __x) 02272 { 02273 pair<iterator, iterator> __p = equal_range(__x); 02274 const size_type __old_size = size(); 02275 erase(__p.first, __p.second); 02276 return __old_size - size(); 02277 } 02278 02279 template<typename _Key, typename _Val, typename _KeyOfValue, 02280 typename _Compare, typename _Alloc> 02281 void 02282 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02283 erase(const _Key* __first, const _Key* __last) 02284 { 02285 while (__first != __last) 02286 erase(*__first++); 02287 } 02288 02289 template<typename _Key, typename _Val, typename _KeyOfValue, 02290 typename _Compare, typename _Alloc> 02291 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02292 _Compare, _Alloc>::iterator 02293 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02294 find(const _Key& __k) 02295 { 02296 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 02297 return (__j == end() 02298 || _M_impl._M_key_compare(__k, 02299 _S_key(__j._M_node))) ? end() : __j; 02300 } 02301 02302 template<typename _Key, typename _Val, typename _KeyOfValue, 02303 typename _Compare, typename _Alloc> 02304 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02305 _Compare, _Alloc>::const_iterator 02306 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02307 find(const _Key& __k) const 02308 { 02309 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 02310 return (__j == end() 02311 || _M_impl._M_key_compare(__k, 02312 _S_key(__j._M_node))) ? end() : __j; 02313 } 02314 02315 template<typename _Key, typename _Val, typename _KeyOfValue, 02316 typename _Compare, typename _Alloc> 02317 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 02318 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02319 count(const _Key& __k) const 02320 { 02321 pair<const_iterator, const_iterator> __p = equal_range(__k); 02322 const size_type __n = std::distance(__p.first, __p.second); 02323 return __n; 02324 } 02325 02326 _GLIBCXX_PURE unsigned int 02327 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 02328 const _Rb_tree_node_base* __root) throw (); 02329 02330 template<typename _Key, typename _Val, typename _KeyOfValue, 02331 typename _Compare, typename _Alloc> 02332 bool 02333 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 02334 { 02335 if (_M_impl._M_node_count == 0 || begin() == end()) 02336 return _M_impl._M_node_count == 0 && begin() == end() 02337 && this->_M_impl._M_header._M_left == _M_end() 02338 && this->_M_impl._M_header._M_right == _M_end(); 02339 02340 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 02341 for (const_iterator __it = begin(); __it != end(); ++__it) 02342 { 02343 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 02344 _Const_Link_type __L = _S_left(__x); 02345 _Const_Link_type __R = _S_right(__x); 02346 02347 if (__x->_M_color == _S_red) 02348 if ((__L && __L->_M_color == _S_red) 02349 || (__R && __R->_M_color == _S_red)) 02350 return false; 02351 02352 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 02353 return false; 02354 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 02355 return false; 02356 02357 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 02358 return false; 02359 } 02360 02361 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 02362 return false; 02363 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 02364 return false; 02365 return true; 02366 } 02367 02368 _GLIBCXX_END_NAMESPACE_VERSION 02369 } // namespace 02370 02371 #endif