WebSVN – Kolibri OS – Blame – /contrib/toolchain/gcc/5x/libstdc++-v3/include/bits/stl_tree.h

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

Subversion Repositories Kolibri OS

(root)/contrib/toolchain/gcc/5x/libstdc++-v3/include/bits/stl_tree.h – Rev 6554