File Coverage

/usr/include/c++/5/bits/stl_tree.h
Criterion Covered Total %
statement 142 158 89.8
branch 36 88 40.9
condition n/a
subroutine n/a
pod n/a
total 178 246 72.3


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