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 01268 // Move assignment from container with equal allocator. 01269 void 01270 _M_move_assign(_Rb_tree&, std::true_type); 01271 01272 // Move assignment from container with possibly non-equal allocator, 01273 // which might result in a copy not a move. 01274 void 01275 _M_move_assign(_Rb_tree&, std::false_type); 01276 #endif 01277 }; 01278 01279 template<typename _Key, typename _Val, typename _KeyOfValue, 01280 typename _Compare, typename _Alloc> 01281 inline bool 01282 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01283 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01284 { 01285 return __x.size() == __y.size() 01286 && std::equal(__x.begin(), __x.end(), __y.begin()); 01287 } 01288 01289 template<typename _Key, typename _Val, typename _KeyOfValue, 01290 typename _Compare, typename _Alloc> 01291 inline bool 01292 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01293 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01294 { 01295 return std::lexicographical_compare(__x.begin(), __x.end(), 01296 __y.begin(), __y.end()); 01297 } 01298 01299 template<typename _Key, typename _Val, typename _KeyOfValue, 01300 typename _Compare, typename _Alloc> 01301 inline bool 01302 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01303 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01304 { return !(__x == __y); } 01305 01306 template<typename _Key, typename _Val, typename _KeyOfValue, 01307 typename _Compare, typename _Alloc> 01308 inline bool 01309 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01310 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01311 { return __y < __x; } 01312 01313 template<typename _Key, typename _Val, typename _KeyOfValue, 01314 typename _Compare, typename _Alloc> 01315 inline bool 01316 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01317 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01318 { return !(__y < __x); } 01319 01320 template<typename _Key, typename _Val, typename _KeyOfValue, 01321 typename _Compare, typename _Alloc> 01322 inline bool 01323 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01324 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01325 { return !(__x < __y); } 01326 01327 template<typename _Key, typename _Val, typename _KeyOfValue, 01328 typename _Compare, typename _Alloc> 01329 inline void 01330 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01331 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01332 { __x.swap(__y); } 01333 01334 #if __cplusplus >= 201103L 01335 template<typename _Key, typename _Val, typename _KeyOfValue, 01336 typename _Compare, typename _Alloc> 01337 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01338 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) 01339 : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) 01340 { 01341 using __eq = typename _Alloc_traits::is_always_equal; 01342 if (__x._M_root() != nullptr) 01343 _M_move_data(__x, __eq()); 01344 } 01345 01346 template<typename _Key, typename _Val, typename _KeyOfValue, 01347 typename _Compare, typename _Alloc> 01348 void 01349 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01350 _M_move_data(_Rb_tree& __x, std::true_type) 01351 { 01352 _M_root() = __x._M_root(); 01353 _M_leftmost() = __x._M_leftmost(); 01354 _M_rightmost() = __x._M_rightmost(); 01355 _M_root()->_M_parent = _M_end(); 01356 01357 __x._M_root() = 0; 01358 __x._M_leftmost() = __x._M_end(); 01359 __x._M_rightmost() = __x._M_end(); 01360 01361 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 01362 __x._M_impl._M_node_count = 0; 01363 } 01364 01365 template<typename _Key, typename _Val, typename _KeyOfValue, 01366 typename _Compare, typename _Alloc> 01367 void 01368 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01369 _M_move_data(_Rb_tree& __x, std::false_type) 01370 { 01371 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 01372 _M_move_data(__x, std::true_type()); 01373 else 01374 { 01375 _Alloc_node __an(*this); 01376 auto __lbd = 01377 [&__an](const value_type& __cval) 01378 { 01379 auto& __val = const_cast<value_type&>(__cval); 01380 return __an(std::move_if_noexcept(__val)); 01381 }; 01382 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); 01383 _M_leftmost() = _S_minimum(_M_root()); 01384 _M_rightmost() = _S_maximum(_M_root()); 01385 _M_impl._M_node_count = __x._M_impl._M_node_count; 01386 } 01387 } 01388 01389 template<typename _Key, typename _Val, typename _KeyOfValue, 01390 typename _Compare, typename _Alloc> 01391 inline void 01392 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01393 _M_move_assign(_Rb_tree& __x, true_type) 01394 { 01395 clear(); 01396 if (__x._M_root() != nullptr) 01397 _M_move_data(__x, std::true_type()); 01398 std::__alloc_on_move(_M_get_Node_allocator(), 01399 __x._M_get_Node_allocator()); 01400 } 01401 01402 template<typename _Key, typename _Val, typename _KeyOfValue, 01403 typename _Compare, typename _Alloc> 01404 void 01405 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01406 _M_move_assign(_Rb_tree& __x, false_type) 01407 { 01408 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 01409 return _M_move_assign(__x, true_type{}); 01410 01411 // Try to move each node reusing existing nodes and copying __x nodes 01412 // structure. 01413 _Reuse_or_alloc_node __roan(*this); 01414 _M_impl._M_reset(); 01415 if (__x._M_root() != nullptr) 01416 { 01417 auto __lbd = 01418 [&__roan](const value_type& __cval) 01419 { 01420 auto& __val = const_cast<value_type&>(__cval); 01421 return __roan(std::move_if_noexcept(__val)); 01422 }; 01423 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); 01424 _M_leftmost() = _S_minimum(_M_root()); 01425 _M_rightmost() = _S_maximum(_M_root()); 01426 _M_impl._M_node_count = __x._M_impl._M_node_count; 01427 __x.clear(); 01428 } 01429 } 01430 01431 template<typename _Key, typename _Val, typename _KeyOfValue, 01432 typename _Compare, typename _Alloc> 01433 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 01434 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01435 operator=(_Rb_tree&& __x) 01436 noexcept(_Alloc_traits::_S_nothrow_move() 01437 && is_nothrow_move_assignable<_Compare>::value) 01438 { 01439 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 01440 constexpr bool __move_storage = 01441 _Alloc_traits::_S_propagate_on_move_assign() 01442 || _Alloc_traits::_S_always_equal(); 01443 _M_move_assign(__x, __bool_constant<__move_storage>()); 01444 return *this; 01445 } 01446 01447 template<typename _Key, typename _Val, typename _KeyOfValue, 01448 typename _Compare, typename _Alloc> 01449 template<typename _Iterator> 01450 void 01451 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01452 _M_assign_unique(_Iterator __first, _Iterator __last) 01453 { 01454 _Reuse_or_alloc_node __roan(*this); 01455 _M_impl._M_reset(); 01456 for (; __first != __last; ++__first) 01457 _M_insert_unique_(end(), *__first, __roan); 01458 } 01459 01460 template<typename _Key, typename _Val, typename _KeyOfValue, 01461 typename _Compare, typename _Alloc> 01462 template<typename _Iterator> 01463 void 01464 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01465 _M_assign_equal(_Iterator __first, _Iterator __last) 01466 { 01467 _Reuse_or_alloc_node __roan(*this); 01468 _M_impl._M_reset(); 01469 for (; __first != __last; ++__first) 01470 _M_insert_equal_(end(), *__first, __roan); 01471 } 01472 #endif 01473 01474 template<typename _Key, typename _Val, typename _KeyOfValue, 01475 typename _Compare, typename _Alloc> 01476 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 01477 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01478 operator=(const _Rb_tree& __x) 01479 { 01480 if (this != &__x) 01481 { 01482 // Note that _Key may be a constant type. 01483 #if __cplusplus >= 201103L 01484 if (_Alloc_traits::_S_propagate_on_copy_assign()) 01485 { 01486 auto& __this_alloc = this->_M_get_Node_allocator(); 01487 auto& __that_alloc = __x._M_get_Node_allocator(); 01488 if (!_Alloc_traits::_S_always_equal() 01489 && __this_alloc != __that_alloc) 01490 { 01491 // Replacement allocator cannot free existing storage, we need 01492 // to erase nodes first. 01493 clear(); 01494 std::__alloc_on_copy(__this_alloc, __that_alloc); 01495 } 01496 } 01497 #endif 01498 01499 _Reuse_or_alloc_node __roan(*this); 01500 _M_impl._M_reset(); 01501 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 01502 if (__x._M_root() != 0) 01503 { 01504 _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan); 01505 _M_leftmost() = _S_minimum(_M_root()); 01506 _M_rightmost() = _S_maximum(_M_root()); 01507 _M_impl._M_node_count = __x._M_impl._M_node_count; 01508 } 01509 } 01510 01511 return *this; 01512 } 01513 01514 template<typename _Key, typename _Val, typename _KeyOfValue, 01515 typename _Compare, typename _Alloc> 01516 #if __cplusplus >= 201103L 01517 template<typename _Arg, typename _NodeGen> 01518 #else 01519 template<typename _NodeGen> 01520 #endif 01521 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01522 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01523 _M_insert_(_Base_ptr __x, _Base_ptr __p, 01524 #if __cplusplus >= 201103L 01525 _Arg&& __v, 01526 #else 01527 const _Val& __v, 01528 #endif 01529 _NodeGen& __node_gen) 01530 { 01531 bool __insert_left = (__x != 0 || __p == _M_end() 01532 || _M_impl._M_key_compare(_KeyOfValue()(__v), 01533 _S_key(__p))); 01534 01535 _Link_type __z = __node_gen(_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_lower(_Base_ptr __p, _Arg&& __v) 01552 #else 01553 _M_insert_lower(_Base_ptr __p, const _Val& __v) 01554 #endif 01555 { 01556 bool __insert_left = (__p == _M_end() 01557 || !_M_impl._M_key_compare(_S_key(__p), 01558 _KeyOfValue()(__v))); 01559 01560 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 01561 01562 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01563 this->_M_impl._M_header); 01564 ++_M_impl._M_node_count; 01565 return iterator(__z); 01566 } 01567 01568 template<typename _Key, typename _Val, typename _KeyOfValue, 01569 typename _Compare, typename _Alloc> 01570 #if __cplusplus >= 201103L 01571 template<typename _Arg> 01572 #endif 01573 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01574 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01575 #if __cplusplus >= 201103L 01576 _M_insert_equal_lower(_Arg&& __v) 01577 #else 01578 _M_insert_equal_lower(const _Val& __v) 01579 #endif 01580 { 01581 _Link_type __x = _M_begin(); 01582 _Base_ptr __y = _M_end(); 01583 while (__x != 0) 01584 { 01585 __y = __x; 01586 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 01587 _S_left(__x) : _S_right(__x); 01588 } 01589 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 01590 } 01591 01592 template<typename _Key, typename _Val, typename _KoV, 01593 typename _Compare, typename _Alloc> 01594 template<typename _NodeGen> 01595 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 01596 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 01597 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) 01598 { 01599 // Structural copy. __x and __p must be non-null. 01600 _Link_type __top = _M_clone_node(__x, __node_gen); 01601 __top->_M_parent = __p; 01602 01603 __try 01604 { 01605 if (__x->_M_right) 01606 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen); 01607 __p = __top; 01608 __x = _S_left(__x); 01609 01610 while (__x != 0) 01611 { 01612 _Link_type __y = _M_clone_node(__x, __node_gen); 01613 __p->_M_left = __y; 01614 __y->_M_parent = __p; 01615 if (__x->_M_right) 01616 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen); 01617 __p = __y; 01618 __x = _S_left(__x); 01619 } 01620 } 01621 __catch(...) 01622 { 01623 _M_erase(__top); 01624 __throw_exception_again; 01625 } 01626 return __top; 01627 } 01628 01629 template<typename _Key, typename _Val, typename _KeyOfValue, 01630 typename _Compare, typename _Alloc> 01631 void 01632 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01633 _M_erase(_Link_type __x) 01634 { 01635 // Erase without rebalancing. 01636 while (__x != 0) 01637 { 01638 _M_erase(_S_right(__x)); 01639 _Link_type __y = _S_left(__x); 01640 _M_drop_node(__x); 01641 __x = __y; 01642 } 01643 } 01644 01645 template<typename _Key, typename _Val, typename _KeyOfValue, 01646 typename _Compare, typename _Alloc> 01647 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01648 _Compare, _Alloc>::iterator 01649 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01650 _M_lower_bound(_Link_type __x, _Base_ptr __y, 01651 const _Key& __k) 01652 { 01653 while (__x != 0) 01654 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01655 __y = __x, __x = _S_left(__x); 01656 else 01657 __x = _S_right(__x); 01658 return iterator(__y); 01659 } 01660 01661 template<typename _Key, typename _Val, typename _KeyOfValue, 01662 typename _Compare, typename _Alloc> 01663 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01664 _Compare, _Alloc>::const_iterator 01665 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01666 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, 01667 const _Key& __k) const 01668 { 01669 while (__x != 0) 01670 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01671 __y = __x, __x = _S_left(__x); 01672 else 01673 __x = _S_right(__x); 01674 return const_iterator(__y); 01675 } 01676 01677 template<typename _Key, typename _Val, typename _KeyOfValue, 01678 typename _Compare, typename _Alloc> 01679 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01680 _Compare, _Alloc>::iterator 01681 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01682 _M_upper_bound(_Link_type __x, _Base_ptr __y, 01683 const _Key& __k) 01684 { 01685 while (__x != 0) 01686 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01687 __y = __x, __x = _S_left(__x); 01688 else 01689 __x = _S_right(__x); 01690 return iterator(__y); 01691 } 01692 01693 template<typename _Key, typename _Val, typename _KeyOfValue, 01694 typename _Compare, typename _Alloc> 01695 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01696 _Compare, _Alloc>::const_iterator 01697 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01698 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, 01699 const _Key& __k) const 01700 { 01701 while (__x != 0) 01702 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01703 __y = __x, __x = _S_left(__x); 01704 else 01705 __x = _S_right(__x); 01706 return const_iterator(__y); 01707 } 01708 01709 template<typename _Key, typename _Val, typename _KeyOfValue, 01710 typename _Compare, typename _Alloc> 01711 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01712 _Compare, _Alloc>::iterator, 01713 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01714 _Compare, _Alloc>::iterator> 01715 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01716 equal_range(const _Key& __k) 01717 { 01718 _Link_type __x = _M_begin(); 01719 _Base_ptr __y = _M_end(); 01720 while (__x != 0) 01721 { 01722 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01723 __x = _S_right(__x); 01724 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01725 __y = __x, __x = _S_left(__x); 01726 else 01727 { 01728 _Link_type __xu(__x); 01729 _Base_ptr __yu(__y); 01730 __y = __x, __x = _S_left(__x); 01731 __xu = _S_right(__xu); 01732 return pair<iterator, 01733 iterator>(_M_lower_bound(__x, __y, __k), 01734 _M_upper_bound(__xu, __yu, __k)); 01735 } 01736 } 01737 return pair<iterator, iterator>(iterator(__y), 01738 iterator(__y)); 01739 } 01740 01741 template<typename _Key, typename _Val, typename _KeyOfValue, 01742 typename _Compare, typename _Alloc> 01743 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01744 _Compare, _Alloc>::const_iterator, 01745 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01746 _Compare, _Alloc>::const_iterator> 01747 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01748 equal_range(const _Key& __k) const 01749 { 01750 _Const_Link_type __x = _M_begin(); 01751 _Const_Base_ptr __y = _M_end(); 01752 while (__x != 0) 01753 { 01754 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01755 __x = _S_right(__x); 01756 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01757 __y = __x, __x = _S_left(__x); 01758 else 01759 { 01760 _Const_Link_type __xu(__x); 01761 _Const_Base_ptr __yu(__y); 01762 __y = __x, __x = _S_left(__x); 01763 __xu = _S_right(__xu); 01764 return pair<const_iterator, 01765 const_iterator>(_M_lower_bound(__x, __y, __k), 01766 _M_upper_bound(__xu, __yu, __k)); 01767 } 01768 } 01769 return pair<const_iterator, const_iterator>(const_iterator(__y), 01770 const_iterator(__y)); 01771 } 01772 01773 template<typename _Key, typename _Val, typename _KeyOfValue, 01774 typename _Compare, typename _Alloc> 01775 void 01776 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01777 swap(_Rb_tree& __t) 01778 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 01779 { 01780 if (_M_root() == 0) 01781 { 01782 if (__t._M_root() != 0) 01783 { 01784 _M_root() = __t._M_root(); 01785 _M_leftmost() = __t._M_leftmost(); 01786 _M_rightmost() = __t._M_rightmost(); 01787 _M_root()->_M_parent = _M_end(); 01788 _M_impl._M_node_count = __t._M_impl._M_node_count; 01789 01790 __t._M_impl._M_reset(); 01791 } 01792 } 01793 else if (__t._M_root() == 0) 01794 { 01795 __t._M_root() = _M_root(); 01796 __t._M_leftmost() = _M_leftmost(); 01797 __t._M_rightmost() = _M_rightmost(); 01798 __t._M_root()->_M_parent = __t._M_end(); 01799 __t._M_impl._M_node_count = _M_impl._M_node_count; 01800 01801 _M_impl._M_reset(); 01802 } 01803 else 01804 { 01805 std::swap(_M_root(),__t._M_root()); 01806 std::swap(_M_leftmost(),__t._M_leftmost()); 01807 std::swap(_M_rightmost(),__t._M_rightmost()); 01808 01809 _M_root()->_M_parent = _M_end(); 01810 __t._M_root()->_M_parent = __t._M_end(); 01811 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 01812 } 01813 // No need to swap header's color as it does not change. 01814 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 01815 01816 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), 01817 __t._M_get_Node_allocator()); 01818 } 01819 01820 template<typename _Key, typename _Val, typename _KeyOfValue, 01821 typename _Compare, typename _Alloc> 01822 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01823 _Compare, _Alloc>::_Base_ptr, 01824 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01825 _Compare, _Alloc>::_Base_ptr> 01826 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01827 _M_get_insert_unique_pos(const key_type& __k) 01828 { 01829 typedef pair<_Base_ptr, _Base_ptr> _Res; 01830 _Link_type __x = _M_begin(); 01831 _Base_ptr __y = _M_end(); 01832 bool __comp = true; 01833 while (__x != 0) 01834 { 01835 __y = __x; 01836 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 01837 __x = __comp ? _S_left(__x) : _S_right(__x); 01838 } 01839 iterator __j = iterator(__y); 01840 if (__comp) 01841 { 01842 if (__j == begin()) 01843 return _Res(__x, __y); 01844 else 01845 --__j; 01846 } 01847 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 01848 return _Res(__x, __y); 01849 return _Res(__j._M_node, 0); 01850 } 01851 01852 template<typename _Key, typename _Val, typename _KeyOfValue, 01853 typename _Compare, typename _Alloc> 01854 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01855 _Compare, _Alloc>::_Base_ptr, 01856 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01857 _Compare, _Alloc>::_Base_ptr> 01858 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01859 _M_get_insert_equal_pos(const key_type& __k) 01860 { 01861 typedef pair<_Base_ptr, _Base_ptr> _Res; 01862 _Link_type __x = _M_begin(); 01863 _Base_ptr __y = _M_end(); 01864 while (__x != 0) 01865 { 01866 __y = __x; 01867 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 01868 _S_left(__x) : _S_right(__x); 01869 } 01870 return _Res(__x, __y); 01871 } 01872 01873 template<typename _Key, typename _Val, typename _KeyOfValue, 01874 typename _Compare, typename _Alloc> 01875 #if __cplusplus >= 201103L 01876 template<typename _Arg> 01877 #endif 01878 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01879 _Compare, _Alloc>::iterator, bool> 01880 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01881 #if __cplusplus >= 201103L 01882 _M_insert_unique(_Arg&& __v) 01883 #else 01884 _M_insert_unique(const _Val& __v) 01885 #endif 01886 { 01887 typedef pair<iterator, bool> _Res; 01888 pair<_Base_ptr, _Base_ptr> __res 01889 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 01890 01891 if (__res.second) 01892 { 01893 _Alloc_node __an(*this); 01894 return _Res(_M_insert_(__res.first, __res.second, 01895 _GLIBCXX_FORWARD(_Arg, __v), __an), 01896 true); 01897 } 01898 01899 return _Res(iterator(__res.first), false); 01900 } 01901 01902 template<typename _Key, typename _Val, typename _KeyOfValue, 01903 typename _Compare, typename _Alloc> 01904 #if __cplusplus >= 201103L 01905 template<typename _Arg> 01906 #endif 01907 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01908 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01909 #if __cplusplus >= 201103L 01910 _M_insert_equal(_Arg&& __v) 01911 #else 01912 _M_insert_equal(const _Val& __v) 01913 #endif 01914 { 01915 pair<_Base_ptr, _Base_ptr> __res 01916 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 01917 _Alloc_node __an(*this); 01918 return _M_insert_(__res.first, __res.second, 01919 _GLIBCXX_FORWARD(_Arg, __v), __an); 01920 } 01921 01922 template<typename _Key, typename _Val, typename _KeyOfValue, 01923 typename _Compare, typename _Alloc> 01924 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01925 _Compare, _Alloc>::_Base_ptr, 01926 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01927 _Compare, _Alloc>::_Base_ptr> 01928 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01929 _M_get_insert_hint_unique_pos(const_iterator __position, 01930 const key_type& __k) 01931 { 01932 iterator __pos = __position._M_const_cast(); 01933 typedef pair<_Base_ptr, _Base_ptr> _Res; 01934 01935 // end() 01936 if (__pos._M_node == _M_end()) 01937 { 01938 if (size() > 0 01939 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 01940 return _Res(0, _M_rightmost()); 01941 else 01942 return _M_get_insert_unique_pos(__k); 01943 } 01944 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 01945 { 01946 // First, try before... 01947 iterator __before = __pos; 01948 if (__pos._M_node == _M_leftmost()) // begin() 01949 return _Res(_M_leftmost(), _M_leftmost()); 01950 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 01951 { 01952 if (_S_right(__before._M_node) == 0) 01953 return _Res(0, __before._M_node); 01954 else 01955 return _Res(__pos._M_node, __pos._M_node); 01956 } 01957 else 01958 return _M_get_insert_unique_pos(__k); 01959 } 01960 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 01961 { 01962 // ... then try after. 01963 iterator __after = __pos; 01964 if (__pos._M_node == _M_rightmost()) 01965 return _Res(0, _M_rightmost()); 01966 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 01967 { 01968 if (_S_right(__pos._M_node) == 0) 01969 return _Res(0, __pos._M_node); 01970 else 01971 return _Res(__after._M_node, __after._M_node); 01972 } 01973 else 01974 return _M_get_insert_unique_pos(__k); 01975 } 01976 else 01977 // Equivalent keys. 01978 return _Res(__pos._M_node, 0); 01979 } 01980 01981 template<typename _Key, typename _Val, typename _KeyOfValue, 01982 typename _Compare, typename _Alloc> 01983 #if __cplusplus >= 201103L 01984 template<typename _Arg, typename _NodeGen> 01985 #else 01986 template<typename _NodeGen> 01987 #endif 01988 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01989 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01990 _M_insert_unique_(const_iterator __position, 01991 #if __cplusplus >= 201103L 01992 _Arg&& __v, 01993 #else 01994 const _Val& __v, 01995 #endif 01996 _NodeGen& __node_gen) 01997 { 01998 pair<_Base_ptr, _Base_ptr> __res 01999 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 02000 02001 if (__res.second) 02002 return _M_insert_(__res.first, __res.second, 02003 _GLIBCXX_FORWARD(_Arg, __v), 02004 __node_gen); 02005 return iterator(__res.first); 02006 } 02007 02008 template<typename _Key, typename _Val, typename _KeyOfValue, 02009 typename _Compare, typename _Alloc> 02010 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02011 _Compare, _Alloc>::_Base_ptr, 02012 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02013 _Compare, _Alloc>::_Base_ptr> 02014 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02015 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 02016 { 02017 iterator __pos = __position._M_const_cast(); 02018 typedef pair<_Base_ptr, _Base_ptr> _Res; 02019 02020 // end() 02021 if (__pos._M_node == _M_end()) 02022 { 02023 if (size() > 0 02024 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 02025 return _Res(0, _M_rightmost()); 02026 else 02027 return _M_get_insert_equal_pos(__k); 02028 } 02029 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 02030 { 02031 // First, try before... 02032 iterator __before = __pos; 02033 if (__pos._M_node == _M_leftmost()) // begin() 02034 return _Res(_M_leftmost(), _M_leftmost()); 02035 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 02036 { 02037 if (_S_right(__before._M_node) == 0) 02038 return _Res(0, __before._M_node); 02039 else 02040 return _Res(__pos._M_node, __pos._M_node); 02041 } 02042 else 02043 return _M_get_insert_equal_pos(__k); 02044 } 02045 else 02046 { 02047 // ... then try after. 02048 iterator __after = __pos; 02049 if (__pos._M_node == _M_rightmost()) 02050 return _Res(0, _M_rightmost()); 02051 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 02052 { 02053 if (_S_right(__pos._M_node) == 0) 02054 return _Res(0, __pos._M_node); 02055 else 02056 return _Res(__after._M_node, __after._M_node); 02057 } 02058 else 02059 return _Res(0, 0); 02060 } 02061 } 02062 02063 template<typename _Key, typename _Val, typename _KeyOfValue, 02064 typename _Compare, typename _Alloc> 02065 #if __cplusplus >= 201103L 02066 template<typename _Arg, typename _NodeGen> 02067 #else 02068 template<typename _NodeGen> 02069 #endif 02070 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02071 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02072 _M_insert_equal_(const_iterator __position, 02073 #if __cplusplus >= 201103L 02074 _Arg&& __v, 02075 #else 02076 const _Val& __v, 02077 #endif 02078 _NodeGen& __node_gen) 02079 { 02080 pair<_Base_ptr, _Base_ptr> __res 02081 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 02082 02083 if (__res.second) 02084 return _M_insert_(__res.first, __res.second, 02085 _GLIBCXX_FORWARD(_Arg, __v), 02086 __node_gen); 02087 02088 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 02089 } 02090 02091 #if __cplusplus >= 201103L 02092 template<typename _Key, typename _Val, typename _KeyOfValue, 02093 typename _Compare, typename _Alloc> 02094 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02095 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02096 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 02097 { 02098 bool __insert_left = (__x != 0 || __p == _M_end() 02099 || _M_impl._M_key_compare(_S_key(__z), 02100 _S_key(__p))); 02101 02102 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 02103 this->_M_impl._M_header); 02104 ++_M_impl._M_node_count; 02105 return iterator(__z); 02106 } 02107 02108 template<typename _Key, typename _Val, typename _KeyOfValue, 02109 typename _Compare, typename _Alloc> 02110 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02111 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02112 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 02113 { 02114 bool __insert_left = (__p == _M_end() 02115 || !_M_impl._M_key_compare(_S_key(__p), 02116 _S_key(__z))); 02117 02118 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 02119 this->_M_impl._M_header); 02120 ++_M_impl._M_node_count; 02121 return iterator(__z); 02122 } 02123 02124 template<typename _Key, typename _Val, typename _KeyOfValue, 02125 typename _Compare, typename _Alloc> 02126 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02127 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02128 _M_insert_equal_lower_node(_Link_type __z) 02129 { 02130 _Link_type __x = _M_begin(); 02131 _Base_ptr __y = _M_end(); 02132 while (__x != 0) 02133 { 02134 __y = __x; 02135 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 02136 _S_left(__x) : _S_right(__x); 02137 } 02138 return _M_insert_lower_node(__y, __z); 02139 } 02140 02141 template<typename _Key, typename _Val, typename _KeyOfValue, 02142 typename _Compare, typename _Alloc> 02143 template<typename... _Args> 02144 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02145 _Compare, _Alloc>::iterator, bool> 02146 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02147 _M_emplace_unique(_Args&&... __args) 02148 { 02149 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02150 02151 __try 02152 { 02153 typedef pair<iterator, bool> _Res; 02154 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 02155 if (__res.second) 02156 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 02157 02158 _M_drop_node(__z); 02159 return _Res(iterator(__res.first), false); 02160 } 02161 __catch(...) 02162 { 02163 _M_drop_node(__z); 02164 __throw_exception_again; 02165 } 02166 } 02167 02168 template<typename _Key, typename _Val, typename _KeyOfValue, 02169 typename _Compare, typename _Alloc> 02170 template<typename... _Args> 02171 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02172 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02173 _M_emplace_equal(_Args&&... __args) 02174 { 02175 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02176 02177 __try 02178 { 02179 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 02180 return _M_insert_node(__res.first, __res.second, __z); 02181 } 02182 __catch(...) 02183 { 02184 _M_drop_node(__z); 02185 __throw_exception_again; 02186 } 02187 } 02188 02189 template<typename _Key, typename _Val, typename _KeyOfValue, 02190 typename _Compare, typename _Alloc> 02191 template<typename... _Args> 02192 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02193 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02194 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 02195 { 02196 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02197 02198 __try 02199 { 02200 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 02201 02202 if (__res.second) 02203 return _M_insert_node(__res.first, __res.second, __z); 02204 02205 _M_drop_node(__z); 02206 return iterator(__res.first); 02207 } 02208 __catch(...) 02209 { 02210 _M_drop_node(__z); 02211 __throw_exception_again; 02212 } 02213 } 02214 02215 template<typename _Key, typename _Val, typename _KeyOfValue, 02216 typename _Compare, typename _Alloc> 02217 template<typename... _Args> 02218 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02219 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02220 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 02221 { 02222 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02223 02224 __try 02225 { 02226 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 02227 02228 if (__res.second) 02229 return _M_insert_node(__res.first, __res.second, __z); 02230 02231 return _M_insert_equal_lower_node(__z); 02232 } 02233 __catch(...) 02234 { 02235 _M_drop_node(__z); 02236 __throw_exception_again; 02237 } 02238 } 02239 #endif 02240 02241 template<typename _Key, typename _Val, typename _KoV, 02242 typename _Cmp, typename _Alloc> 02243 template<class _II> 02244 void 02245 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 02246 _M_insert_unique(_II __first, _II __last) 02247 { 02248 _Alloc_node __an(*this); 02249 for (; __first != __last; ++__first) 02250 _M_insert_unique_(end(), *__first, __an); 02251 } 02252 02253 template<typename _Key, typename _Val, typename _KoV, 02254 typename _Cmp, typename _Alloc> 02255 template<class _II> 02256 void 02257 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 02258 _M_insert_equal(_II __first, _II __last) 02259 { 02260 _Alloc_node __an(*this); 02261 for (; __first != __last; ++__first) 02262 _M_insert_equal_(end(), *__first, __an); 02263 } 02264 02265 template<typename _Key, typename _Val, typename _KeyOfValue, 02266 typename _Compare, typename _Alloc> 02267 void 02268 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02269 _M_erase_aux(const_iterator __position) 02270 { 02271 _Link_type __y = 02272 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 02273 (const_cast<_Base_ptr>(__position._M_node), 02274 this->_M_impl._M_header)); 02275 _M_drop_node(__y); 02276 --_M_impl._M_node_count; 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 _M_erase_aux(const_iterator __first, const_iterator __last) 02284 { 02285 if (__first == begin() && __last == end()) 02286 clear(); 02287 else 02288 while (__first != __last) 02289 erase(__first++); 02290 } 02291 02292 template<typename _Key, typename _Val, typename _KeyOfValue, 02293 typename _Compare, typename _Alloc> 02294 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 02295 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02296 erase(const _Key& __x) 02297 { 02298 pair<iterator, iterator> __p = equal_range(__x); 02299 const size_type __old_size = size(); 02300 erase(__p.first, __p.second); 02301 return __old_size - size(); 02302 } 02303 02304 template<typename _Key, typename _Val, typename _KeyOfValue, 02305 typename _Compare, typename _Alloc> 02306 void 02307 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02308 erase(const _Key* __first, const _Key* __last) 02309 { 02310 while (__first != __last) 02311 erase(*__first++); 02312 } 02313 02314 template<typename _Key, typename _Val, typename _KeyOfValue, 02315 typename _Compare, typename _Alloc> 02316 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02317 _Compare, _Alloc>::iterator 02318 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02319 find(const _Key& __k) 02320 { 02321 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 02322 return (__j == end() 02323 || _M_impl._M_key_compare(__k, 02324 _S_key(__j._M_node))) ? end() : __j; 02325 } 02326 02327 template<typename _Key, typename _Val, typename _KeyOfValue, 02328 typename _Compare, typename _Alloc> 02329 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02330 _Compare, _Alloc>::const_iterator 02331 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02332 find(const _Key& __k) const 02333 { 02334 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 02335 return (__j == end() 02336 || _M_impl._M_key_compare(__k, 02337 _S_key(__j._M_node))) ? end() : __j; 02338 } 02339 02340 template<typename _Key, typename _Val, typename _KeyOfValue, 02341 typename _Compare, typename _Alloc> 02342 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 02343 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02344 count(const _Key& __k) const 02345 { 02346 pair<const_iterator, const_iterator> __p = equal_range(__k); 02347 const size_type __n = std::distance(__p.first, __p.second); 02348 return __n; 02349 } 02350 02351 _GLIBCXX_PURE unsigned int 02352 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 02353 const _Rb_tree_node_base* __root) throw (); 02354 02355 template<typename _Key, typename _Val, typename _KeyOfValue, 02356 typename _Compare, typename _Alloc> 02357 bool 02358 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 02359 { 02360 if (_M_impl._M_node_count == 0 || begin() == end()) 02361 return _M_impl._M_node_count == 0 && begin() == end() 02362 && this->_M_impl._M_header._M_left == _M_end() 02363 && this->_M_impl._M_header._M_right == _M_end(); 02364 02365 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 02366 for (const_iterator __it = begin(); __it != end(); ++__it) 02367 { 02368 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 02369 _Const_Link_type __L = _S_left(__x); 02370 _Const_Link_type __R = _S_right(__x); 02371 02372 if (__x->_M_color == _S_red) 02373 if ((__L && __L->_M_color == _S_red) 02374 || (__R && __R->_M_color == _S_red)) 02375 return false; 02376 02377 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 02378 return false; 02379 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 02380 return false; 02381 02382 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 02383 return false; 02384 } 02385 02386 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 02387 return false; 02388 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 02389 return false; 02390 return true; 02391 } 02392 02393 _GLIBCXX_END_NAMESPACE_VERSION 02394 } // namespace 02395 02396 #endif