1// RB tree implementation -*- C++ -*-
2
3// Copyright (C) 2001-2016 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#pragma GCC system_header
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#include <ext/alloc_traits.h>
68#if __cplusplus >= 201103L
69#include <ext/aligned_buffer.h>
70#endif
71
72namespace std _GLIBCXX_VISIBILITY(default)
73{
74_GLIBCXX_BEGIN_NAMESPACE_VERSION
75
76 // Red-black tree class, designed for use in implementing STL
77 // associative containers (set, multiset, map, and multimap). The
78 // insertion and deletion algorithms are based on those in Cormen,
79 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
80 // 1990), except that
81 //
82 // (1) the header cell is maintained with links not only to the root
83 // but also to the leftmost node of the tree, to enable constant
84 // time begin(), and to the rightmost node of the tree, to enable
85 // linear time performance when used with the generic set algorithms
86 // (set_union, etc.)
87 //
88 // (2) when a node being deleted has two children its successor node
89 // is relinked into its place, rather than copied, so that the only
90 // iterators invalidated are those referring to the deleted node.
91
92 enum _Rb_tree_color { _S_red = false, _S_black = true };
93
94 struct _Rb_tree_node_base
95 {
96 typedef _Rb_tree_node_base* _Base_ptr;
97 typedef const _Rb_tree_node_base* _Const_Base_ptr;
98
99 _Rb_tree_color _M_color;
100 _Base_ptr _M_parent;
101 _Base_ptr _M_left;
102 _Base_ptr _M_right;
103
104 static _Base_ptr
105 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
106 {
107 while (__x->_M_left != 0) __x = __x->_M_left;
108 return __x;
109 }
110
111 static _Const_Base_ptr
112 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
113 {
114 while (__x->_M_left != 0) __x = __x->_M_left;
115 return __x;
116 }
117
118 static _Base_ptr
119 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
120 {
121 while (__x->_M_right != 0) __x = __x->_M_right;
122 return __x;
123 }
124
125 static _Const_Base_ptr
126 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
127 {
128 while (__x->_M_right != 0) __x = __x->_M_right;
129 return __x;
130 }
131 };
132
133 template<typename _Val>
134 struct _Rb_tree_node : public _Rb_tree_node_base
135 {
136 typedef _Rb_tree_node<_Val>* _Link_type;
137
138#if __cplusplus < 201103L
139 _Val _M_value_field;
140
141 _Val*
142 _M_valptr()
143 { return std::__addressof(_M_value_field); }
144
145 const _Val*
146 _M_valptr() const
147 { return std::__addressof(_M_value_field); }
148#else
149 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
150
151 _Val*
152 _M_valptr()
153 { return _M_storage._M_ptr(); }
154
155 const _Val*
156 _M_valptr() const
157 { return _M_storage._M_ptr(); }
158#endif
159 };
160
161 _GLIBCXX_PURE _Rb_tree_node_base*
162 _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
163
164 _GLIBCXX_PURE const _Rb_tree_node_base*
165 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
166
167 _GLIBCXX_PURE _Rb_tree_node_base*
168 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
169
170 _GLIBCXX_PURE const _Rb_tree_node_base*
171 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
172
173 template<typename _Tp>
174 struct _Rb_tree_iterator
175 {
176 typedef _Tp value_type;
177 typedef _Tp& reference;
178 typedef _Tp* pointer;
179
180 typedef bidirectional_iterator_tag iterator_category;
181 typedef ptrdiff_t difference_type;
182
183 typedef _Rb_tree_iterator<_Tp> _Self;
184 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
185 typedef _Rb_tree_node<_Tp>* _Link_type;
186
187 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
188 : _M_node() { }
189
190 explicit
191 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
192 : _M_node(__x) { }
193
194 reference
195 operator*() const _GLIBCXX_NOEXCEPT
196 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
197
198 pointer
199 operator->() const _GLIBCXX_NOEXCEPT
200 { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
201
202 _Self&
203 operator++() _GLIBCXX_NOEXCEPT
204 {
205 _M_node = _Rb_tree_increment(_M_node);
206 return *this;
207 }
208
209 _Self
210 operator++(int) _GLIBCXX_NOEXCEPT
211 {
212 _Self __tmp = *this;
213 _M_node = _Rb_tree_increment(_M_node);
214 return __tmp;
215 }
216
217 _Self&
218 operator--() _GLIBCXX_NOEXCEPT
219 {
220 _M_node = _Rb_tree_decrement(_M_node);
221 return *this;
222 }
223
224 _Self
225 operator--(int) _GLIBCXX_NOEXCEPT
226 {
227 _Self __tmp = *this;
228 _M_node = _Rb_tree_decrement(_M_node);
229 return __tmp;
230 }
231
232 bool
233 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
234 { return _M_node == __x._M_node; }
235
236 bool
237 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
238 { return _M_node != __x._M_node; }
239
240 _Base_ptr _M_node;
241 };
242
243 template<typename _Tp>
244 struct _Rb_tree_const_iterator
245 {
246 typedef _Tp value_type;
247 typedef const _Tp& reference;
248 typedef const _Tp* pointer;
249
250 typedef _Rb_tree_iterator<_Tp> iterator;
251
252 typedef bidirectional_iterator_tag iterator_category;
253 typedef ptrdiff_t difference_type;
254
255 typedef _Rb_tree_const_iterator<_Tp> _Self;
256 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
257 typedef const _Rb_tree_node<_Tp>* _Link_type;
258
259 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
260 : _M_node() { }
261
262 explicit
263 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
264 : _M_node(__x) { }
265
266 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
267 : _M_node(__it._M_node) { }
268
269 iterator
270 _M_const_cast() const _GLIBCXX_NOEXCEPT
271 { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
272
273 reference
274 operator*() const _GLIBCXX_NOEXCEPT
275 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
276
277 pointer
278 operator->() const _GLIBCXX_NOEXCEPT
279 { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
280
281 _Self&
282 operator++() _GLIBCXX_NOEXCEPT
283 {
284 _M_node = _Rb_tree_increment(_M_node);
285 return *this;
286 }
287
288 _Self
289 operator++(int) _GLIBCXX_NOEXCEPT
290 {
291 _Self __tmp = *this;
292 _M_node = _Rb_tree_increment(_M_node);
293 return __tmp;
294 }
295
296 _Self&
297 operator--() _GLIBCXX_NOEXCEPT
298 {
299 _M_node = _Rb_tree_decrement(_M_node);
300 return *this;
301 }
302
303 _Self
304 operator--(int) _GLIBCXX_NOEXCEPT
305 {
306 _Self __tmp = *this;
307 _M_node = _Rb_tree_decrement(_M_node);
308 return __tmp;
309 }
310
311 bool
312 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
313 { return _M_node == __x._M_node; }
314
315 bool
316 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
317 { return _M_node != __x._M_node; }
318
319 _Base_ptr _M_node;
320 };
321
322 template<typename _Val>
323 inline bool
324 operator==(const _Rb_tree_iterator<_Val>& __x,
325 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
326 { return __x._M_node == __y._M_node; }
327
328 template<typename _Val>
329 inline bool
330 operator!=(const _Rb_tree_iterator<_Val>& __x,
331 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
332 { return __x._M_node != __y._M_node; }
333
334 void
335 _Rb_tree_insert_and_rebalance(const bool __insert_left,
336 _Rb_tree_node_base* __x,
337 _Rb_tree_node_base* __p,
338 _Rb_tree_node_base& __header) throw ();
339
340 _Rb_tree_node_base*
341 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
342 _Rb_tree_node_base& __header) throw ();
343
344#if __cplusplus > 201103L
345 template<typename _Cmp, typename _SfinaeType, typename = __void_t<>>
346 struct __has_is_transparent
347 { };
348
349 template<typename _Cmp, typename _SfinaeType>
350 struct __has_is_transparent<_Cmp, _SfinaeType,
351 __void_t<typename _Cmp::is_transparent>>
352 { typedef void type; };
353#endif
354
355 template<typename _Key, typename _Val, typename _KeyOfValue,
356 typename _Compare, typename _Alloc = allocator<_Val> >
357 class _Rb_tree
358 {
359 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
360 rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
361
362 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
363
364 protected:
365 typedef _Rb_tree_node_base* _Base_ptr;
366 typedef const _Rb_tree_node_base* _Const_Base_ptr;
367 typedef _Rb_tree_node<_Val>* _Link_type;
368 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
369
370 private:
371 // Functor recycling a pool of nodes and using allocation once the pool
372 // is empty.
373 struct _Reuse_or_alloc_node
374 {
375 _Reuse_or_alloc_node(_Rb_tree& __t)
376 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
377 {
378 if (_M_root)
379 {
380 _M_root->_M_parent = 0;
381
382 if (_M_nodes->_M_left)
383 _M_nodes = _M_nodes->_M_left;
384 }
385 else
386 _M_nodes = 0;
387 }
388
389#if __cplusplus >= 201103L
390 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
391#endif
392
393 ~_Reuse_or_alloc_node()
394 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
395
396 template<typename _Arg>
397 _Link_type
398#if __cplusplus < 201103L
399 operator()(const _Arg& __arg)
400#else
401 operator()(_Arg&& __arg)
402#endif
403 {
404 _Link_type __node = static_cast<_Link_type>(_M_extract());
405 if (__node)
406 {
407 _M_t._M_destroy_node(__node);
408 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
409 return __node;
410 }
411
412 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
413 }
414
415 private:
416 _Base_ptr
417 _M_extract()
418 {
419 if (!_M_nodes)
420 return _M_nodes;
421
422 _Base_ptr __node = _M_nodes;
423 _M_nodes = _M_nodes->_M_parent;
424 if (_M_nodes)
425 {
426 if (_M_nodes->_M_right == __node)
427 {
428 _M_nodes->_M_right = 0;
429
430 if (_M_nodes->_M_left)
431 {
432 _M_nodes = _M_nodes->_M_left;
433
434 while (_M_nodes->_M_right)
435 _M_nodes = _M_nodes->_M_right;
436
437 if (_M_nodes->_M_left)
438 _M_nodes = _M_nodes->_M_left;
439 }
440 }
441 else // __node is on the left.
442 _M_nodes->_M_left = 0;
443 }
444 else
445 _M_root = 0;
446
447 return __node;
448 }
449
450 _Base_ptr _M_root;
451 _Base_ptr _M_nodes;
452 _Rb_tree& _M_t;
453 };
454
455 // Functor similar to the previous one but without any pool of nodes to
456 // recycle.
457 struct _Alloc_node
458 {
459 _Alloc_node(_Rb_tree& __t)
460 : _M_t(__t) { }
461
462 template<typename _Arg>
463 _Link_type
464#if __cplusplus < 201103L
465 operator()(const _Arg& __arg) const
466#else
467 operator()(_Arg&& __arg) const
468#endif
469 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
470
471 private:
472 _Rb_tree& _M_t;
473 };
474
475 public:
476 typedef _Key key_type;
477 typedef _Val value_type;
478 typedef value_type* pointer;
479 typedef const value_type* const_pointer;
480 typedef value_type& reference;
481 typedef const value_type& const_reference;
482 typedef size_t size_type;
483 typedef ptrdiff_t difference_type;
484 typedef _Alloc allocator_type;
485
486 _Node_allocator&
487 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
488 { return *static_cast<_Node_allocator*>(&this->_M_impl); }
489
490 const _Node_allocator&
491 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
492 { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
493
494 allocator_type
495 get_allocator() const _GLIBCXX_NOEXCEPT
496 { return allocator_type(_M_get_Node_allocator()); }
497
498 protected:
499 _Link_type
500 _M_get_node()
501 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
502
503 void
504 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
505 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
506
507#if __cplusplus < 201103L
508 void
509 _M_construct_node(_Link_type __node, const value_type& __x)
510 {
511 __try
512 { get_allocator().construct(__node->_M_valptr(), __x); }
513 __catch(...)
514 {
515 _M_put_node(__node);
516 __throw_exception_again;
517 }
518 }
519
520 _Link_type
521 _M_create_node(const value_type& __x)
522 {
523 _Link_type __tmp = _M_get_node();
524 _M_construct_node(__tmp, __x);
525 return __tmp;
526 }
527
528 void
529 _M_destroy_node(_Link_type __p)
530 { get_allocator().destroy(__p->_M_valptr()); }
531#else
532 template<typename... _Args>
533 void
534 _M_construct_node(_Link_type __node, _Args&&... __args)
535 {
536 __try
537 {
538 ::new(__node) _Rb_tree_node<_Val>;
539 _Alloc_traits::construct(_M_get_Node_allocator(),
540 __node->_M_valptr(),
541 std::forward<_Args>(__args)...);
542 }
543 __catch(...)
544 {
545 __node->~_Rb_tree_node<_Val>();
546 _M_put_node(__node);
547 __throw_exception_again;
548 }
549 }
550
551 template<typename... _Args>
552 _Link_type
553 _M_create_node(_Args&&... __args)
554 {
555 _Link_type __tmp = _M_get_node();
556 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
557 return __tmp;
558 }
559
560 void
561 _M_destroy_node(_Link_type __p) noexcept
562 {
563 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
564 __p->~_Rb_tree_node<_Val>();
565 }
566#endif
567
568 void
569 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
570 {
571 _M_destroy_node(__p);
572 _M_put_node(__p);
573 }
574
575 template<typename _NodeGen>
576 _Link_type
577 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
578 {
579 _Link_type __tmp = __node_gen(*__x->_M_valptr());
580 __tmp->_M_color = __x->_M_color;
581 __tmp->_M_left = 0;
582 __tmp->_M_right = 0;
583 return __tmp;
584 }
585
586 protected:
587 // Unused _Is_pod_comparator is kept as it is part of mangled name.
588 template<typename _Key_compare,
589 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
590 struct _Rb_tree_impl : public _Node_allocator
591 {
592 _Key_compare _M_key_compare;
593 _Rb_tree_node_base _M_header;
594 size_type _M_node_count; // Keeps track of size of tree.
595
596 _Rb_tree_impl()
597 : _Node_allocator(), _M_key_compare(), _M_header(),
598 _M_node_count(0)
599 { _M_initialize(); }
600
601 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
602 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
603 _M_node_count(0)
604 { _M_initialize(); }
605
606#if __cplusplus >= 201103L
607 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
608 : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
609 _M_header(), _M_node_count(0)
610 { _M_initialize(); }
611#endif
612
613 void
614 _M_reset()
615 {
616 this->_M_header._M_parent = 0;
617 this->_M_header._M_left = &this->_M_header;
618 this->_M_header._M_right = &this->_M_header;
619 this->_M_node_count = 0;
620 }
621
622 private:
623 void
624 _M_initialize()
625 {
626 this->_M_header._M_color = _S_red;
627 this->_M_header._M_parent = 0;
628 this->_M_header._M_left = &this->_M_header;
629 this->_M_header._M_right = &this->_M_header;
630 }
631 };
632
633 _Rb_tree_impl<_Compare> _M_impl;
634
635 protected:
636 _Base_ptr&
637 _M_root() _GLIBCXX_NOEXCEPT
638 { return this->_M_impl._M_header._M_parent; }
639
640 _Const_Base_ptr
641 _M_root() const _GLIBCXX_NOEXCEPT
642 { return this->_M_impl._M_header._M_parent; }
643
644 _Base_ptr&
645 _M_leftmost() _GLIBCXX_NOEXCEPT
646 { return this->_M_impl._M_header._M_left; }
647
648 _Const_Base_ptr
649 _M_leftmost() const _GLIBCXX_NOEXCEPT
650 { return this->_M_impl._M_header._M_left; }
651
652 _Base_ptr&
653 _M_rightmost() _GLIBCXX_NOEXCEPT
654 { return this->_M_impl._M_header._M_right; }
655
656 _Const_Base_ptr
657 _M_rightmost() const _GLIBCXX_NOEXCEPT
658 { return this->_M_impl._M_header._M_right; }
659
660 _Link_type
661 _M_begin() _GLIBCXX_NOEXCEPT
662 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
663
664 _Const_Link_type
665 _M_begin() const _GLIBCXX_NOEXCEPT
666 {
667 return static_cast<_Const_Link_type>
668 (this->_M_impl._M_header._M_parent);
669 }
670
671 _Base_ptr
672 _M_end() _GLIBCXX_NOEXCEPT
673 { return &this->_M_impl._M_header; }
674
675 _Const_Base_ptr
676 _M_end() const _GLIBCXX_NOEXCEPT
677 { return &this->_M_impl._M_header; }
678
679 static const_reference
680 _S_value(_Const_Link_type __x)
681 { return *__x->_M_valptr(); }
682
683 static const _Key&
684 _S_key(_Const_Link_type __x)
685 { return _KeyOfValue()(_S_value(__x)); }
686
687 static _Link_type
688 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
689 { return static_cast<_Link_type>(__x->_M_left); }
690
691 static _Const_Link_type
692 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
693 { return static_cast<_Const_Link_type>(__x->_M_left); }
694
695 static _Link_type
696 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
697 { return static_cast<_Link_type>(__x->_M_right); }
698
699 static _Const_Link_type
700 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
701 { return static_cast<_Const_Link_type>(__x->_M_right); }
702
703 static const_reference
704 _S_value(_Const_Base_ptr __x)
705 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
706
707 static const _Key&
708 _S_key(_Const_Base_ptr __x)
709 { return _KeyOfValue()(_S_value(__x)); }
710
711 static _Base_ptr
712 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
713 { return _Rb_tree_node_base::_S_minimum(__x); }
714
715 static _Const_Base_ptr
716 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
717 { return _Rb_tree_node_base::_S_minimum(__x); }
718
719 static _Base_ptr
720 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
721 { return _Rb_tree_node_base::_S_maximum(__x); }
722
723 static _Const_Base_ptr
724 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
725 { return _Rb_tree_node_base::_S_maximum(__x); }
726
727 public:
728 typedef _Rb_tree_iterator<value_type> iterator;
729 typedef _Rb_tree_const_iterator<value_type> const_iterator;
730
731 typedef std::reverse_iterator<iterator> reverse_iterator;
732 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
733
734 pair<_Base_ptr, _Base_ptr>
735 _M_get_insert_unique_pos(const key_type& __k);
736
737 pair<_Base_ptr, _Base_ptr>
738 _M_get_insert_equal_pos(const key_type& __k);
739
740 pair<_Base_ptr, _Base_ptr>
741 _M_get_insert_hint_unique_pos(const_iterator __pos,
742 const key_type& __k);
743
744 pair<_Base_ptr, _Base_ptr>
745 _M_get_insert_hint_equal_pos(const_iterator __pos,
746 const key_type& __k);
747
748 private:
749#if __cplusplus >= 201103L
750 template<typename _Arg, typename _NodeGen>
751 iterator
752 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
753
754 iterator
755 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
756
757 template<typename _Arg>
758 iterator
759 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
760
761 template<typename _Arg>
762 iterator
763 _M_insert_equal_lower(_Arg&& __x);
764
765 iterator
766 _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
767
768 iterator
769 _M_insert_equal_lower_node(_Link_type __z);
770#else
771 template<typename _NodeGen>
772 iterator
773 _M_insert_(_Base_ptr __x, _Base_ptr __y,
774 const value_type& __v, _NodeGen&);
775
776 // _GLIBCXX_RESOLVE_LIB_DEFECTS
777 // 233. Insertion hints in associative containers.
778 iterator
779 _M_insert_lower(_Base_ptr __y, const value_type& __v);
780
781 iterator
782 _M_insert_equal_lower(const value_type& __x);
783#endif
784
785 template<typename _NodeGen>
786 _Link_type
787 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
788
789 _Link_type
790 _M_copy(_Const_Link_type __x, _Base_ptr __p)
791 {
792 _Alloc_node __an(*this);
793 return _M_copy(__x, __p, __an);
794 }
795
796 void
797 _M_erase(_Link_type __x);
798
799 iterator
800 _M_lower_bound(_Link_type __x, _Base_ptr __y,
801 const _Key& __k);
802
803 const_iterator
804 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
805 const _Key& __k) const;
806
807 iterator
808 _M_upper_bound(_Link_type __x, _Base_ptr __y,
809 const _Key& __k);
810
811 const_iterator
812 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
813 const _Key& __k) const;
814
815 public:
816 // allocation/deallocation
817 _Rb_tree() { }
818
819 _Rb_tree(const _Compare& __comp,
820 const allocator_type& __a = allocator_type())
821 : _M_impl(__comp, _Node_allocator(__a)) { }
822
823 _Rb_tree(const _Rb_tree& __x)
824 : _M_impl(__x._M_impl._M_key_compare,
825 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
826 {
827 if (__x._M_root() != 0)
828 {
829 _M_root() = _M_copy(__x._M_begin(), _M_end());
830 _M_leftmost() = _S_minimum(_M_root());
831 _M_rightmost() = _S_maximum(_M_root());
832 _M_impl._M_node_count = __x._M_impl._M_node_count;
833 }
834 }
835
836#if __cplusplus >= 201103L
837 _Rb_tree(const allocator_type& __a)
838 : _M_impl(_Compare(), _Node_allocator(__a))
839 { }
840
841 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
842 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
843 {
844 if (__x._M_root() != nullptr)
845 {
846 _M_root() = _M_copy(__x._M_begin(), _M_end());
847 _M_leftmost() = _S_minimum(_M_root());
848 _M_rightmost() = _S_maximum(_M_root());
849 _M_impl._M_node_count = __x._M_impl._M_node_count;
850 }
851 }
852
853 _Rb_tree(_Rb_tree&& __x)
854 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
855 {
856 if (__x._M_root() != 0)
857 _M_move_data(__x, std::true_type());
858 }
859
860 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
861 : _Rb_tree(std::move(__x), _Node_allocator(__a))
862 { }
863
864 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
865#endif
866
867 ~_Rb_tree() _GLIBCXX_NOEXCEPT
868 { _M_erase(_M_begin()); }
869
870 _Rb_tree&
871 operator=(const _Rb_tree& __x);
872
873 // Accessors.
874 _Compare
875 key_comp() const
876 { return _M_impl._M_key_compare; }
877
878 iterator
879 begin() _GLIBCXX_NOEXCEPT
880 { return iterator(this->_M_impl._M_header._M_left); }
881
882 const_iterator
883 begin() const _GLIBCXX_NOEXCEPT
884 { return const_iterator(this->_M_impl._M_header._M_left); }
885
886 iterator
887 end() _GLIBCXX_NOEXCEPT
888 { return iterator(&this->_M_impl._M_header); }
889
890 const_iterator
891 end() const _GLIBCXX_NOEXCEPT
892 { return const_iterator(&this->_M_impl._M_header); }
893
894 reverse_iterator
895 rbegin() _GLIBCXX_NOEXCEPT
896 { return reverse_iterator(end()); }
897
898 const_reverse_iterator
899 rbegin() const _GLIBCXX_NOEXCEPT
900 { return const_reverse_iterator(end()); }
901
902 reverse_iterator
903 rend() _GLIBCXX_NOEXCEPT
904 { return reverse_iterator(begin()); }
905
906 const_reverse_iterator
907 rend() const _GLIBCXX_NOEXCEPT
908 { return const_reverse_iterator(begin()); }
909
910 bool
911 empty() const _GLIBCXX_NOEXCEPT
912 { return _M_impl._M_node_count == 0; }
913
914 size_type
915 size() const _GLIBCXX_NOEXCEPT
916 { return _M_impl._M_node_count; }
917
918 size_type
919 max_size() const _GLIBCXX_NOEXCEPT
920 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
921
922 void
923 swap(_Rb_tree& __t)
924 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
925
926 // Insert/erase.
927#if __cplusplus >= 201103L
928 template<typename _Arg>
929 pair<iterator, bool>
930 _M_insert_unique(_Arg&& __x);
931
932 template<typename _Arg>
933 iterator
934 _M_insert_equal(_Arg&& __x);
935
936 template<typename _Arg, typename _NodeGen>
937 iterator
938 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
939
940 template<typename _Arg>
941 iterator
942 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
943 {
944 _Alloc_node __an(*this);
945 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
946 }
947
948 template<typename _Arg, typename _NodeGen>
949 iterator
950 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
951
952 template<typename _Arg>
953 iterator
954 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
955 {
956 _Alloc_node __an(*this);
957 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
958 }
959
960 template<typename... _Args>
961 pair<iterator, bool>
962 _M_emplace_unique(_Args&&... __args);
963
964 template<typename... _Args>
965 iterator
966 _M_emplace_equal(_Args&&... __args);
967
968 template<typename... _Args>
969 iterator
970 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
971
972 template<typename... _Args>
973 iterator
974 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
975#else
976 pair<iterator, bool>
977 _M_insert_unique(const value_type& __x);
978
979 iterator
980 _M_insert_equal(const value_type& __x);
981
982 template<typename _NodeGen>
983 iterator
984 _M_insert_unique_(const_iterator __pos, const value_type& __x,
985 _NodeGen&);
986
987 iterator
988 _M_insert_unique_(const_iterator __pos, const value_type& __x)
989 {
990 _Alloc_node __an(*this);
991 return _M_insert_unique_(__pos, __x, __an);
992 }
993
994 template<typename _NodeGen>
995 iterator
996 _M_insert_equal_(const_iterator __pos, const value_type& __x,
997 _NodeGen&);
998 iterator
999 _M_insert_equal_(const_iterator __pos, const value_type& __x)
1000 {
1001 _Alloc_node __an(*this);
1002 return _M_insert_equal_(__pos, __x, __an);
1003 }
1004#endif
1005
1006 template<typename _InputIterator>
1007 void
1008 _M_insert_unique(_InputIterator __first, _InputIterator __last);
1009
1010 template<typename _InputIterator>
1011 void
1012 _M_insert_equal(_InputIterator __first, _InputIterator __last);
1013
1014 private:
1015 void
1016 _M_erase_aux(const_iterator __position);
1017
1018 void
1019 _M_erase_aux(const_iterator __first, const_iterator __last);
1020
1021 public:
1022#if __cplusplus >= 201103L
1023 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1024 // DR 130. Associative erase should return an iterator.
1025 _GLIBCXX_ABI_TAG_CXX11
1026 iterator
1027 erase(const_iterator __position)
1028 {
1029 const_iterator __result = __position;
1030 ++__result;
1031 _M_erase_aux(__position);
1032 return __result._M_const_cast();
1033 }
1034
1035 // LWG 2059.
1036 _GLIBCXX_ABI_TAG_CXX11
1037 iterator
1038 erase(iterator __position)
1039 {
1040 iterator __result = __position;
1041 ++__result;
1042 _M_erase_aux(__position);
1043 return __result;
1044 }
1045#else
1046 void
1047 erase(iterator __position)
1048 { _M_erase_aux(__position); }
1049
1050 void
1051 erase(const_iterator __position)
1052 { _M_erase_aux(__position); }
1053#endif
1054 size_type
1055 erase(const key_type& __x);
1056
1057#if __cplusplus >= 201103L
1058 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1059 // DR 130. Associative erase should return an iterator.
1060 _GLIBCXX_ABI_TAG_CXX11
1061 iterator
1062 erase(const_iterator __first, const_iterator __last)
1063 {
1064 _M_erase_aux(__first, __last);
1065 return __last._M_const_cast();
1066 }
1067#else
1068 void
1069 erase(iterator __first, iterator __last)
1070 { _M_erase_aux(__first, __last); }
1071
1072 void
1073 erase(const_iterator __first, const_iterator __last)
1074 { _M_erase_aux(__first, __last); }
1075#endif
1076 void
1077 erase(const key_type* __first, const key_type* __last);
1078
1079 void
1080 clear() _GLIBCXX_NOEXCEPT
1081 {
1082 _M_erase(_M_begin());
1083 _M_impl._M_reset();
1084 }
1085
1086 // Set operations.
1087 iterator
1088 find(const key_type& __k);
1089
1090 const_iterator
1091 find(const key_type& __k) const;
1092
1093 size_type
1094 count(const key_type& __k) const;
1095
1096 iterator
1097 lower_bound(const key_type& __k)
1098 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1099
1100 const_iterator
1101 lower_bound(const key_type& __k) const
1102 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1103
1104 iterator
1105 upper_bound(const key_type& __k)
1106 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1107
1108 const_iterator
1109 upper_bound(const key_type& __k) const
1110 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1111
1112 pair<iterator, iterator>
1113 equal_range(const key_type& __k);
1114
1115 pair<const_iterator, const_iterator>
1116 equal_range(const key_type& __k) const;
1117
1118#if __cplusplus > 201103L
1119 template<typename _Kt,
1120 typename _Req =
1121 typename __has_is_transparent<_Compare, _Kt>::type>
1122 iterator
1123 _M_find_tr(const _Kt& __k)
1124 {
1125 const _Rb_tree* __const_this = this;
1126 return __const_this->_M_find_tr(__k)._M_const_cast();
1127 }
1128
1129 template<typename _Kt,
1130 typename _Req =
1131 typename __has_is_transparent<_Compare, _Kt>::type>
1132 const_iterator
1133 _M_find_tr(const _Kt& __k) const
1134 {
1135 auto __j = _M_lower_bound_tr(__k);
1136 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1137 __j = end();
1138 return __j;
1139 }
1140
1141 template<typename _Kt,
1142 typename _Req =
1143 typename __has_is_transparent<_Compare, _Kt>::type>
1144 size_type
1145 _M_count_tr(const _Kt& __k) const
1146 {
1147 auto __p = _M_equal_range_tr(__k);
1148 return std::distance(__p.first, __p.second);
1149 }
1150
1151 template<typename _Kt,
1152 typename _Req =
1153 typename __has_is_transparent<_Compare, _Kt>::type>
1154 iterator
1155 _M_lower_bound_tr(const _Kt& __k)
1156 {
1157 const _Rb_tree* __const_this = this;
1158 return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1159 }
1160
1161 template<typename _Kt,
1162 typename _Req =
1163 typename __has_is_transparent<_Compare, _Kt>::type>
1164 const_iterator
1165 _M_lower_bound_tr(const _Kt& __k) const
1166 {
1167 auto __x = _M_begin();
1168 auto __y = _M_end();
1169 while (__x != 0)
1170 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1171 {
1172 __y = __x;
1173 __x = _S_left(__x);
1174 }
1175 else
1176 __x = _S_right(__x);
1177 return const_iterator(__y);
1178 }
1179
1180 template<typename _Kt,
1181 typename _Req =
1182 typename __has_is_transparent<_Compare, _Kt>::type>
1183 iterator
1184 _M_upper_bound_tr(const _Kt& __k)
1185 {
1186 const _Rb_tree* __const_this = this;
1187 return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1188 }
1189
1190 template<typename _Kt,
1191 typename _Req =
1192 typename __has_is_transparent<_Compare, _Kt>::type>
1193 const_iterator
1194 _M_upper_bound_tr(const _Kt& __k) const
1195 {
1196 auto __x = _M_begin();
1197 auto __y = _M_end();
1198 while (__x != 0)
1199 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1200 {
1201 __y = __x;
1202 __x = _S_left(__x);
1203 }
1204 else
1205 __x = _S_right(__x);
1206 return const_iterator(__y);
1207 }
1208
1209 template<typename _Kt,
1210 typename _Req =
1211 typename __has_is_transparent<_Compare, _Kt>::type>
1212 pair<iterator, iterator>
1213 _M_equal_range_tr(const _Kt& __k)
1214 {
1215 const _Rb_tree* __const_this = this;
1216 auto __ret = __const_this->_M_equal_range_tr(__k);
1217 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1218 }
1219
1220 template<typename _Kt,
1221 typename _Req =
1222 typename __has_is_transparent<_Compare, _Kt>::type>
1223 pair<const_iterator, const_iterator>
1224 _M_equal_range_tr(const _Kt& __k) const
1225 {
1226 auto __low = _M_lower_bound_tr(__k);
1227 auto __high = __low;
1228 auto& __cmp = _M_impl._M_key_compare;
1229 while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1230 ++__high;
1231 return { __low, __high };
1232 }
1233#endif
1234
1235 // Debugging.
1236 bool
1237 __rb_verify() const;
1238
1239#if __cplusplus >= 201103L
1240 _Rb_tree&
1241 operator=(_Rb_tree&&)
1242 noexcept(_Alloc_traits::_S_nothrow_move()
1243 && is_nothrow_move_assignable<_Compare>::value);
1244
1245 template<typename _Iterator>
1246 void
1247 _M_assign_unique(_Iterator, _Iterator);
1248
1249 template<typename _Iterator>
1250 void
1251 _M_assign_equal(_Iterator, _Iterator);
1252
1253 private:
1254 // Move elements from container with equal allocator.
1255 void
1256 _M_move_data(_Rb_tree&, std::true_type);
1257
1258 // Move elements from container with possibly non-equal allocator,
1259 // which might result in a copy not a move.
1260 void
1261 _M_move_data(_Rb_tree&, std::false_type);
1262#endif
1263 };
1264
1265 template<typename _Key, typename _Val, typename _KeyOfValue,
1266 typename _Compare, typename _Alloc>
1267 inline bool
1268 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1269 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1270 {
1271 return __x.size() == __y.size()
1272 && std::equal(__x.begin(), __x.end(), __y.begin());
1273 }
1274
1275 template<typename _Key, typename _Val, typename _KeyOfValue,
1276 typename _Compare, typename _Alloc>
1277 inline bool
1278 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1279 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1280 {
1281 return std::lexicographical_compare(__x.begin(), __x.end(),
1282 __y.begin(), __y.end());
1283 }
1284
1285 template<typename _Key, typename _Val, typename _KeyOfValue,
1286 typename _Compare, typename _Alloc>
1287 inline bool
1288 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1289 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1290 { return !(__x == __y); }
1291
1292 template<typename _Key, typename _Val, typename _KeyOfValue,
1293 typename _Compare, typename _Alloc>
1294 inline bool
1295 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1296 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1297 { return __y < __x; }
1298
1299 template<typename _Key, typename _Val, typename _KeyOfValue,
1300 typename _Compare, typename _Alloc>
1301 inline bool
1302 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1303 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1304 { return !(__y < __x); }
1305
1306 template<typename _Key, typename _Val, typename _KeyOfValue,
1307 typename _Compare, typename _Alloc>
1308 inline bool
1309 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1310 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1311 { return !(__x < __y); }
1312
1313 template<typename _Key, typename _Val, typename _KeyOfValue,
1314 typename _Compare, typename _Alloc>
1315 inline void
1316 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1317 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1318 { __x.swap(__y); }
1319
1320#if __cplusplus >= 201103L
1321 template<typename _Key, typename _Val, typename _KeyOfValue,
1322 typename _Compare, typename _Alloc>
1323 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1324 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1325 : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1326 {
1327 using __eq = typename _Alloc_traits::is_always_equal;
1328 if (__x._M_root() != nullptr)
1329 _M_move_data(__x, __eq());
1330 }
1331
1332 template<typename _Key, typename _Val, typename _KeyOfValue,
1333 typename _Compare, typename _Alloc>
1334 void
1335 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1336 _M_move_data(_Rb_tree& __x, std::true_type)
1337 {
1338 _M_root() = __x._M_root();
1339 _M_leftmost() = __x._M_leftmost();
1340 _M_rightmost() = __x._M_rightmost();
1341 _M_root()->_M_parent = _M_end();
1342
1343 __x._M_root() = 0;
1344 __x._M_leftmost() = __x._M_end();
1345 __x._M_rightmost() = __x._M_end();
1346
1347 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
1348 __x._M_impl._M_node_count = 0;
1349 }
1350
1351 template<typename _Key, typename _Val, typename _KeyOfValue,
1352 typename _Compare, typename _Alloc>
1353 void
1354 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1355 _M_move_data(_Rb_tree& __x, std::false_type)
1356 {
1357 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1358 _M_move_data(__x, std::true_type());
1359 else
1360 {
1361 _Alloc_node __an(*this);
1362 auto __lbd =
1363 [&__an](const value_type& __cval)
1364 {
1365 auto& __val = const_cast<value_type&>(__cval);
1366 return __an(std::move_if_noexcept(__val));
1367 };
1368 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1369 _M_leftmost() = _S_minimum(_M_root());
1370 _M_rightmost() = _S_maximum(_M_root());
1371 _M_impl._M_node_count = __x._M_impl._M_node_count;
1372 }
1373 }
1374
1375 template<typename _Key, typename _Val, typename _KeyOfValue,
1376 typename _Compare, typename _Alloc>
1377 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1378 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1379 operator=(_Rb_tree&& __x)
1380 noexcept(_Alloc_traits::_S_nothrow_move()
1381 && is_nothrow_move_assignable<_Compare>::value)
1382 {
1383 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1384 if (_Alloc_traits::_S_propagate_on_move_assign()
1385 || _Alloc_traits::_S_always_equal()
1386 || _M_get_Node_allocator() == __x._M_get_Node_allocator())
1387 {
1388 clear();
1389 if (__x._M_root() != nullptr)
1390 _M_move_data(__x, std::true_type());
1391 std::__alloc_on_move(_M_get_Node_allocator(),
1392 __x._M_get_Node_allocator());
1393 return *this;
1394 }
1395
1396 // Try to move each node reusing existing nodes and copying __x nodes
1397 // structure.
1398 _Reuse_or_alloc_node __roan(*this);
1399 _M_impl._M_reset();
1400 if (__x._M_root() != nullptr)
1401 {
1402 auto __lbd =
1403 [&__roan](const value_type& __cval)
1404 {
1405 auto& __val = const_cast<value_type&>(__cval);
1406 return __roan(std::move_if_noexcept(__val));
1407 };
1408 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1409 _M_leftmost() = _S_minimum(_M_root());
1410 _M_rightmost() = _S_maximum(_M_root());
1411 _M_impl._M_node_count = __x._M_impl._M_node_count;
1412 __x.clear();
1413 }
1414 return *this;
1415 }
1416
1417 template<typename _Key, typename _Val, typename _KeyOfValue,
1418 typename _Compare, typename _Alloc>
1419 template<typename _Iterator>
1420 void
1421 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1422 _M_assign_unique(_Iterator __first, _Iterator __last)
1423 {
1424 _Reuse_or_alloc_node __roan(*this);
1425 _M_impl._M_reset();
1426 for (; __first != __last; ++__first)
1427 _M_insert_unique_(end(), *__first, __roan);
1428 }
1429
1430 template<typename _Key, typename _Val, typename _KeyOfValue,
1431 typename _Compare, typename _Alloc>
1432 template<typename _Iterator>
1433 void
1434 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1435 _M_assign_equal(_Iterator __first, _Iterator __last)
1436 {
1437 _Reuse_or_alloc_node __roan(*this);
1438 _M_impl._M_reset();
1439 for (; __first != __last; ++__first)
1440 _M_insert_equal_(end(), *__first, __roan);
1441 }
1442#endif
1443
1444 template<typename _Key, typename _Val, typename _KeyOfValue,
1445 typename _Compare, typename _Alloc>
1446 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1447 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1448 operator=(const _Rb_tree& __x)
1449 {
1450 if (this != &__x)
1451 {
1452 // Note that _Key may be a constant type.
1453#if __cplusplus >= 201103L
1454 if (_Alloc_traits::_S_propagate_on_copy_assign())
1455 {
1456 auto& __this_alloc = this->_M_get_Node_allocator();
1457 auto& __that_alloc = __x._M_get_Node_allocator();
1458 if (!_Alloc_traits::_S_always_equal()
1459 && __this_alloc != __that_alloc)
1460 {
1461 // Replacement allocator cannot free existing storage, we need
1462 // to erase nodes first.
1463 clear();
1464 std::__alloc_on_copy(__this_alloc, __that_alloc);
1465 }
1466 }
1467#endif
1468
1469 _Reuse_or_alloc_node __roan(*this);
1470 _M_impl._M_reset();
1471 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1472 if (__x._M_root() != 0)
1473 {
1474 _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
1475 _M_leftmost() = _S_minimum(_M_root());
1476 _M_rightmost() = _S_maximum(_M_root());
1477 _M_impl._M_node_count = __x._M_impl._M_node_count;
1478 }
1479 }
1480
1481 return *this;
1482 }
1483
1484 template<typename _Key, typename _Val, typename _KeyOfValue,
1485 typename _Compare, typename _Alloc>
1486#if __cplusplus >= 201103L
1487 template<typename _Arg, typename _NodeGen>
1488#else
1489 template<typename _NodeGen>
1490#endif
1491 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1492 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1493 _M_insert_(_Base_ptr __x, _Base_ptr __p,
1494#if __cplusplus >= 201103L
1495 _Arg&& __v,
1496#else
1497 const _Val& __v,
1498#endif
1499 _NodeGen& __node_gen)
1500 {
1501 bool __insert_left = (__x != 0 || __p == _M_end()
1502 || _M_impl._M_key_compare(_KeyOfValue()(__v),
1503 _S_key(__p)));
1504
1505 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1506
1507 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1508 this->_M_impl._M_header);
1509 ++_M_impl._M_node_count;
1510 return iterator(__z);
1511 }
1512
1513 template<typename _Key, typename _Val, typename _KeyOfValue,
1514 typename _Compare, typename _Alloc>
1515#if __cplusplus >= 201103L
1516 template<typename _Arg>
1517#endif
1518 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1519 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1520#if __cplusplus >= 201103L
1521 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1522#else
1523 _M_insert_lower(_Base_ptr __p, const _Val& __v)
1524#endif
1525 {
1526 bool __insert_left = (__p == _M_end()
1527 || !_M_impl._M_key_compare(_S_key(__p),
1528 _KeyOfValue()(__v)));
1529
1530 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1531
1532 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1533 this->_M_impl._M_header);
1534 ++_M_impl._M_node_count;
1535 return iterator(__z);
1536 }
1537
1538 template<typename _Key, typename _Val, typename _KeyOfValue,
1539 typename _Compare, typename _Alloc>
1540#if __cplusplus >= 201103L
1541 template<typename _Arg>
1542#endif
1543 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1544 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1545#if __cplusplus >= 201103L
1546 _M_insert_equal_lower(_Arg&& __v)
1547#else
1548 _M_insert_equal_lower(const _Val& __v)
1549#endif
1550 {
1551 _Link_type __x = _M_begin();
1552 _Base_ptr __y = _M_end();
1553 while (__x != 0)
1554 {
1555 __y = __x;
1556 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1557 _S_left(__x) : _S_right(__x);
1558 }
1559 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1560 }
1561
1562 template<typename _Key, typename _Val, typename _KoV,
1563 typename _Compare, typename _Alloc>
1564 template<typename _NodeGen>
1565 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1566 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1567 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1568 {
1569 // Structural copy. __x and __p must be non-null.
1570 _Link_type __top = _M_clone_node(__x, __node_gen);
1571 __top->_M_parent = __p;
1572
1573 __try
1574 {
1575 if (__x->_M_right)
1576 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1577 __p = __top;
1578 __x = _S_left(__x);
1579
1580 while (__x != 0)
1581 {
1582 _Link_type __y = _M_clone_node(__x, __node_gen);
1583 __p->_M_left = __y;
1584 __y->_M_parent = __p;
1585 if (__x->_M_right)
1586 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1587 __p = __y;
1588 __x = _S_left(__x);
1589 }
1590 }
1591 __catch(...)
1592 {
1593 _M_erase(__top);
1594 __throw_exception_again;
1595 }
1596 return __top;
1597 }
1598
1599 template<typename _Key, typename _Val, typename _KeyOfValue,
1600 typename _Compare, typename _Alloc>
1601 void
1602 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1603 _M_erase(_Link_type __x)
1604 {
1605 // Erase without rebalancing.
1606 while (__x != 0)
1607 {
1608 _M_erase(_S_right(__x));
1609 _Link_type __y = _S_left(__x);
1610 _M_drop_node(__x);
1611 __x = __y;
1612 }
1613 }
1614
1615 template<typename _Key, typename _Val, typename _KeyOfValue,
1616 typename _Compare, typename _Alloc>
1617 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1618 _Compare, _Alloc>::iterator
1619 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1620 _M_lower_bound(_Link_type __x, _Base_ptr __y,
1621 const _Key& __k)
1622 {
1623 while (__x != 0)
1624 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1625 __y = __x, __x = _S_left(__x);
1626 else
1627 __x = _S_right(__x);
1628 return iterator(__y);
1629 }
1630
1631 template<typename _Key, typename _Val, typename _KeyOfValue,
1632 typename _Compare, typename _Alloc>
1633 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1634 _Compare, _Alloc>::const_iterator
1635 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1636 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1637 const _Key& __k) const
1638 {
1639 while (__x != 0)
1640 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1641 __y = __x, __x = _S_left(__x);
1642 else
1643 __x = _S_right(__x);
1644 return const_iterator(__y);
1645 }
1646
1647 template<typename _Key, typename _Val, typename _KeyOfValue,
1648 typename _Compare, typename _Alloc>
1649 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1650 _Compare, _Alloc>::iterator
1651 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1652 _M_upper_bound(_Link_type __x, _Base_ptr __y,
1653 const _Key& __k)
1654 {
1655 while (__x != 0)
1656 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1657 __y = __x, __x = _S_left(__x);
1658 else
1659 __x = _S_right(__x);
1660 return iterator(__y);
1661 }
1662
1663 template<typename _Key, typename _Val, typename _KeyOfValue,
1664 typename _Compare, typename _Alloc>
1665 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1666 _Compare, _Alloc>::const_iterator
1667 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1668 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1669 const _Key& __k) const
1670 {
1671 while (__x != 0)
1672 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1673 __y = __x, __x = _S_left(__x);
1674 else
1675 __x = _S_right(__x);
1676 return const_iterator(__y);
1677 }
1678
1679 template<typename _Key, typename _Val, typename _KeyOfValue,
1680 typename _Compare, typename _Alloc>
1681 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1682 _Compare, _Alloc>::iterator,
1683 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1684 _Compare, _Alloc>::iterator>
1685 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1686 equal_range(const _Key& __k)
1687 {
1688 _Link_type __x = _M_begin();
1689 _Base_ptr __y = _M_end();
1690 while (__x != 0)
1691 {
1692 if (_M_impl._M_key_compare(_S_key(__x), __k))
1693 __x = _S_right(__x);
1694 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1695 __y = __x, __x = _S_left(__x);
1696 else
1697 {
1698 _Link_type __xu(__x);
1699 _Base_ptr __yu(__y);
1700 __y = __x, __x = _S_left(__x);
1701 __xu = _S_right(__xu);
1702 return pair<iterator,
1703 iterator>(_M_lower_bound(__x, __y, __k),
1704 _M_upper_bound(__xu, __yu, __k));
1705 }
1706 }
1707 return pair<iterator, iterator>(iterator(__y),
1708 iterator(__y));
1709 }
1710
1711 template<typename _Key, typename _Val, typename _KeyOfValue,
1712 typename _Compare, typename _Alloc>
1713 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1714 _Compare, _Alloc>::const_iterator,
1715 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1716 _Compare, _Alloc>::const_iterator>
1717 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1718 equal_range(const _Key& __k) const
1719 {
1720 _Const_Link_type __x = _M_begin();
1721 _Const_Base_ptr __y = _M_end();
1722 while (__x != 0)
1723 {
1724 if (_M_impl._M_key_compare(_S_key(__x), __k))
1725 __x = _S_right(__x);
1726 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1727 __y = __x, __x = _S_left(__x);
1728 else
1729 {
1730 _Const_Link_type __xu(__x);
1731 _Const_Base_ptr __yu(__y);
1732 __y = __x, __x = _S_left(__x);
1733 __xu = _S_right(__xu);
1734 return pair<const_iterator,
1735 const_iterator>(_M_lower_bound(__x, __y, __k),
1736 _M_upper_bound(__xu, __yu, __k));
1737 }
1738 }
1739 return pair<const_iterator, const_iterator>(const_iterator(__y),
1740 const_iterator(__y));
1741 }
1742
1743 template<typename _Key, typename _Val, typename _KeyOfValue,
1744 typename _Compare, typename _Alloc>
1745 void
1746 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1747 swap(_Rb_tree& __t)
1748 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
1749 {
1750 if (_M_root() == 0)
1751 {
1752 if (__t._M_root() != 0)
1753 {
1754 _M_root() = __t._M_root();
1755 _M_leftmost() = __t._M_leftmost();
1756 _M_rightmost() = __t._M_rightmost();
1757 _M_root()->_M_parent = _M_end();
1758 _M_impl._M_node_count = __t._M_impl._M_node_count;
1759
1760 __t._M_impl._M_reset();
1761 }
1762 }
1763 else if (__t._M_root() == 0)
1764 {
1765 __t._M_root() = _M_root();
1766 __t._M_leftmost() = _M_leftmost();
1767 __t._M_rightmost() = _M_rightmost();
1768 __t._M_root()->_M_parent = __t._M_end();
1769 __t._M_impl._M_node_count = _M_impl._M_node_count;
1770
1771 _M_impl._M_reset();
1772 }
1773 else
1774 {
1775 std::swap(_M_root(),__t._M_root());
1776 std::swap(_M_leftmost(),__t._M_leftmost());
1777 std::swap(_M_rightmost(),__t._M_rightmost());
1778
1779 _M_root()->_M_parent = _M_end();
1780 __t._M_root()->_M_parent = __t._M_end();
1781 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1782 }
1783 // No need to swap header's color as it does not change.
1784 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1785
1786 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1787 __t._M_get_Node_allocator());
1788 }
1789
1790 template<typename _Key, typename _Val, typename _KeyOfValue,
1791 typename _Compare, typename _Alloc>
1792 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1793 _Compare, _Alloc>::_Base_ptr,
1794 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1795 _Compare, _Alloc>::_Base_ptr>
1796 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1797 _M_get_insert_unique_pos(const key_type& __k)
1798 {
1799 typedef pair<_Base_ptr, _Base_ptr> _Res;
1800 _Link_type __x = _M_begin();
1801 _Base_ptr __y = _M_end();
1802 bool __comp = true;
1803 while (__x != 0)
1804 {
1805 __y = __x;
1806 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1807 __x = __comp ? _S_left(__x) : _S_right(__x);
1808 }
1809 iterator __j = iterator(__y);
1810 if (__comp)
1811 {
1812 if (__j == begin())
1813 return _Res(__x, __y);
1814 else
1815 --__j;
1816 }
1817 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1818 return _Res(__x, __y);
1819 return _Res(__j._M_node, 0);
1820 }
1821
1822 template<typename _Key, typename _Val, typename _KeyOfValue,
1823 typename _Compare, typename _Alloc>
1824 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1825 _Compare, _Alloc>::_Base_ptr,
1826 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1827 _Compare, _Alloc>::_Base_ptr>
1828 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1829 _M_get_insert_equal_pos(const key_type& __k)
1830 {
1831 typedef pair<_Base_ptr, _Base_ptr> _Res;
1832 _Link_type __x = _M_begin();
1833 _Base_ptr __y = _M_end();
1834 while (__x != 0)
1835 {
1836 __y = __x;
1837 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1838 _S_left(__x) : _S_right(__x);
1839 }
1840 return _Res(__x, __y);
1841 }
1842
1843 template<typename _Key, typename _Val, typename _KeyOfValue,
1844 typename _Compare, typename _Alloc>
1845#if __cplusplus >= 201103L
1846 template<typename _Arg>
1847#endif
1848 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1849 _Compare, _Alloc>::iterator, bool>
1850 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1851#if __cplusplus >= 201103L
1852 _M_insert_unique(_Arg&& __v)
1853#else
1854 _M_insert_unique(const _Val& __v)
1855#endif
1856 {
1857 typedef pair<iterator, bool> _Res;
1858 pair<_Base_ptr, _Base_ptr> __res
1859 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1860
1861 if (__res.second)
1862 {
1863 _Alloc_node __an(*this);
1864 return _Res(_M_insert_(__res.first, __res.second,
1865 _GLIBCXX_FORWARD(_Arg, __v), __an),
1866 true);
1867 }
1868
1869 return _Res(iterator(__res.first), false);
1870 }
1871
1872 template<typename _Key, typename _Val, typename _KeyOfValue,
1873 typename _Compare, typename _Alloc>
1874#if __cplusplus >= 201103L
1875 template<typename _Arg>
1876#endif
1877 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1878 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1879#if __cplusplus >= 201103L
1880 _M_insert_equal(_Arg&& __v)
1881#else
1882 _M_insert_equal(const _Val& __v)
1883#endif
1884 {
1885 pair<_Base_ptr, _Base_ptr> __res
1886 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1887 _Alloc_node __an(*this);
1888 return _M_insert_(__res.first, __res.second,
1889 _GLIBCXX_FORWARD(_Arg, __v), __an);
1890 }
1891
1892 template<typename _Key, typename _Val, typename _KeyOfValue,
1893 typename _Compare, typename _Alloc>
1894 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1895 _Compare, _Alloc>::_Base_ptr,
1896 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1897 _Compare, _Alloc>::_Base_ptr>
1898 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1899 _M_get_insert_hint_unique_pos(const_iterator __position,
1900 const key_type& __k)
1901 {
1902 iterator __pos = __position._M_const_cast();
1903 typedef pair<_Base_ptr, _Base_ptr> _Res;
1904
1905 // end()
1906 if (__pos._M_node == _M_end())
1907 {
1908 if (size() > 0
1909 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1910 return _Res(0, _M_rightmost());
1911 else
1912 return _M_get_insert_unique_pos(__k);
1913 }
1914 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1915 {
1916 // First, try before...
1917 iterator __before = __pos;
1918 if (__pos._M_node == _M_leftmost()) // begin()
1919 return _Res(_M_leftmost(), _M_leftmost());
1920 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1921 {
1922 if (_S_right(__before._M_node) == 0)
1923 return _Res(0, __before._M_node);
1924 else
1925 return _Res(__pos._M_node, __pos._M_node);
1926 }
1927 else
1928 return _M_get_insert_unique_pos(__k);
1929 }
1930 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1931 {
1932 // ... then try after.
1933 iterator __after = __pos;
1934 if (__pos._M_node == _M_rightmost())
1935 return _Res(0, _M_rightmost());
1936 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1937 {
1938 if (_S_right(__pos._M_node) == 0)
1939 return _Res(0, __pos._M_node);
1940 else
1941 return _Res(__after._M_node, __after._M_node);
1942 }
1943 else
1944 return _M_get_insert_unique_pos(__k);
1945 }
1946 else
1947 // Equivalent keys.
1948 return _Res(__pos._M_node, 0);
1949 }
1950
1951 template<typename _Key, typename _Val, typename _KeyOfValue,
1952 typename _Compare, typename _Alloc>
1953#if __cplusplus >= 201103L
1954 template<typename _Arg, typename _NodeGen>
1955#else
1956 template<typename _NodeGen>
1957#endif
1958 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1959 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1960 _M_insert_unique_(const_iterator __position,
1961#if __cplusplus >= 201103L
1962 _Arg&& __v,
1963#else
1964 const _Val& __v,
1965#endif
1966 _NodeGen& __node_gen)
1967 {
1968 pair<_Base_ptr, _Base_ptr> __res
1969 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
1970
1971 if (__res.second)
1972 return _M_insert_(__res.first, __res.second,
1973 _GLIBCXX_FORWARD(_Arg, __v),
1974 __node_gen);
1975 return iterator(__res.first);
1976 }
1977
1978 template<typename _Key, typename _Val, typename _KeyOfValue,
1979 typename _Compare, typename _Alloc>
1980 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1981 _Compare, _Alloc>::_Base_ptr,
1982 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1983 _Compare, _Alloc>::_Base_ptr>
1984 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1985 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
1986 {
1987 iterator __pos = __position._M_const_cast();
1988 typedef pair<_Base_ptr, _Base_ptr> _Res;
1989
1990 // end()
1991 if (__pos._M_node == _M_end())
1992 {
1993 if (size() > 0
1994 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
1995 return _Res(0, _M_rightmost());
1996 else
1997 return _M_get_insert_equal_pos(__k);
1998 }
1999 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2000 {
2001 // First, try before...
2002 iterator __before = __pos;
2003 if (__pos._M_node == _M_leftmost()) // begin()
2004 return _Res(_M_leftmost(), _M_leftmost());
2005 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2006 {
2007 if (_S_right(__before._M_node) == 0)
2008 return _Res(0, __before._M_node);
2009 else
2010 return _Res(__pos._M_node, __pos._M_node);
2011 }
2012 else
2013 return _M_get_insert_equal_pos(__k);
2014 }
2015 else
2016 {
2017 // ... then try after.
2018 iterator __after = __pos;
2019 if (__pos._M_node == _M_rightmost())
2020 return _Res(0, _M_rightmost());
2021 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2022 {
2023 if (_S_right(__pos._M_node) == 0)
2024 return _Res(0, __pos._M_node);
2025 else
2026 return _Res(__after._M_node, __after._M_node);
2027 }
2028 else
2029 return _Res(0, 0);
2030 }
2031 }
2032
2033 template<typename _Key, typename _Val, typename _KeyOfValue,
2034 typename _Compare, typename _Alloc>
2035#if __cplusplus >= 201103L
2036 template<typename _Arg, typename _NodeGen>
2037#else
2038 template<typename _NodeGen>
2039#endif
2040 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2041 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2042 _M_insert_equal_(const_iterator __position,
2043#if __cplusplus >= 201103L
2044 _Arg&& __v,
2045#else
2046 const _Val& __v,
2047#endif
2048 _NodeGen& __node_gen)
2049 {
2050 pair<_Base_ptr, _Base_ptr> __res
2051 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2052
2053 if (__res.second)
2054 return _M_insert_(__res.first, __res.second,
2055 _GLIBCXX_FORWARD(_Arg, __v),
2056 __node_gen);
2057
2058 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2059 }
2060
2061#if __cplusplus >= 201103L
2062 template<typename _Key, typename _Val, typename _KeyOfValue,
2063 typename _Compare, typename _Alloc>
2064 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2065 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2066 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2067 {
2068 bool __insert_left = (__x != 0 || __p == _M_end()
2069 || _M_impl._M_key_compare(_S_key(__z),
2070 _S_key(__p)));
2071
2072 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2073 this->_M_impl._M_header);
2074 ++_M_impl._M_node_count;
2075 return iterator(__z);
2076 }
2077
2078 template<typename _Key, typename _Val, typename _KeyOfValue,
2079 typename _Compare, typename _Alloc>
2080 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2081 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2082 _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2083 {
2084 bool __insert_left = (__p == _M_end()
2085 || !_M_impl._M_key_compare(_S_key(__p),
2086 _S_key(__z)));
2087
2088 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2089 this->_M_impl._M_header);
2090 ++_M_impl._M_node_count;
2091 return iterator(__z);
2092 }
2093
2094 template<typename _Key, typename _Val, typename _KeyOfValue,
2095 typename _Compare, typename _Alloc>
2096 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2097 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2098 _M_insert_equal_lower_node(_Link_type __z)
2099 {
2100 _Link_type __x = _M_begin();
2101 _Base_ptr __y = _M_end();
2102 while (__x != 0)
2103 {
2104 __y = __x;
2105 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2106 _S_left(__x) : _S_right(__x);
2107 }
2108 return _M_insert_lower_node(__y, __z);
2109 }
2110
2111 template<typename _Key, typename _Val, typename _KeyOfValue,
2112 typename _Compare, typename _Alloc>
2113 template<typename... _Args>
2114 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2115 _Compare, _Alloc>::iterator, bool>
2116 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2117 _M_emplace_unique(_Args&&... __args)
2118 {
2119 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2120
2121 __try
2122 {
2123 typedef pair<iterator, bool> _Res;
2124 auto __res = _M_get_insert_unique_pos(_S_key(__z));
2125 if (__res.second)
2126 return _Res(_M_insert_node(__res.first, __res.second, __z), true);
2127
2128 _M_drop_node(__z);
2129 return _Res(iterator(__res.first), false);
2130 }
2131 __catch(...)
2132 {
2133 _M_drop_node(__z);
2134 __throw_exception_again;
2135 }
2136 }
2137
2138 template<typename _Key, typename _Val, typename _KeyOfValue,
2139 typename _Compare, typename _Alloc>
2140 template<typename... _Args>
2141 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2142 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2143 _M_emplace_equal(_Args&&... __args)
2144 {
2145 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2146
2147 __try
2148 {
2149 auto __res = _M_get_insert_equal_pos(_S_key(__z));
2150 return _M_insert_node(__res.first, __res.second, __z);
2151 }
2152 __catch(...)
2153 {
2154 _M_drop_node(__z);
2155 __throw_exception_again;
2156 }
2157 }
2158
2159 template<typename _Key, typename _Val, typename _KeyOfValue,
2160 typename _Compare, typename _Alloc>
2161 template<typename... _Args>
2162 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2163 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2164 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2165 {
2166 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2167
2168 __try
2169 {
2170 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2171
2172 if (__res.second)
2173 return _M_insert_node(__res.first, __res.second, __z);
2174
2175 _M_drop_node(__z);
2176 return iterator(__res.first);
2177 }
2178 __catch(...)
2179 {
2180 _M_drop_node(__z);
2181 __throw_exception_again;
2182 }
2183 }
2184
2185 template<typename _Key, typename _Val, typename _KeyOfValue,
2186 typename _Compare, typename _Alloc>
2187 template<typename... _Args>
2188 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2189 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2190 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2191 {
2192 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2193
2194 __try
2195 {
2196 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2197
2198 if (__res.second)
2199 return _M_insert_node(__res.first, __res.second, __z);
2200
2201 return _M_insert_equal_lower_node(__z);
2202 }
2203 __catch(...)
2204 {
2205 _M_drop_node(__z);
2206 __throw_exception_again;
2207 }
2208 }
2209#endif
2210
2211 template<typename _Key, typename _Val, typename _KoV,
2212 typename _Cmp, typename _Alloc>
2213 template<class _II>
2214 void
2215 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2216 _M_insert_unique(_II __first, _II __last)
2217 {
2218 _Alloc_node __an(*this);
2219 for (; __first != __last; ++__first)
2220 _M_insert_unique_(end(), *__first, __an);
2221 }
2222
2223 template<typename _Key, typename _Val, typename _KoV,
2224 typename _Cmp, typename _Alloc>
2225 template<class _II>
2226 void
2227 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2228 _M_insert_equal(_II __first, _II __last)
2229 {
2230 _Alloc_node __an(*this);
2231 for (; __first != __last; ++__first)
2232 _M_insert_equal_(end(), *__first, __an);
2233 }
2234
2235 template<typename _Key, typename _Val, typename _KeyOfValue,
2236 typename _Compare, typename _Alloc>
2237 void
2238 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2239 _M_erase_aux(const_iterator __position)
2240 {
2241 _Link_type __y =
2242 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
2243 (const_cast<_Base_ptr>(__position._M_node),
2244 this->_M_impl._M_header));
2245 _M_drop_node(__y);
2246 --_M_impl._M_node_count;
2247 }
2248
2249 template<typename _Key, typename _Val, typename _KeyOfValue,
2250 typename _Compare, typename _Alloc>
2251 void
2252 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2253 _M_erase_aux(const_iterator __first, const_iterator __last)
2254 {
2255 if (__first == begin() && __last == end())
2256 clear();
2257 else
2258 while (__first != __last)
2259 erase(__first++);
2260 }
2261
2262 template<typename _Key, typename _Val, typename _KeyOfValue,
2263 typename _Compare, typename _Alloc>
2264 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2265 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2266 erase(const _Key& __x)
2267 {
2268 pair<iterator, iterator> __p = equal_range(__x);
2269 const size_type __old_size = size();
2270 erase(__p.first, __p.second);
2271 return __old_size - size();
2272 }
2273
2274 template<typename _Key, typename _Val, typename _KeyOfValue,
2275 typename _Compare, typename _Alloc>
2276 void
2277 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2278 erase(const _Key* __first, const _Key* __last)
2279 {
2280 while (__first != __last)
2281 erase(*__first++);
2282 }
2283
2284 template<typename _Key, typename _Val, typename _KeyOfValue,
2285 typename _Compare, typename _Alloc>
2286 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2287 _Compare, _Alloc>::iterator
2288 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2289 find(const _Key& __k)
2290 {
2291 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2292 return (__j == end()
2293 || _M_impl._M_key_compare(__k,
2294 _S_key(__j._M_node))) ? end() : __j;
2295 }
2296
2297 template<typename _Key, typename _Val, typename _KeyOfValue,
2298 typename _Compare, typename _Alloc>
2299 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2300 _Compare, _Alloc>::const_iterator
2301 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2302 find(const _Key& __k) const
2303 {
2304 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2305 return (__j == end()
2306 || _M_impl._M_key_compare(__k,
2307 _S_key(__j._M_node))) ? end() : __j;
2308 }
2309
2310 template<typename _Key, typename _Val, typename _KeyOfValue,
2311 typename _Compare, typename _Alloc>
2312 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2313 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2314 count(const _Key& __k) const
2315 {
2316 pair<const_iterator, const_iterator> __p = equal_range(__k);
2317 const size_type __n = std::distance(__p.first, __p.second);
2318 return __n;
2319 }
2320
2321 _GLIBCXX_PURE unsigned int
2322 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
2323 const _Rb_tree_node_base* __root) throw ();
2324
2325 template<typename _Key, typename _Val, typename _KeyOfValue,
2326 typename _Compare, typename _Alloc>
2327 bool
2328 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
2329 {
2330 if (_M_impl._M_node_count == 0 || begin() == end())
2331 return _M_impl._M_node_count == 0 && begin() == end()
2332 && this->_M_impl._M_header._M_left == _M_end()
2333 && this->_M_impl._M_header._M_right == _M_end();
2334
2335 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2336 for (const_iterator __it = begin(); __it != end(); ++__it)
2337 {
2338 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
2339 _Const_Link_type __L = _S_left(__x);
2340 _Const_Link_type __R = _S_right(__x);
2341
2342 if (__x->_M_color == _S_red)
2343 if ((__L && __L->_M_color == _S_red)
2344 || (__R && __R->_M_color == _S_red))
2345 return false;
2346
2347 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2348 return false;
2349 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2350 return false;
2351
2352 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2353 return false;
2354 }
2355
2356 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2357 return false;
2358 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2359 return false;
2360 return true;
2361 }
2362
2363_GLIBCXX_END_NAMESPACE_VERSION
2364} // namespace
2365
2366#endif
2367