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