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