stl_tree.h source code [include/c++/7/bits/stl

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