1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001-2015 Free Software Foundation, Inc.
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)
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.
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.
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/>.
27 * Copyright (c) 1996,1997
28 * Silicon Graphics Computer Systems, Inc.
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.
40 * Hewlett-Packard Company
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.
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}
61 #pragma GCC system_header
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>
72 namespace std _GLIBCXX_VISIBILITY(default)
74 _GLIBCXX_BEGIN_NAMESPACE_VERSION
76 // Red-black tree class, designed for use in implementing STL
77 // associative containers (set, multiset, map, and multimap). The
78 // insertion and deletion algorithms are based on those in Cormen,
79 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
82 // (1) the header cell is maintained with links not only to the root
83 // but also to the leftmost node of the tree, to enable constant
84 // time begin(), and to the rightmost node of the tree, to enable
85 // linear time performance when used with the generic set algorithms
88 // (2) when a node being deleted has two children its successor node
89 // is relinked into its place, rather than copied, so that the only
90 // iterators invalidated are those referring to the deleted node.
92 enum _Rb_tree_color { _S_red = false, _S_black = true };
94 struct _Rb_tree_node_base
96 typedef _Rb_tree_node_base* _Base_ptr;
97 typedef const _Rb_tree_node_base* _Const_Base_ptr;
99 _Rb_tree_color _M_color;
105 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
107 while (__x->_M_left != 0) __x = __x->_M_left;
111 static _Const_Base_ptr
112 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
114 while (__x->_M_left != 0) __x = __x->_M_left;
119 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
121 while (__x->_M_right != 0) __x = __x->_M_right;
125 static _Const_Base_ptr
126 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
128 while (__x->_M_right != 0) __x = __x->_M_right;
133 template<typename _Val>
134 struct _Rb_tree_node : public _Rb_tree_node_base
136 typedef _Rb_tree_node<_Val>* _Link_type;
138 #if __cplusplus < 201103L
143 { return std::__addressof(_M_value_field); }
147 { return std::__addressof(_M_value_field); }
149 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
153 { return _M_storage._M_ptr(); }
157 { return _M_storage._M_ptr(); }
161 _GLIBCXX_PURE _Rb_tree_node_base*
162 _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
164 _GLIBCXX_PURE const _Rb_tree_node_base*
165 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
167 _GLIBCXX_PURE _Rb_tree_node_base*
168 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
170 _GLIBCXX_PURE const _Rb_tree_node_base*
171 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
173 template<typename _Tp>
174 struct _Rb_tree_iterator
176 typedef _Tp value_type;
177 typedef _Tp& reference;
178 typedef _Tp* pointer;
180 typedef bidirectional_iterator_tag iterator_category;
181 typedef ptrdiff_t difference_type;
183 typedef _Rb_tree_iterator<_Tp> _Self;
184 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
185 typedef _Rb_tree_node<_Tp>* _Link_type;
187 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
191 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
195 operator*() const _GLIBCXX_NOEXCEPT
196 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
199 operator->() const _GLIBCXX_NOEXCEPT
200 { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
203 operator++() _GLIBCXX_NOEXCEPT
205 _M_node = _Rb_tree_increment(_M_node);
210 operator++(int) _GLIBCXX_NOEXCEPT
213 _M_node = _Rb_tree_increment(_M_node);
218 operator--() _GLIBCXX_NOEXCEPT
220 _M_node = _Rb_tree_decrement(_M_node);
225 operator--(int) _GLIBCXX_NOEXCEPT
228 _M_node = _Rb_tree_decrement(_M_node);
233 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
234 { return _M_node == __x._M_node; }
237 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
238 { return _M_node != __x._M_node; }
243 template<typename _Tp>
244 struct _Rb_tree_const_iterator
246 typedef _Tp value_type;
247 typedef const _Tp& reference;
248 typedef const _Tp* pointer;
250 typedef _Rb_tree_iterator<_Tp> iterator;
252 typedef bidirectional_iterator_tag iterator_category;
253 typedef ptrdiff_t difference_type;
255 typedef _Rb_tree_const_iterator<_Tp> _Self;
256 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
257 typedef const _Rb_tree_node<_Tp>* _Link_type;
259 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
263 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
266 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
267 : _M_node(__it._M_node) { }
270 _M_const_cast() const _GLIBCXX_NOEXCEPT
271 { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
274 operator*() const _GLIBCXX_NOEXCEPT
275 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
278 operator->() const _GLIBCXX_NOEXCEPT
279 { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
282 operator++() _GLIBCXX_NOEXCEPT
284 _M_node = _Rb_tree_increment(_M_node);
289 operator++(int) _GLIBCXX_NOEXCEPT
292 _M_node = _Rb_tree_increment(_M_node);
297 operator--() _GLIBCXX_NOEXCEPT
299 _M_node = _Rb_tree_decrement(_M_node);
304 operator--(int) _GLIBCXX_NOEXCEPT
307 _M_node = _Rb_tree_decrement(_M_node);
312 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
313 { return _M_node == __x._M_node; }
316 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
317 { return _M_node != __x._M_node; }
322 template<typename _Val>
324 operator==(const _Rb_tree_iterator<_Val>& __x,
325 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
326 { return __x._M_node == __y._M_node; }
328 template<typename _Val>
330 operator!=(const _Rb_tree_iterator<_Val>& __x,
331 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
332 { return __x._M_node != __y._M_node; }
335 _Rb_tree_insert_and_rebalance(const bool __insert_left,
336 _Rb_tree_node_base* __x,
337 _Rb_tree_node_base* __p,
338 _Rb_tree_node_base& __header) throw ();
341 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
342 _Rb_tree_node_base& __header) throw ();
345 template<typename _Key, typename _Val, typename _KeyOfValue,
346 typename _Compare, typename _Alloc = allocator<_Val> >
349 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
350 rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
352 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
355 typedef _Rb_tree_node_base* _Base_ptr;
356 typedef const _Rb_tree_node_base* _Const_Base_ptr;
357 typedef _Rb_tree_node<_Val>* _Link_type;
358 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
361 // Functor recycling a pool of nodes and using allocation once the pool
363 struct _Reuse_or_alloc_node
365 _Reuse_or_alloc_node(_Rb_tree& __t)
366 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
370 _M_root->_M_parent = 0;
372 if (_M_nodes->_M_left)
373 _M_nodes = _M_nodes->_M_left;
379 #if __cplusplus >= 201103L
380 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
383 ~_Reuse_or_alloc_node()
384 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
386 template<typename _Arg>
388 #if __cplusplus < 201103L
389 operator()(const _Arg& __arg)
391 operator()(_Arg&& __arg)
394 _Link_type __node = static_cast<_Link_type>(_M_extract());
397 _M_t._M_destroy_node(__node);
398 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
402 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
412 _Base_ptr __node = _M_nodes;
413 _M_nodes = _M_nodes->_M_parent;
416 if (_M_nodes->_M_right == __node)
418 _M_nodes->_M_right = 0;
420 if (_M_nodes->_M_left)
422 _M_nodes = _M_nodes->_M_left;
424 while (_M_nodes->_M_right)
425 _M_nodes = _M_nodes->_M_right;
427 if (_M_nodes->_M_left)
428 _M_nodes = _M_nodes->_M_left;
431 else // __node is on the left.
432 _M_nodes->_M_left = 0;
445 // Functor similar to the previous one but without any pool of nodes to
449 _Alloc_node(_Rb_tree& __t)
452 template<typename _Arg>
454 #if __cplusplus < 201103L
455 operator()(const _Arg& __arg) const
457 operator()(_Arg&& __arg) const
459 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
466 typedef _Key key_type;
467 typedef _Val value_type;
468 typedef value_type* pointer;
469 typedef const value_type* const_pointer;
470 typedef value_type& reference;
471 typedef const value_type& const_reference;
472 typedef size_t size_type;
473 typedef ptrdiff_t difference_type;
474 typedef _Alloc allocator_type;
477 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
478 { return *static_cast<_Node_allocator*>(&this->_M_impl); }
480 const _Node_allocator&
481 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
482 { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
485 get_allocator() const _GLIBCXX_NOEXCEPT
486 { return allocator_type(_M_get_Node_allocator()); }
491 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
494 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
495 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
497 #if __cplusplus < 201103L
499 _M_construct_node(_Link_type __node, const value_type& __x)
502 { get_allocator().construct(__node->_M_valptr(), __x); }
506 __throw_exception_again;
511 _M_create_node(const value_type& __x)
513 _Link_type __tmp = _M_get_node();
514 _M_construct_node(__tmp, __x);
519 _M_destroy_node(_Link_type __p)
520 { get_allocator().destroy(__p->_M_valptr()); }
522 template<typename... _Args>
524 _M_construct_node(_Link_type __node, _Args&&... __args)
528 ::new(__node) _Rb_tree_node<_Val>;
529 _Alloc_traits::construct(_M_get_Node_allocator(),
531 std::forward<_Args>(__args)...);
535 __node->~_Rb_tree_node<_Val>();
537 __throw_exception_again;
541 template<typename... _Args>
543 _M_create_node(_Args&&... __args)
545 _Link_type __tmp = _M_get_node();
546 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
551 _M_destroy_node(_Link_type __p) noexcept
553 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
554 __p->~_Rb_tree_node<_Val>();
559 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
561 _M_destroy_node(__p);
565 template<typename _NodeGen>
567 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
569 _Link_type __tmp = __node_gen(*__x->_M_valptr());
570 __tmp->_M_color = __x->_M_color;
577 // Unused _Is_pod_comparator is kept as it is part of mangled name.
578 template<typename _Key_compare,
579 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
580 struct _Rb_tree_impl : public _Node_allocator
582 _Key_compare _M_key_compare;
583 _Rb_tree_node_base _M_header;
584 size_type _M_node_count; // Keeps track of size of tree.
587 : _Node_allocator(), _M_key_compare(), _M_header(),
591 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
592 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
596 #if __cplusplus >= 201103L
597 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
598 : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
599 _M_header(), _M_node_count(0)
606 this->_M_header._M_parent = 0;
607 this->_M_header._M_left = &this->_M_header;
608 this->_M_header._M_right = &this->_M_header;
609 this->_M_node_count = 0;
616 this->_M_header._M_color = _S_red;
617 this->_M_header._M_parent = 0;
618 this->_M_header._M_left = &this->_M_header;
619 this->_M_header._M_right = &this->_M_header;
623 _Rb_tree_impl<_Compare> _M_impl;
627 _M_root() _GLIBCXX_NOEXCEPT
628 { return this->_M_impl._M_header._M_parent; }
631 _M_root() const _GLIBCXX_NOEXCEPT
632 { return this->_M_impl._M_header._M_parent; }
635 _M_leftmost() _GLIBCXX_NOEXCEPT
636 { return this->_M_impl._M_header._M_left; }
639 _M_leftmost() const _GLIBCXX_NOEXCEPT
640 { return this->_M_impl._M_header._M_left; }
643 _M_rightmost() _GLIBCXX_NOEXCEPT
644 { return this->_M_impl._M_header._M_right; }
647 _M_rightmost() const _GLIBCXX_NOEXCEPT
648 { return this->_M_impl._M_header._M_right; }
651 _M_begin() _GLIBCXX_NOEXCEPT
652 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
655 _M_begin() const _GLIBCXX_NOEXCEPT
657 return static_cast<_Const_Link_type>
658 (this->_M_impl._M_header._M_parent);
662 _M_end() _GLIBCXX_NOEXCEPT
663 { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
666 _M_end() const _GLIBCXX_NOEXCEPT
667 { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
669 static const_reference
670 _S_value(_Const_Link_type __x)
671 { return *__x->_M_valptr(); }
674 _S_key(_Const_Link_type __x)
675 { return _KeyOfValue()(_S_value(__x)); }
678 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
679 { return static_cast<_Link_type>(__x->_M_left); }
681 static _Const_Link_type
682 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
683 { return static_cast<_Const_Link_type>(__x->_M_left); }
686 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
687 { return static_cast<_Link_type>(__x->_M_right); }
689 static _Const_Link_type
690 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
691 { return static_cast<_Const_Link_type>(__x->_M_right); }
693 static const_reference
694 _S_value(_Const_Base_ptr __x)
695 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
698 _S_key(_Const_Base_ptr __x)
699 { return _KeyOfValue()(_S_value(__x)); }
702 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
703 { return _Rb_tree_node_base::_S_minimum(__x); }
705 static _Const_Base_ptr
706 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
707 { return _Rb_tree_node_base::_S_minimum(__x); }
710 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
711 { return _Rb_tree_node_base::_S_maximum(__x); }
713 static _Const_Base_ptr
714 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
715 { return _Rb_tree_node_base::_S_maximum(__x); }
718 typedef _Rb_tree_iterator<value_type> iterator;
719 typedef _Rb_tree_const_iterator<value_type> const_iterator;
721 typedef std::reverse_iterator<iterator> reverse_iterator;
722 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
725 pair<_Base_ptr, _Base_ptr>
726 _M_get_insert_unique_pos(const key_type& __k);
728 pair<_Base_ptr, _Base_ptr>
729 _M_get_insert_equal_pos(const key_type& __k);
731 pair<_Base_ptr, _Base_ptr>
732 _M_get_insert_hint_unique_pos(const_iterator __pos,
733 const key_type& __k);
735 pair<_Base_ptr, _Base_ptr>
736 _M_get_insert_hint_equal_pos(const_iterator __pos,
737 const key_type& __k);
739 #if __cplusplus >= 201103L
740 template<typename _Arg, typename _NodeGen>
742 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
745 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
747 template<typename _Arg>
749 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
751 template<typename _Arg>
753 _M_insert_equal_lower(_Arg&& __x);
756 _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
759 _M_insert_equal_lower_node(_Link_type __z);
761 template<typename _NodeGen>
763 _M_insert_(_Base_ptr __x, _Base_ptr __y,
764 const value_type& __v, _NodeGen&);
766 // _GLIBCXX_RESOLVE_LIB_DEFECTS
767 // 233. Insertion hints in associative containers.
769 _M_insert_lower(_Base_ptr __y, const value_type& __v);
772 _M_insert_equal_lower(const value_type& __x);
775 template<typename _NodeGen>
777 _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen&);
780 _M_copy(_Const_Link_type __x, _Link_type __p)
782 _Alloc_node __an(*this);
783 return _M_copy(__x, __p, __an);
787 _M_erase(_Link_type __x);
790 _M_lower_bound(_Link_type __x, _Link_type __y,
794 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
795 const _Key& __k) const;
798 _M_upper_bound(_Link_type __x, _Link_type __y,
802 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
803 const _Key& __k) const;
806 // allocation/deallocation
809 _Rb_tree(const _Compare& __comp,
810 const allocator_type& __a = allocator_type())
811 : _M_impl(__comp, _Node_allocator(__a)) { }
813 _Rb_tree(const _Rb_tree& __x)
814 : _M_impl(__x._M_impl._M_key_compare,
815 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
817 if (__x._M_root() != 0)
819 _M_root() = _M_copy(__x._M_begin(), _M_end());
820 _M_leftmost() = _S_minimum(_M_root());
821 _M_rightmost() = _S_maximum(_M_root());
822 _M_impl._M_node_count = __x._M_impl._M_node_count;
826 #if __cplusplus >= 201103L
827 _Rb_tree(const allocator_type& __a)
828 : _M_impl(_Compare(), _Node_allocator(__a))
831 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
832 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
834 if (__x._M_root() != nullptr)
836 _M_root() = _M_copy(__x._M_begin(), _M_end());
837 _M_leftmost() = _S_minimum(_M_root());
838 _M_rightmost() = _S_maximum(_M_root());
839 _M_impl._M_node_count = __x._M_impl._M_node_count;
843 _Rb_tree(_Rb_tree&& __x)
844 : _M_impl(__x._M_impl._M_key_compare,
845 std::move(__x._M_get_Node_allocator()))
847 if (__x._M_root() != 0)
848 _M_move_data(__x, std::true_type());
851 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
852 : _Rb_tree(std::move(__x), _Node_allocator(__a))
855 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
858 ~_Rb_tree() _GLIBCXX_NOEXCEPT
859 { _M_erase(_M_begin()); }
862 operator=(const _Rb_tree& __x);
867 { return _M_impl._M_key_compare; }
870 begin() _GLIBCXX_NOEXCEPT
871 { return iterator(this->_M_impl._M_header._M_left); }
874 begin() const _GLIBCXX_NOEXCEPT
875 { return const_iterator(this->_M_impl._M_header._M_left); }
878 end() _GLIBCXX_NOEXCEPT
879 { return iterator(&this->_M_impl._M_header); }
882 end() const _GLIBCXX_NOEXCEPT
883 { return const_iterator(&this->_M_impl._M_header); }
886 rbegin() _GLIBCXX_NOEXCEPT
887 { return reverse_iterator(end()); }
889 const_reverse_iterator
890 rbegin() const _GLIBCXX_NOEXCEPT
891 { return const_reverse_iterator(end()); }
894 rend() _GLIBCXX_NOEXCEPT
895 { return reverse_iterator(begin()); }
897 const_reverse_iterator
898 rend() const _GLIBCXX_NOEXCEPT
899 { return const_reverse_iterator(begin()); }
902 empty() const _GLIBCXX_NOEXCEPT
903 { return _M_impl._M_node_count == 0; }
906 size() const _GLIBCXX_NOEXCEPT
907 { return _M_impl._M_node_count; }
910 max_size() const _GLIBCXX_NOEXCEPT
911 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
914 #if __cplusplus >= 201103L
915 swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap());
921 #if __cplusplus >= 201103L
922 template<typename _Arg>
924 _M_insert_unique(_Arg&& __x);
926 template<typename _Arg>
928 _M_insert_equal(_Arg&& __x);
930 template<typename _Arg, typename _NodeGen>
932 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
934 template<typename _Arg>
936 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
938 _Alloc_node __an(*this);
939 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
942 template<typename _Arg, typename _NodeGen>
944 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
946 template<typename _Arg>
948 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
950 _Alloc_node __an(*this);
951 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
954 template<typename... _Args>
956 _M_emplace_unique(_Args&&... __args);
958 template<typename... _Args>
960 _M_emplace_equal(_Args&&... __args);
962 template<typename... _Args>
964 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
966 template<typename... _Args>
968 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
971 _M_insert_unique(const value_type& __x);
974 _M_insert_equal(const value_type& __x);
976 template<typename _NodeGen>
978 _M_insert_unique_(const_iterator __pos, const value_type& __x,
982 _M_insert_unique_(const_iterator __pos, const value_type& __x)
984 _Alloc_node __an(*this);
985 return _M_insert_unique_(__pos, __x, __an);
988 template<typename _NodeGen>
990 _M_insert_equal_(const_iterator __pos, const value_type& __x,
993 _M_insert_equal_(const_iterator __pos, const value_type& __x)
995 _Alloc_node __an(*this);
996 return _M_insert_equal_(__pos, __x, __an);
1000 template<typename _InputIterator>
1002 _M_insert_unique(_InputIterator __first, _InputIterator __last);
1004 template<typename _InputIterator>
1006 _M_insert_equal(_InputIterator __first, _InputIterator __last);
1010 _M_erase_aux(const_iterator __position);
1013 _M_erase_aux(const_iterator __first, const_iterator __last);
1016 #if __cplusplus >= 201103L
1017 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1018 // DR 130. Associative erase should return an iterator.
1019 _GLIBCXX_ABI_TAG_CXX11
1021 erase(const_iterator __position)
1023 const_iterator __result = __position;
1025 _M_erase_aux(__position);
1026 return __result._M_const_cast();
1030 _GLIBCXX_ABI_TAG_CXX11
1032 erase(iterator __position)
1034 iterator __result = __position;
1036 _M_erase_aux(__position);
1041 erase(iterator __position)
1042 { _M_erase_aux(__position); }
1045 erase(const_iterator __position)
1046 { _M_erase_aux(__position); }
1049 erase(const key_type& __x);
1051 #if __cplusplus >= 201103L
1052 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1053 // DR 130. Associative erase should return an iterator.
1054 _GLIBCXX_ABI_TAG_CXX11
1056 erase(const_iterator __first, const_iterator __last)
1058 _M_erase_aux(__first, __last);
1059 return __last._M_const_cast();
1063 erase(iterator __first, iterator __last)
1064 { _M_erase_aux(__first, __last); }
1067 erase(const_iterator __first, const_iterator __last)
1068 { _M_erase_aux(__first, __last); }
1071 erase(const key_type* __first, const key_type* __last);
1074 clear() _GLIBCXX_NOEXCEPT
1076 _M_erase(_M_begin());
1082 find(const key_type& __k);
1085 find(const key_type& __k) const;
1088 count(const key_type& __k) const;
1091 lower_bound(const key_type& __k)
1092 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1095 lower_bound(const key_type& __k) const
1096 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1099 upper_bound(const key_type& __k)
1100 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1103 upper_bound(const key_type& __k) const
1104 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1106 pair<iterator, iterator>
1107 equal_range(const key_type& __k);
1109 pair<const_iterator, const_iterator>
1110 equal_range(const key_type& __k) const;
1112 #if __cplusplus > 201103L
1113 template<typename _Cmp, typename _Kt, typename = __void_t<>>
1114 struct __is_transparent { };
1116 template<typename _Cmp, typename _Kt>
1118 __is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>>
1119 { typedef void type; };
1121 static auto _S_iter(_Link_type __x) { return iterator(__x); }
1123 static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); }
1125 template<typename _Cmp, typename _Link, typename _Kt>
1127 _S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
1130 if (!__cmp(_S_key(__x), __k))
1131 __y = __x, __x = _S_left(__x);
1133 __x = _S_right(__x);
1134 return _S_iter(__y);
1137 template<typename _Cmp, typename _Link, typename _Kt>
1139 _S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
1142 if (__cmp(__k, _S_key(__x)))
1143 __y = __x, __x = _S_left(__x);
1145 __x = _S_right(__x);
1146 return _S_iter(__y);
1149 template<typename _Kt,
1150 typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1152 _M_find_tr(const _Kt& __k)
1154 auto& __cmp = _M_impl._M_key_compare;
1155 auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1156 return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
1160 template<typename _Kt,
1161 typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1163 _M_find_tr(const _Kt& __k) const
1165 auto& __cmp = _M_impl._M_key_compare;
1166 auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1167 return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
1171 template<typename _Kt,
1172 typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1174 _M_count_tr(const _Kt& __k) const
1176 auto __p = _M_equal_range_tr(__k);
1177 return std::distance(__p.first, __p.second);
1180 template<typename _Kt,
1181 typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1183 _M_lower_bound_tr(const _Kt& __k)
1185 auto& __cmp = _M_impl._M_key_compare;
1186 return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1189 template<typename _Kt,
1190 typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1192 _M_lower_bound_tr(const _Kt& __k) const
1194 auto& __cmp = _M_impl._M_key_compare;
1195 return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1198 template<typename _Kt,
1199 typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1201 _M_upper_bound_tr(const _Kt& __k)
1203 auto& __cmp = _M_impl._M_key_compare;
1204 return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1207 template<typename _Kt,
1208 typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1210 _M_upper_bound_tr(const _Kt& __k) const
1212 auto& __cmp = _M_impl._M_key_compare;
1213 return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1216 template<typename _Kt,
1217 typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1218 pair<iterator, iterator>
1219 _M_equal_range_tr(const _Kt& __k)
1221 auto __low = _M_lower_bound_tr(__k);
1222 auto __high = __low;
1223 auto& __cmp = _M_impl._M_key_compare;
1224 while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1226 return { __low, __high };
1229 template<typename _Kt,
1230 typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1231 pair<const_iterator, const_iterator>
1232 _M_equal_range_tr(const _Kt& __k) const
1234 auto __low = _M_lower_bound_tr(__k);
1235 auto __high = __low;
1236 auto& __cmp = _M_impl._M_key_compare;
1237 while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1239 return { __low, __high };
1245 __rb_verify() const;
1247 #if __cplusplus >= 201103L
1249 operator=(_Rb_tree&&)
1250 noexcept(_Alloc_traits::_S_nothrow_move()
1251 && is_nothrow_move_assignable<_Compare>::value);
1253 template<typename _Iterator>
1255 _M_assign_unique(_Iterator, _Iterator);
1257 template<typename _Iterator>
1259 _M_assign_equal(_Iterator, _Iterator);
1262 // Move elements from container with equal allocator.
1264 _M_move_data(_Rb_tree&, std::true_type);
1266 // Move elements from container with possibly non-equal allocator,
1267 // which might result in a copy not a move.
1269 _M_move_data(_Rb_tree&, std::false_type);
1271 // Move assignment from container with equal allocator.
1273 _M_move_assign(_Rb_tree&, std::true_type);
1275 // Move assignment from container with possibly non-equal allocator,
1276 // which might result in a copy not a move.
1278 _M_move_assign(_Rb_tree&, std::false_type);
1282 template<typename _Key, typename _Val, typename _KeyOfValue,
1283 typename _Compare, typename _Alloc>
1285 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1286 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1288 return __x.size() == __y.size()
1289 && std::equal(__x.begin(), __x.end(), __y.begin());
1292 template<typename _Key, typename _Val, typename _KeyOfValue,
1293 typename _Compare, typename _Alloc>
1295 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1296 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1298 return std::lexicographical_compare(__x.begin(), __x.end(),
1299 __y.begin(), __y.end());
1302 template<typename _Key, typename _Val, typename _KeyOfValue,
1303 typename _Compare, typename _Alloc>
1305 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1306 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1307 { return !(__x == __y); }
1309 template<typename _Key, typename _Val, typename _KeyOfValue,
1310 typename _Compare, typename _Alloc>
1312 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1313 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1314 { return __y < __x; }
1316 template<typename _Key, typename _Val, typename _KeyOfValue,
1317 typename _Compare, typename _Alloc>
1319 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1320 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1321 { return !(__y < __x); }
1323 template<typename _Key, typename _Val, typename _KeyOfValue,
1324 typename _Compare, typename _Alloc>
1326 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1327 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1328 { return !(__x < __y); }
1330 template<typename _Key, typename _Val, typename _KeyOfValue,
1331 typename _Compare, typename _Alloc>
1333 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1334 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1337 #if __cplusplus >= 201103L
1338 template<typename _Key, typename _Val, typename _KeyOfValue,
1339 typename _Compare, typename _Alloc>
1340 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1341 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1342 : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1344 using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
1345 if (__x._M_root() != nullptr)
1346 _M_move_data(__x, __eq());
1349 template<typename _Key, typename _Val, typename _KeyOfValue,
1350 typename _Compare, typename _Alloc>
1352 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1353 _M_move_data(_Rb_tree& __x, std::true_type)
1355 _M_root() = __x._M_root();
1356 _M_leftmost() = __x._M_leftmost();
1357 _M_rightmost() = __x._M_rightmost();
1358 _M_root()->_M_parent = _M_end();
1361 __x._M_leftmost() = __x._M_end();
1362 __x._M_rightmost() = __x._M_end();
1364 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
1365 __x._M_impl._M_node_count = 0;
1368 template<typename _Key, typename _Val, typename _KeyOfValue,
1369 typename _Compare, typename _Alloc>
1371 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1372 _M_move_data(_Rb_tree& __x, std::false_type)
1374 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1375 _M_move_data(__x, std::true_type());
1378 _Alloc_node __an(*this);
1380 [&__an](const value_type& __cval)
1382 auto& __val = const_cast<value_type&>(__cval);
1383 return __an(std::move_if_noexcept(__val));
1385 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1386 _M_leftmost() = _S_minimum(_M_root());
1387 _M_rightmost() = _S_maximum(_M_root());
1388 _M_impl._M_node_count = __x._M_impl._M_node_count;
1392 template<typename _Key, typename _Val, typename _KeyOfValue,
1393 typename _Compare, typename _Alloc>
1395 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1396 _M_move_assign(_Rb_tree& __x, true_type)
1399 if (__x._M_root() != nullptr)
1400 _M_move_data(__x, std::true_type());
1401 std::__alloc_on_move(_M_get_Node_allocator(),
1402 __x._M_get_Node_allocator());
1405 template<typename _Key, typename _Val, typename _KeyOfValue,
1406 typename _Compare, typename _Alloc>
1408 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1409 _M_move_assign(_Rb_tree& __x, false_type)
1411 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1412 return _M_move_assign(__x, true_type{});
1414 // Try to move each node reusing existing nodes and copying __x nodes
1416 _Reuse_or_alloc_node __roan(*this);
1418 if (__x._M_root() != nullptr)
1421 [&__roan](const value_type& __cval)
1423 auto& __val = const_cast<value_type&>(__cval);
1424 return __roan(std::move_if_noexcept(__val));
1426 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1427 _M_leftmost() = _S_minimum(_M_root());
1428 _M_rightmost() = _S_maximum(_M_root());
1429 _M_impl._M_node_count = __x._M_impl._M_node_count;
1434 template<typename _Key, typename _Val, typename _KeyOfValue,
1435 typename _Compare, typename _Alloc>
1436 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1437 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1438 operator=(_Rb_tree&& __x)
1439 noexcept(_Alloc_traits::_S_nothrow_move()
1440 && is_nothrow_move_assignable<_Compare>::value)
1442 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1443 constexpr bool __move_storage =
1444 _Alloc_traits::_S_propagate_on_move_assign()
1445 || _Alloc_traits::_S_always_equal();
1446 _M_move_assign(__x, __bool_constant<__move_storage>());
1450 template<typename _Key, typename _Val, typename _KeyOfValue,
1451 typename _Compare, typename _Alloc>
1452 template<typename _Iterator>
1454 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1455 _M_assign_unique(_Iterator __first, _Iterator __last)
1457 _Reuse_or_alloc_node __roan(*this);
1459 for (; __first != __last; ++__first)
1460 _M_insert_unique_(end(), *__first, __roan);
1463 template<typename _Key, typename _Val, typename _KeyOfValue,
1464 typename _Compare, typename _Alloc>
1465 template<typename _Iterator>
1467 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1468 _M_assign_equal(_Iterator __first, _Iterator __last)
1470 _Reuse_or_alloc_node __roan(*this);
1472 for (; __first != __last; ++__first)
1473 _M_insert_equal_(end(), *__first, __roan);
1477 template<typename _Key, typename _Val, typename _KeyOfValue,
1478 typename _Compare, typename _Alloc>
1479 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1480 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1481 operator=(const _Rb_tree& __x)
1485 // Note that _Key may be a constant type.
1486 #if __cplusplus >= 201103L
1487 if (_Alloc_traits::_S_propagate_on_copy_assign())
1489 auto& __this_alloc = this->_M_get_Node_allocator();
1490 auto& __that_alloc = __x._M_get_Node_allocator();
1491 if (!_Alloc_traits::_S_always_equal()
1492 && __this_alloc != __that_alloc)
1494 // Replacement allocator cannot free existing storage, we need
1495 // to erase nodes first.
1497 std::__alloc_on_copy(__this_alloc, __that_alloc);
1502 _Reuse_or_alloc_node __roan(*this);
1504 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1505 if (__x._M_root() != 0)
1507 _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
1508 _M_leftmost() = _S_minimum(_M_root());
1509 _M_rightmost() = _S_maximum(_M_root());
1510 _M_impl._M_node_count = __x._M_impl._M_node_count;
1517 template<typename _Key, typename _Val, typename _KeyOfValue,
1518 typename _Compare, typename _Alloc>
1519 #if __cplusplus >= 201103L
1520 template<typename _Arg, typename _NodeGen>
1522 template<typename _NodeGen>
1524 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1525 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1526 _M_insert_(_Base_ptr __x, _Base_ptr __p,
1527 #if __cplusplus >= 201103L
1532 _NodeGen& __node_gen)
1534 bool __insert_left = (__x != 0 || __p == _M_end()
1535 || _M_impl._M_key_compare(_KeyOfValue()(__v),
1538 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1540 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1541 this->_M_impl._M_header);
1542 ++_M_impl._M_node_count;
1543 return iterator(__z);
1546 template<typename _Key, typename _Val, typename _KeyOfValue,
1547 typename _Compare, typename _Alloc>
1548 #if __cplusplus >= 201103L
1549 template<typename _Arg>
1551 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1552 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1553 #if __cplusplus >= 201103L
1554 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1556 _M_insert_lower(_Base_ptr __p, const _Val& __v)
1559 bool __insert_left = (__p == _M_end()
1560 || !_M_impl._M_key_compare(_S_key(__p),
1561 _KeyOfValue()(__v)));
1563 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1565 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1566 this->_M_impl._M_header);
1567 ++_M_impl._M_node_count;
1568 return iterator(__z);
1571 template<typename _Key, typename _Val, typename _KeyOfValue,
1572 typename _Compare, typename _Alloc>
1573 #if __cplusplus >= 201103L
1574 template<typename _Arg>
1576 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1577 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1578 #if __cplusplus >= 201103L
1579 _M_insert_equal_lower(_Arg&& __v)
1581 _M_insert_equal_lower(const _Val& __v)
1584 _Link_type __x = _M_begin();
1585 _Link_type __y = _M_end();
1589 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1590 _S_left(__x) : _S_right(__x);
1592 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1595 template<typename _Key, typename _Val, typename _KoV,
1596 typename _Compare, typename _Alloc>
1597 template<typename _NodeGen>
1598 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1599 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1600 _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen& __node_gen)
1602 // Structural copy. __x and __p must be non-null.
1603 _Link_type __top = _M_clone_node(__x, __node_gen);
1604 __top->_M_parent = __p;
1609 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1615 _Link_type __y = _M_clone_node(__x, __node_gen);
1617 __y->_M_parent = __p;
1619 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1627 __throw_exception_again;
1632 template<typename _Key, typename _Val, typename _KeyOfValue,
1633 typename _Compare, typename _Alloc>
1635 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1636 _M_erase(_Link_type __x)
1638 // Erase without rebalancing.
1641 _M_erase(_S_right(__x));
1642 _Link_type __y = _S_left(__x);
1648 template<typename _Key, typename _Val, typename _KeyOfValue,
1649 typename _Compare, typename _Alloc>
1650 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1651 _Compare, _Alloc>::iterator
1652 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1653 _M_lower_bound(_Link_type __x, _Link_type __y,
1657 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1658 __y = __x, __x = _S_left(__x);
1660 __x = _S_right(__x);
1661 return iterator(__y);
1664 template<typename _Key, typename _Val, typename _KeyOfValue,
1665 typename _Compare, typename _Alloc>
1666 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1667 _Compare, _Alloc>::const_iterator
1668 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1669 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1670 const _Key& __k) const
1673 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1674 __y = __x, __x = _S_left(__x);
1676 __x = _S_right(__x);
1677 return const_iterator(__y);
1680 template<typename _Key, typename _Val, typename _KeyOfValue,
1681 typename _Compare, typename _Alloc>
1682 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1683 _Compare, _Alloc>::iterator
1684 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1685 _M_upper_bound(_Link_type __x, _Link_type __y,
1689 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1690 __y = __x, __x = _S_left(__x);
1692 __x = _S_right(__x);
1693 return iterator(__y);
1696 template<typename _Key, typename _Val, typename _KeyOfValue,
1697 typename _Compare, typename _Alloc>
1698 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1699 _Compare, _Alloc>::const_iterator
1700 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1701 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1702 const _Key& __k) const
1705 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1706 __y = __x, __x = _S_left(__x);
1708 __x = _S_right(__x);
1709 return const_iterator(__y);
1712 template<typename _Key, typename _Val, typename _KeyOfValue,
1713 typename _Compare, typename _Alloc>
1714 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1715 _Compare, _Alloc>::iterator,
1716 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1717 _Compare, _Alloc>::iterator>
1718 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1719 equal_range(const _Key& __k)
1721 _Link_type __x = _M_begin();
1722 _Link_type __y = _M_end();
1725 if (_M_impl._M_key_compare(_S_key(__x), __k))
1726 __x = _S_right(__x);
1727 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1728 __y = __x, __x = _S_left(__x);
1731 _Link_type __xu(__x), __yu(__y);
1732 __y = __x, __x = _S_left(__x);
1733 __xu = _S_right(__xu);
1734 return pair<iterator,
1735 iterator>(_M_lower_bound(__x, __y, __k),
1736 _M_upper_bound(__xu, __yu, __k));
1739 return pair<iterator, iterator>(iterator(__y),
1743 template<typename _Key, typename _Val, typename _KeyOfValue,
1744 typename _Compare, typename _Alloc>
1745 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1746 _Compare, _Alloc>::const_iterator,
1747 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1748 _Compare, _Alloc>::const_iterator>
1749 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1750 equal_range(const _Key& __k) const
1752 _Const_Link_type __x = _M_begin();
1753 _Const_Link_type __y = _M_end();
1756 if (_M_impl._M_key_compare(_S_key(__x), __k))
1757 __x = _S_right(__x);
1758 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1759 __y = __x, __x = _S_left(__x);
1762 _Const_Link_type __xu(__x), __yu(__y);
1763 __y = __x, __x = _S_left(__x);
1764 __xu = _S_right(__xu);
1765 return pair<const_iterator,
1766 const_iterator>(_M_lower_bound(__x, __y, __k),
1767 _M_upper_bound(__xu, __yu, __k));
1770 return pair<const_iterator, const_iterator>(const_iterator(__y),
1771 const_iterator(__y));
1774 template<typename _Key, typename _Val, typename _KeyOfValue,
1775 typename _Compare, typename _Alloc>
1777 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1778 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1779 #if __cplusplus >= 201103L
1780 noexcept(_Alloc_traits::_S_nothrow_swap())
1785 if (__t._M_root() != 0)
1787 _M_root() = __t._M_root();
1788 _M_leftmost() = __t._M_leftmost();
1789 _M_rightmost() = __t._M_rightmost();
1790 _M_root()->_M_parent = _M_end();
1791 _M_impl._M_node_count = __t._M_impl._M_node_count;
1793 __t._M_impl._M_reset();
1796 else if (__t._M_root() == 0)
1798 __t._M_root() = _M_root();
1799 __t._M_leftmost() = _M_leftmost();
1800 __t._M_rightmost() = _M_rightmost();
1801 __t._M_root()->_M_parent = __t._M_end();
1802 __t._M_impl._M_node_count = _M_impl._M_node_count;
1808 std::swap(_M_root(),__t._M_root());
1809 std::swap(_M_leftmost(),__t._M_leftmost());
1810 std::swap(_M_rightmost(),__t._M_rightmost());
1812 _M_root()->_M_parent = _M_end();
1813 __t._M_root()->_M_parent = __t._M_end();
1814 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1816 // No need to swap header's color as it does not change.
1817 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1819 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1820 __t._M_get_Node_allocator());
1823 template<typename _Key, typename _Val, typename _KeyOfValue,
1824 typename _Compare, typename _Alloc>
1825 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1826 _Compare, _Alloc>::_Base_ptr,
1827 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1828 _Compare, _Alloc>::_Base_ptr>
1829 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1830 _M_get_insert_unique_pos(const key_type& __k)
1832 typedef pair<_Base_ptr, _Base_ptr> _Res;
1833 _Link_type __x = _M_begin();
1834 _Link_type __y = _M_end();
1839 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1840 __x = __comp ? _S_left(__x) : _S_right(__x);
1842 iterator __j = iterator(__y);
1846 return _Res(__x, __y);
1850 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1851 return _Res(__x, __y);
1852 return _Res(__j._M_node, 0);
1855 template<typename _Key, typename _Val, typename _KeyOfValue,
1856 typename _Compare, typename _Alloc>
1857 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1858 _Compare, _Alloc>::_Base_ptr,
1859 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1860 _Compare, _Alloc>::_Base_ptr>
1861 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1862 _M_get_insert_equal_pos(const key_type& __k)
1864 typedef pair<_Base_ptr, _Base_ptr> _Res;
1865 _Link_type __x = _M_begin();
1866 _Link_type __y = _M_end();
1870 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1871 _S_left(__x) : _S_right(__x);
1873 return _Res(__x, __y);
1876 template<typename _Key, typename _Val, typename _KeyOfValue,
1877 typename _Compare, typename _Alloc>
1878 #if __cplusplus >= 201103L
1879 template<typename _Arg>
1881 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1882 _Compare, _Alloc>::iterator, bool>
1883 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1884 #if __cplusplus >= 201103L
1885 _M_insert_unique(_Arg&& __v)
1887 _M_insert_unique(const _Val& __v)
1890 typedef pair<iterator, bool> _Res;
1891 pair<_Base_ptr, _Base_ptr> __res
1892 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1896 _Alloc_node __an(*this);
1897 return _Res(_M_insert_(__res.first, __res.second,
1898 _GLIBCXX_FORWARD(_Arg, __v), __an),
1902 return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1905 template<typename _Key, typename _Val, typename _KeyOfValue,
1906 typename _Compare, typename _Alloc>
1907 #if __cplusplus >= 201103L
1908 template<typename _Arg>
1910 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1911 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1912 #if __cplusplus >= 201103L
1913 _M_insert_equal(_Arg&& __v)
1915 _M_insert_equal(const _Val& __v)
1918 pair<_Base_ptr, _Base_ptr> __res
1919 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1920 _Alloc_node __an(*this);
1921 return _M_insert_(__res.first, __res.second,
1922 _GLIBCXX_FORWARD(_Arg, __v), __an);
1925 template<typename _Key, typename _Val, typename _KeyOfValue,
1926 typename _Compare, typename _Alloc>
1927 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1928 _Compare, _Alloc>::_Base_ptr,
1929 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1930 _Compare, _Alloc>::_Base_ptr>
1931 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1932 _M_get_insert_hint_unique_pos(const_iterator __position,
1933 const key_type& __k)
1935 iterator __pos = __position._M_const_cast();
1936 typedef pair<_Base_ptr, _Base_ptr> _Res;
1939 if (__pos._M_node == _M_end())
1942 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1943 return _Res(0, _M_rightmost());
1945 return _M_get_insert_unique_pos(__k);
1947 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1949 // First, try before...
1950 iterator __before = __pos;
1951 if (__pos._M_node == _M_leftmost()) // begin()
1952 return _Res(_M_leftmost(), _M_leftmost());
1953 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1955 if (_S_right(__before._M_node) == 0)
1956 return _Res(0, __before._M_node);
1958 return _Res(__pos._M_node, __pos._M_node);
1961 return _M_get_insert_unique_pos(__k);
1963 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1965 // ... then try after.
1966 iterator __after = __pos;
1967 if (__pos._M_node == _M_rightmost())
1968 return _Res(0, _M_rightmost());
1969 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1971 if (_S_right(__pos._M_node) == 0)
1972 return _Res(0, __pos._M_node);
1974 return _Res(__after._M_node, __after._M_node);
1977 return _M_get_insert_unique_pos(__k);
1981 return _Res(__pos._M_node, 0);
1984 template<typename _Key, typename _Val, typename _KeyOfValue,
1985 typename _Compare, typename _Alloc>
1986 #if __cplusplus >= 201103L
1987 template<typename _Arg, typename _NodeGen>
1989 template<typename _NodeGen>
1991 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1992 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1993 _M_insert_unique_(const_iterator __position,
1994 #if __cplusplus >= 201103L
1999 _NodeGen& __node_gen)
2001 pair<_Base_ptr, _Base_ptr> __res
2002 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2005 return _M_insert_(__res.first, __res.second,
2006 _GLIBCXX_FORWARD(_Arg, __v),
2008 return iterator(static_cast<_Link_type>(__res.first));
2011 template<typename _Key, typename _Val, typename _KeyOfValue,
2012 typename _Compare, typename _Alloc>
2013 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2014 _Compare, _Alloc>::_Base_ptr,
2015 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2016 _Compare, _Alloc>::_Base_ptr>
2017 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2018 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
2020 iterator __pos = __position._M_const_cast();
2021 typedef pair<_Base_ptr, _Base_ptr> _Res;
2024 if (__pos._M_node == _M_end())
2027 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2028 return _Res(0, _M_rightmost());
2030 return _M_get_insert_equal_pos(__k);
2032 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2034 // First, try before...
2035 iterator __before = __pos;
2036 if (__pos._M_node == _M_leftmost()) // begin()
2037 return _Res(_M_leftmost(), _M_leftmost());
2038 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2040 if (_S_right(__before._M_node) == 0)
2041 return _Res(0, __before._M_node);
2043 return _Res(__pos._M_node, __pos._M_node);
2046 return _M_get_insert_equal_pos(__k);
2050 // ... then try after.
2051 iterator __after = __pos;
2052 if (__pos._M_node == _M_rightmost())
2053 return _Res(0, _M_rightmost());
2054 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2056 if (_S_right(__pos._M_node) == 0)
2057 return _Res(0, __pos._M_node);
2059 return _Res(__after._M_node, __after._M_node);
2066 template<typename _Key, typename _Val, typename _KeyOfValue,
2067 typename _Compare, typename _Alloc>
2068 #if __cplusplus >= 201103L
2069 template<typename _Arg, typename _NodeGen>
2071 template<typename _NodeGen>
2073 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2074 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2075 _M_insert_equal_(const_iterator __position,
2076 #if __cplusplus >= 201103L
2081 _NodeGen& __node_gen)
2083 pair<_Base_ptr, _Base_ptr> __res
2084 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2087 return _M_insert_(__res.first, __res.second,
2088 _GLIBCXX_FORWARD(_Arg, __v),
2091 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2094 #if __cplusplus >= 201103L
2095 template<typename _Key, typename _Val, typename _KeyOfValue,
2096 typename _Compare, typename _Alloc>
2097 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2098 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2099 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2101 bool __insert_left = (__x != 0 || __p == _M_end()
2102 || _M_impl._M_key_compare(_S_key(__z),
2105 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2106 this->_M_impl._M_header);
2107 ++_M_impl._M_node_count;
2108 return iterator(__z);
2111 template<typename _Key, typename _Val, typename _KeyOfValue,
2112 typename _Compare, typename _Alloc>
2113 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2114 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2115 _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2117 bool __insert_left = (__p == _M_end()
2118 || !_M_impl._M_key_compare(_S_key(__p),
2121 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2122 this->_M_impl._M_header);
2123 ++_M_impl._M_node_count;
2124 return iterator(__z);
2127 template<typename _Key, typename _Val, typename _KeyOfValue,
2128 typename _Compare, typename _Alloc>
2129 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2130 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2131 _M_insert_equal_lower_node(_Link_type __z)
2133 _Link_type __x = _M_begin();
2134 _Link_type __y = _M_end();
2138 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2139 _S_left(__x) : _S_right(__x);
2141 return _M_insert_lower_node(__y, __z);
2144 template<typename _Key, typename _Val, typename _KeyOfValue,
2145 typename _Compare, typename _Alloc>
2146 template<typename... _Args>
2147 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2148 _Compare, _Alloc>::iterator, bool>
2149 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2150 _M_emplace_unique(_Args&&... __args)
2152 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2156 typedef pair<iterator, bool> _Res;
2157 auto __res = _M_get_insert_unique_pos(_S_key(__z));
2159 return _Res(_M_insert_node(__res.first, __res.second, __z), true);
2162 return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
2167 __throw_exception_again;
2171 template<typename _Key, typename _Val, typename _KeyOfValue,
2172 typename _Compare, typename _Alloc>
2173 template<typename... _Args>
2174 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2175 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2176 _M_emplace_equal(_Args&&... __args)
2178 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2182 auto __res = _M_get_insert_equal_pos(_S_key(__z));
2183 return _M_insert_node(__res.first, __res.second, __z);
2188 __throw_exception_again;
2192 template<typename _Key, typename _Val, typename _KeyOfValue,
2193 typename _Compare, typename _Alloc>
2194 template<typename... _Args>
2195 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2196 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2197 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2199 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2203 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2206 return _M_insert_node(__res.first, __res.second, __z);
2209 return iterator(static_cast<_Link_type>(__res.first));
2214 __throw_exception_again;
2218 template<typename _Key, typename _Val, typename _KeyOfValue,
2219 typename _Compare, typename _Alloc>
2220 template<typename... _Args>
2221 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2222 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2223 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2225 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2229 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2232 return _M_insert_node(__res.first, __res.second, __z);
2234 return _M_insert_equal_lower_node(__z);
2239 __throw_exception_again;
2244 template<typename _Key, typename _Val, typename _KoV,
2245 typename _Cmp, typename _Alloc>
2248 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2249 _M_insert_unique(_II __first, _II __last)
2251 _Alloc_node __an(*this);
2252 for (; __first != __last; ++__first)
2253 _M_insert_unique_(end(), *__first, __an);
2256 template<typename _Key, typename _Val, typename _KoV,
2257 typename _Cmp, typename _Alloc>
2260 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2261 _M_insert_equal(_II __first, _II __last)
2263 _Alloc_node __an(*this);
2264 for (; __first != __last; ++__first)
2265 _M_insert_equal_(end(), *__first, __an);
2268 template<typename _Key, typename _Val, typename _KeyOfValue,
2269 typename _Compare, typename _Alloc>
2271 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2272 _M_erase_aux(const_iterator __position)
2275 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
2276 (const_cast<_Base_ptr>(__position._M_node),
2277 this->_M_impl._M_header));
2279 --_M_impl._M_node_count;
2282 template<typename _Key, typename _Val, typename _KeyOfValue,
2283 typename _Compare, typename _Alloc>
2285 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2286 _M_erase_aux(const_iterator __first, const_iterator __last)
2288 if (__first == begin() && __last == end())
2291 while (__first != __last)
2295 template<typename _Key, typename _Val, typename _KeyOfValue,
2296 typename _Compare, typename _Alloc>
2297 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2298 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2299 erase(const _Key& __x)
2301 pair<iterator, iterator> __p = equal_range(__x);
2302 const size_type __old_size = size();
2303 erase(__p.first, __p.second);
2304 return __old_size - size();
2307 template<typename _Key, typename _Val, typename _KeyOfValue,
2308 typename _Compare, typename _Alloc>
2310 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2311 erase(const _Key* __first, const _Key* __last)
2313 while (__first != __last)
2317 template<typename _Key, typename _Val, typename _KeyOfValue,
2318 typename _Compare, typename _Alloc>
2319 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2320 _Compare, _Alloc>::iterator
2321 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2322 find(const _Key& __k)
2324 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2325 return (__j == end()
2326 || _M_impl._M_key_compare(__k,
2327 _S_key(__j._M_node))) ? end() : __j;
2330 template<typename _Key, typename _Val, typename _KeyOfValue,
2331 typename _Compare, typename _Alloc>
2332 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2333 _Compare, _Alloc>::const_iterator
2334 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2335 find(const _Key& __k) const
2337 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2338 return (__j == end()
2339 || _M_impl._M_key_compare(__k,
2340 _S_key(__j._M_node))) ? end() : __j;
2343 template<typename _Key, typename _Val, typename _KeyOfValue,
2344 typename _Compare, typename _Alloc>
2345 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2346 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2347 count(const _Key& __k) const
2349 pair<const_iterator, const_iterator> __p = equal_range(__k);
2350 const size_type __n = std::distance(__p.first, __p.second);
2354 _GLIBCXX_PURE unsigned int
2355 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
2356 const _Rb_tree_node_base* __root) throw ();
2358 template<typename _Key, typename _Val, typename _KeyOfValue,
2359 typename _Compare, typename _Alloc>
2361 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
2363 if (_M_impl._M_node_count == 0 || begin() == end())
2364 return _M_impl._M_node_count == 0 && begin() == end()
2365 && this->_M_impl._M_header._M_left == _M_end()
2366 && this->_M_impl._M_header._M_right == _M_end();
2368 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2369 for (const_iterator __it = begin(); __it != end(); ++__it)
2371 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
2372 _Const_Link_type __L = _S_left(__x);
2373 _Const_Link_type __R = _S_right(__x);
2375 if (__x->_M_color == _S_red)
2376 if ((__L && __L->_M_color == _S_red)
2377 || (__R && __R->_M_color == _S_red))
2380 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2382 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2385 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2389 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2391 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2396 _GLIBCXX_END_NAMESPACE_VERSION