libstdc++
|
00001 // RB tree implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2014 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 #include <bits/stl_algobase.h> 00062 #include <bits/allocator.h> 00063 #include <bits/stl_function.h> 00064 #include <bits/cpp_type_traits.h> 00065 #include <ext/alloc_traits.h> 00066 #if __cplusplus >= 201103L 00067 #include <ext/aligned_buffer.h> 00068 #endif 00069 00070 namespace std _GLIBCXX_VISIBILITY(default) 00071 { 00072 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00073 00074 // Red-black tree class, designed for use in implementing STL 00075 // associative containers (set, multiset, map, and multimap). The 00076 // insertion and deletion algorithms are based on those in Cormen, 00077 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 00078 // 1990), except that 00079 // 00080 // (1) the header cell is maintained with links not only to the root 00081 // but also to the leftmost node of the tree, to enable constant 00082 // time begin(), and to the rightmost node of the tree, to enable 00083 // linear time performance when used with the generic set algorithms 00084 // (set_union, etc.) 00085 // 00086 // (2) when a node being deleted has two children its successor node 00087 // is relinked into its place, rather than copied, so that the only 00088 // iterators invalidated are those referring to the deleted node. 00089 00090 enum _Rb_tree_color { _S_red = false, _S_black = true }; 00091 00092 struct _Rb_tree_node_base 00093 { 00094 typedef _Rb_tree_node_base* _Base_ptr; 00095 typedef const _Rb_tree_node_base* _Const_Base_ptr; 00096 00097 _Rb_tree_color _M_color; 00098 _Base_ptr _M_parent; 00099 _Base_ptr _M_left; 00100 _Base_ptr _M_right; 00101 00102 static _Base_ptr 00103 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00104 { 00105 while (__x->_M_left != 0) __x = __x->_M_left; 00106 return __x; 00107 } 00108 00109 static _Const_Base_ptr 00110 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00111 { 00112 while (__x->_M_left != 0) __x = __x->_M_left; 00113 return __x; 00114 } 00115 00116 static _Base_ptr 00117 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00118 { 00119 while (__x->_M_right != 0) __x = __x->_M_right; 00120 return __x; 00121 } 00122 00123 static _Const_Base_ptr 00124 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00125 { 00126 while (__x->_M_right != 0) __x = __x->_M_right; 00127 return __x; 00128 } 00129 }; 00130 00131 template<typename _Val> 00132 struct _Rb_tree_node : public _Rb_tree_node_base 00133 { 00134 typedef _Rb_tree_node<_Val>* _Link_type; 00135 00136 #if __cplusplus < 201103L 00137 _Val _M_value_field; 00138 00139 _Val* 00140 _M_valptr() 00141 { return std::__addressof(_M_value_field); } 00142 00143 const _Val* 00144 _M_valptr() const 00145 { return std::__addressof(_M_value_field); } 00146 #else 00147 __gnu_cxx::__aligned_buffer<_Val> _M_storage; 00148 00149 _Val* 00150 _M_valptr() 00151 { return _M_storage._M_ptr(); } 00152 00153 const _Val* 00154 _M_valptr() const 00155 { return _M_storage._M_ptr(); } 00156 #endif 00157 }; 00158 00159 _GLIBCXX_PURE _Rb_tree_node_base* 00160 _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); 00161 00162 _GLIBCXX_PURE const _Rb_tree_node_base* 00163 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw (); 00164 00165 _GLIBCXX_PURE _Rb_tree_node_base* 00166 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw (); 00167 00168 _GLIBCXX_PURE const _Rb_tree_node_base* 00169 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw (); 00170 00171 template<typename _Tp> 00172 struct _Rb_tree_iterator 00173 { 00174 typedef _Tp value_type; 00175 typedef _Tp& reference; 00176 typedef _Tp* pointer; 00177 00178 typedef bidirectional_iterator_tag iterator_category; 00179 typedef ptrdiff_t difference_type; 00180 00181 typedef _Rb_tree_iterator<_Tp> _Self; 00182 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 00183 typedef _Rb_tree_node<_Tp>* _Link_type; 00184 00185 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT 00186 : _M_node() { } 00187 00188 explicit 00189 _Rb_tree_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT 00190 : _M_node(__x) { } 00191 00192 reference 00193 operator*() const _GLIBCXX_NOEXCEPT 00194 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 00195 00196 pointer 00197 operator->() const _GLIBCXX_NOEXCEPT 00198 { return static_cast<_Link_type> (_M_node)->_M_valptr(); } 00199 00200 _Self& 00201 operator++() _GLIBCXX_NOEXCEPT 00202 { 00203 _M_node = _Rb_tree_increment(_M_node); 00204 return *this; 00205 } 00206 00207 _Self 00208 operator++(int) _GLIBCXX_NOEXCEPT 00209 { 00210 _Self __tmp = *this; 00211 _M_node = _Rb_tree_increment(_M_node); 00212 return __tmp; 00213 } 00214 00215 _Self& 00216 operator--() _GLIBCXX_NOEXCEPT 00217 { 00218 _M_node = _Rb_tree_decrement(_M_node); 00219 return *this; 00220 } 00221 00222 _Self 00223 operator--(int) _GLIBCXX_NOEXCEPT 00224 { 00225 _Self __tmp = *this; 00226 _M_node = _Rb_tree_decrement(_M_node); 00227 return __tmp; 00228 } 00229 00230 bool 00231 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 00232 { return _M_node == __x._M_node; } 00233 00234 bool 00235 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 00236 { return _M_node != __x._M_node; } 00237 00238 _Base_ptr _M_node; 00239 }; 00240 00241 template<typename _Tp> 00242 struct _Rb_tree_const_iterator 00243 { 00244 typedef _Tp value_type; 00245 typedef const _Tp& reference; 00246 typedef const _Tp* pointer; 00247 00248 typedef _Rb_tree_iterator<_Tp> iterator; 00249 00250 typedef bidirectional_iterator_tag iterator_category; 00251 typedef ptrdiff_t difference_type; 00252 00253 typedef _Rb_tree_const_iterator<_Tp> _Self; 00254 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 00255 typedef const _Rb_tree_node<_Tp>* _Link_type; 00256 00257 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT 00258 : _M_node() { } 00259 00260 explicit 00261 _Rb_tree_const_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT 00262 : _M_node(__x) { } 00263 00264 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT 00265 : _M_node(__it._M_node) { } 00266 00267 iterator 00268 _M_const_cast() const _GLIBCXX_NOEXCEPT 00269 { return iterator(static_cast<typename iterator::_Link_type> 00270 (const_cast<typename iterator::_Base_ptr>(_M_node))); } 00271 00272 reference 00273 operator*() const _GLIBCXX_NOEXCEPT 00274 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 00275 00276 pointer 00277 operator->() const _GLIBCXX_NOEXCEPT 00278 { return static_cast<_Link_type>(_M_node)->_M_valptr(); } 00279 00280 _Self& 00281 operator++() _GLIBCXX_NOEXCEPT 00282 { 00283 _M_node = _Rb_tree_increment(_M_node); 00284 return *this; 00285 } 00286 00287 _Self 00288 operator++(int) _GLIBCXX_NOEXCEPT 00289 { 00290 _Self __tmp = *this; 00291 _M_node = _Rb_tree_increment(_M_node); 00292 return __tmp; 00293 } 00294 00295 _Self& 00296 operator--() _GLIBCXX_NOEXCEPT 00297 { 00298 _M_node = _Rb_tree_decrement(_M_node); 00299 return *this; 00300 } 00301 00302 _Self 00303 operator--(int) _GLIBCXX_NOEXCEPT 00304 { 00305 _Self __tmp = *this; 00306 _M_node = _Rb_tree_decrement(_M_node); 00307 return __tmp; 00308 } 00309 00310 bool 00311 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 00312 { return _M_node == __x._M_node; } 00313 00314 bool 00315 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 00316 { return _M_node != __x._M_node; } 00317 00318 _Base_ptr _M_node; 00319 }; 00320 00321 template<typename _Val> 00322 inline bool 00323 operator==(const _Rb_tree_iterator<_Val>& __x, 00324 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 00325 { return __x._M_node == __y._M_node; } 00326 00327 template<typename _Val> 00328 inline bool 00329 operator!=(const _Rb_tree_iterator<_Val>& __x, 00330 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 00331 { return __x._M_node != __y._M_node; } 00332 00333 void 00334 _Rb_tree_insert_and_rebalance(const bool __insert_left, 00335 _Rb_tree_node_base* __x, 00336 _Rb_tree_node_base* __p, 00337 _Rb_tree_node_base& __header) throw (); 00338 00339 _Rb_tree_node_base* 00340 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 00341 _Rb_tree_node_base& __header) throw (); 00342 00343 00344 template<typename _Key, typename _Val, typename _KeyOfValue, 00345 typename _Compare, typename _Alloc = allocator<_Val> > 00346 class _Rb_tree 00347 { 00348 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 00349 rebind<_Rb_tree_node<_Val> >::other _Node_allocator; 00350 00351 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits; 00352 00353 protected: 00354 typedef _Rb_tree_node_base* _Base_ptr; 00355 typedef const _Rb_tree_node_base* _Const_Base_ptr; 00356 00357 public: 00358 typedef _Key key_type; 00359 typedef _Val value_type; 00360 typedef value_type* pointer; 00361 typedef const value_type* const_pointer; 00362 typedef value_type& reference; 00363 typedef const value_type& const_reference; 00364 typedef _Rb_tree_node<_Val>* _Link_type; 00365 typedef const _Rb_tree_node<_Val>* _Const_Link_type; 00366 typedef size_t size_type; 00367 typedef ptrdiff_t difference_type; 00368 typedef _Alloc allocator_type; 00369 00370 _Node_allocator& 00371 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT 00372 { return *static_cast<_Node_allocator*>(&this->_M_impl); } 00373 00374 const _Node_allocator& 00375 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT 00376 { return *static_cast<const _Node_allocator*>(&this->_M_impl); } 00377 00378 allocator_type 00379 get_allocator() const _GLIBCXX_NOEXCEPT 00380 { return allocator_type(_M_get_Node_allocator()); } 00381 00382 protected: 00383 _Link_type 00384 _M_get_node() 00385 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); } 00386 00387 void 00388 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT 00389 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); } 00390 00391 #if __cplusplus < 201103L 00392 _Link_type 00393 _M_create_node(const value_type& __x) 00394 { 00395 _Link_type __tmp = _M_get_node(); 00396 __try 00397 { get_allocator().construct(__tmp->_M_valptr(), __x); } 00398 __catch(...) 00399 { 00400 _M_put_node(__tmp); 00401 __throw_exception_again; 00402 } 00403 return __tmp; 00404 } 00405 00406 void 00407 _M_destroy_node(_Link_type __p) 00408 { 00409 get_allocator().destroy(__p->_M_valptr()); 00410 _M_put_node(__p); 00411 } 00412 #else 00413 template<typename... _Args> 00414 _Link_type 00415 _M_create_node(_Args&&... __args) 00416 { 00417 _Link_type __tmp = _M_get_node(); 00418 __try 00419 { 00420 ::new(__tmp) _Rb_tree_node<_Val>; 00421 _Alloc_traits::construct(_M_get_Node_allocator(), 00422 __tmp->_M_valptr(), 00423 std::forward<_Args>(__args)...); 00424 } 00425 __catch(...) 00426 { 00427 _M_put_node(__tmp); 00428 __throw_exception_again; 00429 } 00430 return __tmp; 00431 } 00432 00433 void 00434 _M_destroy_node(_Link_type __p) noexcept 00435 { 00436 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr()); 00437 __p->~_Rb_tree_node<_Val>(); 00438 _M_put_node(__p); 00439 } 00440 #endif 00441 00442 _Link_type 00443 _M_clone_node(_Const_Link_type __x) 00444 { 00445 _Link_type __tmp = _M_create_node(*__x->_M_valptr()); 00446 __tmp->_M_color = __x->_M_color; 00447 __tmp->_M_left = 0; 00448 __tmp->_M_right = 0; 00449 return __tmp; 00450 } 00451 00452 protected: 00453 template<typename _Key_compare, 00454 bool _Is_pod_comparator = __is_pod(_Key_compare)> 00455 struct _Rb_tree_impl : public _Node_allocator 00456 { 00457 _Key_compare _M_key_compare; 00458 _Rb_tree_node_base _M_header; 00459 size_type _M_node_count; // Keeps track of size of tree. 00460 00461 _Rb_tree_impl() 00462 : _Node_allocator(), _M_key_compare(), _M_header(), 00463 _M_node_count(0) 00464 { _M_initialize(); } 00465 00466 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 00467 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), 00468 _M_node_count(0) 00469 { _M_initialize(); } 00470 00471 #if __cplusplus >= 201103L 00472 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) 00473 : _Node_allocator(std::move(__a)), _M_key_compare(__comp), 00474 _M_header(), _M_node_count(0) 00475 { _M_initialize(); } 00476 #endif 00477 00478 private: 00479 void 00480 _M_initialize() 00481 { 00482 this->_M_header._M_color = _S_red; 00483 this->_M_header._M_parent = 0; 00484 this->_M_header._M_left = &this->_M_header; 00485 this->_M_header._M_right = &this->_M_header; 00486 } 00487 }; 00488 00489 _Rb_tree_impl<_Compare> _M_impl; 00490 00491 protected: 00492 _Base_ptr& 00493 _M_root() _GLIBCXX_NOEXCEPT 00494 { return this->_M_impl._M_header._M_parent; } 00495 00496 _Const_Base_ptr 00497 _M_root() const _GLIBCXX_NOEXCEPT 00498 { return this->_M_impl._M_header._M_parent; } 00499 00500 _Base_ptr& 00501 _M_leftmost() _GLIBCXX_NOEXCEPT 00502 { return this->_M_impl._M_header._M_left; } 00503 00504 _Const_Base_ptr 00505 _M_leftmost() const _GLIBCXX_NOEXCEPT 00506 { return this->_M_impl._M_header._M_left; } 00507 00508 _Base_ptr& 00509 _M_rightmost() _GLIBCXX_NOEXCEPT 00510 { return this->_M_impl._M_header._M_right; } 00511 00512 _Const_Base_ptr 00513 _M_rightmost() const _GLIBCXX_NOEXCEPT 00514 { return this->_M_impl._M_header._M_right; } 00515 00516 _Link_type 00517 _M_begin() _GLIBCXX_NOEXCEPT 00518 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 00519 00520 _Const_Link_type 00521 _M_begin() const _GLIBCXX_NOEXCEPT 00522 { 00523 return static_cast<_Const_Link_type> 00524 (this->_M_impl._M_header._M_parent); 00525 } 00526 00527 _Link_type 00528 _M_end() _GLIBCXX_NOEXCEPT 00529 { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); } 00530 00531 _Const_Link_type 00532 _M_end() const _GLIBCXX_NOEXCEPT 00533 { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); } 00534 00535 static const_reference 00536 _S_value(_Const_Link_type __x) 00537 { return *__x->_M_valptr(); } 00538 00539 static const _Key& 00540 _S_key(_Const_Link_type __x) 00541 { return _KeyOfValue()(_S_value(__x)); } 00542 00543 static _Link_type 00544 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00545 { return static_cast<_Link_type>(__x->_M_left); } 00546 00547 static _Const_Link_type 00548 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00549 { return static_cast<_Const_Link_type>(__x->_M_left); } 00550 00551 static _Link_type 00552 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00553 { return static_cast<_Link_type>(__x->_M_right); } 00554 00555 static _Const_Link_type 00556 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00557 { return static_cast<_Const_Link_type>(__x->_M_right); } 00558 00559 static const_reference 00560 _S_value(_Const_Base_ptr __x) 00561 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); } 00562 00563 static const _Key& 00564 _S_key(_Const_Base_ptr __x) 00565 { return _KeyOfValue()(_S_value(__x)); } 00566 00567 static _Base_ptr 00568 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00569 { return _Rb_tree_node_base::_S_minimum(__x); } 00570 00571 static _Const_Base_ptr 00572 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00573 { return _Rb_tree_node_base::_S_minimum(__x); } 00574 00575 static _Base_ptr 00576 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00577 { return _Rb_tree_node_base::_S_maximum(__x); } 00578 00579 static _Const_Base_ptr 00580 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00581 { return _Rb_tree_node_base::_S_maximum(__x); } 00582 00583 public: 00584 typedef _Rb_tree_iterator<value_type> iterator; 00585 typedef _Rb_tree_const_iterator<value_type> const_iterator; 00586 00587 typedef std::reverse_iterator<iterator> reverse_iterator; 00588 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00589 00590 private: 00591 pair<_Base_ptr, _Base_ptr> 00592 _M_get_insert_unique_pos(const key_type& __k); 00593 00594 pair<_Base_ptr, _Base_ptr> 00595 _M_get_insert_equal_pos(const key_type& __k); 00596 00597 pair<_Base_ptr, _Base_ptr> 00598 _M_get_insert_hint_unique_pos(const_iterator __pos, 00599 const key_type& __k); 00600 00601 pair<_Base_ptr, _Base_ptr> 00602 _M_get_insert_hint_equal_pos(const_iterator __pos, 00603 const key_type& __k); 00604 00605 #if __cplusplus >= 201103L 00606 template<typename _Arg> 00607 iterator 00608 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v); 00609 00610 iterator 00611 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); 00612 00613 template<typename _Arg> 00614 iterator 00615 _M_insert_lower(_Base_ptr __y, _Arg&& __v); 00616 00617 template<typename _Arg> 00618 iterator 00619 _M_insert_equal_lower(_Arg&& __x); 00620 00621 iterator 00622 _M_insert_lower_node(_Base_ptr __p, _Link_type __z); 00623 00624 iterator 00625 _M_insert_equal_lower_node(_Link_type __z); 00626 #else 00627 iterator 00628 _M_insert_(_Base_ptr __x, _Base_ptr __y, 00629 const value_type& __v); 00630 00631 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00632 // 233. Insertion hints in associative containers. 00633 iterator 00634 _M_insert_lower(_Base_ptr __y, const value_type& __v); 00635 00636 iterator 00637 _M_insert_equal_lower(const value_type& __x); 00638 #endif 00639 00640 _Link_type 00641 _M_copy(_Const_Link_type __x, _Link_type __p); 00642 00643 void 00644 _M_erase(_Link_type __x); 00645 00646 iterator 00647 _M_lower_bound(_Link_type __x, _Link_type __y, 00648 const _Key& __k); 00649 00650 const_iterator 00651 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 00652 const _Key& __k) const; 00653 00654 iterator 00655 _M_upper_bound(_Link_type __x, _Link_type __y, 00656 const _Key& __k); 00657 00658 const_iterator 00659 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 00660 const _Key& __k) const; 00661 00662 public: 00663 // allocation/deallocation 00664 _Rb_tree() { } 00665 00666 _Rb_tree(const _Compare& __comp, 00667 const allocator_type& __a = allocator_type()) 00668 : _M_impl(__comp, _Node_allocator(__a)) { } 00669 00670 _Rb_tree(const _Rb_tree& __x) 00671 : _M_impl(__x._M_impl._M_key_compare, 00672 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator())) 00673 { 00674 if (__x._M_root() != 0) 00675 { 00676 _M_root() = _M_copy(__x._M_begin(), _M_end()); 00677 _M_leftmost() = _S_minimum(_M_root()); 00678 _M_rightmost() = _S_maximum(_M_root()); 00679 _M_impl._M_node_count = __x._M_impl._M_node_count; 00680 } 00681 } 00682 00683 #if __cplusplus >= 201103L 00684 _Rb_tree(const allocator_type& __a) 00685 : _M_impl(_Compare(), _Node_allocator(__a)) 00686 { } 00687 00688 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a) 00689 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) 00690 { 00691 if (__x._M_root() != 0) 00692 { 00693 _M_root() = _M_copy(__x._M_begin(), _M_end()); 00694 _M_leftmost() = _S_minimum(_M_root()); 00695 _M_rightmost() = _S_maximum(_M_root()); 00696 _M_impl._M_node_count = __x._M_impl._M_node_count; 00697 } 00698 } 00699 00700 _Rb_tree(_Rb_tree&& __x) 00701 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) 00702 { 00703 if (__x._M_root() != 0) 00704 _M_move_data(__x, std::true_type()); 00705 } 00706 00707 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a) 00708 : _Rb_tree(std::move(__x), _Node_allocator(__a)) 00709 { } 00710 00711 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a); 00712 #endif 00713 00714 ~_Rb_tree() _GLIBCXX_NOEXCEPT 00715 { _M_erase(_M_begin()); } 00716 00717 _Rb_tree& 00718 operator=(const _Rb_tree& __x); 00719 00720 // Accessors. 00721 _Compare 00722 key_comp() const 00723 { return _M_impl._M_key_compare; } 00724 00725 iterator 00726 begin() _GLIBCXX_NOEXCEPT 00727 { 00728 return iterator(static_cast<_Link_type> 00729 (this->_M_impl._M_header._M_left)); 00730 } 00731 00732 const_iterator 00733 begin() const _GLIBCXX_NOEXCEPT 00734 { 00735 return const_iterator(static_cast<_Const_Link_type> 00736 (this->_M_impl._M_header._M_left)); 00737 } 00738 00739 iterator 00740 end() _GLIBCXX_NOEXCEPT 00741 { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); } 00742 00743 const_iterator 00744 end() const _GLIBCXX_NOEXCEPT 00745 { 00746 return const_iterator(static_cast<_Const_Link_type> 00747 (&this->_M_impl._M_header)); 00748 } 00749 00750 reverse_iterator 00751 rbegin() _GLIBCXX_NOEXCEPT 00752 { return reverse_iterator(end()); } 00753 00754 const_reverse_iterator 00755 rbegin() const _GLIBCXX_NOEXCEPT 00756 { return const_reverse_iterator(end()); } 00757 00758 reverse_iterator 00759 rend() _GLIBCXX_NOEXCEPT 00760 { return reverse_iterator(begin()); } 00761 00762 const_reverse_iterator 00763 rend() const _GLIBCXX_NOEXCEPT 00764 { return const_reverse_iterator(begin()); } 00765 00766 bool 00767 empty() const _GLIBCXX_NOEXCEPT 00768 { return _M_impl._M_node_count == 0; } 00769 00770 size_type 00771 size() const _GLIBCXX_NOEXCEPT 00772 { return _M_impl._M_node_count; } 00773 00774 size_type 00775 max_size() const _GLIBCXX_NOEXCEPT 00776 { return _Alloc_traits::max_size(_M_get_Node_allocator()); } 00777 00778 void 00779 #if __cplusplus >= 201103L 00780 swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap()); 00781 #else 00782 swap(_Rb_tree& __t); 00783 #endif 00784 00785 // Insert/erase. 00786 #if __cplusplus >= 201103L 00787 template<typename _Arg> 00788 pair<iterator, bool> 00789 _M_insert_unique(_Arg&& __x); 00790 00791 template<typename _Arg> 00792 iterator 00793 _M_insert_equal(_Arg&& __x); 00794 00795 template<typename _Arg> 00796 iterator 00797 _M_insert_unique_(const_iterator __position, _Arg&& __x); 00798 00799 template<typename _Arg> 00800 iterator 00801 _M_insert_equal_(const_iterator __position, _Arg&& __x); 00802 00803 template<typename... _Args> 00804 pair<iterator, bool> 00805 _M_emplace_unique(_Args&&... __args); 00806 00807 template<typename... _Args> 00808 iterator 00809 _M_emplace_equal(_Args&&... __args); 00810 00811 template<typename... _Args> 00812 iterator 00813 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); 00814 00815 template<typename... _Args> 00816 iterator 00817 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); 00818 #else 00819 pair<iterator, bool> 00820 _M_insert_unique(const value_type& __x); 00821 00822 iterator 00823 _M_insert_equal(const value_type& __x); 00824 00825 iterator 00826 _M_insert_unique_(const_iterator __position, const value_type& __x); 00827 00828 iterator 00829 _M_insert_equal_(const_iterator __position, const value_type& __x); 00830 #endif 00831 00832 template<typename _InputIterator> 00833 void 00834 _M_insert_unique(_InputIterator __first, _InputIterator __last); 00835 00836 template<typename _InputIterator> 00837 void 00838 _M_insert_equal(_InputIterator __first, _InputIterator __last); 00839 00840 private: 00841 void 00842 _M_erase_aux(const_iterator __position); 00843 00844 void 00845 _M_erase_aux(const_iterator __first, const_iterator __last); 00846 00847 public: 00848 #if __cplusplus >= 201103L 00849 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00850 // DR 130. Associative erase should return an iterator. 00851 _GLIBCXX_ABI_TAG_CXX11 00852 iterator 00853 erase(const_iterator __position) 00854 { 00855 const_iterator __result = __position; 00856 ++__result; 00857 _M_erase_aux(__position); 00858 return __result._M_const_cast(); 00859 } 00860 00861 // LWG 2059. 00862 _GLIBCXX_ABI_TAG_CXX11 00863 iterator 00864 erase(iterator __position) 00865 { 00866 iterator __result = __position; 00867 ++__result; 00868 _M_erase_aux(__position); 00869 return __result; 00870 } 00871 #else 00872 void 00873 erase(iterator __position) 00874 { _M_erase_aux(__position); } 00875 00876 void 00877 erase(const_iterator __position) 00878 { _M_erase_aux(__position); } 00879 #endif 00880 size_type 00881 erase(const key_type& __x); 00882 00883 #if __cplusplus >= 201103L 00884 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00885 // DR 130. Associative erase should return an iterator. 00886 _GLIBCXX_ABI_TAG_CXX11 00887 iterator 00888 erase(const_iterator __first, const_iterator __last) 00889 { 00890 _M_erase_aux(__first, __last); 00891 return __last._M_const_cast(); 00892 } 00893 #else 00894 void 00895 erase(iterator __first, iterator __last) 00896 { _M_erase_aux(__first, __last); } 00897 00898 void 00899 erase(const_iterator __first, const_iterator __last) 00900 { _M_erase_aux(__first, __last); } 00901 #endif 00902 void 00903 erase(const key_type* __first, const key_type* __last); 00904 00905 void 00906 clear() _GLIBCXX_NOEXCEPT 00907 { 00908 _M_erase(_M_begin()); 00909 _M_leftmost() = _M_end(); 00910 _M_root() = 0; 00911 _M_rightmost() = _M_end(); 00912 _M_impl._M_node_count = 0; 00913 } 00914 00915 // Set operations. 00916 iterator 00917 find(const key_type& __k); 00918 00919 const_iterator 00920 find(const key_type& __k) const; 00921 00922 size_type 00923 count(const key_type& __k) const; 00924 00925 iterator 00926 lower_bound(const key_type& __k) 00927 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 00928 00929 const_iterator 00930 lower_bound(const key_type& __k) const 00931 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 00932 00933 iterator 00934 upper_bound(const key_type& __k) 00935 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 00936 00937 const_iterator 00938 upper_bound(const key_type& __k) const 00939 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 00940 00941 pair<iterator, iterator> 00942 equal_range(const key_type& __k); 00943 00944 pair<const_iterator, const_iterator> 00945 equal_range(const key_type& __k) const; 00946 00947 // Debugging. 00948 bool 00949 __rb_verify() const; 00950 00951 #if __cplusplus >= 201103L 00952 bool 00953 _M_move_assign(_Rb_tree&); 00954 00955 private: 00956 // Move elements from container with equal allocator. 00957 void 00958 _M_move_data(_Rb_tree&, std::true_type); 00959 00960 // Move elements from container with possibly non-equal allocator, 00961 // which might result in a copy not a move. 00962 void 00963 _M_move_data(_Rb_tree&, std::false_type); 00964 #endif 00965 }; 00966 00967 template<typename _Key, typename _Val, typename _KeyOfValue, 00968 typename _Compare, typename _Alloc> 00969 inline bool 00970 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00971 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00972 { 00973 return __x.size() == __y.size() 00974 && std::equal(__x.begin(), __x.end(), __y.begin()); 00975 } 00976 00977 template<typename _Key, typename _Val, typename _KeyOfValue, 00978 typename _Compare, typename _Alloc> 00979 inline bool 00980 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00981 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00982 { 00983 return std::lexicographical_compare(__x.begin(), __x.end(), 00984 __y.begin(), __y.end()); 00985 } 00986 00987 template<typename _Key, typename _Val, typename _KeyOfValue, 00988 typename _Compare, typename _Alloc> 00989 inline bool 00990 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00991 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00992 { return !(__x == __y); } 00993 00994 template<typename _Key, typename _Val, typename _KeyOfValue, 00995 typename _Compare, typename _Alloc> 00996 inline bool 00997 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00998 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00999 { return __y < __x; } 01000 01001 template<typename _Key, typename _Val, typename _KeyOfValue, 01002 typename _Compare, typename _Alloc> 01003 inline bool 01004 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01005 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01006 { return !(__y < __x); } 01007 01008 template<typename _Key, typename _Val, typename _KeyOfValue, 01009 typename _Compare, typename _Alloc> 01010 inline bool 01011 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01012 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01013 { return !(__x < __y); } 01014 01015 template<typename _Key, typename _Val, typename _KeyOfValue, 01016 typename _Compare, typename _Alloc> 01017 inline void 01018 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01019 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01020 { __x.swap(__y); } 01021 01022 #if __cplusplus >= 201103L 01023 template<typename _Key, typename _Val, typename _KeyOfValue, 01024 typename _Compare, typename _Alloc> 01025 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01026 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) 01027 : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) 01028 { 01029 using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>; 01030 if (__x._M_root() != 0) 01031 _M_move_data(__x, __eq()); 01032 } 01033 01034 template<typename _Key, typename _Val, typename _KeyOfValue, 01035 typename _Compare, typename _Alloc> 01036 void 01037 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01038 _M_move_data(_Rb_tree& __x, std::true_type) 01039 { 01040 _M_root() = __x._M_root(); 01041 _M_leftmost() = __x._M_leftmost(); 01042 _M_rightmost() = __x._M_rightmost(); 01043 _M_root()->_M_parent = _M_end(); 01044 01045 __x._M_root() = 0; 01046 __x._M_leftmost() = __x._M_end(); 01047 __x._M_rightmost() = __x._M_end(); 01048 01049 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 01050 __x._M_impl._M_node_count = 0; 01051 } 01052 01053 template<typename _Key, typename _Val, typename _KeyOfValue, 01054 typename _Compare, typename _Alloc> 01055 void 01056 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01057 _M_move_data(_Rb_tree& __x, std::false_type) 01058 { 01059 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 01060 _M_move_data(__x, std::true_type()); 01061 else 01062 { 01063 _M_root() = _M_copy(__x._M_begin(), _M_end()); 01064 _M_leftmost() = _S_minimum(_M_root()); 01065 _M_rightmost() = _S_maximum(_M_root()); 01066 _M_impl._M_node_count = __x._M_impl._M_node_count; 01067 } 01068 } 01069 01070 template<typename _Key, typename _Val, typename _KeyOfValue, 01071 typename _Compare, typename _Alloc> 01072 bool 01073 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01074 _M_move_assign(_Rb_tree& __x) 01075 { 01076 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 01077 if (_Alloc_traits::_S_propagate_on_move_assign() 01078 || _Alloc_traits::_S_always_equal() 01079 || _M_get_Node_allocator() == __x._M_get_Node_allocator()) 01080 { 01081 clear(); 01082 if (__x._M_root() != 0) 01083 _M_move_data(__x, std::true_type()); 01084 std::__alloc_on_move(_M_get_Node_allocator(), 01085 __x._M_get_Node_allocator()); 01086 return true; 01087 } 01088 return false; 01089 } 01090 #endif 01091 01092 template<typename _Key, typename _Val, typename _KeyOfValue, 01093 typename _Compare, typename _Alloc> 01094 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 01095 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01096 operator=(const _Rb_tree& __x) 01097 { 01098 if (this != &__x) 01099 { 01100 // Note that _Key may be a constant type. 01101 clear(); 01102 #if __cplusplus >= 201103L 01103 if (_Alloc_traits::_S_propagate_on_copy_assign()) 01104 { 01105 auto& __this_alloc = this->_M_get_Node_allocator(); 01106 auto& __that_alloc = __x._M_get_Node_allocator(); 01107 if (!_Alloc_traits::_S_always_equal() 01108 && __this_alloc != __that_alloc) 01109 { 01110 std::__alloc_on_copy(__this_alloc, __that_alloc); 01111 } 01112 } 01113 #endif 01114 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 01115 if (__x._M_root() != 0) 01116 { 01117 _M_root() = _M_copy(__x._M_begin(), _M_end()); 01118 _M_leftmost() = _S_minimum(_M_root()); 01119 _M_rightmost() = _S_maximum(_M_root()); 01120 _M_impl._M_node_count = __x._M_impl._M_node_count; 01121 } 01122 } 01123 return *this; 01124 } 01125 01126 template<typename _Key, typename _Val, typename _KeyOfValue, 01127 typename _Compare, typename _Alloc> 01128 #if __cplusplus >= 201103L 01129 template<typename _Arg> 01130 #endif 01131 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01132 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01133 #if __cplusplus >= 201103L 01134 _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) 01135 #else 01136 _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 01137 #endif 01138 { 01139 bool __insert_left = (__x != 0 || __p == _M_end() 01140 || _M_impl._M_key_compare(_KeyOfValue()(__v), 01141 _S_key(__p))); 01142 01143 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 01144 01145 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01146 this->_M_impl._M_header); 01147 ++_M_impl._M_node_count; 01148 return iterator(__z); 01149 } 01150 01151 template<typename _Key, typename _Val, typename _KeyOfValue, 01152 typename _Compare, typename _Alloc> 01153 #if __cplusplus >= 201103L 01154 template<typename _Arg> 01155 #endif 01156 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01157 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01158 #if __cplusplus >= 201103L 01159 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 01160 #else 01161 _M_insert_lower(_Base_ptr __p, const _Val& __v) 01162 #endif 01163 { 01164 bool __insert_left = (__p == _M_end() 01165 || !_M_impl._M_key_compare(_S_key(__p), 01166 _KeyOfValue()(__v))); 01167 01168 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 01169 01170 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01171 this->_M_impl._M_header); 01172 ++_M_impl._M_node_count; 01173 return iterator(__z); 01174 } 01175 01176 template<typename _Key, typename _Val, typename _KeyOfValue, 01177 typename _Compare, typename _Alloc> 01178 #if __cplusplus >= 201103L 01179 template<typename _Arg> 01180 #endif 01181 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01182 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01183 #if __cplusplus >= 201103L 01184 _M_insert_equal_lower(_Arg&& __v) 01185 #else 01186 _M_insert_equal_lower(const _Val& __v) 01187 #endif 01188 { 01189 _Link_type __x = _M_begin(); 01190 _Link_type __y = _M_end(); 01191 while (__x != 0) 01192 { 01193 __y = __x; 01194 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 01195 _S_left(__x) : _S_right(__x); 01196 } 01197 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 01198 } 01199 01200 template<typename _Key, typename _Val, typename _KoV, 01201 typename _Compare, typename _Alloc> 01202 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 01203 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 01204 _M_copy(_Const_Link_type __x, _Link_type __p) 01205 { 01206 // Structural copy. __x and __p must be non-null. 01207 _Link_type __top = _M_clone_node(__x); 01208 __top->_M_parent = __p; 01209 01210 __try 01211 { 01212 if (__x->_M_right) 01213 __top->_M_right = _M_copy(_S_right(__x), __top); 01214 __p = __top; 01215 __x = _S_left(__x); 01216 01217 while (__x != 0) 01218 { 01219 _Link_type __y = _M_clone_node(__x); 01220 __p->_M_left = __y; 01221 __y->_M_parent = __p; 01222 if (__x->_M_right) 01223 __y->_M_right = _M_copy(_S_right(__x), __y); 01224 __p = __y; 01225 __x = _S_left(__x); 01226 } 01227 } 01228 __catch(...) 01229 { 01230 _M_erase(__top); 01231 __throw_exception_again; 01232 } 01233 return __top; 01234 } 01235 01236 template<typename _Key, typename _Val, typename _KeyOfValue, 01237 typename _Compare, typename _Alloc> 01238 void 01239 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01240 _M_erase(_Link_type __x) 01241 { 01242 // Erase without rebalancing. 01243 while (__x != 0) 01244 { 01245 _M_erase(_S_right(__x)); 01246 _Link_type __y = _S_left(__x); 01247 _M_destroy_node(__x); 01248 __x = __y; 01249 } 01250 } 01251 01252 template<typename _Key, typename _Val, typename _KeyOfValue, 01253 typename _Compare, typename _Alloc> 01254 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01255 _Compare, _Alloc>::iterator 01256 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01257 _M_lower_bound(_Link_type __x, _Link_type __y, 01258 const _Key& __k) 01259 { 01260 while (__x != 0) 01261 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01262 __y = __x, __x = _S_left(__x); 01263 else 01264 __x = _S_right(__x); 01265 return iterator(__y); 01266 } 01267 01268 template<typename _Key, typename _Val, typename _KeyOfValue, 01269 typename _Compare, typename _Alloc> 01270 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01271 _Compare, _Alloc>::const_iterator 01272 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01273 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 01274 const _Key& __k) const 01275 { 01276 while (__x != 0) 01277 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01278 __y = __x, __x = _S_left(__x); 01279 else 01280 __x = _S_right(__x); 01281 return const_iterator(__y); 01282 } 01283 01284 template<typename _Key, typename _Val, typename _KeyOfValue, 01285 typename _Compare, typename _Alloc> 01286 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01287 _Compare, _Alloc>::iterator 01288 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01289 _M_upper_bound(_Link_type __x, _Link_type __y, 01290 const _Key& __k) 01291 { 01292 while (__x != 0) 01293 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01294 __y = __x, __x = _S_left(__x); 01295 else 01296 __x = _S_right(__x); 01297 return iterator(__y); 01298 } 01299 01300 template<typename _Key, typename _Val, typename _KeyOfValue, 01301 typename _Compare, typename _Alloc> 01302 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01303 _Compare, _Alloc>::const_iterator 01304 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01305 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 01306 const _Key& __k) const 01307 { 01308 while (__x != 0) 01309 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01310 __y = __x, __x = _S_left(__x); 01311 else 01312 __x = _S_right(__x); 01313 return const_iterator(__y); 01314 } 01315 01316 template<typename _Key, typename _Val, typename _KeyOfValue, 01317 typename _Compare, typename _Alloc> 01318 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01319 _Compare, _Alloc>::iterator, 01320 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01321 _Compare, _Alloc>::iterator> 01322 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01323 equal_range(const _Key& __k) 01324 { 01325 _Link_type __x = _M_begin(); 01326 _Link_type __y = _M_end(); 01327 while (__x != 0) 01328 { 01329 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01330 __x = _S_right(__x); 01331 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01332 __y = __x, __x = _S_left(__x); 01333 else 01334 { 01335 _Link_type __xu(__x), __yu(__y); 01336 __y = __x, __x = _S_left(__x); 01337 __xu = _S_right(__xu); 01338 return pair<iterator, 01339 iterator>(_M_lower_bound(__x, __y, __k), 01340 _M_upper_bound(__xu, __yu, __k)); 01341 } 01342 } 01343 return pair<iterator, iterator>(iterator(__y), 01344 iterator(__y)); 01345 } 01346 01347 template<typename _Key, typename _Val, typename _KeyOfValue, 01348 typename _Compare, typename _Alloc> 01349 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01350 _Compare, _Alloc>::const_iterator, 01351 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01352 _Compare, _Alloc>::const_iterator> 01353 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01354 equal_range(const _Key& __k) const 01355 { 01356 _Const_Link_type __x = _M_begin(); 01357 _Const_Link_type __y = _M_end(); 01358 while (__x != 0) 01359 { 01360 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01361 __x = _S_right(__x); 01362 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01363 __y = __x, __x = _S_left(__x); 01364 else 01365 { 01366 _Const_Link_type __xu(__x), __yu(__y); 01367 __y = __x, __x = _S_left(__x); 01368 __xu = _S_right(__xu); 01369 return pair<const_iterator, 01370 const_iterator>(_M_lower_bound(__x, __y, __k), 01371 _M_upper_bound(__xu, __yu, __k)); 01372 } 01373 } 01374 return pair<const_iterator, const_iterator>(const_iterator(__y), 01375 const_iterator(__y)); 01376 } 01377 01378 template<typename _Key, typename _Val, typename _KeyOfValue, 01379 typename _Compare, typename _Alloc> 01380 void 01381 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01382 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 01383 #if __cplusplus >= 201103L 01384 noexcept(_Alloc_traits::_S_nothrow_swap()) 01385 #endif 01386 { 01387 if (_M_root() == 0) 01388 { 01389 if (__t._M_root() != 0) 01390 { 01391 _M_root() = __t._M_root(); 01392 _M_leftmost() = __t._M_leftmost(); 01393 _M_rightmost() = __t._M_rightmost(); 01394 _M_root()->_M_parent = _M_end(); 01395 01396 __t._M_root() = 0; 01397 __t._M_leftmost() = __t._M_end(); 01398 __t._M_rightmost() = __t._M_end(); 01399 } 01400 } 01401 else if (__t._M_root() == 0) 01402 { 01403 __t._M_root() = _M_root(); 01404 __t._M_leftmost() = _M_leftmost(); 01405 __t._M_rightmost() = _M_rightmost(); 01406 __t._M_root()->_M_parent = __t._M_end(); 01407 01408 _M_root() = 0; 01409 _M_leftmost() = _M_end(); 01410 _M_rightmost() = _M_end(); 01411 } 01412 else 01413 { 01414 std::swap(_M_root(),__t._M_root()); 01415 std::swap(_M_leftmost(),__t._M_leftmost()); 01416 std::swap(_M_rightmost(),__t._M_rightmost()); 01417 01418 _M_root()->_M_parent = _M_end(); 01419 __t._M_root()->_M_parent = __t._M_end(); 01420 } 01421 // No need to swap header's color as it does not change. 01422 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 01423 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 01424 01425 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), 01426 __t._M_get_Node_allocator()); 01427 } 01428 01429 template<typename _Key, typename _Val, typename _KeyOfValue, 01430 typename _Compare, typename _Alloc> 01431 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01432 _Compare, _Alloc>::_Base_ptr, 01433 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01434 _Compare, _Alloc>::_Base_ptr> 01435 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01436 _M_get_insert_unique_pos(const key_type& __k) 01437 { 01438 typedef pair<_Base_ptr, _Base_ptr> _Res; 01439 _Link_type __x = _M_begin(); 01440 _Link_type __y = _M_end(); 01441 bool __comp = true; 01442 while (__x != 0) 01443 { 01444 __y = __x; 01445 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 01446 __x = __comp ? _S_left(__x) : _S_right(__x); 01447 } 01448 iterator __j = iterator(__y); 01449 if (__comp) 01450 { 01451 if (__j == begin()) 01452 return _Res(__x, __y); 01453 else 01454 --__j; 01455 } 01456 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 01457 return _Res(__x, __y); 01458 return _Res(__j._M_node, 0); 01459 } 01460 01461 template<typename _Key, typename _Val, typename _KeyOfValue, 01462 typename _Compare, typename _Alloc> 01463 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01464 _Compare, _Alloc>::_Base_ptr, 01465 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01466 _Compare, _Alloc>::_Base_ptr> 01467 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01468 _M_get_insert_equal_pos(const key_type& __k) 01469 { 01470 typedef pair<_Base_ptr, _Base_ptr> _Res; 01471 _Link_type __x = _M_begin(); 01472 _Link_type __y = _M_end(); 01473 while (__x != 0) 01474 { 01475 __y = __x; 01476 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 01477 _S_left(__x) : _S_right(__x); 01478 } 01479 return _Res(__x, __y); 01480 } 01481 01482 template<typename _Key, typename _Val, typename _KeyOfValue, 01483 typename _Compare, typename _Alloc> 01484 #if __cplusplus >= 201103L 01485 template<typename _Arg> 01486 #endif 01487 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01488 _Compare, _Alloc>::iterator, bool> 01489 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01490 #if __cplusplus >= 201103L 01491 _M_insert_unique(_Arg&& __v) 01492 #else 01493 _M_insert_unique(const _Val& __v) 01494 #endif 01495 { 01496 typedef pair<iterator, bool> _Res; 01497 pair<_Base_ptr, _Base_ptr> __res 01498 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 01499 01500 if (__res.second) 01501 return _Res(_M_insert_(__res.first, __res.second, 01502 _GLIBCXX_FORWARD(_Arg, __v)), 01503 true); 01504 01505 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 01506 } 01507 01508 template<typename _Key, typename _Val, typename _KeyOfValue, 01509 typename _Compare, typename _Alloc> 01510 #if __cplusplus >= 201103L 01511 template<typename _Arg> 01512 #endif 01513 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01514 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01515 #if __cplusplus >= 201103L 01516 _M_insert_equal(_Arg&& __v) 01517 #else 01518 _M_insert_equal(const _Val& __v) 01519 #endif 01520 { 01521 pair<_Base_ptr, _Base_ptr> __res 01522 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 01523 return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v)); 01524 } 01525 01526 template<typename _Key, typename _Val, typename _KeyOfValue, 01527 typename _Compare, typename _Alloc> 01528 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01529 _Compare, _Alloc>::_Base_ptr, 01530 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01531 _Compare, _Alloc>::_Base_ptr> 01532 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01533 _M_get_insert_hint_unique_pos(const_iterator __position, 01534 const key_type& __k) 01535 { 01536 iterator __pos = __position._M_const_cast(); 01537 typedef pair<_Base_ptr, _Base_ptr> _Res; 01538 01539 // end() 01540 if (__pos._M_node == _M_end()) 01541 { 01542 if (size() > 0 01543 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 01544 return _Res(0, _M_rightmost()); 01545 else 01546 return _M_get_insert_unique_pos(__k); 01547 } 01548 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 01549 { 01550 // First, try before... 01551 iterator __before = __pos; 01552 if (__pos._M_node == _M_leftmost()) // begin() 01553 return _Res(_M_leftmost(), _M_leftmost()); 01554 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 01555 { 01556 if (_S_right(__before._M_node) == 0) 01557 return _Res(0, __before._M_node); 01558 else 01559 return _Res(__pos._M_node, __pos._M_node); 01560 } 01561 else 01562 return _M_get_insert_unique_pos(__k); 01563 } 01564 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 01565 { 01566 // ... then try after. 01567 iterator __after = __pos; 01568 if (__pos._M_node == _M_rightmost()) 01569 return _Res(0, _M_rightmost()); 01570 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 01571 { 01572 if (_S_right(__pos._M_node) == 0) 01573 return _Res(0, __pos._M_node); 01574 else 01575 return _Res(__after._M_node, __after._M_node); 01576 } 01577 else 01578 return _M_get_insert_unique_pos(__k); 01579 } 01580 else 01581 // Equivalent keys. 01582 return _Res(__pos._M_node, 0); 01583 } 01584 01585 template<typename _Key, typename _Val, typename _KeyOfValue, 01586 typename _Compare, typename _Alloc> 01587 #if __cplusplus >= 201103L 01588 template<typename _Arg> 01589 #endif 01590 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01591 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01592 #if __cplusplus >= 201103L 01593 _M_insert_unique_(const_iterator __position, _Arg&& __v) 01594 #else 01595 _M_insert_unique_(const_iterator __position, const _Val& __v) 01596 #endif 01597 { 01598 pair<_Base_ptr, _Base_ptr> __res 01599 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 01600 01601 if (__res.second) 01602 return _M_insert_(__res.first, __res.second, 01603 _GLIBCXX_FORWARD(_Arg, __v)); 01604 return iterator(static_cast<_Link_type>(__res.first)); 01605 } 01606 01607 template<typename _Key, typename _Val, typename _KeyOfValue, 01608 typename _Compare, typename _Alloc> 01609 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01610 _Compare, _Alloc>::_Base_ptr, 01611 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01612 _Compare, _Alloc>::_Base_ptr> 01613 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01614 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 01615 { 01616 iterator __pos = __position._M_const_cast(); 01617 typedef pair<_Base_ptr, _Base_ptr> _Res; 01618 01619 // end() 01620 if (__pos._M_node == _M_end()) 01621 { 01622 if (size() > 0 01623 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 01624 return _Res(0, _M_rightmost()); 01625 else 01626 return _M_get_insert_equal_pos(__k); 01627 } 01628 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 01629 { 01630 // First, try before... 01631 iterator __before = __pos; 01632 if (__pos._M_node == _M_leftmost()) // begin() 01633 return _Res(_M_leftmost(), _M_leftmost()); 01634 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 01635 { 01636 if (_S_right(__before._M_node) == 0) 01637 return _Res(0, __before._M_node); 01638 else 01639 return _Res(__pos._M_node, __pos._M_node); 01640 } 01641 else 01642 return _M_get_insert_equal_pos(__k); 01643 } 01644 else 01645 { 01646 // ... then try after. 01647 iterator __after = __pos; 01648 if (__pos._M_node == _M_rightmost()) 01649 return _Res(0, _M_rightmost()); 01650 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 01651 { 01652 if (_S_right(__pos._M_node) == 0) 01653 return _Res(0, __pos._M_node); 01654 else 01655 return _Res(__after._M_node, __after._M_node); 01656 } 01657 else 01658 return _Res(0, 0); 01659 } 01660 } 01661 01662 template<typename _Key, typename _Val, typename _KeyOfValue, 01663 typename _Compare, typename _Alloc> 01664 #if __cplusplus >= 201103L 01665 template<typename _Arg> 01666 #endif 01667 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01668 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01669 #if __cplusplus >= 201103L 01670 _M_insert_equal_(const_iterator __position, _Arg&& __v) 01671 #else 01672 _M_insert_equal_(const_iterator __position, const _Val& __v) 01673 #endif 01674 { 01675 pair<_Base_ptr, _Base_ptr> __res 01676 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 01677 01678 if (__res.second) 01679 return _M_insert_(__res.first, __res.second, 01680 _GLIBCXX_FORWARD(_Arg, __v)); 01681 01682 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 01683 } 01684 01685 #if __cplusplus >= 201103L 01686 template<typename _Key, typename _Val, typename _KeyOfValue, 01687 typename _Compare, typename _Alloc> 01688 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01689 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01690 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 01691 { 01692 bool __insert_left = (__x != 0 || __p == _M_end() 01693 || _M_impl._M_key_compare(_S_key(__z), 01694 _S_key(__p))); 01695 01696 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01697 this->_M_impl._M_header); 01698 ++_M_impl._M_node_count; 01699 return iterator(__z); 01700 } 01701 01702 template<typename _Key, typename _Val, typename _KeyOfValue, 01703 typename _Compare, typename _Alloc> 01704 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01705 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01706 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 01707 { 01708 bool __insert_left = (__p == _M_end() 01709 || !_M_impl._M_key_compare(_S_key(__p), 01710 _S_key(__z))); 01711 01712 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01713 this->_M_impl._M_header); 01714 ++_M_impl._M_node_count; 01715 return iterator(__z); 01716 } 01717 01718 template<typename _Key, typename _Val, typename _KeyOfValue, 01719 typename _Compare, typename _Alloc> 01720 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01721 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01722 _M_insert_equal_lower_node(_Link_type __z) 01723 { 01724 _Link_type __x = _M_begin(); 01725 _Link_type __y = _M_end(); 01726 while (__x != 0) 01727 { 01728 __y = __x; 01729 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 01730 _S_left(__x) : _S_right(__x); 01731 } 01732 return _M_insert_lower_node(__y, __z); 01733 } 01734 01735 template<typename _Key, typename _Val, typename _KeyOfValue, 01736 typename _Compare, typename _Alloc> 01737 template<typename... _Args> 01738 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01739 _Compare, _Alloc>::iterator, bool> 01740 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01741 _M_emplace_unique(_Args&&... __args) 01742 { 01743 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 01744 01745 __try 01746 { 01747 typedef pair<iterator, bool> _Res; 01748 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 01749 if (__res.second) 01750 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 01751 01752 _M_destroy_node(__z); 01753 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 01754 } 01755 __catch(...) 01756 { 01757 _M_destroy_node(__z); 01758 __throw_exception_again; 01759 } 01760 } 01761 01762 template<typename _Key, typename _Val, typename _KeyOfValue, 01763 typename _Compare, typename _Alloc> 01764 template<typename... _Args> 01765 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01766 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01767 _M_emplace_equal(_Args&&... __args) 01768 { 01769 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 01770 01771 __try 01772 { 01773 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 01774 return _M_insert_node(__res.first, __res.second, __z); 01775 } 01776 __catch(...) 01777 { 01778 _M_destroy_node(__z); 01779 __throw_exception_again; 01780 } 01781 } 01782 01783 template<typename _Key, typename _Val, typename _KeyOfValue, 01784 typename _Compare, typename _Alloc> 01785 template<typename... _Args> 01786 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01787 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01788 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 01789 { 01790 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 01791 01792 __try 01793 { 01794 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 01795 01796 if (__res.second) 01797 return _M_insert_node(__res.first, __res.second, __z); 01798 01799 _M_destroy_node(__z); 01800 return iterator(static_cast<_Link_type>(__res.first)); 01801 } 01802 __catch(...) 01803 { 01804 _M_destroy_node(__z); 01805 __throw_exception_again; 01806 } 01807 } 01808 01809 template<typename _Key, typename _Val, typename _KeyOfValue, 01810 typename _Compare, typename _Alloc> 01811 template<typename... _Args> 01812 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01813 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01814 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 01815 { 01816 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 01817 01818 __try 01819 { 01820 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 01821 01822 if (__res.second) 01823 return _M_insert_node(__res.first, __res.second, __z); 01824 01825 return _M_insert_equal_lower_node(__z); 01826 } 01827 __catch(...) 01828 { 01829 _M_destroy_node(__z); 01830 __throw_exception_again; 01831 } 01832 } 01833 #endif 01834 01835 template<typename _Key, typename _Val, typename _KoV, 01836 typename _Cmp, typename _Alloc> 01837 template<class _II> 01838 void 01839 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 01840 _M_insert_unique(_II __first, _II __last) 01841 { 01842 for (; __first != __last; ++__first) 01843 _M_insert_unique_(end(), *__first); 01844 } 01845 01846 template<typename _Key, typename _Val, typename _KoV, 01847 typename _Cmp, typename _Alloc> 01848 template<class _II> 01849 void 01850 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 01851 _M_insert_equal(_II __first, _II __last) 01852 { 01853 for (; __first != __last; ++__first) 01854 _M_insert_equal_(end(), *__first); 01855 } 01856 01857 template<typename _Key, typename _Val, typename _KeyOfValue, 01858 typename _Compare, typename _Alloc> 01859 void 01860 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01861 _M_erase_aux(const_iterator __position) 01862 { 01863 _Link_type __y = 01864 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 01865 (const_cast<_Base_ptr>(__position._M_node), 01866 this->_M_impl._M_header)); 01867 _M_destroy_node(__y); 01868 --_M_impl._M_node_count; 01869 } 01870 01871 template<typename _Key, typename _Val, typename _KeyOfValue, 01872 typename _Compare, typename _Alloc> 01873 void 01874 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01875 _M_erase_aux(const_iterator __first, const_iterator __last) 01876 { 01877 if (__first == begin() && __last == end()) 01878 clear(); 01879 else 01880 while (__first != __last) 01881 erase(__first++); 01882 } 01883 01884 template<typename _Key, typename _Val, typename _KeyOfValue, 01885 typename _Compare, typename _Alloc> 01886 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 01887 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01888 erase(const _Key& __x) 01889 { 01890 pair<iterator, iterator> __p = equal_range(__x); 01891 const size_type __old_size = size(); 01892 erase(__p.first, __p.second); 01893 return __old_size - size(); 01894 } 01895 01896 template<typename _Key, typename _Val, typename _KeyOfValue, 01897 typename _Compare, typename _Alloc> 01898 void 01899 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01900 erase(const _Key* __first, const _Key* __last) 01901 { 01902 while (__first != __last) 01903 erase(*__first++); 01904 } 01905 01906 template<typename _Key, typename _Val, typename _KeyOfValue, 01907 typename _Compare, typename _Alloc> 01908 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01909 _Compare, _Alloc>::iterator 01910 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01911 find(const _Key& __k) 01912 { 01913 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 01914 return (__j == end() 01915 || _M_impl._M_key_compare(__k, 01916 _S_key(__j._M_node))) ? end() : __j; 01917 } 01918 01919 template<typename _Key, typename _Val, typename _KeyOfValue, 01920 typename _Compare, typename _Alloc> 01921 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01922 _Compare, _Alloc>::const_iterator 01923 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01924 find(const _Key& __k) const 01925 { 01926 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 01927 return (__j == end() 01928 || _M_impl._M_key_compare(__k, 01929 _S_key(__j._M_node))) ? end() : __j; 01930 } 01931 01932 template<typename _Key, typename _Val, typename _KeyOfValue, 01933 typename _Compare, typename _Alloc> 01934 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 01935 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01936 count(const _Key& __k) const 01937 { 01938 pair<const_iterator, const_iterator> __p = equal_range(__k); 01939 const size_type __n = std::distance(__p.first, __p.second); 01940 return __n; 01941 } 01942 01943 _GLIBCXX_PURE unsigned int 01944 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 01945 const _Rb_tree_node_base* __root) throw (); 01946 01947 template<typename _Key, typename _Val, typename _KeyOfValue, 01948 typename _Compare, typename _Alloc> 01949 bool 01950 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 01951 { 01952 if (_M_impl._M_node_count == 0 || begin() == end()) 01953 return _M_impl._M_node_count == 0 && begin() == end() 01954 && this->_M_impl._M_header._M_left == _M_end() 01955 && this->_M_impl._M_header._M_right == _M_end(); 01956 01957 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 01958 for (const_iterator __it = begin(); __it != end(); ++__it) 01959 { 01960 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 01961 _Const_Link_type __L = _S_left(__x); 01962 _Const_Link_type __R = _S_right(__x); 01963 01964 if (__x->_M_color == _S_red) 01965 if ((__L && __L->_M_color == _S_red) 01966 || (__R && __R->_M_color == _S_red)) 01967 return false; 01968 01969 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 01970 return false; 01971 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 01972 return false; 01973 01974 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 01975 return false; 01976 } 01977 01978 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 01979 return false; 01980 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 01981 return false; 01982 return true; 01983 } 01984 01985 _GLIBCXX_END_NAMESPACE_VERSION 01986 } // namespace 01987 01988 #endif