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