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