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