projects / gcc.git / blob
? search:


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