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