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
#ifndef _TREE_H
00064
#define _TREE_H 1
00065
00066
#include <bits/stl_algobase.h>
00067
#include <bits/allocator.h>
00068
#include <bits/stl_construct.h>
00069
#include <bits/stl_function.h>
00070
#include <bits/cpp_type_traits.h>
00071
00072
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
00166 _Rb_tree_iterator(_Link_type __x)
00167 : _M_node(__x) { }
00168
00169 reference
00170 operator*()
const
00171
{
return static_cast<_Link_type>(_M_node)->_M_value_field; }
00172
00173 pointer
00174 operator->()
const
00175
{
return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00176
00177 _Self&
00178 operator++()
00179 {
00180 _M_node = _Rb_tree_increment(_M_node);
00181
return *
this;
00182 }
00183
00184 _Self
00185 operator++(
int)
00186 {
00187 _Self __tmp = *
this;
00188 _M_node = _Rb_tree_increment(_M_node);
00189
return __tmp;
00190 }
00191
00192 _Self&
00193 operator--()
00194 {
00195 _M_node = _Rb_tree_decrement(_M_node);
00196
return *
this;
00197 }
00198
00199 _Self
00200 operator--(
int)
00201 {
00202 _Self __tmp = *
this;
00203 _M_node = _Rb_tree_decrement(_M_node);
00204
return __tmp;
00205 }
00206
00207
bool
00208
operator==(
const _Self& __x)
const
00209
{
return _M_node == __x._M_node; }
00210
00211
bool
00212
operator!=(
const _Self& __x)
const
00213
{
return _M_node != __x._M_node; }
00214
00215 _Base_ptr _M_node;
00216 };
00217
00218
template<
typename _Tp>
00219
struct _Rb_tree_const_iterator
00220 {
00221
typedef _Tp value_type;
00222
typedef const _Tp& reference;
00223
typedef const _Tp* pointer;
00224
00225
typedef _Rb_tree_iterator<_Tp> iterator;
00226
00227
typedef bidirectional_iterator_tag iterator_category;
00228
typedef ptrdiff_t difference_type;
00229
00230
typedef _Rb_tree_const_iterator<_Tp> _Self;
00231
typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
00232
typedef const _Rb_tree_node<_Tp>* _Link_type;
00233
00234 _Rb_tree_const_iterator() { }
00235
00236 _Rb_tree_const_iterator(_Link_type __x)
00237 : _M_node(__x) { }
00238
00239 _Rb_tree_const_iterator(
const iterator& __it)
00240 : _M_node(__it._M_node) { }
00241
00242 reference
00243 operator*()
const
00244
{
return static_cast<_Link_type>(_M_node)->_M_value_field; }
00245
00246 pointer
00247 operator->()
const
00248
{
return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00249
00250 _Self&
00251 operator++()
00252 {
00253 _M_node = _Rb_tree_increment(_M_node);
00254
return *
this;
00255 }
00256
00257 _Self
00258 operator++(
int)
00259 {
00260 _Self __tmp = *
this;
00261 _M_node = _Rb_tree_increment(_M_node);
00262
return __tmp;
00263 }
00264
00265 _Self&
00266 operator--()
00267 {
00268 _M_node = _Rb_tree_decrement(_M_node);
00269
return *
this;
00270 }
00271
00272 _Self
00273 operator--(
int)
00274 {
00275 _Self __tmp = *
this;
00276 _M_node = _Rb_tree_decrement(_M_node);
00277
return __tmp;
00278 }
00279
00280
bool
00281
operator==(
const _Self& __x)
const
00282
{
return _M_node == __x._M_node; }
00283
00284
bool
00285
operator!=(
const _Self& __x)
const
00286
{
return _M_node != __x._M_node; }
00287
00288 _Base_ptr _M_node;
00289 };
00290
00291
template<
typename _Val>
00292
inline bool
00293
operator==(
const _Rb_tree_iterator<_Val>& __x,
00294
const _Rb_tree_const_iterator<_Val>& __y)
00295 {
return __x._M_node == __y._M_node; }
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
void
00304 _Rb_tree_rotate_left(_Rb_tree_node_base*
const __x,
00305 _Rb_tree_node_base*& __root);
00306
00307
void
00308 _Rb_tree_rotate_right(_Rb_tree_node_base*
const __x,
00309 _Rb_tree_node_base*& __root);
00310
00311
void
00312 _Rb_tree_insert_and_rebalance(
const bool __insert_left,
00313 _Rb_tree_node_base* __x,
00314 _Rb_tree_node_base* __p,
00315 _Rb_tree_node_base& __header);
00316
00317 _Rb_tree_node_base*
00318 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base*
const __z,
00319 _Rb_tree_node_base& __header);
00320
00321
00322
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00323
typename _Compare,
typename _Alloc = allocator<_Val> >
00324
class _Rb_tree
00325 {
00326
typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
00327 _Node_allocator;
00328
00329
protected:
00330
typedef _Rb_tree_node_base* _Base_ptr;
00331
typedef const _Rb_tree_node_base* _Const_Base_ptr;
00332
typedef _Rb_tree_node<_Val> _Rb_tree_node;
00333
00334
public:
00335
typedef _Key key_type;
00336
typedef _Val value_type;
00337
typedef value_type* pointer;
00338
typedef const value_type* const_pointer;
00339
typedef value_type& reference;
00340
typedef const value_type& const_reference;
00341
typedef _Rb_tree_node* _Link_type;
00342
typedef const _Rb_tree_node* _Const_Link_type;
00343
typedef size_t size_type;
00344
typedef ptrdiff_t difference_type;
00345
typedef _Alloc allocator_type;
00346
00347 allocator_type
00348 get_allocator()
const
00349
{
return *static_cast<const _Node_allocator*>(&this->_M_impl); }
00350
00351
protected:
00352 _Rb_tree_node*
00353 _M_get_node()
00354 {
return _M_impl._Node_allocator::allocate(1); }
00355
00356
void
00357 _M_put_node(_Rb_tree_node* __p)
00358 { _M_impl._Node_allocator::deallocate(__p, 1); }
00359
00360 _Link_type
00361 _M_create_node(
const value_type& __x)
00362 {
00363 _Link_type __tmp = _M_get_node();
00364
try
00365 { std::_Construct(&__tmp->_M_value_field, __x); }
00366
catch(...)
00367 {
00368 _M_put_node(__tmp);
00369 __throw_exception_again;
00370 }
00371
return __tmp;
00372 }
00373
00374 _Link_type
00375 _M_clone_node(_Const_Link_type __x)
00376 {
00377 _Link_type __tmp = _M_create_node(__x->_M_value_field);
00378 __tmp->_M_color = __x->_M_color;
00379 __tmp->_M_left = 0;
00380 __tmp->_M_right = 0;
00381
return __tmp;
00382 }
00383
00384
void
00385 destroy_node(_Link_type __p)
00386 {
00387 std::_Destroy(&__p->_M_value_field);
00388 _M_put_node(__p);
00389 }
00390
00391
protected:
00392
template<
typename _Key_compare,
00393
bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type>
00394
struct _Rb_tree_impl :
public _Node_allocator
00395 {
00396 _Key_compare _M_key_compare;
00397 _Rb_tree_node_base _M_header;
00398 size_type _M_node_count;
00399
00400 _Rb_tree_impl(
const _Node_allocator& __a = _Node_allocator(),
00401
const _Key_compare& __comp = _Key_compare())
00402 : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
00403 {
00404 this->_M_header._M_color = _S_red;
00405 this->_M_header._M_parent = 0;
00406 this->_M_header._M_left = &this->_M_header;
00407 this->_M_header._M_right = &this->_M_header;
00408 }
00409 };
00410
00411
00412
00413
template<
typename _Key_compare>
00414
struct _Rb_tree_impl<_Key_compare, true> :
public _Node_allocator
00415 {
00416 _Key_compare _M_key_compare;
00417 _Rb_tree_node_base _M_header;
00418 size_type _M_node_count;
00419
00420 _Rb_tree_impl(
const _Node_allocator& __a = _Node_allocator(),
00421
const _Key_compare& __comp = _Key_compare())
00422 : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
00423 {
00424 this->_M_header._M_color = _S_red;
00425 this->_M_header._M_parent = 0;
00426 this->_M_header._M_left = &this->_M_header;
00427 this->_M_header._M_right = &this->_M_header;
00428 }
00429 };
00430
00431 _Rb_tree_impl<_Compare> _M_impl;
00432
00433
protected:
00434 _Base_ptr&
00435 _M_root()
00436 {
return this->_M_impl._M_header._M_parent; }
00437
00438 _Const_Base_ptr
00439 _M_root()
const
00440
{
return this->_M_impl._M_header._M_parent; }
00441
00442 _Base_ptr&
00443 _M_leftmost()
00444 {
return this->_M_impl._M_header._M_left; }
00445
00446 _Const_Base_ptr
00447 _M_leftmost()
const
00448
{
return this->_M_impl._M_header._M_left; }
00449
00450 _Base_ptr&
00451 _M_rightmost()
00452 {
return this->_M_impl._M_header._M_right; }
00453
00454 _Const_Base_ptr
00455 _M_rightmost()
const
00456
{
return this->_M_impl._M_header._M_right; }
00457
00458 _Link_type
00459 _M_begin()
00460 {
return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00461
00462 _Const_Link_type
00463 _M_begin()
const
00464
{
return static_cast<
00465 _Const_Link_type>(this->_M_impl._M_header._M_parent); }
00466
00467 _Link_type
00468 _M_end()
00469 {
return static_cast<_Link_type>(&this->_M_impl._M_header); }
00470
00471 _Const_Link_type
00472 _M_end()
const
00473
{
return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00474
00475
static const_reference
00476 _S_value(_Const_Link_type __x)
00477 {
return __x->_M_value_field; }
00478
00479
static const _Key&
00480 _S_key(_Const_Link_type __x)
00481 {
return _KeyOfValue()(_S_value(__x)); }
00482
00483
static _Link_type
00484 _S_left(_Base_ptr __x)
00485 {
return static_cast<_Link_type>(__x->_M_left); }
00486
00487
static _Const_Link_type
00488 _S_left(_Const_Base_ptr __x)
00489 {
return static_cast<_Const_Link_type>(__x->_M_left); }
00490
00491
static _Link_type
00492 _S_right(_Base_ptr __x)
00493 {
return static_cast<_Link_type>(__x->_M_right); }
00494
00495
static _Const_Link_type
00496 _S_right(_Const_Base_ptr __x)
00497 {
return static_cast<_Const_Link_type>(__x->_M_right); }
00498
00499
static const_reference
00500 _S_value(_Const_Base_ptr __x)
00501 {
return static_cast<_Const_Link_type>(__x)->_M_value_field; }
00502
00503
static const _Key&
00504 _S_key(_Const_Base_ptr __x)
00505 {
return _KeyOfValue()(_S_value(__x)); }
00506
00507
static _Base_ptr
00508 _S_minimum(_Base_ptr __x)
00509 {
return _Rb_tree_node_base::_S_minimum(__x); }
00510
00511
static _Const_Base_ptr
00512 _S_minimum(_Const_Base_ptr __x)
00513 {
return _Rb_tree_node_base::_S_minimum(__x); }
00514
00515
static _Base_ptr
00516 _S_maximum(_Base_ptr __x)
00517 {
return _Rb_tree_node_base::_S_maximum(__x); }
00518
00519
static _Const_Base_ptr
00520 _S_maximum(_Const_Base_ptr __x)
00521 {
return _Rb_tree_node_base::_S_maximum(__x); }
00522
00523
public:
00524
typedef _Rb_tree_iterator<value_type> iterator;
00525
typedef _Rb_tree_const_iterator<value_type> const_iterator;
00526
00527
typedef std::reverse_iterator<iterator> reverse_iterator;
00528
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00529
00530
private:
00531 iterator
00532 _M_insert(_Base_ptr __x, _Base_ptr __y,
const value_type& __v);
00533
00534 _Link_type
00535 _M_copy(_Const_Link_type __x, _Link_type __p);
00536
00537
void
00538 _M_erase(_Link_type __x);
00539
00540
public:
00541
00542 _Rb_tree()
00543 { }
00544
00545 _Rb_tree(
const _Compare& __comp)
00546 : _M_impl(allocator_type(), __comp)
00547 { }
00548
00549 _Rb_tree(
const _Compare& __comp,
const allocator_type& __a)
00550 : _M_impl(__a, __comp)
00551 { }
00552
00553 _Rb_tree(
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
00554 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
00555 {
00556
if (__x._M_root() != 0)
00557 {
00558 _M_root() = _M_copy(__x._M_begin(), _M_end());
00559 _M_leftmost() = _S_minimum(_M_root());
00560 _M_rightmost() = _S_maximum(_M_root());
00561 _M_impl._M_node_count = __x._M_impl._M_node_count;
00562 }
00563 }
00564
00565 ~_Rb_tree()
00566 { _M_erase(_M_begin()); }
00567
00568 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
00569 operator=(
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
00570
00571
00572 _Compare
00573 key_comp()
const
00574
{
return _M_impl._M_key_compare; }
00575
00576 iterator
00577 begin()
00578 {
return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
00579
00580 const_iterator
00581 begin()
const
00582
{
return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); }
00583
00584 iterator
00585 end()
00586 {
return static_cast<_Link_type>(&this->_M_impl._M_header); }
00587
00588 const_iterator
00589 end()
const
00590
{
return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00591
00592 reverse_iterator
00593 rbegin()
00594 {
return reverse_iterator(end()); }
00595
00596 const_reverse_iterator
00597 rbegin()
const
00598
{
return const_reverse_iterator(end()); }
00599
00600 reverse_iterator
00601 rend()
00602 {
return reverse_iterator(begin()); }
00603
00604 const_reverse_iterator
00605 rend()
const
00606
{
return const_reverse_iterator(begin()); }
00607
00608
bool
00609 empty()
const
00610
{
return _M_impl._M_node_count == 0; }
00611
00612 size_type
00613 size()
const
00614
{
return _M_impl._M_node_count; }
00615
00616 size_type
00617 max_size()
const
00618
{
return size_type(-1); }
00619
00620
void
00621
swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t);
00622
00623
00624 pair<iterator,bool>
00625 insert_unique(
const value_type& __x);
00626
00627 iterator
00628 insert_equal(
const value_type& __x);
00629
00630 iterator
00631 insert_unique(iterator __position,
const value_type& __x);
00632
00633 iterator
00634 insert_equal(iterator __position,
const value_type& __x);
00635
00636
template<
typename _InputIterator>
00637
void
00638 insert_unique(_InputIterator __first, _InputIterator __last);
00639
00640
template<
typename _InputIterator>
00641
void
00642 insert_equal(_InputIterator __first, _InputIterator __last);
00643
00644
void
00645 erase(iterator __position);
00646
00647 size_type
00648 erase(
const key_type& __x);
00649
00650
void
00651 erase(iterator __first, iterator __last);
00652
00653
void
00654 erase(
const key_type* __first,
const key_type* __last);
00655
00656
void
00657 clear()
00658 {
00659 _M_erase(_M_begin());
00660 _M_leftmost() = _M_end();
00661 _M_root() = 0;
00662 _M_rightmost() = _M_end();
00663 _M_impl._M_node_count = 0;
00664 }
00665
00666
00667 iterator
00668
find(
const key_type& __x);
00669
00670 const_iterator
00671
find(
const key_type& __x)
const;
00672
00673 size_type
00674
count(
const key_type& __x)
const;
00675
00676 iterator
00677
lower_bound(
const key_type& __x);
00678
00679 const_iterator
00680
lower_bound(
const key_type& __x)
const;
00681
00682 iterator
00683
upper_bound(
const key_type& __x);
00684
00685 const_iterator
00686
upper_bound(
const key_type& __x)
const;
00687
00688 pair<iterator,iterator>
00689
equal_range(
const key_type& __x);
00690
00691 pair<const_iterator, const_iterator>
00692
equal_range(
const key_type& __x)
const;
00693
00694
00695
bool
00696 __rb_verify() const;
00697 };
00698
00699 template<typename _Key, typename _Val, typename _KeyOfValue,
00700 typename _Compare, typename _Alloc>
00701 inline
bool
00702 operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
00703 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00704 {
00705
return __x.size() == __y.size()
00706 &&
equal(__x.begin(), __x.end(), __y.begin());
00707 }
00708
00709
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00710
typename _Compare,
typename _Alloc>
00711
inline bool
00712 operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
00713
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00714 {
00715
return lexicographical_compare(__x.begin(), __x.end(),
00716 __y.begin(), __y.end());
00717 }
00718
00719
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00720
typename _Compare,
typename _Alloc>
00721
inline bool
00722
operator!=(
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
00723
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00724 {
return !(__x == __y); }
00725
00726
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00727
typename _Compare,
typename _Alloc>
00728
inline bool
00729
operator>(
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
00730
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00731 {
return __y < __x; }
00732
00733
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00734
typename _Compare,
typename _Alloc>
00735
inline bool
00736 operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
00737
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00738 {
return !(__y < __x); }
00739
00740
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00741
typename _Compare,
typename _Alloc>
00742
inline bool
00743
operator>=(
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
00744
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00745 {
return !(__x < __y); }
00746
00747
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00748
typename _Compare,
typename _Alloc>
00749
inline void
00750
swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
00751 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00752 { __x.swap(__y); }
00753
00754
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00755
typename _Compare,
typename _Alloc>
00756 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
00757 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
00758 operator=(
const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
00759 {
00760
if (
this != &__x)
00761 {
00762
00763 clear();
00764 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00765
if (__x._M_root() != 0)
00766 {
00767 _M_root() = _M_copy(__x._M_begin(), _M_end());
00768 _M_leftmost() = _S_minimum(_M_root());
00769 _M_rightmost() = _S_maximum(_M_root());
00770 _M_impl._M_node_count = __x._M_impl._M_node_count;
00771 }
00772 }
00773
return *
this;
00774 }
00775
00776
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00777
typename _Compare,
typename _Alloc>
00778
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
00779 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
00780 _M_insert(_Base_ptr __x, _Base_ptr __p,
const _Val& __v)
00781 {
00782 _Link_type __z = _M_create_node(__v);
00783
bool __insert_left;
00784
00785 __insert_left = __x != 0 || __p == _M_end()
00786 || _M_impl._M_key_compare(_KeyOfValue()(__v),
00787 _S_key(__p));
00788
00789 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
00790 this->_M_impl._M_header);
00791 ++_M_impl._M_node_count;
00792
return iterator(__z);
00793 }
00794
00795
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00796
typename _Compare,
typename _Alloc>
00797
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
00798 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
00799 insert_equal(
const _Val& __v)
00800 {
00801 _Link_type __x = _M_begin();
00802 _Link_type __y = _M_end();
00803
while (__x != 0)
00804 {
00805 __y = __x;
00806 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
00807 _S_left(__x) : _S_right(__x);
00808 }
00809
return _M_insert(__x, __y, __v);
00810 }
00811
00812
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00813
typename _Compare,
typename _Alloc>
00814
void
00815 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
00816 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
00817 {
00818
if (_M_root() == 0)
00819 {
00820
if (__t._M_root() != 0)
00821 {
00822 _M_root() = __t._M_root();
00823 _M_leftmost() = __t._M_leftmost();
00824 _M_rightmost() = __t._M_rightmost();
00825 _M_root()->_M_parent = _M_end();
00826
00827 __t._M_root() = 0;
00828 __t._M_leftmost() = __t._M_end();
00829 __t._M_rightmost() = __t._M_end();
00830 }
00831 }
00832
else if (__t._M_root() == 0)
00833 {
00834 __t._M_root() = _M_root();
00835 __t._M_leftmost() = _M_leftmost();
00836 __t._M_rightmost() = _M_rightmost();
00837 __t._M_root()->_M_parent = __t._M_end();
00838
00839 _M_root() = 0;
00840 _M_leftmost() = _M_end();
00841 _M_rightmost() = _M_end();
00842 }
00843
else
00844 {
00845
std::swap(_M_root(),__t._M_root());
00846
std::swap(_M_leftmost(),__t._M_leftmost());
00847
std::swap(_M_rightmost(),__t._M_rightmost());
00848
00849 _M_root()->_M_parent = _M_end();
00850 __t._M_root()->_M_parent = __t._M_end();
00851 }
00852
00853
std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
00854
std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
00855 }
00856
00857
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00858
typename _Compare,
typename _Alloc>
00859 pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
00860
bool>
00861 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
00862 insert_unique(
const _Val& __v)
00863 {
00864 _Link_type __x = _M_begin();
00865 _Link_type __y = _M_end();
00866
bool __comp =
true;
00867
while (__x != 0)
00868 {
00869 __y = __x;
00870 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
00871 __x = __comp ? _S_left(__x) : _S_right(__x);
00872 }
00873 iterator __j = iterator(__y);
00874
if (__comp)
00875
if (__j == begin())
00876
return pair<iterator,bool>(_M_insert(__x, __y, __v),
true);
00877
else
00878 --__j;
00879
if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
00880
return pair<iterator,bool>(_M_insert(__x, __y, __v),
true);
00881
return pair<iterator,bool>(__j,
false);
00882 }
00883
00884
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00885
typename _Compare,
typename _Alloc>
00886
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00887 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00888 insert_unique(iterator __position,
const _Val& __v)
00889 {
00890
if (__position._M_node == _M_leftmost())
00891 {
00892
00893
if (size() > 0
00894 && _M_impl._M_key_compare(_KeyOfValue()(__v),
00895 _S_key(__position._M_node)))
00896
return _M_insert(__position._M_node, __position._M_node, __v);
00897
00898
else
00899
return insert_unique(__v).first;
00900 }
00901
else if (__position._M_node == _M_end())
00902 {
00903
00904
if (_M_impl._M_key_compare(_S_key(_M_rightmost()),
00905 _KeyOfValue()(__v)))
00906
return _M_insert(0, _M_rightmost(), __v);
00907
else
00908
return insert_unique(__v).first;
00909 }
00910
else
00911 {
00912 iterator __before = __position;
00913 --__before;
00914
if (_M_impl._M_key_compare(_S_key(__before._M_node),
00915 _KeyOfValue()(__v))
00916 && _M_impl._M_key_compare(_KeyOfValue()(__v),
00917 _S_key(__position._M_node)))
00918 {
00919
if (_S_right(__before._M_node) == 0)
00920
return _M_insert(0, __before._M_node, __v);
00921
else
00922
return _M_insert(__position._M_node, __position._M_node, __v);
00923
00924 }
00925
else
00926
return insert_unique(__v).first;
00927 }
00928 }
00929
00930
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00931
typename _Compare,
typename _Alloc>
00932
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
00933 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
00934 insert_equal(iterator __position,
const _Val& __v)
00935 {
00936
if (__position._M_node == _M_leftmost())
00937 {
00938
00939
if (size() > 0
00940 && !_M_impl._M_key_compare(_S_key(__position._M_node),
00941 _KeyOfValue()(__v)))
00942
return _M_insert(__position._M_node, __position._M_node, __v);
00943
00944
else
00945
return insert_equal(__v);
00946 }
00947
else if (__position._M_node == _M_end())
00948 {
00949
00950
if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
00951 _S_key(_M_rightmost())))
00952
return _M_insert(0, _M_rightmost(), __v);
00953
else
00954
return insert_equal(__v);
00955 }
00956
else
00957 {
00958 iterator __before = __position;
00959 --__before;
00960
if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
00961 _S_key(__before._M_node))
00962 && !_M_impl._M_key_compare(_S_key(__position._M_node),
00963 _KeyOfValue()(__v)))
00964 {
00965
if (_S_right(__before._M_node) == 0)
00966
return _M_insert(0, __before._M_node, __v);
00967
else
00968
return _M_insert(__position._M_node, __position._M_node, __v);
00969
00970 }
00971
else
00972
return insert_equal(__v);
00973 }
00974 }
00975
00976
template<
typename _Key,
typename _Val,
typename _KoV,
00977
typename _Cmp,
typename _Alloc>
00978
template<
class _II>
00979
void
00980 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
00981 insert_equal(_II __first, _II __last)
00982 {
00983
for ( ; __first != __last; ++__first)
00984 insert_equal(*__first);
00985 }
00986
00987
template<
typename _Key,
typename _Val,
typename _KoV,
00988
typename _Cmp,
typename _Alloc>
00989
template<
class _II>
00990
void
00991 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
00992 insert_unique(_II __first, _II __last)
00993 {
00994
for ( ; __first != __last; ++__first)
00995 insert_unique(*__first);
00996 }
00997
00998
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
00999
typename _Compare,
typename _Alloc>
01000
inline void
01001 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
01002 {
01003 _Link_type __y =
static_cast<
01004 _Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
01005 this->_M_impl._M_header));
01006 destroy_node(__y);
01007 --_M_impl._M_node_count;
01008 }
01009
01010
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01011
typename _Compare,
typename _Alloc>
01012
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
01013 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(
const _Key& __x)
01014 {
01015 pair<iterator,iterator> __p =
equal_range(__x);
01016 size_type __n =
std::distance(__p.first, __p.second);
01017 erase(__p.first, __p.second);
01018
return __n;
01019 }
01020
01021
template<
typename _Key,
typename _Val,
typename _KoV,
01022
typename _Compare,
typename _Alloc>
01023
typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01024 _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
01025 _M_copy(_Const_Link_type __x, _Link_type __p)
01026 {
01027
01028 _Link_type __top = _M_clone_node(__x);
01029 __top->_M_parent = __p;
01030
01031
try
01032 {
01033
if (__x->_M_right)
01034 __top->_M_right = _M_copy(_S_right(__x), __top);
01035 __p = __top;
01036 __x = _S_left(__x);
01037
01038
while (__x != 0)
01039 {
01040 _Link_type __y = _M_clone_node(__x);
01041 __p->_M_left = __y;
01042 __y->_M_parent = __p;
01043
if (__x->_M_right)
01044 __y->_M_right = _M_copy(_S_right(__x), __y);
01045 __p = __y;
01046 __x = _S_left(__x);
01047 }
01048 }
01049
catch(...)
01050 {
01051 _M_erase(__top);
01052 __throw_exception_again;
01053 }
01054
return __top;
01055 }
01056
01057
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01058
typename _Compare,
typename _Alloc>
01059
void
01060 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
01061 {
01062
01063
while (__x != 0)
01064 {
01065 _M_erase(_S_right(__x));
01066 _Link_type __y = _S_left(__x);
01067 destroy_node(__x);
01068 __x = __y;
01069 }
01070 }
01071
01072
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01073
typename _Compare,
typename _Alloc>
01074
void
01075 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01076 erase(iterator __first, iterator __last)
01077 {
01078
if (__first == begin() && __last == end())
01079 clear();
01080
else
01081
while (__first != __last) erase(__first++);
01082 }
01083
01084
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01085
typename _Compare,
typename _Alloc>
01086
void
01087 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01088 erase(
const _Key* __first,
const _Key* __last)
01089 {
01090
while (__first != __last)
01091 erase(*__first++);
01092 }
01093
01094
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01095
typename _Compare,
typename _Alloc>
01096
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
01097 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(
const _Key& __k)
01098 {
01099 _Link_type __x = _M_begin();
01100 _Link_type __y = _M_end();
01101
01102
while (__x != 0)
01103
if (!_M_impl._M_key_compare(_S_key(__x), __k))
01104 __y = __x, __x = _S_left(__x);
01105
else
01106 __x = _S_right(__x);
01107
01108 iterator __j = iterator(__y);
01109
return (__j == end()
01110 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
01111 }
01112
01113
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01114
typename _Compare,
typename _Alloc>
01115
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
01116 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01117 find(
const _Key& __k)
const
01118
{
01119 _Const_Link_type __x = _M_begin();
01120 _Const_Link_type __y = _M_end();
01121
01122
while (__x != 0)
01123 {
01124
if (!_M_impl._M_key_compare(_S_key(__x), __k))
01125 __y = __x, __x = _S_left(__x);
01126
else
01127 __x = _S_right(__x);
01128 }
01129 const_iterator __j = const_iterator(__y);
01130
return (__j == end()
01131 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
01132 }
01133
01134
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01135
typename _Compare,
typename _Alloc>
01136
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
01137 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01138 count(
const _Key& __k)
const
01139
{
01140 pair<const_iterator, const_iterator> __p =
equal_range(__k);
01141
const size_type __n =
std::distance(__p.first, __p.second);
01142
return __n;
01143 }
01144
01145
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01146
typename _Compare,
typename _Alloc>
01147
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
01148
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01149
lower_bound(
const _Key& __k)
01150 {
01151 _Link_type __x = _M_begin();
01152 _Link_type __y = _M_end();
01153
01154
while (__x != 0)
01155
if (!_M_impl._M_key_compare(_S_key(__x), __k))
01156 __y = __x, __x = _S_left(__x);
01157
else
01158 __x = _S_right(__x);
01159
01160
return iterator(__y);
01161 }
01162
01163
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01164
typename _Compare,
typename _Alloc>
01165
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
01166
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01167
lower_bound(
const _Key& __k)
const
01168
{
01169 _Const_Link_type __x = _M_begin();
01170 _Const_Link_type __y = _M_end();
01171
01172
while (__x != 0)
01173
if (!_M_impl._M_key_compare(_S_key(__x), __k))
01174 __y = __x, __x = _S_left(__x);
01175
else
01176 __x = _S_right(__x);
01177
01178
return const_iterator(__y);
01179 }
01180
01181
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01182
typename _Compare,
typename _Alloc>
01183
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
01184
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01185
upper_bound(
const _Key& __k)
01186 {
01187 _Link_type __x = _M_begin();
01188 _Link_type __y = _M_end();
01189
01190
while (__x != 0)
01191
if (_M_impl._M_key_compare(__k, _S_key(__x)))
01192 __y = __x, __x = _S_left(__x);
01193
else
01194 __x = _S_right(__x);
01195
01196
return iterator(__y);
01197 }
01198
01199
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01200
typename _Compare,
typename _Alloc>
01201
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
01202
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01203
upper_bound(
const _Key& __k)
const
01204
{
01205 _Const_Link_type __x = _M_begin();
01206 _Const_Link_type __y = _M_end();
01207
01208
while (__x != 0)
01209
if (_M_impl._M_key_compare(__k, _S_key(__x)))
01210 __y = __x, __x = _S_left(__x);
01211
else
01212 __x = _S_right(__x);
01213
01214
return const_iterator(__y);
01215 }
01216
01217
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01218
typename _Compare,
typename _Alloc>
01219
inline
01220 pair<
typename _Rb_tree<_Key,_Val,_KeyOfValue,
01221 _Compare,_Alloc>::iterator,
01222
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
01223
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01224
equal_range(
const _Key& __k)
01225 {
return pair<iterator, iterator>(
lower_bound(__k),
upper_bound(__k)); }
01226
01227
template<
typename _Key,
typename _Val,
typename _KoV,
01228
typename _Compare,
typename _Alloc>
01229
inline
01230 pair<
typename _Rb_tree<_Key, _Val, _KoV,
01231 _Compare, _Alloc>::const_iterator,
01232
typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
01233
_Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01234
equal_range(
const _Key& __k)
const
01235
{
return pair<const_iterator, const_iterator>(
lower_bound(__k),
01236
upper_bound(__k)); }
01237
01238
unsigned int
01239 _Rb_tree_black_count(
const _Rb_tree_node_base* __node,
01240
const _Rb_tree_node_base* __root);
01241
01242
template<
typename _Key,
typename _Val,
typename _KeyOfValue,
01243
typename _Compare,
typename _Alloc>
01244
bool
01245 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify()
const
01246
{
01247
if (_M_impl._M_node_count == 0 || begin() == end())
01248
return _M_impl._M_node_count == 0 && begin() == end()
01249 && this->_M_impl._M_header._M_left == _M_end()
01250 && this->_M_impl._M_header._M_right == _M_end();
01251
01252
unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01253
for (const_iterator __it = begin(); __it != end(); ++__it)
01254 {
01255 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01256 _Const_Link_type __L = _S_left(__x);
01257 _Const_Link_type __R = _S_right(__x);
01258
01259
if (__x->_M_color == _S_red)
01260
if ((__L && __L->_M_color == _S_red)
01261 || (__R && __R->_M_color == _S_red))
01262
return false;
01263
01264
if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01265
return false;
01266
if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01267
return false;
01268
01269
if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01270
return false;
01271 }
01272
01273
if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01274
return false;
01275
if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01276
return false;
01277
return true;
01278 }
01279 }
01280
01281
#endif