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