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