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