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