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