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