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 _Rb_tree_node_base*
00141 _Rb_tree_increment(_Rb_tree_node_base* __x);
00142
00143 const _Rb_tree_node_base*
00144 _Rb_tree_increment(const _Rb_tree_node_base* __x);
00145
00146 _Rb_tree_node_base*
00147 _Rb_tree_decrement(_Rb_tree_node_base* __x);
00148
00149 const _Rb_tree_node_base*
00150 _Rb_tree_decrement(const _Rb_tree_node_base* __x);
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);
00314
00315 _Rb_tree_node_base*
00316 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
00317 _Rb_tree_node_base& __header);
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 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00679 swap(_Rb_tree&& __t);
00680 #else
00681 swap(_Rb_tree& __t);
00682 #endif
00683
00684
00685 pair<iterator, bool>
00686 _M_insert_unique(const value_type& __x);
00687
00688 iterator
00689 _M_insert_equal(const value_type& __x);
00690
00691 iterator
00692 _M_insert_unique_(const_iterator __position, const value_type& __x);
00693
00694 iterator
00695 _M_insert_equal_(const_iterator __position, const value_type& __x);
00696
00697 template<typename _InputIterator>
00698 void
00699 _M_insert_unique(_InputIterator __first, _InputIterator __last);
00700
00701 template<typename _InputIterator>
00702 void
00703 _M_insert_equal(_InputIterator __first, _InputIterator __last);
00704
00705 void
00706 erase(iterator __position);
00707
00708 void
00709 erase(const_iterator __position);
00710
00711 size_type
00712 erase(const key_type& __x);
00713
00714 void
00715 erase(iterator __first, iterator __last);
00716
00717 void
00718 erase(const_iterator __first, const_iterator __last);
00719
00720 void
00721 erase(const key_type* __first, const key_type* __last);
00722
00723 void
00724 clear()
00725 {
00726 _M_erase(_M_begin());
00727 _M_leftmost() = _M_end();
00728 _M_root() = 0;
00729 _M_rightmost() = _M_end();
00730 _M_impl._M_node_count = 0;
00731 }
00732
00733
00734 iterator
00735 find(const key_type& __k);
00736
00737 const_iterator
00738 find(const key_type& __k) const;
00739
00740 size_type
00741 count(const key_type& __k) const;
00742
00743 iterator
00744 lower_bound(const key_type& __k)
00745 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
00746
00747 const_iterator
00748 lower_bound(const key_type& __k) const
00749 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
00750
00751 iterator
00752 upper_bound(const key_type& __k)
00753 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
00754
00755 const_iterator
00756 upper_bound(const key_type& __k) const
00757 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
00758
00759 pair<iterator, iterator>
00760 equal_range(const key_type& __k);
00761
00762 pair<const_iterator, const_iterator>
00763 equal_range(const key_type& __k) const;
00764
00765
00766 bool
00767 __rb_verify() const;
00768 };
00769
00770 template<typename _Key, typename _Val, typename _KeyOfValue,
00771 typename _Compare, typename _Alloc>
00772 inline bool
00773 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00774 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00775 {
00776 return __x.size() == __y.size()
00777 && std::equal(__x.begin(), __x.end(), __y.begin());
00778 }
00779
00780 template<typename _Key, typename _Val, typename _KeyOfValue,
00781 typename _Compare, typename _Alloc>
00782 inline bool
00783 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00784 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00785 {
00786 return std::lexicographical_compare(__x.begin(), __x.end(),
00787 __y.begin(), __y.end());
00788 }
00789
00790 template<typename _Key, typename _Val, typename _KeyOfValue,
00791 typename _Compare, typename _Alloc>
00792 inline bool
00793 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00794 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00795 { return !(__x == __y); }
00796
00797 template<typename _Key, typename _Val, typename _KeyOfValue,
00798 typename _Compare, typename _Alloc>
00799 inline bool
00800 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00801 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00802 { return __y < __x; }
00803
00804 template<typename _Key, typename _Val, typename _KeyOfValue,
00805 typename _Compare, typename _Alloc>
00806 inline bool
00807 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00808 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00809 { return !(__y < __x); }
00810
00811 template<typename _Key, typename _Val, typename _KeyOfValue,
00812 typename _Compare, typename _Alloc>
00813 inline bool
00814 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00815 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00816 { return !(__x < __y); }
00817
00818 template<typename _Key, typename _Val, typename _KeyOfValue,
00819 typename _Compare, typename _Alloc>
00820 inline void
00821 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00822 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00823 { __x.swap(__y); }
00824
00825 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00826 template<typename _Key, typename _Val, typename _KeyOfValue,
00827 typename _Compare, typename _Alloc>
00828 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00829 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
00830 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
00831 {
00832 if (__x._M_root() != 0)
00833 {
00834 _M_root() = __x._M_root();
00835 _M_leftmost() = __x._M_leftmost();
00836 _M_rightmost() = __x._M_rightmost();
00837 _M_root()->_M_parent = _M_end();
00838
00839 __x._M_root() = 0;
00840 __x._M_leftmost() = __x._M_end();
00841 __x._M_rightmost() = __x._M_end();
00842
00843 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
00844 __x._M_impl._M_node_count = 0;
00845 }
00846 }
00847 #endif
00848
00849 template<typename _Key, typename _Val, typename _KeyOfValue,
00850 typename _Compare, typename _Alloc>
00851 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00852 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00853 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00854 {
00855 if (this != &__x)
00856 {
00857
00858 clear();
00859 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00860 if (__x._M_root() != 0)
00861 {
00862 _M_root() = _M_copy(__x._M_begin(), _M_end());
00863 _M_leftmost() = _S_minimum(_M_root());
00864 _M_rightmost() = _S_maximum(_M_root());
00865 _M_impl._M_node_count = __x._M_impl._M_node_count;
00866 }
00867 }
00868 return *this;
00869 }
00870
00871 template<typename _Key, typename _Val, typename _KeyOfValue,
00872 typename _Compare, typename _Alloc>
00873 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00874 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00875 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
00876 {
00877 bool __insert_left = (__x != 0 || __p == _M_end()
00878 || _M_impl._M_key_compare(_KeyOfValue()(__v),
00879 _S_key(__p)));
00880
00881 _Link_type __z = _M_create_node(__v);
00882
00883 _Rb_tree_insert_and_rebalance(__insert_left, __z,
00884 const_cast<_Base_ptr>(__p),
00885 this->_M_impl._M_header);
00886 ++_M_impl._M_node_count;
00887 return iterator(__z);
00888 }
00889
00890 template<typename _Key, typename _Val, typename _KeyOfValue,
00891 typename _Compare, typename _Alloc>
00892 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00893 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00894 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
00895 {
00896 bool __insert_left = (__x != 0 || __p == _M_end()
00897 || !_M_impl._M_key_compare(_S_key(__p),
00898 _KeyOfValue()(__v)));
00899
00900 _Link_type __z = _M_create_node(__v);
00901
00902 _Rb_tree_insert_and_rebalance(__insert_left, __z, __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_equal_lower(const _Val& __v)
00913 {
00914 _Link_type __x = _M_begin();
00915 _Link_type __y = _M_end();
00916 while (__x != 0)
00917 {
00918 __y = __x;
00919 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
00920 _S_left(__x) : _S_right(__x);
00921 }
00922 return _M_insert_lower(__x, __y, __v);
00923 }
00924
00925 template<typename _Key, typename _Val, typename _KoV,
00926 typename _Compare, typename _Alloc>
00927 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
00928 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
00929 _M_copy(_Const_Link_type __x, _Link_type __p)
00930 {
00931
00932 _Link_type __top = _M_clone_node(__x);
00933 __top->_M_parent = __p;
00934
00935 __try
00936 {
00937 if (__x->_M_right)
00938 __top->_M_right = _M_copy(_S_right(__x), __top);
00939 __p = __top;
00940 __x = _S_left(__x);
00941
00942 while (__x != 0)
00943 {
00944 _Link_type __y = _M_clone_node(__x);
00945 __p->_M_left = __y;
00946 __y->_M_parent = __p;
00947 if (__x->_M_right)
00948 __y->_M_right = _M_copy(_S_right(__x), __y);
00949 __p = __y;
00950 __x = _S_left(__x);
00951 }
00952 }
00953 __catch(...)
00954 {
00955 _M_erase(__top);
00956 __throw_exception_again;
00957 }
00958 return __top;
00959 }
00960
00961 template<typename _Key, typename _Val, typename _KeyOfValue,
00962 typename _Compare, typename _Alloc>
00963 void
00964 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00965 _M_erase(_Link_type __x)
00966 {
00967
00968 while (__x != 0)
00969 {
00970 _M_erase(_S_right(__x));
00971 _Link_type __y = _S_left(__x);
00972 _M_destroy_node(__x);
00973 __x = __y;
00974 }
00975 }
00976
00977 template<typename _Key, typename _Val, typename _KeyOfValue,
00978 typename _Compare, typename _Alloc>
00979 typename _Rb_tree<_Key, _Val, _KeyOfValue,
00980 _Compare, _Alloc>::iterator
00981 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00982 _M_lower_bound(_Link_type __x, _Link_type __y,
00983 const _Key& __k)
00984 {
00985 while (__x != 0)
00986 if (!_M_impl._M_key_compare(_S_key(__x), __k))
00987 __y = __x, __x = _S_left(__x);
00988 else
00989 __x = _S_right(__x);
00990 return iterator(__y);
00991 }
00992
00993 template<typename _Key, typename _Val, typename _KeyOfValue,
00994 typename _Compare, typename _Alloc>
00995 typename _Rb_tree<_Key, _Val, _KeyOfValue,
00996 _Compare, _Alloc>::const_iterator
00997 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00998 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
00999 const _Key& __k) const
01000 {
01001 while (__x != 0)
01002 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01003 __y = __x, __x = _S_left(__x);
01004 else
01005 __x = _S_right(__x);
01006 return const_iterator(__y);
01007 }
01008
01009 template<typename _Key, typename _Val, typename _KeyOfValue,
01010 typename _Compare, typename _Alloc>
01011 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01012 _Compare, _Alloc>::iterator
01013 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01014 _M_upper_bound(_Link_type __x, _Link_type __y,
01015 const _Key& __k)
01016 {
01017 while (__x != 0)
01018 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01019 __y = __x, __x = _S_left(__x);
01020 else
01021 __x = _S_right(__x);
01022 return iterator(__y);
01023 }
01024
01025 template<typename _Key, typename _Val, typename _KeyOfValue,
01026 typename _Compare, typename _Alloc>
01027 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01028 _Compare, _Alloc>::const_iterator
01029 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01030 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
01031 const _Key& __k) const
01032 {
01033 while (__x != 0)
01034 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01035 __y = __x, __x = _S_left(__x);
01036 else
01037 __x = _S_right(__x);
01038 return const_iterator(__y);
01039 }
01040
01041 template<typename _Key, typename _Val, typename _KeyOfValue,
01042 typename _Compare, typename _Alloc>
01043 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01044 _Compare, _Alloc>::iterator,
01045 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01046 _Compare, _Alloc>::iterator>
01047 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01048 equal_range(const _Key& __k)
01049 {
01050 _Link_type __x = _M_begin();
01051 _Link_type __y = _M_end();
01052 while (__x != 0)
01053 {
01054 if (_M_impl._M_key_compare(_S_key(__x), __k))
01055 __x = _S_right(__x);
01056 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01057 __y = __x, __x = _S_left(__x);
01058 else
01059 {
01060 _Link_type __xu(__x), __yu(__y);
01061 __y = __x, __x = _S_left(__x);
01062 __xu = _S_right(__xu);
01063 return pair<iterator,
01064 iterator>(_M_lower_bound(__x, __y, __k),
01065 _M_upper_bound(__xu, __yu, __k));
01066 }
01067 }
01068 return pair<iterator, iterator>(iterator(__y),
01069 iterator(__y));
01070 }
01071
01072 template<typename _Key, typename _Val, typename _KeyOfValue,
01073 typename _Compare, typename _Alloc>
01074 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01075 _Compare, _Alloc>::const_iterator,
01076 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01077 _Compare, _Alloc>::const_iterator>
01078 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01079 equal_range(const _Key& __k) const
01080 {
01081 _Const_Link_type __x = _M_begin();
01082 _Const_Link_type __y = _M_end();
01083 while (__x != 0)
01084 {
01085 if (_M_impl._M_key_compare(_S_key(__x), __k))
01086 __x = _S_right(__x);
01087 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01088 __y = __x, __x = _S_left(__x);
01089 else
01090 {
01091 _Const_Link_type __xu(__x), __yu(__y);
01092 __y = __x, __x = _S_left(__x);
01093 __xu = _S_right(__xu);
01094 return pair<const_iterator,
01095 const_iterator>(_M_lower_bound(__x, __y, __k),
01096 _M_upper_bound(__xu, __yu, __k));
01097 }
01098 }
01099 return pair<const_iterator, const_iterator>(const_iterator(__y),
01100 const_iterator(__y));
01101 }
01102
01103 template<typename _Key, typename _Val, typename _KeyOfValue,
01104 typename _Compare, typename _Alloc>
01105 void
01106 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01107 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01108 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __t)
01109 #else
01110 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
01111 #endif
01112 {
01113 if (_M_root() == 0)
01114 {
01115 if (__t._M_root() != 0)
01116 {
01117 _M_root() = __t._M_root();
01118 _M_leftmost() = __t._M_leftmost();
01119 _M_rightmost() = __t._M_rightmost();
01120 _M_root()->_M_parent = _M_end();
01121
01122 __t._M_root() = 0;
01123 __t._M_leftmost() = __t._M_end();
01124 __t._M_rightmost() = __t._M_end();
01125 }
01126 }
01127 else if (__t._M_root() == 0)
01128 {
01129 __t._M_root() = _M_root();
01130 __t._M_leftmost() = _M_leftmost();
01131 __t._M_rightmost() = _M_rightmost();
01132 __t._M_root()->_M_parent = __t._M_end();
01133
01134 _M_root() = 0;
01135 _M_leftmost() = _M_end();
01136 _M_rightmost() = _M_end();
01137 }
01138 else
01139 {
01140 std::swap(_M_root(),__t._M_root());
01141 std::swap(_M_leftmost(),__t._M_leftmost());
01142 std::swap(_M_rightmost(),__t._M_rightmost());
01143
01144 _M_root()->_M_parent = _M_end();
01145 __t._M_root()->_M_parent = __t._M_end();
01146 }
01147
01148 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
01149 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
01150
01151
01152
01153 std::__alloc_swap<_Node_allocator>::
01154 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
01155 }
01156
01157 template<typename _Key, typename _Val, typename _KeyOfValue,
01158 typename _Compare, typename _Alloc>
01159 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01160 _Compare, _Alloc>::iterator, bool>
01161 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01162 _M_insert_unique(const _Val& __v)
01163 {
01164 _Link_type __x = _M_begin();
01165 _Link_type __y = _M_end();
01166 bool __comp = true;
01167 while (__x != 0)
01168 {
01169 __y = __x;
01170 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
01171 __x = __comp ? _S_left(__x) : _S_right(__x);
01172 }
01173 iterator __j = iterator(__y);
01174 if (__comp)
01175 {
01176 if (__j == begin())
01177 return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
01178 else
01179 --__j;
01180 }
01181 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
01182 return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
01183 return pair<iterator, bool>(__j, false);
01184 }
01185
01186 template<typename _Key, typename _Val, typename _KeyOfValue,
01187 typename _Compare, typename _Alloc>
01188 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01189 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01190 _M_insert_equal(const _Val& __v)
01191 {
01192 _Link_type __x = _M_begin();
01193 _Link_type __y = _M_end();
01194 while (__x != 0)
01195 {
01196 __y = __x;
01197 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
01198 _S_left(__x) : _S_right(__x);
01199 }
01200 return _M_insert_(__x, __y, __v);
01201 }
01202
01203 template<typename _Key, typename _Val, typename _KeyOfValue,
01204 typename _Compare, typename _Alloc>
01205 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01206 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01207 _M_insert_unique_(const_iterator __position, const _Val& __v)
01208 {
01209
01210 if (__position._M_node == _M_end())
01211 {
01212 if (size() > 0
01213 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
01214 _KeyOfValue()(__v)))
01215 return _M_insert_(0, _M_rightmost(), __v);
01216 else
01217 return _M_insert_unique(__v).first;
01218 }
01219 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01220 _S_key(__position._M_node)))
01221 {
01222
01223 const_iterator __before = __position;
01224 if (__position._M_node == _M_leftmost())
01225 return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
01226 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
01227 _KeyOfValue()(__v)))
01228 {
01229 if (_S_right(__before._M_node) == 0)
01230 return _M_insert_(0, __before._M_node, __v);
01231 else
01232 return _M_insert_(__position._M_node,
01233 __position._M_node, __v);
01234 }
01235 else
01236 return _M_insert_unique(__v).first;
01237 }
01238 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
01239 _KeyOfValue()(__v)))
01240 {
01241
01242 const_iterator __after = __position;
01243 if (__position._M_node == _M_rightmost())
01244 return _M_insert_(0, _M_rightmost(), __v);
01245 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01246 _S_key((++__after)._M_node)))
01247 {
01248 if (_S_right(__position._M_node) == 0)
01249 return _M_insert_(0, __position._M_node, __v);
01250 else
01251 return _M_insert_(__after._M_node, __after._M_node, __v);
01252 }
01253 else
01254 return _M_insert_unique(__v).first;
01255 }
01256 else
01257
01258 return iterator(static_cast<_Link_type>
01259 (const_cast<_Base_ptr>(__position._M_node)));
01260 }
01261
01262 template<typename _Key, typename _Val, typename _KeyOfValue,
01263 typename _Compare, typename _Alloc>
01264 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01265 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01266 _M_insert_equal_(const_iterator __position, const _Val& __v)
01267 {
01268
01269 if (__position._M_node == _M_end())
01270 {
01271 if (size() > 0
01272 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
01273 _S_key(_M_rightmost())))
01274 return _M_insert_(0, _M_rightmost(), __v);
01275 else
01276 return _M_insert_equal(__v);
01277 }
01278 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
01279 _KeyOfValue()(__v)))
01280 {
01281
01282 const_iterator __before = __position;
01283 if (__position._M_node == _M_leftmost())
01284 return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
01285 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
01286 _S_key((--__before)._M_node)))
01287 {
01288 if (_S_right(__before._M_node) == 0)
01289 return _M_insert_(0, __before._M_node, __v);
01290 else
01291 return _M_insert_(__position._M_node,
01292 __position._M_node, __v);
01293 }
01294 else
01295 return _M_insert_equal(__v);
01296 }
01297 else
01298 {
01299
01300 const_iterator __after = __position;
01301 if (__position._M_node == _M_rightmost())
01302 return _M_insert_(0, _M_rightmost(), __v);
01303 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
01304 _KeyOfValue()(__v)))
01305 {
01306 if (_S_right(__position._M_node) == 0)
01307 return _M_insert_(0, __position._M_node, __v);
01308 else
01309 return _M_insert_(__after._M_node, __after._M_node, __v);
01310 }
01311 else
01312 return _M_insert_equal_lower(__v);
01313 }
01314 }
01315
01316 template<typename _Key, typename _Val, typename _KoV,
01317 typename _Cmp, typename _Alloc>
01318 template<class _II>
01319 void
01320 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01321 _M_insert_unique(_II __first, _II __last)
01322 {
01323 for (; __first != __last; ++__first)
01324 _M_insert_unique_(end(), *__first);
01325 }
01326
01327 template<typename _Key, typename _Val, typename _KoV,
01328 typename _Cmp, typename _Alloc>
01329 template<class _II>
01330 void
01331 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01332 _M_insert_equal(_II __first, _II __last)
01333 {
01334 for (; __first != __last; ++__first)
01335 _M_insert_equal_(end(), *__first);
01336 }
01337
01338 template<typename _Key, typename _Val, typename _KeyOfValue,
01339 typename _Compare, typename _Alloc>
01340 inline void
01341 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01342 erase(iterator __position)
01343 {
01344 _Link_type __y =
01345 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01346 (__position._M_node,
01347 this->_M_impl._M_header));
01348 _M_destroy_node(__y);
01349 --_M_impl._M_node_count;
01350 }
01351
01352 template<typename _Key, typename _Val, typename _KeyOfValue,
01353 typename _Compare, typename _Alloc>
01354 inline void
01355 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01356 erase(const_iterator __position)
01357 {
01358 _Link_type __y =
01359 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01360 (const_cast<_Base_ptr>(__position._M_node),
01361 this->_M_impl._M_header));
01362 _M_destroy_node(__y);
01363 --_M_impl._M_node_count;
01364 }
01365
01366 template<typename _Key, typename _Val, typename _KeyOfValue,
01367 typename _Compare, typename _Alloc>
01368 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01369 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01370 erase(const _Key& __x)
01371 {
01372 pair<iterator, iterator> __p = equal_range(__x);
01373 const size_type __old_size = size();
01374 erase(__p.first, __p.second);
01375 return __old_size - size();
01376 }
01377
01378 template<typename _Key, typename _Val, typename _KeyOfValue,
01379 typename _Compare, typename _Alloc>
01380 void
01381 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01382 erase(iterator __first, iterator __last)
01383 {
01384 if (__first == begin() && __last == end())
01385 clear();
01386 else
01387 while (__first != __last)
01388 erase(__first++);
01389 }
01390
01391 template<typename _Key, typename _Val, typename _KeyOfValue,
01392 typename _Compare, typename _Alloc>
01393 void
01394 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01395 erase(const_iterator __first, const_iterator __last)
01396 {
01397 if (__first == begin() && __last == end())
01398 clear();
01399 else
01400 while (__first != __last)
01401 erase(__first++);
01402 }
01403
01404 template<typename _Key, typename _Val, typename _KeyOfValue,
01405 typename _Compare, typename _Alloc>
01406 void
01407 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01408 erase(const _Key* __first, const _Key* __last)
01409 {
01410 while (__first != __last)
01411 erase(*__first++);
01412 }
01413
01414 template<typename _Key, typename _Val, typename _KeyOfValue,
01415 typename _Compare, typename _Alloc>
01416 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01417 _Compare, _Alloc>::iterator
01418 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01419 find(const _Key& __k)
01420 {
01421 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
01422 return (__j == end()
01423 || _M_impl._M_key_compare(__k,
01424 _S_key(__j._M_node))) ? end() : __j;
01425 }
01426
01427 template<typename _Key, typename _Val, typename _KeyOfValue,
01428 typename _Compare, typename _Alloc>
01429 typename _Rb_tree<_Key, _Val, _KeyOfValue,
01430 _Compare, _Alloc>::const_iterator
01431 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01432 find(const _Key& __k) const
01433 {
01434 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
01435 return (__j == end()
01436 || _M_impl._M_key_compare(__k,
01437 _S_key(__j._M_node))) ? end() : __j;
01438 }
01439
01440 template<typename _Key, typename _Val, typename _KeyOfValue,
01441 typename _Compare, typename _Alloc>
01442 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01443 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01444 count(const _Key& __k) const
01445 {
01446 pair<const_iterator, const_iterator> __p = equal_range(__k);
01447 const size_type __n = std::distance(__p.first, __p.second);
01448 return __n;
01449 }
01450
01451 unsigned int
01452 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01453 const _Rb_tree_node_base* __root);
01454
01455 template<typename _Key, typename _Val, typename _KeyOfValue,
01456 typename _Compare, typename _Alloc>
01457 bool
01458 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01459 {
01460 if (_M_impl._M_node_count == 0 || begin() == end())
01461 return _M_impl._M_node_count == 0 && begin() == end()
01462 && this->_M_impl._M_header._M_left == _M_end()
01463 && this->_M_impl._M_header._M_right == _M_end();
01464
01465 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01466 for (const_iterator __it = begin(); __it != end(); ++__it)
01467 {
01468 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01469 _Const_Link_type __L = _S_left(__x);
01470 _Const_Link_type __R = _S_right(__x);
01471
01472 if (__x->_M_color == _S_red)
01473 if ((__L && __L->_M_color == _S_red)
01474 || (__R && __R->_M_color == _S_red))
01475 return false;
01476
01477 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01478 return false;
01479 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01480 return false;
01481
01482 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01483 return false;
01484 }
01485
01486 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01487 return false;
01488 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01489 return false;
01490 return true;
01491 }
01492
01493 _GLIBCXX_END_NAMESPACE
01494
01495 #endif