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