stl_tree.h revision 117397
1// RB tree implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * 32 * Copyright (c) 1996,1997 33 * Silicon Graphics Computer Systems, Inc. 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Silicon Graphics makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1994 45 * Hewlett-Packard Company 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Hewlett-Packard Company makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 * 55 * 56 */ 57 58/** @file stl_tree.h 59 * This is an internal header file, included by other library headers. 60 * You should not attempt to use it directly. 61 */ 62 63#ifndef __GLIBCPP_INTERNAL_TREE_H 64#define __GLIBCPP_INTERNAL_TREE_H 65 66/* 67 68Red-black tree class, designed for use in implementing STL 69associative containers (set, multiset, map, and multimap). The 70insertion and deletion algorithms are based on those in Cormen, 71Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), 72except that 73 74(1) the header cell is maintained with links not only to the root 75but also to the leftmost node of the tree, to enable constant time 76begin(), and to the rightmost node of the tree, to enable linear time 77performance when used with the generic set algorithms (set_union, 78etc.); 79 80(2) when a node being deleted has two children its successor node is 81relinked into its place, rather than copied, so that the only 82iterators invalidated are those referring to the deleted node. 83 84*/ 85 86#include <bits/stl_algobase.h> 87#include <bits/stl_alloc.h> 88#include <bits/stl_construct.h> 89#include <bits/stl_function.h> 90 91namespace std 92{ 93 enum _Rb_tree_color { _M_red = false, _M_black = true }; 94 95 struct _Rb_tree_node_base 96 { 97 typedef _Rb_tree_node_base* _Base_ptr; 98 99 _Rb_tree_color _M_color; 100 _Base_ptr _M_parent; 101 _Base_ptr _M_left; 102 _Base_ptr _M_right; 103 104 static _Base_ptr 105 _S_minimum(_Base_ptr __x) 106 { 107 while (__x->_M_left != 0) __x = __x->_M_left; 108 return __x; 109 } 110 111 static _Base_ptr 112 _S_maximum(_Base_ptr __x) 113 { 114 while (__x->_M_right != 0) __x = __x->_M_right; 115 return __x; 116 } 117 }; 118 119 template<typename _Val> 120 struct _Rb_tree_node : public _Rb_tree_node_base 121 { 122 typedef _Rb_tree_node<_Val>* _Link_type; 123 _Val _M_value_field; 124 }; 125 126 struct _Rb_tree_base_iterator 127 { 128 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 129 typedef bidirectional_iterator_tag iterator_category; 130 typedef ptrdiff_t difference_type; 131 132 _Base_ptr _M_node; 133 134 void 135 _M_increment() 136 { 137 if (_M_node->_M_right != 0) 138 { 139 _M_node = _M_node->_M_right; 140 while (_M_node->_M_left != 0) 141 _M_node = _M_node->_M_left; 142 } 143 else 144 { 145 _Base_ptr __y = _M_node->_M_parent; 146 while (_M_node == __y->_M_right) 147 { 148 _M_node = __y; 149 __y = __y->_M_parent; 150 } 151 if (_M_node->_M_right != __y) 152 _M_node = __y; 153 } 154 } 155 156 void 157 _M_decrement() 158 { 159 if (_M_node->_M_color == _M_red 160 && _M_node->_M_parent->_M_parent == _M_node) 161 _M_node = _M_node->_M_right; 162 else if (_M_node->_M_left != 0) 163 { 164 _Base_ptr __y = _M_node->_M_left; 165 while (__y->_M_right != 0) 166 __y = __y->_M_right; 167 _M_node = __y; 168 } 169 else 170 { 171 _Base_ptr __y = _M_node->_M_parent; 172 while (_M_node == __y->_M_left) 173 { 174 _M_node = __y; 175 __y = __y->_M_parent; 176 } 177 _M_node = __y; 178 } 179 } 180 }; 181 182 template<typename _Val, typename _Ref, typename _Ptr> 183 struct _Rb_tree_iterator : public _Rb_tree_base_iterator 184 { 185 typedef _Val value_type; 186 typedef _Ref reference; 187 typedef _Ptr pointer; 188 typedef _Rb_tree_iterator<_Val, _Val&, _Val*> iterator; 189 typedef _Rb_tree_iterator<_Val, const _Val&, const _Val*> 190 const_iterator; 191 typedef _Rb_tree_iterator<_Val, _Ref, _Ptr> _Self; 192 typedef _Rb_tree_node<_Val>* _Link_type; 193 194 _Rb_tree_iterator() {} 195 _Rb_tree_iterator(_Link_type __x) { _M_node = __x; } 196 _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; } 197 198 reference 199 operator*() const { return _Link_type(_M_node)->_M_value_field; } 200 201 pointer 202 operator->() const { return &(operator*()); } 203 204 _Self& 205 operator++() 206 { 207 _M_increment(); 208 return *this; 209 } 210 211 _Self 212 operator++(int) 213 { 214 _Self __tmp = *this; 215 _M_increment(); 216 return __tmp; 217 } 218 219 _Self& 220 operator--() { _M_decrement(); return *this; } 221 222 _Self 223 operator--(int) 224 { 225 _Self __tmp = *this; 226 _M_decrement(); 227 return __tmp; 228 } 229 }; 230 231 template<typename _Val, typename _Ref, typename _Ptr> 232 inline bool 233 operator==(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x, 234 const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y) 235 { return __x._M_node == __y._M_node; } 236 237 template<typename _Val> 238 inline bool 239 operator==(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x, 240 const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y) 241 { return __x._M_node == __y._M_node; } 242 243 template<typename _Val> 244 inline bool 245 operator==(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x, 246 const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y) 247 { return __x._M_node == __y._M_node; } 248 249 template<typename _Val, typename _Ref, typename _Ptr> 250 inline bool 251 operator!=(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x, 252 const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y) 253 { return __x._M_node != __y._M_node; } 254 255 template<typename _Val> 256 inline bool 257 operator!=(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x, 258 const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y) 259 { return __x._M_node != __y._M_node; } 260 261 template<typename _Val> 262 inline bool 263 operator!=(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x, 264 const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y) 265 { return __x._M_node != __y._M_node; } 266 267 inline void 268 _Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) 269 { 270 _Rb_tree_node_base* __y = __x->_M_right; 271 __x->_M_right = __y->_M_left; 272 if (__y->_M_left !=0) 273 __y->_M_left->_M_parent = __x; 274 __y->_M_parent = __x->_M_parent; 275 276 if (__x == __root) 277 __root = __y; 278 else if (__x == __x->_M_parent->_M_left) 279 __x->_M_parent->_M_left = __y; 280 else 281 __x->_M_parent->_M_right = __y; 282 __y->_M_left = __x; 283 __x->_M_parent = __y; 284 } 285 286 inline void 287 _Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) 288 { 289 _Rb_tree_node_base* __y = __x->_M_left; 290 __x->_M_left = __y->_M_right; 291 if (__y->_M_right != 0) 292 __y->_M_right->_M_parent = __x; 293 __y->_M_parent = __x->_M_parent; 294 295 if (__x == __root) 296 __root = __y; 297 else if (__x == __x->_M_parent->_M_right) 298 __x->_M_parent->_M_right = __y; 299 else 300 __x->_M_parent->_M_left = __y; 301 __y->_M_right = __x; 302 __x->_M_parent = __y; 303 } 304 305 inline void 306 _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) 307 { 308 __x->_M_color = _M_red; 309 while (__x != __root 310 && __x->_M_parent->_M_color == _M_red) 311 { 312 if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) 313 { 314 _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; 315 if (__y && __y->_M_color == _M_red) 316 { 317 __x->_M_parent->_M_color = _M_black; 318 __y->_M_color = _M_black; 319 __x->_M_parent->_M_parent->_M_color = _M_red; 320 __x = __x->_M_parent->_M_parent; 321 } 322 else 323 { 324 if (__x == __x->_M_parent->_M_right) 325 { 326 __x = __x->_M_parent; 327 _Rb_tree_rotate_left(__x, __root); 328 } 329 __x->_M_parent->_M_color = _M_black; 330 __x->_M_parent->_M_parent->_M_color = _M_red; 331 _Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root); 332 } 333 } 334 else 335 { 336 _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left; 337 if (__y && __y->_M_color == _M_red) 338 { 339 __x->_M_parent->_M_color = _M_black; 340 __y->_M_color = _M_black; 341 __x->_M_parent->_M_parent->_M_color = _M_red; 342 __x = __x->_M_parent->_M_parent; 343 } 344 else 345 { 346 if (__x == __x->_M_parent->_M_left) 347 { 348 __x = __x->_M_parent; 349 _Rb_tree_rotate_right(__x, __root); 350 } 351 __x->_M_parent->_M_color = _M_black; 352 __x->_M_parent->_M_parent->_M_color = _M_red; 353 _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root); 354 } 355 } 356 } 357 __root->_M_color = _M_black; 358 } 359 360 inline _Rb_tree_node_base* 361 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z, 362 _Rb_tree_node_base*& __root, 363 _Rb_tree_node_base*& __leftmost, 364 _Rb_tree_node_base*& __rightmost) 365 { 366 _Rb_tree_node_base* __y = __z; 367 _Rb_tree_node_base* __x = 0; 368 _Rb_tree_node_base* __x_parent = 0; 369 if (__y->_M_left == 0) // __z has at most one non-null child. y == z. 370 __x = __y->_M_right; // __x might be null. 371 else 372 if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. 373 __x = __y->_M_left; // __x is not null. 374 else 375 { 376 // __z has two non-null children. Set __y to 377 __y = __y->_M_right; // __z's successor. __x might be null. 378 while (__y->_M_left != 0) 379 __y = __y->_M_left; 380 __x = __y->_M_right; 381 } 382 if (__y != __z) 383 { 384 // relink y in place of z. y is z's successor 385 __z->_M_left->_M_parent = __y; 386 __y->_M_left = __z->_M_left; 387 if (__y != __z->_M_right) 388 { 389 __x_parent = __y->_M_parent; 390 if (__x) __x->_M_parent = __y->_M_parent; 391 __y->_M_parent->_M_left = __x; // __y must be a child of _M_left 392 __y->_M_right = __z->_M_right; 393 __z->_M_right->_M_parent = __y; 394 } 395 else 396 __x_parent = __y; 397 if (__root == __z) 398 __root = __y; 399 else if (__z->_M_parent->_M_left == __z) 400 __z->_M_parent->_M_left = __y; 401 else 402 __z->_M_parent->_M_right = __y; 403 __y->_M_parent = __z->_M_parent; 404 std::swap(__y->_M_color, __z->_M_color); 405 __y = __z; 406 // __y now points to node to be actually deleted 407 } 408 else 409 { // __y == __z 410 __x_parent = __y->_M_parent; 411 if (__x) 412 __x->_M_parent = __y->_M_parent; 413 if (__root == __z) 414 __root = __x; 415 else 416 if (__z->_M_parent->_M_left == __z) 417 __z->_M_parent->_M_left = __x; 418 else 419 __z->_M_parent->_M_right = __x; 420 if (__leftmost == __z) 421 if (__z->_M_right == 0) // __z->_M_left must be null also 422 __leftmost = __z->_M_parent; 423 // makes __leftmost == _M_header if __z == __root 424 else 425 __leftmost = _Rb_tree_node_base::_S_minimum(__x); 426 if (__rightmost == __z) 427 if (__z->_M_left == 0) // __z->_M_right must be null also 428 __rightmost = __z->_M_parent; 429 // makes __rightmost == _M_header if __z == __root 430 else // __x == __z->_M_left 431 __rightmost = _Rb_tree_node_base::_S_maximum(__x); 432 } 433 if (__y->_M_color != _M_red) 434 { 435 while (__x != __root && (__x == 0 || __x->_M_color == _M_black)) 436 if (__x == __x_parent->_M_left) 437 { 438 _Rb_tree_node_base* __w = __x_parent->_M_right; 439 if (__w->_M_color == _M_red) 440 { 441 __w->_M_color = _M_black; 442 __x_parent->_M_color = _M_red; 443 _Rb_tree_rotate_left(__x_parent, __root); 444 __w = __x_parent->_M_right; 445 } 446 if ((__w->_M_left == 0 || 447 __w->_M_left->_M_color == _M_black) && 448 (__w->_M_right == 0 || 449 __w->_M_right->_M_color == _M_black)) 450 { 451 __w->_M_color = _M_red; 452 __x = __x_parent; 453 __x_parent = __x_parent->_M_parent; 454 } 455 else 456 { 457 if (__w->_M_right == 0 458 || __w->_M_right->_M_color == _M_black) 459 { 460 __w->_M_left->_M_color = _M_black; 461 __w->_M_color = _M_red; 462 _Rb_tree_rotate_right(__w, __root); 463 __w = __x_parent->_M_right; 464 } 465 __w->_M_color = __x_parent->_M_color; 466 __x_parent->_M_color = _M_black; 467 if (__w->_M_right) 468 __w->_M_right->_M_color = _M_black; 469 _Rb_tree_rotate_left(__x_parent, __root); 470 break; 471 } 472 } 473 else 474 { 475 // same as above, with _M_right <-> _M_left. 476 _Rb_tree_node_base* __w = __x_parent->_M_left; 477 if (__w->_M_color == _M_red) 478 { 479 __w->_M_color = _M_black; 480 __x_parent->_M_color = _M_red; 481 _Rb_tree_rotate_right(__x_parent, __root); 482 __w = __x_parent->_M_left; 483 } 484 if ((__w->_M_right == 0 || 485 __w->_M_right->_M_color == _M_black) && 486 (__w->_M_left == 0 || 487 __w->_M_left->_M_color == _M_black)) 488 { 489 __w->_M_color = _M_red; 490 __x = __x_parent; 491 __x_parent = __x_parent->_M_parent; 492 } 493 else 494 { 495 if (__w->_M_left == 0 || __w->_M_left->_M_color == _M_black) 496 { 497 __w->_M_right->_M_color = _M_black; 498 __w->_M_color = _M_red; 499 _Rb_tree_rotate_left(__w, __root); 500 __w = __x_parent->_M_left; 501 } 502 __w->_M_color = __x_parent->_M_color; 503 __x_parent->_M_color = _M_black; 504 if (__w->_M_left) 505 __w->_M_left->_M_color = _M_black; 506 _Rb_tree_rotate_right(__x_parent, __root); 507 break; 508 } 509 } 510 if (__x) __x->_M_color = _M_black; 511 } 512 return __y; 513 } 514 515 // Base class to encapsulate the differences between old SGI-style 516 // allocators and standard-conforming allocators. In order to avoid 517 // having an empty base class, we arbitrarily move one of rb_tree's 518 // data members into the base class. 519 520 // _Base for general standard-conforming allocators. 521 template<typename _Tp, typename _Alloc, bool _S_instanceless> 522 class _Rb_tree_alloc_base 523 { 524 public: 525 typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; 526 527 allocator_type 528 get_allocator() const { return _M_node_allocator; } 529 530 _Rb_tree_alloc_base(const allocator_type& __a) 531 : _M_node_allocator(__a), _M_header(0) {} 532 533 protected: 534 typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type 535 _M_node_allocator; 536 537 _Rb_tree_node<_Tp>* _M_header; 538 539 _Rb_tree_node<_Tp>* 540 _M_get_node() { return _M_node_allocator.allocate(1); } 541 542 void 543 _M_put_node(_Rb_tree_node<_Tp>* __p) 544 { _M_node_allocator.deallocate(__p, 1); } 545 }; 546 547 // Specialization for instanceless allocators. 548 template<typename _Tp, typename _Alloc> 549 class _Rb_tree_alloc_base<_Tp, _Alloc, true> 550 { 551 public: 552 typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; 553 allocator_type get_allocator() const { return allocator_type(); } 554 555 _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {} 556 557 protected: 558 _Rb_tree_node<_Tp>* _M_header; 559 560 typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type 561 _Alloc_type; 562 563 _Rb_tree_node<_Tp>* 564 _M_get_node() { return _Alloc_type::allocate(1); } 565 566 void 567 _M_put_node(_Rb_tree_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } 568 }; 569 570 template<typename _Tp, typename _Alloc> 571 struct _Rb_tree_base : public _Rb_tree_alloc_base<_Tp, _Alloc, 572 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 573 { 574 typedef _Rb_tree_alloc_base<_Tp, 575 _Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> _Base; 576 typedef typename _Base::allocator_type allocator_type; 577 578 _Rb_tree_base(const allocator_type& __a) 579 : _Base(__a) { _M_header = _M_get_node(); } 580 ~_Rb_tree_base() { _M_put_node(_M_header); } 581 }; 582 583 584 template<typename _Key, typename _Val, typename _KeyOfValue, 585 typename _Compare, typename _Alloc = allocator<_Val> > 586 class _Rb_tree : protected _Rb_tree_base<_Val, _Alloc> 587 { 588 typedef _Rb_tree_base<_Val, _Alloc> _Base; 589 590 protected: 591 typedef _Rb_tree_node_base* _Base_ptr; 592 typedef _Rb_tree_node<_Val> _Rb_tree_node; 593 594 public: 595 typedef _Key key_type; 596 typedef _Val value_type; 597 typedef value_type* pointer; 598 typedef const value_type* const_pointer; 599 typedef value_type& reference; 600 typedef const value_type& const_reference; 601 typedef _Rb_tree_node* _Link_type; 602 typedef size_t size_type; 603 typedef ptrdiff_t difference_type; 604 605 typedef typename _Base::allocator_type allocator_type; 606 allocator_type get_allocator() const { return _Base::get_allocator(); } 607 608 protected: 609 using _Base::_M_get_node; 610 using _Base::_M_put_node; 611 using _Base::_M_header; 612 613 _Link_type 614 _M_create_node(const value_type& __x) 615 { 616 _Link_type __tmp = _M_get_node(); 617 try 618 { _Construct(&__tmp->_M_value_field, __x); } 619 catch(...) 620 { 621 _M_put_node(__tmp); 622 __throw_exception_again; 623 } 624 return __tmp; 625 } 626 627 _Link_type 628 _M_clone_node(_Link_type __x) 629 { 630 _Link_type __tmp = _M_create_node(__x->_M_value_field); 631 __tmp->_M_color = __x->_M_color; 632 __tmp->_M_left = 0; 633 __tmp->_M_right = 0; 634 return __tmp; 635 } 636 637 void 638 destroy_node(_Link_type __p) 639 { 640 _Destroy(&__p->_M_value_field); 641 _M_put_node(__p); 642 } 643 644 size_type _M_node_count; // keeps track of size of tree 645 _Compare _M_key_compare; 646 647 _Link_type& 648 _M_root() const { return (_Link_type&) _M_header->_M_parent; } 649 650 _Link_type& 651 _M_leftmost() const { return (_Link_type&) _M_header->_M_left; } 652 653 _Link_type& 654 _M_rightmost() const { return (_Link_type&) _M_header->_M_right; } 655 656 static _Link_type& 657 _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); } 658 659 static _Link_type& 660 _S_right(_Link_type __x) { return (_Link_type&)(__x->_M_right); } 661 662 static _Link_type& 663 _S_parent(_Link_type __x) { return (_Link_type&)(__x->_M_parent); } 664 665 static reference 666 _S_value(_Link_type __x) { return __x->_M_value_field; } 667 668 static const _Key& 669 _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); } 670 671 static _Rb_tree_color& 672 _S_color(_Link_type __x) { return __x->_M_color; } 673 674 static _Link_type& 675 _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); } 676 677 static _Link_type& 678 _S_right(_Base_ptr __x) { return (_Link_type&)(__x->_M_right); } 679 680 static _Link_type& 681 _S_parent(_Base_ptr __x) { return (_Link_type&)(__x->_M_parent); } 682 683 static reference 684 _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; } 685 686 static const _Key& 687 _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));} 688 689 static _Rb_tree_color& 690 _S_color(_Base_ptr __x) { return (_Link_type(__x)->_M_color); } 691 692 static _Link_type 693 _S_minimum(_Link_type __x) 694 { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); } 695 696 static _Link_type 697 _S_maximum(_Link_type __x) 698 { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); } 699 700 public: 701 typedef _Rb_tree_iterator<value_type, reference, pointer> iterator; 702 typedef _Rb_tree_iterator<value_type, const_reference, const_pointer> 703 const_iterator; 704 705 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 706 typedef std::reverse_iterator<iterator> reverse_iterator; 707 708 private: 709 iterator 710 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 711 712 _Link_type 713 _M_copy(_Link_type __x, _Link_type __p); 714 715 void 716 _M_erase(_Link_type __x); 717 718 public: 719 // allocation/deallocation 720 _Rb_tree() 721 : _Base(allocator_type()), _M_node_count(0), _M_key_compare() 722 { _M_empty_initialize(); } 723 724 _Rb_tree(const _Compare& __comp) 725 : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 726 { _M_empty_initialize(); } 727 728 _Rb_tree(const _Compare& __comp, const allocator_type& __a) 729 : _Base(__a), _M_node_count(0), _M_key_compare(__comp) 730 { _M_empty_initialize(); } 731 732 _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) 733 : _Base(__x.get_allocator()), _M_node_count(0), 734 _M_key_compare(__x._M_key_compare) 735 { 736 if (__x._M_root() == 0) 737 _M_empty_initialize(); 738 else 739 { 740 _S_color(_M_header) = _M_red; 741 _M_root() = _M_copy(__x._M_root(), _M_header); 742 _M_leftmost() = _S_minimum(_M_root()); 743 _M_rightmost() = _S_maximum(_M_root()); 744 } 745 _M_node_count = __x._M_node_count; 746 } 747 748 ~_Rb_tree() { clear(); } 749 750 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 751 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x); 752 753 private: 754 void _M_empty_initialize() 755 { 756 _S_color(_M_header) = _M_red; // used to distinguish header from 757 // __root, in iterator.operator++ 758 _M_root() = 0; 759 _M_leftmost() = _M_header; 760 _M_rightmost() = _M_header; 761 } 762 763 public: 764 // Accessors. 765 _Compare 766 key_comp() const { return _M_key_compare; } 767 768 iterator 769 begin() { return _M_leftmost(); } 770 771 const_iterator 772 begin() const { return _M_leftmost(); } 773 774 iterator 775 end() { return _M_header; } 776 777 const_iterator 778 end() const { return _M_header; } 779 780 reverse_iterator 781 rbegin() { return reverse_iterator(end()); } 782 783 const_reverse_iterator 784 rbegin() const { return const_reverse_iterator(end()); } 785 786 reverse_iterator 787 rend() { return reverse_iterator(begin()); } 788 789 const_reverse_iterator 790 rend() const { return const_reverse_iterator(begin()); } 791 792 bool 793 empty() const { return _M_node_count == 0; } 794 795 size_type 796 size() const { return _M_node_count; } 797 798 size_type 799 max_size() const { return size_type(-1); } 800 801 void 802 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) 803 { 804 std::swap(_M_header, __t._M_header); 805 std::swap(_M_node_count, __t._M_node_count); 806 std::swap(_M_key_compare, __t._M_key_compare); 807 } 808 809 // Insert/erase. 810 pair<iterator,bool> 811 insert_unique(const value_type& __x); 812 813 iterator 814 insert_equal(const value_type& __x); 815 816 iterator 817 insert_unique(iterator __position, const value_type& __x); 818 819 iterator 820 insert_equal(iterator __position, const value_type& __x); 821 822 template<typename _InputIterator> 823 void 824 insert_unique(_InputIterator __first, _InputIterator __last); 825 826 template<typename _InputIterator> 827 void 828 insert_equal(_InputIterator __first, _InputIterator __last); 829 830 void 831 erase(iterator __position); 832 833 size_type 834 erase(const key_type& __x); 835 836 void 837 erase(iterator __first, iterator __last); 838 839 void 840 erase(const key_type* __first, const key_type* __last); 841 842 void 843 clear() 844 { 845 if (_M_node_count != 0) 846 { 847 _M_erase(_M_root()); 848 _M_leftmost() = _M_header; 849 _M_root() = 0; 850 _M_rightmost() = _M_header; 851 _M_node_count = 0; 852 } 853 } 854 855 // Set operations. 856 iterator 857 find(const key_type& __x); 858 859 const_iterator 860 find(const key_type& __x) const; 861 862 size_type 863 count(const key_type& __x) const; 864 865 iterator 866 lower_bound(const key_type& __x); 867 868 const_iterator 869 lower_bound(const key_type& __x) const; 870 871 iterator 872 upper_bound(const key_type& __x); 873 874 const_iterator 875 upper_bound(const key_type& __x) const; 876 877 pair<iterator,iterator> 878 equal_range(const key_type& __x); 879 880 pair<const_iterator, const_iterator> 881 equal_range(const key_type& __x) const; 882 883 // Debugging. 884 bool 885 __rb_verify() const; 886 }; 887 888 template<typename _Key, typename _Val, typename _KeyOfValue, 889 typename _Compare, typename _Alloc> 890 inline bool 891 operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 892 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 893 { 894 return __x.size() == __y.size() && 895 equal(__x.begin(), __x.end(), __y.begin()); 896 } 897 898 template<typename _Key, typename _Val, typename _KeyOfValue, 899 typename _Compare, typename _Alloc> 900 inline bool 901 operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 902 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 903 { 904 return lexicographical_compare(__x.begin(), __x.end(), 905 __y.begin(), __y.end()); 906 } 907 908 template<typename _Key, typename _Val, typename _KeyOfValue, 909 typename _Compare, typename _Alloc> 910 inline bool 911 operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 912 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 913 { return !(__x == __y); } 914 915 template<typename _Key, typename _Val, typename _KeyOfValue, 916 typename _Compare, typename _Alloc> 917 inline bool 918 operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 919 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 920 { return __y < __x; } 921 922 template<typename _Key, typename _Val, typename _KeyOfValue, 923 typename _Compare, typename _Alloc> 924 inline bool 925 operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 926 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 927 { return !(__y < __x); } 928 929 template<typename _Key, typename _Val, typename _KeyOfValue, 930 typename _Compare, typename _Alloc> 931 inline bool 932 operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 933 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 934 { return !(__x < __y); } 935 936 template<typename _Key, typename _Val, typename _KeyOfValue, 937 typename _Compare, typename _Alloc> 938 inline void 939 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 940 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 941 { __x.swap(__y); } 942 943 template<typename _Key, typename _Val, typename _KeyOfValue, 944 typename _Compare, typename _Alloc> 945 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 946 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 947 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) 948 { 949 if (this != &__x) 950 { 951 // Note that _Key may be a constant type. 952 clear(); 953 _M_node_count = 0; 954 _M_key_compare = __x._M_key_compare; 955 if (__x._M_root() == 0) 956 { 957 _M_root() = 0; 958 _M_leftmost() = _M_header; 959 _M_rightmost() = _M_header; 960 } 961 else 962 { 963 _M_root() = _M_copy(__x._M_root(), _M_header); 964 _M_leftmost() = _S_minimum(_M_root()); 965 _M_rightmost() = _S_maximum(_M_root()); 966 _M_node_count = __x._M_node_count; 967 } 968 } 969 return *this; 970 } 971 972 template<typename _Key, typename _Val, typename _KeyOfValue, 973 typename _Compare, typename _Alloc> 974 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 975 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 976 _M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Val& __v) 977 { 978 _Link_type __x = (_Link_type) __x_; 979 _Link_type __y = (_Link_type) __y_; 980 _Link_type __z; 981 982 if (__y == _M_header || __x != 0 || 983 _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) 984 { 985 __z = _M_create_node(__v); 986 _S_left(__y) = __z; // also makes _M_leftmost() = __z 987 // when __y == _M_header 988 if (__y == _M_header) 989 { 990 _M_root() = __z; 991 _M_rightmost() = __z; 992 } 993 else if (__y == _M_leftmost()) 994 _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node 995 } 996 else 997 { 998 __z = _M_create_node(__v); 999 _S_right(__y) = __z; 1000 // Maintain _M_rightmost() pointing to max node. 1001 if (__y == _M_rightmost()) 1002 _M_rightmost() = __z; 1003 } 1004 _S_parent(__z) = __y; 1005 _S_left(__z) = 0; 1006 _S_right(__z) = 0; 1007 _Rb_tree_rebalance(__z, _M_header->_M_parent); 1008 ++_M_node_count; 1009 return iterator(__z); 1010 } 1011 1012 template<typename _Key, typename _Val, typename _KeyOfValue, 1013 typename _Compare, typename _Alloc> 1014 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 1015 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1016 insert_equal(const _Val& __v) 1017 { 1018 _Link_type __y = _M_header; 1019 _Link_type __x = _M_root(); 1020 while (__x != 0) 1021 { 1022 __y = __x; 1023 __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 1024 _S_left(__x) : _S_right(__x); 1025 } 1026 return _M_insert(__x, __y, __v); 1027 } 1028 1029 template<typename _Key, typename _Val, typename _KeyOfValue, 1030 typename _Compare, typename _Alloc> 1031 pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, 1032 bool> 1033 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1034 insert_unique(const _Val& __v) 1035 { 1036 _Link_type __y = _M_header; 1037 _Link_type __x = _M_root(); 1038 bool __comp = true; 1039 while (__x != 0) 1040 { 1041 __y = __x; 1042 __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 1043 __x = __comp ? _S_left(__x) : _S_right(__x); 1044 } 1045 iterator __j = iterator(__y); 1046 if (__comp) 1047 if (__j == begin()) 1048 return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 1049 else 1050 --__j; 1051 if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 1052 return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 1053 return pair<iterator,bool>(__j, false); 1054 } 1055 1056 1057 template<typename _Key, typename _Val, typename _KeyOfValue, 1058 typename _Compare, typename _Alloc> 1059 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1060 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1061 insert_unique(iterator __position, const _Val& __v) 1062 { 1063 if (__position._M_node == _M_header->_M_left) 1064 { 1065 // begin() 1066 if (size() > 0 && 1067 _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) 1068 return _M_insert(__position._M_node, __position._M_node, __v); 1069 // first argument just needs to be non-null 1070 else 1071 return insert_unique(__v).first; 1072 } 1073 else if (__position._M_node == _M_header) 1074 { 1075 // end() 1076 if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v))) 1077 return _M_insert(0, _M_rightmost(), __v); 1078 else 1079 return insert_unique(__v).first; 1080 } 1081 else 1082 { 1083 iterator __before = __position; 1084 --__before; 1085 if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v)) 1086 && _M_key_compare(_KeyOfValue()(__v),_S_key(__position._M_node))) 1087 { 1088 if (_S_right(__before._M_node) == 0) 1089 return _M_insert(0, __before._M_node, __v); 1090 else 1091 return _M_insert(__position._M_node, __position._M_node, __v); 1092 // first argument just needs to be non-null 1093 } 1094 else 1095 return insert_unique(__v).first; 1096 } 1097 } 1098 1099 template<typename _Key, typename _Val, typename _KeyOfValue, 1100 typename _Compare, typename _Alloc> 1101 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 1102 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1103 insert_equal(iterator __position, const _Val& __v) 1104 { 1105 if (__position._M_node == _M_header->_M_left) 1106 { 1107 // begin() 1108 if (size() > 0 && 1109 !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) 1110 return _M_insert(__position._M_node, __position._M_node, __v); 1111 // first argument just needs to be non-null 1112 else 1113 return insert_equal(__v); 1114 } 1115 else if (__position._M_node == _M_header) 1116 { 1117 // end() 1118 if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost()))) 1119 return _M_insert(0, _M_rightmost(), __v); 1120 else 1121 return insert_equal(__v); 1122 } 1123 else 1124 { 1125 iterator __before = __position; 1126 --__before; 1127 if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node)) 1128 && !_M_key_compare(_S_key(__position._M_node), 1129 _KeyOfValue()(__v))) 1130 { 1131 if (_S_right(__before._M_node) == 0) 1132 return _M_insert(0, __before._M_node, __v); 1133 else 1134 return _M_insert(__position._M_node, __position._M_node, __v); 1135 // first argument just needs to be non-null 1136 } 1137 else 1138 return insert_equal(__v); 1139 } 1140 } 1141 1142 template<typename _Key, typename _Val, typename _KoV, 1143 typename _Cmp, typename _Alloc> 1144 template<class _II> 1145 void 1146 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: 1147 insert_equal(_II __first, _II __last) 1148 { 1149 for ( ; __first != __last; ++__first) 1150 insert_equal(*__first); 1151 } 1152 1153 template<typename _Key, typename _Val, typename _KoV, 1154 typename _Cmp, typename _Alloc> 1155 template<class _II> 1156 void 1157 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: 1158 insert_unique(_II __first, _II __last) 1159 { 1160 for ( ; __first != __last; ++__first) 1161 insert_unique(*__first); 1162 } 1163 1164 template<typename _Key, typename _Val, typename _KeyOfValue, 1165 typename _Compare, typename _Alloc> 1166 inline void 1167 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position) 1168 { 1169 _Link_type __y = 1170 (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node, 1171 _M_header->_M_parent, 1172 _M_header->_M_left, 1173 _M_header->_M_right); 1174 destroy_node(__y); 1175 --_M_node_count; 1176 } 1177 1178 template<typename _Key, typename _Val, typename _KeyOfValue, 1179 typename _Compare, typename _Alloc> 1180 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 1181 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x) 1182 { 1183 pair<iterator,iterator> __p = equal_range(__x); 1184 size_type __n = distance(__p.first, __p.second); 1185 erase(__p.first, __p.second); 1186 return __n; 1187 } 1188 1189 template<typename _Key, typename _Val, typename _KoV, 1190 typename _Compare, typename _Alloc> 1191 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 1192 _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>:: 1193 _M_copy(_Link_type __x, _Link_type __p) 1194 { 1195 // Structural copy. __x and __p must be non-null. 1196 _Link_type __top = _M_clone_node(__x); 1197 __top->_M_parent = __p; 1198 1199 try 1200 { 1201 if (__x->_M_right) 1202 __top->_M_right = _M_copy(_S_right(__x), __top); 1203 __p = __top; 1204 __x = _S_left(__x); 1205 1206 while (__x != 0) 1207 { 1208 _Link_type __y = _M_clone_node(__x); 1209 __p->_M_left = __y; 1210 __y->_M_parent = __p; 1211 if (__x->_M_right) 1212 __y->_M_right = _M_copy(_S_right(__x), __y); 1213 __p = __y; 1214 __x = _S_left(__x); 1215 } 1216 } 1217 catch(...) 1218 { 1219 _M_erase(__top); 1220 __throw_exception_again; 1221 } 1222 return __top; 1223 } 1224 1225 template<typename _Key, typename _Val, typename _KeyOfValue, 1226 typename _Compare, typename _Alloc> 1227 void 1228 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x) 1229 { 1230 // Erase without rebalancing. 1231 while (__x != 0) 1232 { 1233 _M_erase(_S_right(__x)); 1234 _Link_type __y = _S_left(__x); 1235 destroy_node(__x); 1236 __x = __y; 1237 } 1238 } 1239 1240 template<typename _Key, typename _Val, typename _KeyOfValue, 1241 typename _Compare, typename _Alloc> 1242 void 1243 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1244 erase(iterator __first, iterator __last) 1245 { 1246 if (__first == begin() && __last == end()) 1247 clear(); 1248 else 1249 while (__first != __last) erase(__first++); 1250 } 1251 1252 template<typename _Key, typename _Val, typename _KeyOfValue, 1253 typename _Compare, typename _Alloc> 1254 void 1255 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1256 erase(const _Key* __first, const _Key* __last) 1257 { 1258 while (__first != __last) 1259 erase(*__first++); 1260 } 1261 1262 template<typename _Key, typename _Val, typename _KeyOfValue, 1263 typename _Compare, typename _Alloc> 1264 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 1265 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) 1266 { 1267 _Link_type __y = _M_header; // Last node which is not less than __k. 1268 _Link_type __x = _M_root(); // Current node. 1269 1270 while (__x != 0) 1271 if (!_M_key_compare(_S_key(__x), __k)) 1272 __y = __x, __x = _S_left(__x); 1273 else 1274 __x = _S_right(__x); 1275 1276 iterator __j = iterator(__y); 1277 return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? 1278 end() : __j; 1279 } 1280 1281 template<typename _Key, typename _Val, typename _KeyOfValue, 1282 typename _Compare, typename _Alloc> 1283 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 1284 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1285 find(const _Key& __k) const 1286 { 1287 _Link_type __y = _M_header; // Last node which is not less than __k. 1288 _Link_type __x = _M_root(); // Current node. 1289 1290 while (__x != 0) 1291 { 1292 if (!_M_key_compare(_S_key(__x), __k)) 1293 __y = __x, __x = _S_left(__x); 1294 else 1295 __x = _S_right(__x); 1296 } 1297 const_iterator __j = const_iterator(__y); 1298 return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? 1299 end() : __j; 1300 } 1301 1302 template<typename _Key, typename _Val, typename _KeyOfValue, 1303 typename _Compare, typename _Alloc> 1304 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 1305 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1306 count(const _Key& __k) const 1307 { 1308 pair<const_iterator, const_iterator> __p = equal_range(__k); 1309 size_type __n = distance(__p.first, __p.second); 1310 return __n; 1311 } 1312 1313 template<typename _Key, typename _Val, typename _KeyOfValue, 1314 typename _Compare, typename _Alloc> 1315 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 1316 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1317 lower_bound(const _Key& __k) 1318 { 1319 _Link_type __y = _M_header; /* Last node which is not less than __k. */ 1320 _Link_type __x = _M_root(); /* Current node. */ 1321 1322 while (__x != 0) 1323 if (!_M_key_compare(_S_key(__x), __k)) 1324 __y = __x, __x = _S_left(__x); 1325 else 1326 __x = _S_right(__x); 1327 1328 return iterator(__y); 1329 } 1330 1331 template<typename _Key, typename _Val, typename _KeyOfValue, 1332 typename _Compare, typename _Alloc> 1333 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 1334 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1335 lower_bound(const _Key& __k) const 1336 { 1337 _Link_type __y = _M_header; /* Last node which is not less than __k. */ 1338 _Link_type __x = _M_root(); /* Current node. */ 1339 1340 while (__x != 0) 1341 if (!_M_key_compare(_S_key(__x), __k)) 1342 __y = __x, __x = _S_left(__x); 1343 else 1344 __x = _S_right(__x); 1345 1346 return const_iterator(__y); 1347 } 1348 1349 template<typename _Key, typename _Val, typename _KeyOfValue, 1350 typename _Compare, typename _Alloc> 1351 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 1352 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1353 upper_bound(const _Key& __k) 1354 { 1355 _Link_type __y = _M_header; /* Last node which is greater than __k. */ 1356 _Link_type __x = _M_root(); /* Current node. */ 1357 1358 while (__x != 0) 1359 if (_M_key_compare(__k, _S_key(__x))) 1360 __y = __x, __x = _S_left(__x); 1361 else 1362 __x = _S_right(__x); 1363 1364 return iterator(__y); 1365 } 1366 1367 template<typename _Key, typename _Val, typename _KeyOfValue, 1368 typename _Compare, typename _Alloc> 1369 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 1370 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1371 upper_bound(const _Key& __k) const 1372 { 1373 _Link_type __y = _M_header; /* Last node which is greater than __k. */ 1374 _Link_type __x = _M_root(); /* Current node. */ 1375 1376 while (__x != 0) 1377 if (_M_key_compare(__k, _S_key(__x))) 1378 __y = __x, __x = _S_left(__x); 1379 else 1380 __x = _S_right(__x); 1381 1382 return const_iterator(__y); 1383 } 1384 1385 template<typename _Key, typename _Val, typename _KeyOfValue, 1386 typename _Compare, typename _Alloc> 1387 inline 1388 pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, 1389 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator> 1390 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 1391 equal_range(const _Key& __k) 1392 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); } 1393 1394 template<typename _Key, typename _Val, typename _KoV, 1395 typename _Compare, typename _Alloc> 1396 inline 1397 pair<typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator, 1398 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator> 1399 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc> 1400 ::equal_range(const _Key& __k) const 1401 { 1402 return pair<const_iterator,const_iterator>(lower_bound(__k), 1403 upper_bound(__k)); 1404 } 1405 1406 inline int 1407 __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) 1408 { 1409 if (__node == 0) 1410 return 0; 1411 int __sum = 0; 1412 do 1413 { 1414 if (__node->_M_color == _M_black) 1415 ++__sum; 1416 if (__node == __root) 1417 break; 1418 __node = __node->_M_parent; 1419 } 1420 while (1); 1421 return __sum; 1422 } 1423 1424 template<typename _Key, typename _Val, typename _KeyOfValue, 1425 typename _Compare, typename _Alloc> 1426 bool 1427 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 1428 { 1429 if (_M_node_count == 0 || begin() == end()) 1430 return _M_node_count == 0 && begin() == end() && 1431 _M_header->_M_left == _M_header && _M_header->_M_right == _M_header; 1432 1433 int __len = __black_count(_M_leftmost(), _M_root()); 1434 for (const_iterator __it = begin(); __it != end(); ++__it) 1435 { 1436 _Link_type __x = (_Link_type) __it._M_node; 1437 _Link_type __L = _S_left(__x); 1438 _Link_type __R = _S_right(__x); 1439 1440 if (__x->_M_color == _M_red) 1441 if ((__L && __L->_M_color == _M_red) 1442 || (__R && __R->_M_color == _M_red)) 1443 return false; 1444 1445 if (__L && _M_key_compare(_S_key(__x), _S_key(__L))) 1446 return false; 1447 if (__R && _M_key_compare(_S_key(__R), _S_key(__x))) 1448 return false; 1449 1450 if (!__L && !__R && __black_count(__x, _M_root()) != __len) 1451 return false; 1452 } 1453 1454 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 1455 return false; 1456 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 1457 return false; 1458 return true; 1459 } 1460} // namespace std 1461 1462#endif 1463