00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060 #ifndef _STL_TREE_H
00061 #define _STL_TREE_H 1
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
00068 namespace std _GLIBCXX_VISIBILITY(default)
00069 {
00070 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088 enum _Rb_tree_color { _S_red = false, _S_black = true };
00089
00090 struct _Rb_tree_node_base
00091 {
00092 typedef _Rb_tree_node_base* _Base_ptr;
00093 typedef const _Rb_tree_node_base* _Const_Base_ptr;
00094
00095 _Rb_tree_color _M_color;
00096 _Base_ptr _M_parent;
00097 _Base_ptr _M_left;
00098 _Base_ptr _M_right;
00099
00100 static _Base_ptr
00101 _S_minimum(_Base_ptr __x)
00102 {
00103 while (__x->_M_left != 0) __x = __x->_M_left;
00104 return __x;
00105 }
00106
00107 static _Const_Base_ptr
00108 _S_minimum(_Const_Base_ptr __x)
00109 {
00110 while (__x->_M_left != 0) __x = __x->_M_left;
00111 return __x;
00112 }
00113
00114 static _Base_ptr
00115 _S_maximum(_Base_ptr __x)
00116 {
00117 while (__x->_M_right != 0) __x = __x->_M_right;
00118 return __x;
00119 }
00120
00121 static _Const_Base_ptr
00122 _S_maximum(_Const_Base_ptr __x)
00123 {
00124 while (__x->_M_right != 0) __x = __x->_M_right;
00125 return __x;
00126 }
00127 };
00128
00129 template<typename _Val>
00130 struct _Rb_tree_node : public _Rb_tree_node_base
00131 {
00132 typedef _Rb_tree_node<_Val>* _Link_type;
00133 _Val _M_value_field;
00134
00135 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00136 template<typename... _Args>
00137 _Rb_tree_node(_Args&&... __args)
00138 : _Rb_tree_node_base(),
00139 _M_value_field(std::forward<_Args>(__args)...) { }
00140 #endif
00141 };
00142
00143 _GLIBCXX_PURE _Rb_tree_node_base*
00144 _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
00145
00146 _GLIBCXX_PURE const _Rb_tree_node_base*
00147 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
00148
00149 _GLIBCXX_PURE _Rb_tree_node_base*
00150 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
00151
00152 _GLIBCXX_PURE const _Rb_tree_node_base*
00153 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
00154
00155 template<typename _Tp>
00156 struct _Rb_tree_iterator
00157 {
00158 typedef _Tp value_type;
00159 typedef _Tp& reference;
00160 typedef _Tp* pointer;
00161
00162 typedef bidirectional_iterator_tag iterator_category;
00163 typedef ptrdiff_t difference_type;
00164
00165 typedef _Rb_tree_iterator<_Tp> _Self;
00166 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
00167 typedef _Rb_tree_node<_Tp>* _Link_type;
00168
00169 _Rb_tree_iterator()
00170 : _M_node() { }
00171
00172 explicit
00173 _Rb_tree_iterator(_Link_type __x)
00174 : _M_node(__x) { }
00175
00176 reference
00177 operator*() const
00178 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00179
00180 pointer
00181 operator->() const
00182 { return std::__addressof(static_cast<_Link_type>
00183 (_M_node)->_M_value_field); }
00184
00185 _Self&
00186 operator++()
00187 {
00188 _M_node = _Rb_tree_increment(_M_node);
00189 return *this;
00190 }
00191
00192 _Self
00193 operator++(int)
00194 {
00195 _Self __tmp = *this;
00196 _M_node = _Rb_tree_increment(_M_node);
00197 return __tmp;
00198 }
00199
00200 _Self&
00201 operator--()
00202 {
00203 _M_node = _Rb_tree_decrement(_M_node);
00204 return *this;
00205 }
00206
00207 _Self
00208 operator--(int)
00209 {
00210 _Self __tmp = *this;
00211 _M_node = _Rb_tree_decrement(_M_node);
00212 return __tmp;
00213 }
00214
00215 bool
00216 operator==(const _Self& __x) const
00217 { return _M_node == __x._M_node; }
00218
00219 bool
00220 operator!=(const _Self& __x) const
00221 { return _M_node != __x._M_node; }
00222
00223 _Base_ptr _M_node;
00224 };
00225
00226 template<typename _Tp>
00227 struct _Rb_tree_const_iterator
00228 {
00229 typedef _Tp value_type;
00230 typedef const _Tp& reference;
00231 typedef const _Tp* pointer;
00232
00233 typedef _Rb_tree_iterator<_Tp> iterator;
00234
00235 typedef bidirectional_iterator_tag iterator_category;
00236 typedef ptrdiff_t difference_type;
00237
00238 typedef _Rb_tree_const_iterator<_Tp> _Self;
00239 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
00240 typedef const _Rb_tree_node<_Tp>* _Link_type;
00241
00242 _Rb_tree_const_iterator()
00243 : _M_node() { }
00244
00245 explicit
00246 _Rb_tree_const_iterator(_Link_type __x)
00247 : _M_node(__x) { }
00248
00249 _Rb_tree_const_iterator(const iterator& __it)
00250 : _M_node(__it._M_node) { }
00251
00252 iterator
00253 _M_const_cast() const
00254 { return iterator(static_cast<typename iterator::_Link_type>
00255 (const_cast<typename iterator::_Base_ptr>(_M_node))); }
00256
00257 reference
00258 operator*() const
00259 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00260
00261 pointer
00262 operator->() const
00263 { return std::__addressof(static_cast<_Link_type>
00264 (_M_node)->_M_value_field); }
00265
00266 _Self&
00267 operator++()
00268 {
00269 _M_node = _Rb_tree_increment(_M_node);
00270 return *this;
00271 }
00272
00273 _Self
00274 operator++(int)
00275 {
00276 _Self __tmp = *this;
00277 _M_node = _Rb_tree_increment(_M_node);
00278 return __tmp;
00279 }
00280
00281 _Self&
00282 operator--()
00283 {
00284 _M_node = _Rb_tree_decrement(_M_node);
00285 return *this;
00286 }
00287
00288 _Self
00289 operator--(int)
00290 {
00291 _Self __tmp = *this;
00292 _M_node = _Rb_tree_decrement(_M_node);
00293 return __tmp;
00294 }
00295
00296 bool
00297 operator==(const _Self& __x) const
00298 { return _M_node == __x._M_node; }
00299
00300 bool
00301 operator!=(const _Self& __x) const
00302 { return _M_node != __x._M_node; }
00303
00304 _Base_ptr _M_node;
00305 };
00306
00307 template<typename _Val>
00308 inline bool
00309 operator==(const _Rb_tree_iterator<_Val>& __x,
00310 const _Rb_tree_const_iterator<_Val>& __y)
00311 { return __x._M_node == __y._M_node; }
00312
00313 template<typename _Val>
00314 inline bool
00315 operator!=(const _Rb_tree_iterator<_Val>& __x,
00316 const _Rb_tree_const_iterator<_Val>& __y)
00317 { return __x._M_node != __y._M_node; }
00318
00319 void
00320 _Rb_tree_insert_and_rebalance(const bool __insert_left,
00321 _Rb_tree_node_base* __x,
00322 _Rb_tree_node_base* __p,
00323 _Rb_tree_node_base& __header) throw ();
00324
00325 _Rb_tree_node_base*
00326 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
00327 _Rb_tree_node_base& __header) throw ();
00328
00329
00330 template<typename _Key, typename _Val, typename _KeyOfValue,
00331 typename _Compare, typename _Alloc = allocator<_Val> >
00332 class _Rb_tree
00333 {
00334 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
00335 _Node_allocator;
00336
00337 protected:
00338 typedef _Rb_tree_node_base* _Base_ptr;
00339 typedef const _Rb_tree_node_base* _Const_Base_ptr;
00340
00341 public:
00342 typedef _Key key_type;
00343 typedef _Val value_type;
00344 typedef value_type* pointer;
00345 typedef const value_type* const_pointer;
00346 typedef value_type& reference;
00347 typedef const value_type& const_reference;
00348 typedef _Rb_tree_node<_Val>* _Link_type;
00349 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
00350 typedef size_t size_type;
00351 typedef ptrdiff_t difference_type;
00352 typedef _Alloc allocator_type;
00353
00354 _Node_allocator&
00355 _M_get_Node_allocator()
00356 { return *static_cast<_Node_allocator*>(&this->_M_impl); }
00357
00358 const _Node_allocator&
00359 _M_get_Node_allocator() const
00360 { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
00361
00362 allocator_type
00363 get_allocator() const
00364 { return allocator_type(_M_get_Node_allocator()); }
00365
00366 protected:
00367 _Link_type
00368 _M_get_node()
00369 { return _M_impl._Node_allocator::allocate(1); }
00370
00371 void
00372 _M_put_node(_Link_type __p)
00373 { _M_impl._Node_allocator::deallocate(__p, 1); }
00374
00375 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00376 _Link_type
00377 _M_create_node(const value_type& __x)
00378 {
00379 _Link_type __tmp = _M_get_node();
00380 __try
00381 { get_allocator().construct
00382 (std::__addressof(__tmp->_M_value_field), __x); }
00383 __catch(...)
00384 {
00385 _M_put_node(__tmp);
00386 __throw_exception_again;
00387 }
00388 return __tmp;
00389 }
00390
00391 void
00392 _M_destroy_node(_Link_type __p)
00393 {
00394 get_allocator().destroy(std::__addressof(__p->_M_value_field));
00395 _M_put_node(__p);
00396 }
00397 #else
00398 template<typename... _Args>
00399 _Link_type
00400 _M_create_node(_Args&&... __args)
00401 {
00402 _Link_type __tmp = _M_get_node();
00403 __try
00404 {
00405 _M_get_Node_allocator().construct(__tmp,
00406 std::forward<_Args>(__args)...);
00407 }
00408 __catch(...)
00409 {
00410 _M_put_node(__tmp);
00411 __throw_exception_again;
00412 }
00413 return __tmp;
00414 }
00415
00416 void
00417 _M_destroy_node(_Link_type __p)
00418 {
00419 _M_get_Node_allocator().destroy(__p);
00420 _M_put_node(__p);
00421 }
00422 #endif
00423
00424 _Link_type
00425 _M_clone_node(_Const_Link_type __x)
00426 {
00427 _Link_type __tmp = _M_create_node(__x->_M_value_field);
00428 __tmp->_M_color = __x->_M_color;
00429 __tmp->_M_left = 0;
00430 __tmp->_M_right = 0;
00431 return __tmp;
00432 }
00433
00434 protected:
00435 template<typename _Key_compare,
00436 bool _Is_pod_comparator = __is_pod(_Key_compare)>
00437 struct _Rb_tree_impl : public _Node_allocator
00438 {
00439 _Key_compare _M_key_compare;
00440 _Rb_tree_node_base _M_header;
00441 size_type _M_node_count;
00442
00443 _Rb_tree_impl()
00444 : _Node_allocator(), _M_key_compare(), _M_header(),
00445 _M_node_count(0)
00446 { _M_initialize(); }
00447
00448 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
00449 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
00450 _M_node_count(0)
00451 { _M_initialize(); }
00452
00453 private:
00454 void
00455 _M_initialize()
00456 {
00457 this->_M_header._M_color = _S_red;
00458 this->_M_header._M_parent = 0;
00459 this->_M_header._M_left = &this->_M_header;
00460 this->_M_header._M_right = &this->_M_header;
00461 }
00462 };
00463
00464 _Rb_tree_impl<_Compare> _M_impl;
00465
00466 protected:
00467 _Base_ptr&
00468 _M_root()
00469 { return this->_M_impl._M_header._M_parent; }
00470
00471 _Const_Base_ptr
00472 _M_root() const
00473 { return this->_M_impl._M_header._M_parent; }
00474
00475 _Base_ptr&
00476 _M_leftmost()
00477 { return this->_M_impl._M_header._M_left; }
00478
00479 _Const_Base_ptr
00480 _M_leftmost() const
00481 { return this->_M_impl._M_header._M_left; }
00482
00483 _Base_ptr&
00484 _M_rightmost()
00485 { return this->_M_impl._M_header._M_right; }
00486
00487 _Const_Base_ptr
00488 _M_rightmost() const
00489 { return this->_M_impl._M_header._M_right; }
00490
00491 _Link_type
00492 _M_begin()
00493 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00494
00495 _Const_Link_type
00496 _M_begin() const
00497 {
00498 return static_cast<_Const_Link_type>
00499 (this->_M_impl._M_header._M_parent);
00500 }
00501
00502 _Link_type
00503 _M_end()
00504 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00505
00506 _Const_Link_type
00507 _M_end() const
00508 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00509
00510 static const_reference
00511 _S_value(_Const_Link_type __x)
00512 { return __x->_M_value_field; }
00513
00514 static const _Key&
00515 _S_key(_Const_Link_type __x)
00516 { return _KeyOfValue()(_S_value(__x)); }
00517
00518 static _Link_type
00519 _S_left(_Base_ptr __x)
00520 { return static_cast<_Link_type>(__x->_M_left); }
00521
00522 static _Const_Link_type
00523 _S_left(_Const_Base_ptr __x)
00524 { return static_cast<_Const_Link_type>(__x->_M_left); }
00525
00526 static _Link_type
00527 _S_right(_Base_ptr __x)
00528 { return static_cast<_Link_type>(__x->_M_right); }
00529
00530 static _Const_Link_type
00531 _S_right(_Const_Base_ptr __x)
00532 { return static_cast<_Const_Link_type>(__x->_M_right); }
00533
00534 static const_reference
00535 _S_value(_Const_Base_ptr __x)
00536 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
00537
00538 static const _Key&
00539 _S_key(_Const_Base_ptr __x)
00540 { return _KeyOfValue()(_S_value(__x)); }
00541
00542 static _Base_ptr
00543 _S_minimum(_Base_ptr __x)
00544 { return _Rb_tree_node_base::_S_minimum(__x); }
00545
00546 static _Const_Base_ptr
00547 _S_minimum(_Const_Base_ptr __x)
00548 { return _Rb_tree_node_base::_S_minimum(__x); }
00549
00550 static _Base_ptr
00551 _S_maximum(_Base_ptr __x)
00552 { return _Rb_tree_node_base::_S_maximum(__x); }
00553
00554 static _Const_Base_ptr
00555 _S_maximum(_Const_Base_ptr __x)
00556 { return _Rb_tree_node_base::_S_maximum(__x); }
00557
00558 public:
00559 typedef _Rb_tree_iterator<value_type> iterator;
00560 typedef _Rb_tree_const_iterator<value_type> const_iterator;
00561
00562 typedef std::reverse_iterator<iterator> reverse_iterator;
00563 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00564
00565 private:
00566 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00567 template<typename _Arg>
00568 iterator
00569 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v);
00570
00571 template<typename _Arg>
00572 iterator
00573 _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
00574
00575 template<typename _Arg>
00576 iterator
00577 _M_insert_equal_lower(_Arg&& __x);
00578 #else
00579 iterator
00580 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
00581 const value_type& __v);
00582
00583
00584
00585 iterator
00586 _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
00587
00588 iterator
00589 _M_insert_equal_lower(const value_type& __x);
00590 #endif
00591
00592 _Link_type
00593 _M_copy(_Const_Link_type __x, _Link_type __p);
00594
00595 void
00596 _M_erase(_Link_type __x);
00597
00598 iterator
00599 _M_lower_bound(_Link_type __x, _Link_type __y,
00600 const _Key& __k);
00601
00602 const_iterator
00603 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
00604 const _Key& __k) const;
00605
00606 iterator
00607 _M_upper_bound(_Link_type __x, _Link_type __y,
00608 const _Key& __k);
00609
00610 const_iterator
00611 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
00612 const _Key& __k) const;
00613
00614 public:
00615
00616 _Rb_tree() { }
00617
00618 _Rb_tree(const _Compare& __comp,
00619 const allocator_type& __a = allocator_type())
00620 : _M_impl(__comp, __a) { }
00621
00622 _Rb_tree(const _Rb_tree& __x)
00623 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
00624 {
00625 if (__x._M_root() != 0)
00626 {
00627 _M_root() = _M_copy(__x._M_begin(), _M_end());
00628 _M_leftmost() = _S_minimum(_M_root());
00629 _M_rightmost() = _S_maximum(_M_root());
00630 _M_impl._M_node_count = __x._M_impl._M_node_count;
00631 }
00632 }
00633
00634 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00635 _Rb_tree(_Rb_tree&& __x);
00636 #endif
00637
00638 ~_Rb_tree()
00639 { _M_erase(_M_begin()); }
00640
00641 _Rb_tree&
00642 operator=(const _Rb_tree& __x);
00643
00644
00645 _Compare
00646 key_comp() const
00647 { return _M_impl._M_key_compare; }
00648
00649 iterator
00650 begin()
00651 {
00652 return iterator(static_cast<_Link_type>
00653 (this->_M_impl._M_header._M_left));
00654 }
00655
00656 const_iterator
00657 begin() const
00658 {
00659 return const_iterator(static_cast<_Const_Link_type>
00660 (this->_M_impl._M_header._M_left));
00661 }
00662
00663 iterator
00664 end()
00665 { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
00666
00667 const_iterator
00668 end() const
00669 {
00670 return const_iterator(static_cast<_Const_Link_type>
00671 (&this->_M_impl._M_header));
00672 }
00673
00674 reverse_iterator
00675 rbegin()
00676 { return reverse_iterator(end()); }
00677
00678 const_reverse_iterator
00679 rbegin() const
00680 { return const_reverse_iterator(end()); }
00681
00682 reverse_iterator
00683 rend()
00684 { return reverse_iterator(begin()); }
00685
00686 const_reverse_iterator
00687 rend() const
00688 { return const_reverse_iterator(begin()); }
00689
00690 bool
00691 empty() const
00692 { return _M_impl._M_node_count == 0; }
00693
00694 size_type
00695 size() const
00696 { return _M_impl._M_node_count; }
00697
00698 size_type
00699 max_size() const
00700 { return _M_get_Node_allocator().max_size(); }
00701
00702 void
00703 swap(_Rb_tree& __t);
00704
00705
00706 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00707 template<typename _Arg>
00708 pair<iterator, bool>
00709 _M_insert_unique(_Arg&& __x);
00710
00711 template<typename _Arg>
00712 iterator
00713 _M_insert_equal(_Arg&& __x);
00714
00715 template<typename _Arg>
00716 iterator
00717 _M_insert_unique_(const_iterator __position, _Arg&& __x);
00718
00719 template<typename _Arg>
00720 iterator
00721 _M_insert_equal_(const_iterator __position, _Arg&& __x);
00722 #else
00723 pair<iterator, bool>
00724 _M_insert_unique(const value_type& __x);
00725
00726 iterator
00727 _M_insert_equal(const value_type& __x);
00728
00729 iterator
00730 _M_insert_unique_(const_iterator __position, const value_type& __x);
00731
00732 iterator
00733 _M_insert_equal_(const_iterator __position, const value_type& __x);
00734 #endif
00735
00736 template<typename _InputIterator>
00737 void
00738 _M_insert_unique(_InputIterator __first, _InputIterator __last);
00739
00740 template<typename _InputIterator>
00741 void
00742 _M_insert_equal(_InputIterator __first, _InputIterator __last);
00743
00744 private:
00745 void
00746 _M_erase_aux(const_iterator __position);
00747
00748 void
00749 _M_erase_aux(const_iterator __first, const_iterator __last);
00750
00751 public:
00752 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00753
00754
00755 iterator
00756 erase(const_iterator __position)
00757 {
00758 const_iterator __result = __position;
00759 ++__result;
00760 _M_erase_aux(__position);
00761 return __result._M_const_cast();
00762 }
00763 #else
00764 void
00765 erase(iterator __position)
00766 { _M_erase_aux(__position); }
00767
00768 void
00769 erase(const_iterator __position)
00770 { _M_erase_aux(__position); }
00771 #endif
00772 size_type
00773 erase(const key_type& __x);
00774
00775 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00776
00777
00778 iterator
00779 erase(const_iterator __first, const_iterator __last)
00780 {
00781 _M_erase_aux(__first, __last);
00782 return __last._M_const_cast();
00783 }
00784 #else
00785 void
00786 erase(iterator __first, iterator __last)
00787 { _M_erase_aux(__first, __last); }
00788
00789 void
00790 erase(const_iterator __first, const_iterator __last)
00791 { _M_erase_aux(__first, __last); }
00792 #endif
00793 void
00794 erase(const key_type* __first, const key_type* __last);
00795
00796 void
00797 clear()
00798 {
00799 _M_erase(_M_begin());
00800 _M_leftmost() = _M_end();
00801 _M_root() = 0;
00802 _M_rightmost() = _M_end();
00803 _M_impl._M_node_count = 0;
00804 }
00805
00806
00807 iterator
00808 find(const key_type& __k);
00809
00810 const_iterator
00811 find(const key_type& __k) const;
00812
00813 size_type
00814 count(const key_type& __k) const;
00815
00816 iterator
00817 lower_bound(const key_type& __k)
00818 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
00819
00820 const_iterator
00821 lower_bound(const key_type& __k) const
00822 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
00823
00824 iterator
00825 upper_bound(const key_type& __k)
00826 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
00827
00828 const_iterator
00829 upper_bound(const key_type& __k) const
00830 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
00831
00832 pair<iterator, iterator>
00833 equal_range(const key_type& __k);
00834
00835 pair<const_iterator, const_iterator>
00836 equal_range(const key_type& __k) const;
00837
00838
00839 bool
00840 __rb_verify() const;
00841 };
00842
00843 template<typename _Key, typename _Val, typename _KeyOfValue,
00844 typename _Compare, typename _Alloc>
00845 inline bool
00846 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00847 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00848 {
00849 return __x.size() == __y.size()
00850 && std::equal(__x.begin(), __x.end(), __y.begin());
00851 }
00852
00853 template<typename _Key, typename _Val, typename _KeyOfValue,
00854 typename _Compare, typename _Alloc>
00855 inline bool
00856 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00857 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00858 {
00859 return std::lexicographical_compare(__x.begin(), __x.end(),
00860 __y.begin(), __y.end());
00861 }
00862
00863 template<typename _Key, typename _Val, typename _KeyOfValue,
00864 typename _Compare, typename _Alloc>
00865 inline bool
00866 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00867 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00868 { return !(__x == __y); }
00869
00870 template<typename _Key, typename _Val, typename _KeyOfValue,
00871 typename _Compare, typename _Alloc>
00872 inline bool
00873 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00874 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00875 { return __y < __x; }
00876
00877 template<typename _Key, typename _Val, typename _KeyOfValue,
00878 typename _Compare, typename _Alloc>
00879 inline bool
00880 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00881 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00882 { return !(__y < __x); }
00883
00884 template<typename _Key, typename _Val, typename _KeyOfValue,
00885 typename _Compare, typename _Alloc>
00886 inline bool
00887 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00888 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00889 { return !(__x < __y); }
00890
00891 template<typename _Key, typename _Val, typename _KeyOfValue,
00892 typename _Compare, typename _Alloc>
00893 inline void
00894 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00895 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00896 { __x.swap(__y); }
00897
00898 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00899 template<typename _Key, typename _Val, typename _KeyOfValue,
00900 typename _Compare, typename _Alloc>
00901 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00902 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
00903 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
00904 {
00905 if (__x._M_root() != 0)
00906 {
00907 _M_root() = __x._M_root();
00908 _M_leftmost() = __x._M_leftmost();
00909 _M_rightmost() = __x._M_rightmost();
00910 _M_root()->_M_parent = _M_end();
00911
00912 __x._M_root() = 0;
00913 __x._M_leftmost() = __x._M_end();
00914 __x._M_rightmost() = __x._M_end();
00915
00916 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
00917 __x._M_impl._M_node_count = 0;
00918 }
00919 }
00920 #endif
00921
00922 template<typename _Key, typename _Val, typename _KeyOfValue,
00923 typename _Compare, typename _Alloc>
00924 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00925 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00926 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00927 {
00928 if (this != &__x)
00929 {
00930
00931 clear();
00932 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00933 if (__x._M_root() != 0)
00934 {
00935 _M_root() = _M_copy(__x._M_begin(), _M_end());
00936 _M_leftmost() = _S_minimum(_M_root());
00937 _M_rightmost() = _S_maximum(_M_root());
00938 _M_impl._M_node_count = __x._M_impl._M_node_count;
00939 }
00940 }
00941 return *this;
00942 }
00943
00944 template<typename _Key, typename _Val, typename _KeyOfValue,
00945 typename _Compare, typename _Alloc>
00946 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00947 template<typename _Arg>
00948 #endif
00949 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00950 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00951 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00952 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v)
00953 #else
00954 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
00955 #endif
00956 {
00957 bool __insert_left = (__x != 0 || __p == _M_end()
00958 || _M_impl._M_key_compare(_KeyOfValue()(__v),
00959 _S_key(__p)));
00960
00961 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
00962
00963 _Rb_tree_insert_and_rebalance(__insert_left, __z,
00964 const_cast<_Base_ptr>(__p),
00965 this->_M_impl._M_header);
00966 ++_M_impl._M_node_count;
00967 return iterator(__z);
00968 }
00969
00970 template<typename _Key, typename _Val, typename _KeyOfValue,
00971 typename _Compare, typename _Alloc>
00972 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00973 template<typename _Arg>
00974 #endif
00975 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00976 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00977 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00978 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
00979 #else
00980 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
00981 #endif
00982 {
00983 bool __insert_left = (__x != 0 || __p == _M_end()
00984 || !_M_impl._M_key_compare(_S_key(__p),
00985 _KeyOfValue()(__v)));
00986
00987 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
00988
00989 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
00990 this->_M_impl._M_header);
00991 ++_M_impl._M_node_count;
00992 return iterator(__z);
00993 }
00994
00995 template<typename _Key, typename _Val, typename _KeyOfValue,
00996 typename _Compare, typename _Alloc>
00997 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00998 template<typename _Arg>
00999 #endif
01000 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01001 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01002 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01003 _M_insert_equal_lower(_Arg&& __v)
01004 #else
01005 _M_insert_equal_lower(const _Val& __v)
01006 #endif
01007 {
01008 _Link_type __x = _M_begin();
01009 _Link_type __y = _M_end();
01010 while (__x != 0)
01011 {
01012 __y = __x;
01013 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
01014 _S_left(__x) : _S_right(__x);
01015 }
01016 return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
01017 }
01018
01019 template<typename _Key, typename _Val, typename _KoV,
01020 typename _Compare, typename _Alloc>
01021 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01022 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01023 _M_copy(_Const_Link_type __x, _Link_type __p)
01024 {
01025
01026 _Link_type __top = _M_clone_node(__x);
01027 __top->_M_parent = __p;
01028
01029 __try
01030 {
01031 if (__x->_M_right)
01032 __top->_M_right = _M_copy(_S_right(__x), __top);
01033 __p = __top;
01034 __x = _S_left(__x);
01035
01036 while (__x != 0)
01037 {
01038 _Link_type __y = _M_clone_node(__x);
01039 __p->_M_left = __y;
01040 __y->_M_parent = __p;
01041 if (__x->_M_right)
01042 __y->_M_right = _M_copy(_S_right(__x), __y);
01043 __p = __y;
01044 __x = _S_left(__x);
01045 }
01046 }
01047 __catch(...)
01048 {
01049 _M_erase(__top);
01050 __throw_exception_again;
01051 }
01052 return __top;
01053 }
01054
01055 template<typename _Key, typename _Val, typename _KeyOfValue,
01056 typename _Compare, typename _Alloc>
01057 void
01058 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01059 _M_erase(_Link_type __x)
01060 {
01061
01062 while (__x != 0)
01063 {
01064 _M_erase(_S_right(__x));
01065 _Link_type __y = _S_left(__x);
01066 _M_destroy_node(__x);
01067 __x = __y;
01068 }
01069 }
01070
01071 template<typename _Key, typename _Val, typename _KeyOfValue,
01072 typename _Compare, typename _Alloc>
01073 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01074 _Compare, _Alloc>::iterator
01075 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01076 _M_lower_bound(_Link_type __x, _Link_type __y,
01077 const _Key& __k)
01078 {
01079 while (__x != 0)
01080 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01081 __y = __x, __x = _S_left(__x);
01082 else
01083 __x = _S_right(__x);
01084 return iterator(__y);
01085 }
01086
01087 template<typename _Key, typename _Val, typename _KeyOfValue,
01088 typename _Compare, typename _Alloc>
01089 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01090 _Compare, _Alloc>::const_iterator
01091 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01092 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
01093 const _Key& __k) const
01094 {
01095 while (__x != 0)
01096 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01097 __y = __x, __x = _S_left(__x);
01098 else
01099 __x = _S_right(__x);
01100 return const_iterator(__y);
01101 }
01102
01103 template<typename _Key, typename _Val, typename _KeyOfValue,
01104 typename _Compare, typename _Alloc>
01105 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01106 _Compare, _Alloc>::iterator
01107 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01108 _M_upper_bound(_Link_type __x, _Link_type __y,
01109 const _Key& __k)
01110 {
01111 while (__x != 0)
01112 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01113 __y = __x, __x = _S_left(__x);
01114 else
01115 __x = _S_right(__x);
01116 return iterator(__y);
01117 }
01118
01119 template<typename _Key, typename _Val, typename _KeyOfValue,
01120 typename _Compare, typename _Alloc>
01121 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01122 _Compare, _Alloc>::const_iterator
01123 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01124 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
01125 const _Key& __k) const
01126 {
01127 while (__x != 0)
01128 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01129 __y = __x, __x = _S_left(__x);
01130 else
01131 __x = _S_right(__x);
01132 return const_iterator(__y);
01133 }
01134
01135 template<typename _Key, typename _Val, typename _KeyOfValue,
01136 typename _Compare, typename _Alloc>
01137 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01138 _Compare, _Alloc>::iterator,
01139 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01140 _Compare, _Alloc>::iterator>
01141 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01142 equal_range(const _Key& __k)
01143 {
01144 _Link_type __x = _M_begin();
01145 _Link_type __y = _M_end();
01146 while (__x != 0)
01147 {
01148 if (_M_impl._M_key_compare(_S_key(__x), __k))
01149 __x = _S_right(__x);
01150 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01151 __y = __x, __x = _S_left(__x);
01152 else
01153 {
01154 _Link_type __xu(__x), __yu(__y);
01155 __y = __x, __x = _S_left(__x);
01156 __xu = _S_right(__xu);
01157 return pair<iterator,
01158 iterator>(_M_lower_bound(__x, __y, __k),
01159 _M_upper_bound(__xu, __yu, __k));
01160 }
01161 }
01162 return pair<iterator, iterator>(iterator(__y),
01163 iterator(__y));
01164 }
01165
01166 template<typename _Key, typename _Val, typename _KeyOfValue,
01167 typename _Compare, typename _Alloc>
01168 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01169 _Compare, _Alloc>::const_iterator,
01170 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01171 _Compare, _Alloc>::const_iterator>
01172 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01173 equal_range(const _Key& __k) const
01174 {
01175 _Const_Link_type __x = _M_begin();
01176 _Const_Link_type __y = _M_end();
01177 while (__x != 0)
01178 {
01179 if (_M_impl._M_key_compare(_S_key(__x), __k))
01180 __x = _S_right(__x);
01181 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01182 __y = __x, __x = _S_left(__x);
01183 else
01184 {
01185 _Const_Link_type __xu(__x), __yu(__y);
01186 __y = __x, __x = _S_left(__x);
01187 __xu = _S_right(__xu);
01188 return pair<const_iterator,
01189 const_iterator>(_M_lower_bound(__x, __y, __k),
01190 _M_upper_bound(__xu, __yu, __k));
01191 }
01192 }
01193 return pair<const_iterator, const_iterator>(const_iterator(__y),
01194 const_iterator(__y));
01195 }
01196
01197 template<typename _Key, typename _Val, typename _KeyOfValue,
01198 typename _Compare, typename _Alloc>
01199 void
01200 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01201 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
01202 {
01203 if (_M_root() == 0)
01204 {
01205 if (__t._M_root() != 0)
01206 {
01207 _M_root() = __t._M_root();
01208 _M_leftmost() = __t._M_leftmost();
01209 _M_rightmost() = __t._M_rightmost();
01210 _M_root()->_M_parent = _M_end();
01211
01212 __t._M_root() = 0;
01213 __t._M_leftmost() = __t._M_end();
01214 __t._M_rightmost() = __t._M_end();
01215 }
01216 }
01217 else if (__t._M_root() == 0)
01218 {
01219 __t._M_root() = _M_root();
01220 __t._M_leftmost() = _M_leftmost();
01221 __t._M_rightmost() = _M_rightmost();
01222 __t._M_root()->_M_parent = __t._M_end();
01223
01224 _M_root() = 0;
01225 _M_leftmost() = _M_end();
01226 _M_rightmost() = _M_end();
01227 }
01228 else
01229 {
01230 std::swap(_M_root(),__t._M_root());
01231 std::swap(_M_leftmost(),__t._M_leftmost());
01232 std::swap(_M_rightmost(),__t._M_rightmost());
01233
01234 _M_root()->_M_parent = _M_end();
01235 __t._M_root()->_M_parent = __t._M_end();
01236 }
01237
01238 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
01239 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
01240
01241
01242
01243 std::__alloc_swap<_Node_allocator>::
01244 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
01245 }
01246
01247 template<typename _Key, typename _Val, typename _KeyOfValue,
01248 typename _Compare, typename _Alloc>
01249 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01250 template<typename _Arg>
01251 #endif
01252 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01253 _Compare, _Alloc>::iterator, bool>
01254 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01255 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01256 _M_insert_unique(_Arg&& __v)
01257 #else
01258 _M_insert_unique(const _Val& __v)
01259 #endif
01260 {
01261 _Link_type __x = _M_begin();
01262 _Link_type __y = _M_end();
01263 bool __comp = true;
01264 while (__x != 0)
01265 {
01266 __y = __x;
01267 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
01268 __x = __comp ? _S_left(__x) : _S_right(__x);
01269 }
01270 iterator __j = iterator(__y);
01271 if (__comp)
01272 {
01273 if (__j == begin())
01274 return pair<iterator, bool>
01275 (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
01276 else
01277 --__j;
01278 }
01279 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
01280 return pair<iterator, bool>
01281 (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
01282 return pair<iterator, bool>(__j, false);
01283 }
01284
01285 template<typename _Key, typename _Val, typename _KeyOfValue,
01286 typename _Compare, typename _Alloc>
01287 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01288 template<typename _Arg>
01289 #endif
01290 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01291 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01292 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01293 _M_insert_equal(_Arg&& __v)
01294 #else
01295 _M_insert_equal(const _Val& __v)
01296 #endif
01297 {
01298 _Link_type __x = _M_begin();
01299 _Link_type __y = _M_end();
01300 while (__x != 0)
01301 {
01302 __y = __x;
01303 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
01304 _S_left(__x) : _S_right(__x);
01305 }
01306 return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
01307 }
01308
01309 template<typename _Key, typename _Val, typename _KeyOfValue,
01310 typename _Compare, typename _Alloc>
01311 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01312 template<typename _Arg>
01313 #endif
01314 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01315 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01316 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01317 _M_insert_unique_(const_iterator __position, _Arg&& __v)
01318 #else
01319 _M_insert_unique_(const_iterator __position, const _Val& __v)
01320 #endif
01321 {
01322
01323 if (__position._M_node == _M_end())
01324 {
01325 if (size() > 0
01326 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
01327 _KeyOfValue()(__v)))
01328 return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v));
01329 else
01330 return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
01331 }
01332 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01333 _S_key(__position._M_node)))
01334 {
01335
01336 const_iterator __before = __position;
01337 if (__position._M_node == _M_leftmost())
01338 return _M_insert_(_M_leftmost(), _M_leftmost(),
01339 _GLIBCXX_FORWARD(_Arg, __v));
01340 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
01341 _KeyOfValue()(__v)))
01342 {
01343 if (_S_right(__before._M_node) == 0)
01344 return _M_insert_(0, __before._M_node,
01345 _GLIBCXX_FORWARD(_Arg, __v));
01346 else
01347 return _M_insert_(__position._M_node,
01348 __position._M_node,
01349 _GLIBCXX_FORWARD(_Arg, __v));
01350 }
01351 else
01352 return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
01353 }
01354 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
01355 _KeyOfValue()(__v)))
01356 {
01357
01358 const_iterator __after = __position;
01359 if (__position._M_node == _M_rightmost())
01360 return _M_insert_(0, _M_rightmost(),
01361 _GLIBCXX_FORWARD(_Arg, __v));
01362 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01363 _S_key((++__after)._M_node)))
01364 {
01365 if (_S_right(__position._M_node) == 0)
01366 return _M_insert_(0, __position._M_node,
01367 _GLIBCXX_FORWARD(_Arg, __v));
01368 else
01369 return _M_insert_(__after._M_node, __after._M_node,
01370 _GLIBCXX_FORWARD(_Arg, __v));
01371 }
01372 else
01373 return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
01374 }
01375 else
01376
01377 return __position._M_const_cast();
01378 }
01379
01380 template<typename _Key, typename _Val, typename _KeyOfValue,
01381 typename _Compare, typename _Alloc>
01382 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01383 template<typename _Arg>
01384 #endif
01385 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01386 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01387 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01388 _M_insert_equal_(const_iterator __position, _Arg&& __v)
01389 #else
01390 _M_insert_equal_(const_iterator __position, const _Val& __v)
01391 #endif
01392 {
01393
01394 if (__position._M_node == _M_end())
01395 {
01396 if (size() > 0
01397 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
01398 _S_key(_M_rightmost())))
01399 return _M_insert_(0, _M_rightmost(),
01400 _GLIBCXX_FORWARD(_Arg, __v));
01401 else
01402 return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
01403 }
01404 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
01405 _KeyOfValue()(__v)))
01406 {
01407
01408 const_iterator __before = __position;
01409 if (__position._M_node == _M_leftmost())
01410 return _M_insert_(_M_leftmost(), _M_leftmost(),
01411 _GLIBCXX_FORWARD(_Arg, __v));
01412 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
01413 _S_key((--__before)._M_node)))
01414 {
01415 if (_S_right(__before._M_node) == 0)
01416 return _M_insert_(0, __before._M_node,
01417 _GLIBCXX_FORWARD(_Arg, __v));
01418 else
01419 return _M_insert_(__position._M_node,
01420 __position._M_node,
01421 _GLIBCXX_FORWARD(_Arg, __v));
01422 }
01423 else
01424 return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
01425 }
01426 else
01427 {
01428
01429 const_iterator __after = __position;
01430 if (__position._M_node == _M_rightmost())
01431 return _M_insert_(0, _M_rightmost(),
01432 _GLIBCXX_FORWARD(_Arg, __v));
01433 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
01434 _KeyOfValue()(__v)))
01435 {
01436 if (_S_right(__position._M_node) == 0)
01437 return _M_insert_(0, __position._M_node,
01438 _GLIBCXX_FORWARD(_Arg, __v));
01439 else
01440 return _M_insert_(__after._M_node, __after._M_node,
01441 _GLIBCXX_FORWARD(_Arg, __v));
01442 }
01443 else
01444 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
01445 }
01446 }
01447
01448 template<typename _Key, typename _Val, typename _KoV,
01449 typename _Cmp, typename _Alloc>
01450 template<class _II>
01451 void
01452 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01453 _M_insert_unique(_II __first, _II __last)
01454 {
01455 for (; __first != __last; ++__first)
01456 _M_insert_unique_(end(), *__first);
01457 }
01458
01459 template<typename _Key, typename _Val, typename _KoV,
01460 typename _Cmp, typename _Alloc>
01461 template<class _II>
01462 void
01463 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01464 _M_insert_equal(_II __first, _II __last)
01465 {
01466 for (; __first != __last; ++__first)
01467 _M_insert_equal_(end(), *__first);
01468 }
01469
01470 template<typename _Key, typename _Val, typename _KeyOfValue,
01471 typename _Compare, typename _Alloc>
01472 void
01473 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01474 _M_erase_aux(const_iterator __position)
01475 {
01476 _Link_type __y =
01477 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01478 (const_cast<_Base_ptr>(__position._M_node),
01479 this->_M_impl._M_header));
01480 _M_destroy_node(__y);
01481 --_M_impl._M_node_count;
01482 }
01483
01484 template<typename _Key, typename _Val, typename _KeyOfValue,
01485 typename _Compare, typename _Alloc>
01486 void
01487 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01488 _M_erase_aux(const_iterator __first, const_iterator __last)
01489 {
01490 if (__first == begin() && __last == end())
01491 clear();
01492 else
01493 while (__first != __last)
01494 erase(__first++);
01495 }
01496
01497 template<typename _Key, typename _Val, typename _KeyOfValue,
01498 typename _Compare, typename _Alloc>
01499 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01500 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01501 erase(const _Key& __x)
01502 {
01503 pair<iterator, iterator> __p = equal_range(__x);
01504 const size_type __old_size = size();
01505 erase(__p.first, __p.second);
01506 return __old_size - size();
01507 }
01508
01509 template<typename _Key, typename _Val, typename _KeyOfValue,
01510 typename _Compare, typename _Alloc>
01511 void
01512 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01513 erase(const _Key* __first, const _Key* __last)
01514 {
01515 while (__first != __last)
01516 erase(*__first++);
01517 }
01518
01519 template<typename _Key, typename _Val, typename _KeyOfValue,
01520 typename _Compare, typename _Alloc>
01521 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01522 _Compare, _Alloc>::iterator
01523 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01524 find(const _Key& __k)
01525 {
01526 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
01527 return (__j == end()
01528 || _M_impl._M_key_compare(__k,
01529 _S_key(__j._M_node))) ? end() : __j;
01530 }
01531
01532 template<typename _Key, typename _Val, typename _KeyOfValue,
01533 typename _Compare, typename _Alloc>
01534 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01535 _Compare, _Alloc>::const_iterator
01536 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01537 find(const _Key& __k) const
01538 {
01539 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
01540 return (__j == end()
01541 || _M_impl._M_key_compare(__k,
01542 _S_key(__j._M_node))) ? end() : __j;
01543 }
01544
01545 template<typename _Key, typename _Val, typename _KeyOfValue,
01546 typename _Compare, typename _Alloc>
01547 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01548 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01549 count(const _Key& __k) const
01550 {
01551 pair<const_iterator, const_iterator> __p = equal_range(__k);
01552 const size_type __n = std::distance(__p.first, __p.second);
01553 return __n;
01554 }
01555
01556 _GLIBCXX_PURE unsigned int
01557 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01558 const _Rb_tree_node_base* __root) throw ();
01559
01560 template<typename _Key, typename _Val, typename _KeyOfValue,
01561 typename _Compare, typename _Alloc>
01562 bool
01563 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01564 {
01565 if (_M_impl._M_node_count == 0 || begin() == end())
01566 return _M_impl._M_node_count == 0 && begin() == end()
01567 && this->_M_impl._M_header._M_left == _M_end()
01568 && this->_M_impl._M_header._M_right == _M_end();
01569
01570 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01571 for (const_iterator __it = begin(); __it != end(); ++__it)
01572 {
01573 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01574 _Const_Link_type __L = _S_left(__x);
01575 _Const_Link_type __R = _S_right(__x);
01576
01577 if (__x->_M_color == _S_red)
01578 if ((__L && __L->_M_color == _S_red)
01579 || (__R && __R->_M_color == _S_red))
01580 return false;
01581
01582 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01583 return false;
01584 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01585 return false;
01586
01587 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01588 return false;
01589 }
01590
01591 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01592 return false;
01593 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01594 return false;
01595 return true;
01596 }
01597
01598 _GLIBCXX_END_NAMESPACE_VERSION
01599 }
01600
01601 #endif