1 : // RB tree implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2002, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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 _TREE_H
64 : #define _TREE_H 1
65 :
66 : #include <bits/stl_algobase.h>
67 : #include <bits/allocator.h>
68 : #include <bits/stl_construct.h>
69 : #include <bits/stl_function.h>
70 : #include <bits/cpp_type_traits.h>
71 :
72 : namespace std
73 : {
74 : // Red-black tree class, designed for use in implementing STL
75 : // associative containers (set, multiset, map, and multimap). The
76 : // insertion and deletion algorithms are based on those in Cormen,
77 : // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
78 : // 1990), except that
79 : //
80 : // (1) the header cell is maintained with links not only to the root
81 : // but also to the leftmost node of the tree, to enable constant
82 : // time begin(), and to the rightmost node of the tree, to enable
83 : // linear time performance when used with the generic set algorithms
84 : // (set_union, etc.)
85 : //
86 : // (2) when a node being deleted has two children its successor node
87 : // is relinked into its place, rather than copied, so that the only
88 : // iterators invalidated are those referring to the deleted node.
89 :
90 : enum _Rb_tree_color { _S_red = false, _S_black = true };
91 :
92 : struct _Rb_tree_node_base
93 : {
94 : typedef _Rb_tree_node_base* _Base_ptr;
95 : typedef const _Rb_tree_node_base* _Const_Base_ptr;
96 :
97 : _Rb_tree_color _M_color;
98 : _Base_ptr _M_parent;
99 : _Base_ptr _M_left;
100 : _Base_ptr _M_right;
101 :
102 : static _Base_ptr
103 : _S_minimum(_Base_ptr __x)
104 : {
105 : while (__x->_M_left != 0) __x = __x->_M_left;
106 : return __x;
107 : }
108 :
109 : static _Const_Base_ptr
110 : _S_minimum(_Const_Base_ptr __x)
111 : {
112 : while (__x->_M_left != 0) __x = __x->_M_left;
113 : return __x;
114 : }
115 :
116 : static _Base_ptr
117 : _S_maximum(_Base_ptr __x)
118 : {
119 : while (__x->_M_right != 0) __x = __x->_M_right;
120 : return __x;
121 : }
122 :
123 : static _Const_Base_ptr
124 : _S_maximum(_Const_Base_ptr __x)
125 : {
126 : while (__x->_M_right != 0) __x = __x->_M_right;
127 : return __x;
128 : }
129 : };
130 :
131 : template<typename _Val>
132 : struct _Rb_tree_node : public _Rb_tree_node_base
133 : {
134 : typedef _Rb_tree_node<_Val>* _Link_type;
135 : _Val _M_value_field;
136 : };
137 :
138 : _Rb_tree_node_base*
139 : _Rb_tree_increment(_Rb_tree_node_base* __x);
140 :
141 : const _Rb_tree_node_base*
142 : _Rb_tree_increment(const _Rb_tree_node_base* __x);
143 :
144 : _Rb_tree_node_base*
145 : _Rb_tree_decrement(_Rb_tree_node_base* __x);
146 :
147 : const _Rb_tree_node_base*
148 : _Rb_tree_decrement(const _Rb_tree_node_base* __x);
149 :
150 : template<typename _Tp>
151 : struct _Rb_tree_iterator
152 : {
153 : typedef _Tp value_type;
154 : typedef _Tp& reference;
155 : typedef _Tp* pointer;
156 :
157 : typedef bidirectional_iterator_tag iterator_category;
158 : typedef ptrdiff_t difference_type;
159 :
160 : typedef _Rb_tree_iterator<_Tp> _Self;
161 : typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
162 : typedef _Rb_tree_node<_Tp>* _Link_type;
163 :
164 : _Rb_tree_iterator()
165 : : _M_node() { }
166 :
167 : explicit
168 350772140 : _Rb_tree_iterator(_Link_type __x)
169 350772140 : : _M_node(__x) { }
170 :
171 : reference
172 105387540 : operator*() const
173 105387540 : { return static_cast<_Link_type>(_M_node)->_M_value_field; }
174 :
175 : pointer
176 1896338 : operator->() const
177 1896338 : { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
178 :
179 : _Self&
180 535224 : operator++()
181 : {
182 535224 : _M_node = _Rb_tree_increment(_M_node);
183 535224 : return *this;
184 : }
185 :
186 : _Self
187 625701 : operator++(int)
188 : {
189 625701 : _Self __tmp = *this;
190 625701 : _M_node = _Rb_tree_increment(_M_node);
191 625701 : return __tmp;
192 : }
193 :
194 : _Self&
195 1386846 : operator--()
196 : {
197 1386846 : _M_node = _Rb_tree_decrement(_M_node);
198 1386846 : return *this;
199 : }
200 :
201 : _Self
202 : operator--(int)
203 : {
204 : _Self __tmp = *this;
205 : _M_node = _Rb_tree_decrement(_M_node);
206 : return __tmp;
207 : }
208 :
209 : bool
210 62371299 : operator==(const _Self& __x) const
211 62371299 : { return _M_node == __x._M_node; }
212 :
213 : bool
214 104335714 : operator!=(const _Self& __x) const
215 104335714 : { return _M_node != __x._M_node; }
216 :
217 : _Base_ptr _M_node;
218 : };
219 :
220 : template<typename _Tp>
221 : struct _Rb_tree_const_iterator
222 : {
223 : typedef _Tp value_type;
224 : typedef const _Tp& reference;
225 : typedef const _Tp* pointer;
226 :
227 : typedef _Rb_tree_iterator<_Tp> iterator;
228 :
229 : typedef bidirectional_iterator_tag iterator_category;
230 : typedef ptrdiff_t difference_type;
231 :
232 : typedef _Rb_tree_const_iterator<_Tp> _Self;
233 : typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
234 : typedef const _Rb_tree_node<_Tp>* _Link_type;
235 :
236 6321 : _Rb_tree_const_iterator()
237 6321 : : _M_node() { }
238 :
239 : explicit
240 13010693 : _Rb_tree_const_iterator(_Link_type __x)
241 13010693 : : _M_node(__x) { }
242 :
243 14044125 : _Rb_tree_const_iterator(const iterator& __it)
244 14044125 : : _M_node(__it._M_node) { }
245 :
246 : reference
247 8999276 : operator*() const
248 8999276 : { return static_cast<_Link_type>(_M_node)->_M_value_field; }
249 :
250 : pointer
251 1140652 : operator->() const
252 1140652 : { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
253 :
254 : _Self&
255 3189766 : operator++()
256 : {
257 3189766 : _M_node = _Rb_tree_increment(_M_node);
258 3189766 : return *this;
259 : }
260 :
261 : _Self
262 0 : operator++(int)
263 : {
264 0 : _Self __tmp = *this;
265 0 : _M_node = _Rb_tree_increment(_M_node);
266 0 : return __tmp;
267 : }
268 :
269 : _Self&
270 0 : operator--()
271 : {
272 0 : _M_node = _Rb_tree_decrement(_M_node);
273 0 : return *this;
274 : }
275 :
276 : _Self
277 : operator--(int)
278 : {
279 : _Self __tmp = *this;
280 : _M_node = _Rb_tree_decrement(_M_node);
281 : return __tmp;
282 : }
283 :
284 : bool
285 6251088 : operator==(const _Self& __x) const
286 6251088 : { return _M_node == __x._M_node; }
287 :
288 : bool
289 7126112 : operator!=(const _Self& __x) const
290 7126112 : { return _M_node != __x._M_node; }
291 :
292 : _Base_ptr _M_node;
293 : };
294 :
295 : template<typename _Val>
296 : inline bool
297 : operator==(const _Rb_tree_iterator<_Val>& __x,
298 : const _Rb_tree_const_iterator<_Val>& __y)
299 : { return __x._M_node == __y._M_node; }
300 :
301 : template<typename _Val>
302 : inline bool
303 : operator!=(const _Rb_tree_iterator<_Val>& __x,
304 : const _Rb_tree_const_iterator<_Val>& __y)
305 : { return __x._M_node != __y._M_node; }
306 :
307 : void
308 : _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
309 : _Rb_tree_node_base*& __root);
310 :
311 : void
312 : _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
313 : _Rb_tree_node_base*& __root);
314 :
315 : void
316 : _Rb_tree_insert_and_rebalance(const bool __insert_left,
317 : _Rb_tree_node_base* __x,
318 : _Rb_tree_node_base* __p,
319 : _Rb_tree_node_base& __header);
320 :
321 : _Rb_tree_node_base*
322 : _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
323 : _Rb_tree_node_base& __header);
324 :
325 :
326 : template<typename _Key, typename _Val, typename _KeyOfValue,
327 : typename _Compare, typename _Alloc = allocator<_Val> >
328 : class _Rb_tree
329 : {
330 : typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
331 : _Node_allocator;
332 :
333 : protected:
334 : typedef _Rb_tree_node_base* _Base_ptr;
335 : typedef const _Rb_tree_node_base* _Const_Base_ptr;
336 : typedef _Rb_tree_node<_Val> _Rb_tree_node;
337 :
338 : public:
339 : typedef _Key key_type;
340 : typedef _Val value_type;
341 : typedef value_type* pointer;
342 : typedef const value_type* const_pointer;
343 : typedef value_type& reference;
344 : typedef const value_type& const_reference;
345 : typedef _Rb_tree_node* _Link_type;
346 : typedef const _Rb_tree_node* _Const_Link_type;
347 : typedef size_t size_type;
348 : typedef ptrdiff_t difference_type;
349 : typedef _Alloc allocator_type;
350 :
351 : allocator_type
352 15924489 : get_allocator() const
353 15924489 : { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
354 :
355 : protected:
356 : _Rb_tree_node*
357 8490195 : _M_get_node()
358 8490195 : { return _M_impl._Node_allocator::allocate(1); }
359 :
360 : void
361 7434294 : _M_put_node(_Rb_tree_node* __p)
362 7434294 : { _M_impl._Node_allocator::deallocate(__p, 1); }
363 :
364 : _Link_type
365 8490195 : _M_create_node(const value_type& __x)
366 : {
367 8490195 : _Link_type __tmp = _M_get_node();
368 : try
369 8490195 : { get_allocator().construct(&__tmp->_M_value_field, __x); }
370 0 : catch(...)
371 : {
372 0 : _M_put_node(__tmp);
373 0 : __throw_exception_again;
374 : }
375 8490195 : return __tmp;
376 : }
377 :
378 : _Link_type
379 : _M_clone_node(_Const_Link_type __x)
380 : {
381 : _Link_type __tmp = _M_create_node(__x->_M_value_field);
382 : __tmp->_M_color = __x->_M_color;
383 : __tmp->_M_left = 0;
384 : __tmp->_M_right = 0;
385 : return __tmp;
386 : }
387 :
388 : void
389 7434294 : destroy_node(_Link_type __p)
390 : {
391 7434294 : get_allocator().destroy(&__p->_M_value_field);
392 7434294 : _M_put_node(__p);
393 : }
394 :
395 : protected:
396 : template<typename _Key_compare,
397 : bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
398 : struct _Rb_tree_impl : public _Node_allocator
399 4568983 : {
400 : _Key_compare _M_key_compare;
401 : _Rb_tree_node_base _M_header;
402 : size_type _M_node_count; // Keeps track of size of tree.
403 :
404 : _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
405 5147404 : const _Key_compare& __comp = _Key_compare())
406 : : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
407 5147404 : _M_node_count(0)
408 : {
409 5147404 : this->_M_header._M_color = _S_red;
410 5147404 : this->_M_header._M_parent = 0;
411 5147404 : this->_M_header._M_left = &this->_M_header;
412 5147404 : this->_M_header._M_right = &this->_M_header;
413 : }
414 : };
415 :
416 : // Specialization for _Comparison types that are not capable of
417 : // being base classes / super classes.
418 : template<typename _Key_compare>
419 : struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
420 : {
421 : _Key_compare _M_key_compare;
422 : _Rb_tree_node_base _M_header;
423 : size_type _M_node_count; // Keeps track of size of tree.
424 :
425 : _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
426 : const _Key_compare& __comp = _Key_compare())
427 : : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
428 : _M_node_count(0)
429 : {
430 : this->_M_header._M_color = _S_red;
431 : this->_M_header._M_parent = 0;
432 : this->_M_header._M_left = &this->_M_header;
433 : this->_M_header._M_right = &this->_M_header;
434 : }
435 : };
436 :
437 : _Rb_tree_impl<_Compare> _M_impl;
438 :
439 : protected:
440 : _Base_ptr&
441 154878864 : _M_root()
442 154878864 : { return this->_M_impl._M_header._M_parent; }
443 :
444 : _Const_Base_ptr
445 : _M_root() const
446 : { return this->_M_impl._M_header._M_parent; }
447 :
448 : _Base_ptr&
449 155790893 : _M_leftmost()
450 155790893 : { return this->_M_impl._M_header._M_left; }
451 :
452 : _Const_Base_ptr
453 : _M_leftmost() const
454 : { return this->_M_impl._M_header._M_left; }
455 :
456 : _Base_ptr&
457 158346034 : _M_rightmost()
458 158346034 : { return this->_M_impl._M_header._M_right; }
459 :
460 : _Const_Base_ptr
461 : _M_rightmost() const
462 : { return this->_M_impl._M_header._M_right; }
463 :
464 : _Link_type
465 226533855 : _M_begin()
466 226533855 : { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
467 :
468 : _Const_Link_type
469 1360758 : _M_begin() const
470 : {
471 : return static_cast<_Const_Link_type>
472 1360758 : (this->_M_impl._M_header._M_parent);
473 : }
474 :
475 : _Link_type
476 388542503 : _M_end()
477 388542503 : { return static_cast<_Link_type>(&this->_M_impl._M_header); }
478 :
479 : _Const_Link_type
480 1360758 : _M_end() const
481 1360758 : { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
482 :
483 : static const_reference
484 677268479 : _S_value(_Const_Link_type __x)
485 677268479 : { return __x->_M_value_field; }
486 :
487 : static const _Key&
488 677268479 : _S_key(_Const_Link_type __x)
489 677268479 : { return _KeyOfValue()(_S_value(__x)); }
490 :
491 : static _Link_type
492 314430621 : _S_left(_Base_ptr __x)
493 314430621 : { return static_cast<_Link_type>(__x->_M_left); }
494 :
495 : static _Const_Link_type
496 5463548 : _S_left(_Const_Base_ptr __x)
497 5463548 : { return static_cast<_Const_Link_type>(__x->_M_left); }
498 :
499 : static _Link_type
500 369663558 : _S_right(_Base_ptr __x)
501 369663558 : { return static_cast<_Link_type>(__x->_M_right); }
502 :
503 : static _Const_Link_type
504 3159467 : _S_right(_Const_Base_ptr __x)
505 3159467 : { return static_cast<_Const_Link_type>(__x->_M_right); }
506 :
507 : static const_reference
508 19062408 : _S_value(_Const_Base_ptr __x)
509 19062408 : { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
510 :
511 : static const _Key&
512 19062408 : _S_key(_Const_Base_ptr __x)
513 19062408 : { return _KeyOfValue()(_S_value(__x)); }
514 :
515 : static _Base_ptr
516 : _S_minimum(_Base_ptr __x)
517 : { return _Rb_tree_node_base::_S_minimum(__x); }
518 :
519 : static _Const_Base_ptr
520 : _S_minimum(_Const_Base_ptr __x)
521 : { return _Rb_tree_node_base::_S_minimum(__x); }
522 :
523 : static _Base_ptr
524 : _S_maximum(_Base_ptr __x)
525 : { return _Rb_tree_node_base::_S_maximum(__x); }
526 :
527 : static _Const_Base_ptr
528 : _S_maximum(_Const_Base_ptr __x)
529 : { return _Rb_tree_node_base::_S_maximum(__x); }
530 :
531 : public:
532 : typedef _Rb_tree_iterator<value_type> iterator;
533 : typedef _Rb_tree_const_iterator<value_type> const_iterator;
534 :
535 : typedef std::reverse_iterator<iterator> reverse_iterator;
536 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
537 :
538 : private:
539 : iterator
540 : _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
541 :
542 : const_iterator
543 : _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
544 : const value_type& __v);
545 :
546 : _Link_type
547 : _M_copy(_Const_Link_type __x, _Link_type __p);
548 :
549 : void
550 : _M_erase(_Link_type __x);
551 :
552 : public:
553 : // allocation/deallocation
554 : _Rb_tree()
555 : { }
556 :
557 : _Rb_tree(const _Compare& __comp)
558 : : _M_impl(allocator_type(), __comp)
559 : { }
560 :
561 5147404 : _Rb_tree(const _Compare& __comp, const allocator_type& __a)
562 5147404 : : _M_impl(__a, __comp)
563 5147404 : { }
564 :
565 : _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
566 : : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
567 : {
568 : if (__x._M_root() != 0)
569 : {
570 : _M_root() = _M_copy(__x._M_begin(), _M_end());
571 : _M_leftmost() = _S_minimum(_M_root());
572 : _M_rightmost() = _S_maximum(_M_root());
573 : _M_impl._M_node_count = __x._M_impl._M_node_count;
574 : }
575 : }
576 :
577 4568983 : ~_Rb_tree()
578 4568983 : { _M_erase(_M_begin()); }
579 :
580 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
581 : operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
582 :
583 : // Accessors.
584 : _Compare
585 52490502 : key_comp() const
586 52490502 : { return _M_impl._M_key_compare; }
587 :
588 : iterator
589 106798347 : begin()
590 : {
591 : return iterator(static_cast<_Link_type>
592 106798347 : (this->_M_impl._M_header._M_left));
593 : }
594 :
595 : const_iterator
596 2674662 : begin() const
597 : {
598 : return const_iterator(static_cast<_Const_Link_type>
599 2674662 : (this->_M_impl._M_header._M_left));
600 : }
601 :
602 : iterator
603 168884965 : end()
604 168884965 : { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
605 :
606 : const_iterator
607 8975273 : end() const
608 : {
609 : return const_iterator(static_cast<_Const_Link_type>
610 8975273 : (&this->_M_impl._M_header));
611 : }
612 :
613 : reverse_iterator
614 : rbegin()
615 : { return reverse_iterator(end()); }
616 :
617 : const_reverse_iterator
618 : rbegin() const
619 : { return const_reverse_iterator(end()); }
620 :
621 : reverse_iterator
622 : rend()
623 : { return reverse_iterator(begin()); }
624 :
625 : const_reverse_iterator
626 : rend() const
627 : { return const_reverse_iterator(begin()); }
628 :
629 : bool
630 1008120 : empty() const
631 1008120 : { return _M_impl._M_node_count == 0; }
632 :
633 : size_type
634 2866300 : size() const
635 2866300 : { return _M_impl._M_node_count; }
636 :
637 : size_type
638 : max_size() const
639 : { return size_type(-1); }
640 :
641 : void
642 : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
643 :
644 : // Insert/erase.
645 : pair<iterator,bool>
646 : insert_unique(const value_type& __x);
647 :
648 : iterator
649 : insert_equal(const value_type& __x);
650 :
651 : iterator
652 : insert_unique(iterator __position, const value_type& __x);
653 :
654 : const_iterator
655 : insert_unique(const_iterator __position, const value_type& __x);
656 :
657 : iterator
658 : insert_equal(iterator __position, const value_type& __x);
659 :
660 : const_iterator
661 : insert_equal(const_iterator __position, const value_type& __x);
662 :
663 : template<typename _InputIterator>
664 : void
665 : insert_unique(_InputIterator __first, _InputIterator __last);
666 :
667 : template<typename _InputIterator>
668 : void
669 : insert_equal(_InputIterator __first, _InputIterator __last);
670 :
671 : void
672 : erase(iterator __position);
673 :
674 : void
675 : erase(const_iterator __position);
676 :
677 : size_type
678 : erase(const key_type& __x);
679 :
680 : void
681 : erase(iterator __first, iterator __last);
682 :
683 : void
684 : erase(const_iterator __first, const_iterator __last);
685 :
686 : void
687 : erase(const key_type* __first, const key_type* __last);
688 :
689 : void
690 154878864 : clear()
691 : {
692 154878864 : _M_erase(_M_begin());
693 154878864 : _M_leftmost() = _M_end();
694 154878864 : _M_root() = 0;
695 154878864 : _M_rightmost() = _M_end();
696 154878864 : _M_impl._M_node_count = 0;
697 : }
698 :
699 : // Set operations.
700 : iterator
701 : find(const key_type& __x);
702 :
703 : const_iterator
704 : find(const key_type& __x) const;
705 :
706 : size_type
707 : count(const key_type& __x) const;
708 :
709 : iterator
710 : lower_bound(const key_type& __x);
711 :
712 : const_iterator
713 : lower_bound(const key_type& __x) const;
714 :
715 : iterator
716 : upper_bound(const key_type& __x);
717 :
718 : const_iterator
719 : upper_bound(const key_type& __x) const;
720 :
721 : pair<iterator,iterator>
722 : equal_range(const key_type& __x);
723 :
724 : pair<const_iterator, const_iterator>
725 : equal_range(const key_type& __x) const;
726 :
727 : // Debugging.
728 : bool
729 : __rb_verify() const;
730 : };
731 :
732 : template<typename _Key, typename _Val, typename _KeyOfValue,
733 : typename _Compare, typename _Alloc>
734 : inline bool
735 : operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
736 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
737 : {
738 : return __x.size() == __y.size()
739 : && std::equal(__x.begin(), __x.end(), __y.begin());
740 : }
741 :
742 : template<typename _Key, typename _Val, typename _KeyOfValue,
743 : typename _Compare, typename _Alloc>
744 : inline bool
745 : operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
746 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
747 : {
748 : return std::lexicographical_compare(__x.begin(), __x.end(),
749 : __y.begin(), __y.end());
750 : }
751 :
752 : template<typename _Key, typename _Val, typename _KeyOfValue,
753 : typename _Compare, typename _Alloc>
754 : inline bool
755 : operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
756 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
757 : { return !(__x == __y); }
758 :
759 : template<typename _Key, typename _Val, typename _KeyOfValue,
760 : typename _Compare, typename _Alloc>
761 : inline bool
762 : operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
763 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
764 : { return __y < __x; }
765 :
766 : template<typename _Key, typename _Val, typename _KeyOfValue,
767 : typename _Compare, typename _Alloc>
768 : inline bool
769 : operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
770 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
771 : { return !(__y < __x); }
772 :
773 : template<typename _Key, typename _Val, typename _KeyOfValue,
774 : typename _Compare, typename _Alloc>
775 : inline bool
776 : operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
777 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
778 : { return !(__x < __y); }
779 :
780 : template<typename _Key, typename _Val, typename _KeyOfValue,
781 : typename _Compare, typename _Alloc>
782 : inline void
783 : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
784 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
785 : { __x.swap(__y); }
786 :
787 : template<typename _Key, typename _Val, typename _KeyOfValue,
788 : typename _Compare, typename _Alloc>
789 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
790 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
791 : operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
792 : {
793 : if (this != &__x)
794 : {
795 : // Note that _Key may be a constant type.
796 : clear();
797 : _M_impl._M_key_compare = __x._M_impl._M_key_compare;
798 : if (__x._M_root() != 0)
799 : {
800 : _M_root() = _M_copy(__x._M_begin(), _M_end());
801 : _M_leftmost() = _S_minimum(_M_root());
802 : _M_rightmost() = _S_maximum(_M_root());
803 : _M_impl._M_node_count = __x._M_impl._M_node_count;
804 : }
805 : }
806 : return *this;
807 : }
808 :
809 : template<typename _Key, typename _Val, typename _KeyOfValue,
810 : typename _Compare, typename _Alloc>
811 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
812 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
813 8490195 : _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
814 : {
815 : bool __insert_left = (__x != 0 || __p == _M_end()
816 : || _M_impl._M_key_compare(_KeyOfValue()(__v),
817 8490195 : _S_key(__p)));
818 :
819 8490195 : _Link_type __z = _M_create_node(__v);
820 :
821 8490195 : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
822 : this->_M_impl._M_header);
823 8490195 : ++_M_impl._M_node_count;
824 8490195 : return iterator(__z);
825 : }
826 :
827 : template<typename _Key, typename _Val, typename _KeyOfValue,
828 : typename _Compare, typename _Alloc>
829 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
830 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
831 0 : _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
832 : {
833 : bool __insert_left = (__x != 0 || __p == _M_end()
834 : || _M_impl._M_key_compare(_KeyOfValue()(__v),
835 0 : _S_key(__p)));
836 :
837 0 : _Link_type __z = _M_create_node(__v);
838 :
839 0 : _Rb_tree_insert_and_rebalance(__insert_left, __z,
840 : const_cast<_Base_ptr>(__p),
841 : this->_M_impl._M_header);
842 0 : ++_M_impl._M_node_count;
843 0 : return const_iterator(__z);
844 : }
845 :
846 : template<typename _Key, typename _Val, typename _KeyOfValue,
847 : typename _Compare, typename _Alloc>
848 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
849 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
850 487375 : insert_equal(const _Val& __v)
851 : {
852 487375 : _Link_type __x = _M_begin();
853 487375 : _Link_type __y = _M_end();
854 13457573 : while (__x != 0)
855 : {
856 12482823 : __y = __x;
857 12482823 : __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
858 : _S_left(__x) : _S_right(__x);
859 : }
860 487375 : return _M_insert(__x, __y, __v);
861 : }
862 :
863 : template<typename _Key, typename _Val, typename _KeyOfValue,
864 : typename _Compare, typename _Alloc>
865 : void
866 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
867 : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
868 : {
869 : if (_M_root() == 0)
870 : {
871 : if (__t._M_root() != 0)
872 : {
873 : _M_root() = __t._M_root();
874 : _M_leftmost() = __t._M_leftmost();
875 : _M_rightmost() = __t._M_rightmost();
876 : _M_root()->_M_parent = _M_end();
877 :
878 : __t._M_root() = 0;
879 : __t._M_leftmost() = __t._M_end();
880 : __t._M_rightmost() = __t._M_end();
881 : }
882 : }
883 : else if (__t._M_root() == 0)
884 : {
885 : __t._M_root() = _M_root();
886 : __t._M_leftmost() = _M_leftmost();
887 : __t._M_rightmost() = _M_rightmost();
888 : __t._M_root()->_M_parent = __t._M_end();
889 :
890 : _M_root() = 0;
891 : _M_leftmost() = _M_end();
892 : _M_rightmost() = _M_end();
893 : }
894 : else
895 : {
896 : std::swap(_M_root(),__t._M_root());
897 : std::swap(_M_leftmost(),__t._M_leftmost());
898 : std::swap(_M_rightmost(),__t._M_rightmost());
899 :
900 : _M_root()->_M_parent = _M_end();
901 : __t._M_root()->_M_parent = __t._M_end();
902 : }
903 : // No need to swap header's color as it does not change.
904 : std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
905 : std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
906 : }
907 :
908 : template<typename _Key, typename _Val, typename _KeyOfValue,
909 : typename _Compare, typename _Alloc>
910 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
911 : _Compare, _Alloc>::iterator, bool>
912 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
913 8012520 : insert_unique(const _Val& __v)
914 : {
915 8012520 : _Link_type __x = _M_begin();
916 8012520 : _Link_type __y = _M_end();
917 8012520 : bool __comp = true;
918 71644421 : while (__x != 0)
919 : {
920 55619381 : __y = __x;
921 55619381 : __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
922 55619381 : __x = __comp ? _S_left(__x) : _S_right(__x);
923 : }
924 8012520 : iterator __j = iterator(__y);
925 8012520 : if (__comp)
926 3623624 : if (__j == begin())
927 2816905 : return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
928 : else
929 806719 : --__j;
930 5195615 : if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
931 2790766 : return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
932 2404849 : return pair<iterator, bool>(__j, false);
933 : }
934 :
935 : template<typename _Key, typename _Val, typename _KeyOfValue,
936 : typename _Compare, typename _Alloc>
937 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
938 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
939 3016652 : insert_unique(iterator __position, const _Val& __v)
940 : {
941 : // end()
942 3016652 : if (__position._M_node == _M_end())
943 : {
944 2325891 : if (size() > 0
945 : && _M_impl._M_key_compare(_S_key(_M_rightmost()),
946 : _KeyOfValue()(__v)))
947 1700014 : return _M_insert(0, _M_rightmost(), __v);
948 : else
949 625877 : return insert_unique(__v).first;
950 : }
951 690761 : else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
952 : _S_key(__position._M_node)))
953 : {
954 : // First, try before...
955 690761 : iterator __before = __position;
956 690761 : if (__position._M_node == _M_leftmost()) // begin()
957 110634 : return _M_insert(_M_leftmost(), _M_leftmost(), __v);
958 580127 : else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
959 : _KeyOfValue()(__v)))
960 : {
961 580127 : if (_S_right(__before._M_node) == 0)
962 345800 : return _M_insert(0, __before._M_node, __v);
963 : else
964 : return _M_insert(__position._M_node,
965 234327 : __position._M_node, __v);
966 : }
967 : else
968 0 : return insert_unique(__v).first;
969 : }
970 0 : else if (_M_impl._M_key_compare(_S_key(__position._M_node),
971 : _KeyOfValue()(__v)))
972 : {
973 : // ... then try after.
974 0 : iterator __after = __position;
975 0 : if (__position._M_node == _M_rightmost())
976 0 : return _M_insert(0, _M_rightmost(), __v);
977 0 : else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
978 : _S_key((++__after)._M_node)))
979 : {
980 0 : if (_S_right(__position._M_node) == 0)
981 0 : return _M_insert(0, __position._M_node, __v);
982 : else
983 0 : return _M_insert(__after._M_node, __after._M_node, __v);
984 : }
985 : else
986 0 : return insert_unique(__v).first;
987 : }
988 : else
989 0 : return __position; // Equivalent keys.
990 : }
991 :
992 : template<typename _Key, typename _Val, typename _KeyOfValue,
993 : typename _Compare, typename _Alloc>
994 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
995 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
996 536881 : insert_unique(const_iterator __position, const _Val& __v)
997 : {
998 : // end()
999 536881 : if (__position._M_node == _M_end())
1000 : {
1001 536881 : if (size() > 0
1002 : && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1003 : _KeyOfValue()(__v)))
1004 4374 : return _M_insert(0, _M_rightmost(), __v);
1005 : else
1006 532507 : return const_iterator(insert_unique(__v).first);
1007 : }
1008 0 : else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1009 : _S_key(__position._M_node)))
1010 : {
1011 : // First, try before...
1012 0 : const_iterator __before = __position;
1013 0 : if (__position._M_node == _M_leftmost()) // begin()
1014 0 : return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1015 0 : else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1016 : _KeyOfValue()(__v)))
1017 : {
1018 0 : if (_S_right(__before._M_node) == 0)
1019 0 : return _M_insert(0, __before._M_node, __v);
1020 : else
1021 : return _M_insert(__position._M_node,
1022 0 : __position._M_node, __v);
1023 : }
1024 : else
1025 0 : return const_iterator(insert_unique(__v).first);
1026 : }
1027 0 : else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1028 : _KeyOfValue()(__v)))
1029 : {
1030 : // ... then try after.
1031 0 : const_iterator __after = __position;
1032 0 : if (__position._M_node == _M_rightmost())
1033 0 : return _M_insert(0, _M_rightmost(), __v);
1034 0 : else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1035 : _S_key((++__after)._M_node)))
1036 : {
1037 0 : if (_S_right(__position._M_node) == 0)
1038 0 : return _M_insert(0, __position._M_node, __v);
1039 : else
1040 0 : return _M_insert(__after._M_node, __after._M_node, __v);
1041 : }
1042 : else
1043 0 : return const_iterator(insert_unique(__v).first);
1044 : }
1045 : else
1046 0 : return __position; // Equivalent keys.
1047 : }
1048 :
1049 : template<typename _Key, typename _Val, typename _KeyOfValue,
1050 : typename _Compare, typename _Alloc>
1051 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1052 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1053 : insert_equal(iterator __position, const _Val& __v)
1054 : {
1055 : // end()
1056 : if (__position._M_node == _M_end())
1057 : {
1058 : if (size() > 0
1059 : && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1060 : _S_key(_M_rightmost())))
1061 : return _M_insert(0, _M_rightmost(), __v);
1062 : else
1063 : return insert_equal(__v);
1064 : }
1065 : else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1066 : _KeyOfValue()(__v)))
1067 : {
1068 : // First, try before...
1069 : iterator __before = __position;
1070 : if (__position._M_node == _M_leftmost()) // begin()
1071 : return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1072 : else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1073 : _S_key((--__before)._M_node)))
1074 : {
1075 : if (_S_right(__before._M_node) == 0)
1076 : return _M_insert(0, __before._M_node, __v);
1077 : else
1078 : return _M_insert(__position._M_node,
1079 : __position._M_node, __v);
1080 : }
1081 : else
1082 : return insert_equal(__v);
1083 : }
1084 : else
1085 : {
1086 : // ... then try after.
1087 : iterator __after = __position;
1088 : if (__position._M_node == _M_rightmost())
1089 : return _M_insert(0, _M_rightmost(), __v);
1090 : else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1091 : _KeyOfValue()(__v)))
1092 : {
1093 : if (_S_right(__position._M_node) == 0)
1094 : return _M_insert(0, __position._M_node, __v);
1095 : else
1096 : return _M_insert(__after._M_node, __after._M_node, __v);
1097 : }
1098 : else
1099 : return insert_equal(__v);
1100 : }
1101 : }
1102 :
1103 : template<typename _Key, typename _Val, typename _KeyOfValue,
1104 : typename _Compare, typename _Alloc>
1105 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1106 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1107 : insert_equal(const_iterator __position, const _Val& __v)
1108 : {
1109 : // end()
1110 : if (__position._M_node == _M_end())
1111 : {
1112 : if (size() > 0
1113 : && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1114 : _S_key(_M_rightmost())))
1115 : return _M_insert(0, _M_rightmost(), __v);
1116 : else
1117 : return const_iterator(insert_equal(__v));
1118 : }
1119 : else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1120 : _KeyOfValue()(__v)))
1121 : {
1122 : // First, try before...
1123 : const_iterator __before = __position;
1124 : if (__position._M_node == _M_leftmost()) // begin()
1125 : return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1126 : else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1127 : _S_key((--__before)._M_node)))
1128 : {
1129 : if (_S_right(__before._M_node) == 0)
1130 : return _M_insert(0, __before._M_node, __v);
1131 : else
1132 : return _M_insert(__position._M_node,
1133 : __position._M_node, __v);
1134 : }
1135 : else
1136 : return const_iterator(insert_equal(__v));
1137 : }
1138 : else
1139 : {
1140 : // ... then try after.
1141 : const_iterator __after = __position;
1142 : if (__position._M_node == _M_rightmost())
1143 : return _M_insert(0, _M_rightmost(), __v);
1144 : else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1145 : _KeyOfValue()(__v)))
1146 : {
1147 : if (_S_right(__position._M_node) == 0)
1148 : return _M_insert(0, __position._M_node, __v);
1149 : else
1150 : return _M_insert(__after._M_node, __after._M_node, __v);
1151 : }
1152 : else
1153 : return const_iterator(insert_equal(__v));
1154 : }
1155 : }
1156 :
1157 : template<typename _Key, typename _Val, typename _KoV,
1158 : typename _Cmp, typename _Alloc>
1159 : template<class _II>
1160 : void
1161 : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1162 : insert_equal(_II __first, _II __last)
1163 : {
1164 : for (; __first != __last; ++__first)
1165 : insert_equal(end(), *__first);
1166 : }
1167 :
1168 : template<typename _Key, typename _Val, typename _KoV,
1169 : typename _Cmp, typename _Alloc>
1170 : template<class _II>
1171 : void
1172 : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1173 1945044 : insert_unique(_II __first, _II __last)
1174 : {
1175 3864399 : for (; __first != __last; ++__first)
1176 3864399 : insert_unique(end(), *__first);
1177 : }
1178 :
1179 : template<typename _Key, typename _Val, typename _KeyOfValue,
1180 : typename _Compare, typename _Alloc>
1181 : inline void
1182 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1183 0 : erase(iterator __position)
1184 : {
1185 : _Link_type __y =
1186 : static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1187 : (__position._M_node,
1188 0 : this->_M_impl._M_header));
1189 0 : destroy_node(__y);
1190 0 : --_M_impl._M_node_count;
1191 : }
1192 :
1193 : template<typename _Key, typename _Val, typename _KeyOfValue,
1194 : typename _Compare, typename _Alloc>
1195 : inline void
1196 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1197 : erase(const_iterator __position)
1198 : {
1199 : _Link_type __y =
1200 : static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1201 : (const_cast<_Base_ptr>(__position._M_node),
1202 : this->_M_impl._M_header));
1203 : destroy_node(__y);
1204 : --_M_impl._M_node_count;
1205 : }
1206 :
1207 : template<typename _Key, typename _Val, typename _KeyOfValue,
1208 : typename _Compare, typename _Alloc>
1209 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1210 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1211 23 : erase(const _Key& __x)
1212 : {
1213 23 : pair<iterator,iterator> __p = equal_range(__x);
1214 23 : size_type __n = std::distance(__p.first, __p.second);
1215 23 : erase(__p.first, __p.second);
1216 23 : return __n;
1217 : }
1218 :
1219 : template<typename _Key, typename _Val, typename _KoV,
1220 : typename _Compare, typename _Alloc>
1221 : typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1222 : _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1223 : _M_copy(_Const_Link_type __x, _Link_type __p)
1224 : {
1225 : // Structural copy. __x and __p must be non-null.
1226 : _Link_type __top = _M_clone_node(__x);
1227 : __top->_M_parent = __p;
1228 :
1229 : try
1230 : {
1231 : if (__x->_M_right)
1232 : __top->_M_right = _M_copy(_S_right(__x), __top);
1233 : __p = __top;
1234 : __x = _S_left(__x);
1235 :
1236 : while (__x != 0)
1237 : {
1238 : _Link_type __y = _M_clone_node(__x);
1239 : __p->_M_left = __y;
1240 : __y->_M_parent = __p;
1241 : if (__x->_M_right)
1242 : __y->_M_right = _M_copy(_S_right(__x), __y);
1243 : __p = __y;
1244 : __x = _S_left(__x);
1245 : }
1246 : }
1247 : catch(...)
1248 : {
1249 : _M_erase(__top);
1250 : __throw_exception_again;
1251 : }
1252 : return __top;
1253 : }
1254 :
1255 : template<typename _Key, typename _Val, typename _KeyOfValue,
1256 : typename _Compare, typename _Alloc>
1257 : void
1258 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1259 166882141 : _M_erase(_Link_type __x)
1260 : {
1261 : // Erase without rebalancing.
1262 341198576 : while (__x != 0)
1263 : {
1264 7434294 : _M_erase(_S_right(__x));
1265 7434294 : _Link_type __y = _S_left(__x);
1266 7434294 : destroy_node(__x);
1267 174316435 : __x = __y;
1268 : }
1269 : }
1270 :
1271 : template<typename _Key, typename _Val, typename _KeyOfValue,
1272 : typename _Compare, typename _Alloc>
1273 : void
1274 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1275 23 : erase(iterator __first, iterator __last)
1276 : {
1277 23 : if (__first == begin() && __last == end())
1278 23 : clear();
1279 : else
1280 0 : while (__first != __last)
1281 23 : erase(__first++);
1282 : }
1283 :
1284 : template<typename _Key, typename _Val, typename _KeyOfValue,
1285 : typename _Compare, typename _Alloc>
1286 : void
1287 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1288 : erase(const_iterator __first, const_iterator __last)
1289 : {
1290 : if (__first == begin() && __last == end())
1291 : clear();
1292 : else
1293 : while (__first != __last)
1294 : erase(__first++);
1295 : }
1296 :
1297 : template<typename _Key, typename _Val, typename _KeyOfValue,
1298 : typename _Compare, typename _Alloc>
1299 : void
1300 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1301 : erase(const _Key* __first, const _Key* __last)
1302 : {
1303 : while (__first != __last)
1304 : erase(*__first++);
1305 : }
1306 :
1307 : template<typename _Key, typename _Val, typename _KeyOfValue,
1308 : typename _Compare, typename _Alloc>
1309 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1310 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1311 5689029 : find(const _Key& __k)
1312 : {
1313 5689029 : _Link_type __x = _M_begin(); // Current node.
1314 5689029 : _Link_type __y = _M_end(); // Last node which is not less than __k.
1315 :
1316 59855197 : while (__x != 0)
1317 48477139 : if (!_M_impl._M_key_compare(_S_key(__x), __k))
1318 20288932 : __y = __x, __x = _S_left(__x);
1319 : else
1320 28188207 : __x = _S_right(__x);
1321 :
1322 5689029 : iterator __j = iterator(__y);
1323 : return (__j == end()
1324 : || _M_impl._M_key_compare(__k,
1325 5689029 : _S_key(__j._M_node))) ? end() : __j;
1326 : }
1327 :
1328 : template<typename _Key, typename _Val, typename _KeyOfValue,
1329 : typename _Compare, typename _Alloc>
1330 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1331 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1332 1360758 : find(const _Key& __k) const
1333 : {
1334 1360758 : _Const_Link_type __x = _M_begin(); // Current node.
1335 1360758 : _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1336 :
1337 11344531 : while (__x != 0)
1338 : {
1339 8623015 : if (!_M_impl._M_key_compare(_S_key(__x), __k))
1340 5463548 : __y = __x, __x = _S_left(__x);
1341 : else
1342 3159467 : __x = _S_right(__x);
1343 : }
1344 1360758 : const_iterator __j = const_iterator(__y);
1345 : return (__j == end()
1346 : || _M_impl._M_key_compare(__k,
1347 1360758 : _S_key(__j._M_node))) ? end() : __j;
1348 : }
1349 :
1350 : template<typename _Key, typename _Val, typename _KeyOfValue,
1351 : typename _Compare, typename _Alloc>
1352 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1353 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1354 0 : count(const _Key& __k) const
1355 : {
1356 0 : pair<const_iterator, const_iterator> __p = equal_range(__k);
1357 0 : const size_type __n = std::distance(__p.first, __p.second);
1358 0 : return __n;
1359 : }
1360 :
1361 : template<typename _Key, typename _Val, typename _KeyOfValue,
1362 : typename _Compare, typename _Alloc>
1363 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1364 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1365 52897061 : lower_bound(const _Key& __k)
1366 : {
1367 52897061 : _Link_type __x = _M_begin(); // Current node.
1368 52897061 : _Link_type __y = _M_end(); // Last node which is not less than __k.
1369 :
1370 657860220 : while (__x != 0)
1371 552066098 : if (!_M_impl._M_key_compare(_S_key(__x), __k))
1372 263686367 : __y = __x, __x = _S_left(__x);
1373 : else
1374 288379731 : __x = _S_right(__x);
1375 :
1376 52897061 : return iterator(__y);
1377 : }
1378 :
1379 : template<typename _Key, typename _Val, typename _KeyOfValue,
1380 : typename _Compare, typename _Alloc>
1381 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1382 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1383 0 : lower_bound(const _Key& __k) const
1384 : {
1385 0 : _Const_Link_type __x = _M_begin(); // Current node.
1386 0 : _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1387 :
1388 0 : while (__x != 0)
1389 0 : if (!_M_impl._M_key_compare(_S_key(__x), __k))
1390 0 : __y = __x, __x = _S_left(__x);
1391 : else
1392 0 : __x = _S_right(__x);
1393 :
1394 0 : return const_iterator(__y);
1395 : }
1396 :
1397 : template<typename _Key, typename _Val, typename _KeyOfValue,
1398 : typename _Compare, typename _Alloc>
1399 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1400 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1401 23 : upper_bound(const _Key& __k)
1402 : {
1403 23 : _Link_type __x = _M_begin(); // Current node.
1404 23 : _Link_type __y = _M_end(); // Last node which is greater than __k.
1405 :
1406 69 : while (__x != 0)
1407 23 : if (_M_impl._M_key_compare(__k, _S_key(__x)))
1408 0 : __y = __x, __x = _S_left(__x);
1409 : else
1410 23 : __x = _S_right(__x);
1411 :
1412 23 : return iterator(__y);
1413 : }
1414 :
1415 : template<typename _Key, typename _Val, typename _KeyOfValue,
1416 : typename _Compare, typename _Alloc>
1417 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1418 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1419 0 : upper_bound(const _Key& __k) const
1420 : {
1421 0 : _Const_Link_type __x = _M_begin(); // Current node.
1422 0 : _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1423 :
1424 0 : while (__x != 0)
1425 0 : if (_M_impl._M_key_compare(__k, _S_key(__x)))
1426 0 : __y = __x, __x = _S_left(__x);
1427 : else
1428 0 : __x = _S_right(__x);
1429 :
1430 0 : return const_iterator(__y);
1431 : }
1432 :
1433 : template<typename _Key, typename _Val, typename _KeyOfValue,
1434 : typename _Compare, typename _Alloc>
1435 : inline
1436 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1437 : _Compare, _Alloc>::iterator,
1438 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
1439 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1440 23 : equal_range(const _Key& __k)
1441 23 : { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1442 :
1443 : template<typename _Key, typename _Val, typename _KoV,
1444 : typename _Compare, typename _Alloc>
1445 : inline
1446 : pair<typename _Rb_tree<_Key, _Val, _KoV,
1447 : _Compare, _Alloc>::const_iterator,
1448 : typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1449 : _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1450 0 : equal_range(const _Key& __k) const
1451 : { return pair<const_iterator, const_iterator>(lower_bound(__k),
1452 0 : upper_bound(__k)); }
1453 :
1454 : unsigned int
1455 : _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1456 : const _Rb_tree_node_base* __root);
1457 :
1458 : template<typename _Key, typename _Val, typename _KeyOfValue,
1459 : typename _Compare, typename _Alloc>
1460 : bool
1461 : _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1462 : {
1463 : if (_M_impl._M_node_count == 0 || begin() == end())
1464 : return _M_impl._M_node_count == 0 && begin() == end()
1465 : && this->_M_impl._M_header._M_left == _M_end()
1466 : && this->_M_impl._M_header._M_right == _M_end();
1467 :
1468 : unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1469 : for (const_iterator __it = begin(); __it != end(); ++__it)
1470 : {
1471 : _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1472 : _Const_Link_type __L = _S_left(__x);
1473 : _Const_Link_type __R = _S_right(__x);
1474 :
1475 : if (__x->_M_color == _S_red)
1476 : if ((__L && __L->_M_color == _S_red)
1477 : || (__R && __R->_M_color == _S_red))
1478 : return false;
1479 :
1480 : if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1481 : return false;
1482 : if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1483 : return false;
1484 :
1485 : if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1486 : return false;
1487 : }
1488 :
1489 : if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1490 : return false;
1491 : if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1492 : return false;
1493 : return true;
1494 : }
1495 : } // namespace std
1496 :
1497 : #endif
|
