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

1	// Multimap 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) 1994
28	* Hewlett-Packard Company
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. Hewlett-Packard Company 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) 1996,1997
40	* Silicon Graphics Computer Systems, Inc.
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. Silicon Graphics 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	/** @file bits/stl_multimap.h
52	* This is an internal header file, included by other library headers.
53	* Do not attempt to use it directly. @headername{map}
54	*/
55
56	#ifndef _STL_MULTIMAP_H
57	#define _STL_MULTIMAP_H 1
58
59	#include <bits/concept_check.h>
60	#if __cplusplus >= 201103L
61	#include <initializer_list>
62	#endif
63
64	namespace std _GLIBCXX_VISIBILITY(default)
65	{
66	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
67
68	template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
69	class map;
70
71	/**
72	* @brief A standard container made up of (key,value) pairs, which can be
73	* retrieved based on a key, in logarithmic time.
74	*
75	* @ingroup associative_containers
76	*
77	* @tparam _Key Type of key objects.
78	* @tparam _Tp Type of mapped objects.
79	* @tparam _Compare Comparison function object type, defaults to less<_Key>.
80	* @tparam _Alloc Allocator type, defaults to
81	* allocator<pair<const _Key, _Tp>.
82	*
83	* Meets the requirements of a <a href="tables.html#65">container</a>, a
84	* <a href="tables.html#66">reversible container</a>, and an
85	* <a href="tables.html#69">associative container</a> (using equivalent
86	* keys). For a @c multimap<Key,T> the key_type is Key, the mapped_type
87	* is T, and the value_type is std::pair<const Key,T>.
88	*
89	* Multimaps support bidirectional iterators.
90	*
91	* The private tree data is declared exactly the same way for map and
92	* multimap; the distinction is made entirely in how the tree functions are
93	* called (_unique versus _equal, same as the standard).
94	*/
95	template <typename _Key, typename _Tp,
96	typename _Compare = std::less<_Key>,
97	typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
98	class multimap
99	{
100	public:
101	typedef _Key key_type;
102	typedef _Tp mapped_type;
103	typedef std::pair<const _Key, _Tp> value_type;
104	typedef _Compare key_compare;
105	typedef _Alloc allocator_type;
106
107	private:
108	#ifdef _GLIBCXX_CONCEPT_CHECKS
109	// concept requirements
110	typedef typename _Alloc::value_type _Alloc_value_type;
111	# if __cplusplus < 201103L
112	__glibcxx_class_requires(_Tp, _SGIAssignableConcept)
113	# endif
114	__glibcxx_class_requires4(_Compare, bool, _Key, _Key,
115	_BinaryFunctionConcept)
116	__glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
117	#endif
118
119	public:
120	class value_compare
121	: public std::binary_function<value_type, value_type, bool>
122	{
123	friend class multimap<_Key, _Tp, _Compare, _Alloc>;
124	protected:
125	_Compare comp;
126
127	value_compare(_Compare __c)
128	: comp(__c) { }
129
130	public:
131	bool operator()(const value_type& __x, const value_type& __y) const
132	{ return comp(__x.first, __y.first); }
133	};
134
135	private:
136	/// This turns a red-black tree into a [multi]map.
137	typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
138	rebind<value_type>::other _Pair_alloc_type;
139
140	typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
141	key_compare, _Pair_alloc_type> _Rep_type;
142	/// The actual tree structure.
143	_Rep_type _M_t;
144
145	typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
146
147	public:
148	// many of these are specified differently in ISO, but the following are
149	// "functionally equivalent"
150	typedef typename _Alloc_traits::pointer pointer;
151	typedef typename _Alloc_traits::const_pointer const_pointer;
152	typedef typename _Alloc_traits::reference reference;
153	typedef typename _Alloc_traits::const_reference const_reference;
154	typedef typename _Rep_type::iterator iterator;
155	typedef typename _Rep_type::const_iterator const_iterator;
156	typedef typename _Rep_type::size_type size_type;
157	typedef typename _Rep_type::difference_type difference_type;
158	typedef typename _Rep_type::reverse_iterator reverse_iterator;
159	typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
160
161	#if __cplusplus > 201402L
162	using node_type = typename _Rep_type::node_type;
163	#endif
164
165	// [23.3.2] construct/copy/destroy
166	// (get_allocator() is also listed in this section)
167
168	/**
169	* @brief Default constructor creates no elements.
170	*/
171	#if __cplusplus < 201103L
172	multimap() : _M_t() { }
173	#else
174	multimap() = default;
175	#endif
176
177	/**
178	* @brief Creates a %multimap with no elements.
179	* @param __comp A comparison object.
180	* @param __a An allocator object.
181	*/
182	explicit
183	multimap(const _Compare& __comp,
184	const allocator_type& __a = allocator_type())
185	: _M_t(__comp, _Pair_alloc_type(__a)) { }
186
187	/**
188	* @brief %Multimap copy constructor.
189	*
190	* Whether the allocator is copied depends on the allocator traits.
191	*/
192	#if __cplusplus < 201103L
193	multimap(const multimap& __x)
194	: _M_t(__x._M_t) { }
195	#else
196	multimap(const multimap&) = default;
197
198	/**
199	* @brief %Multimap move constructor.
200	*
201	* The newly-created %multimap contains the exact contents of the
202	* moved instance. The moved instance is a valid, but unspecified
203	* %multimap.
204	*/
205	multimap(multimap&&) = default;
206
207	/**
208	* @brief Builds a %multimap from an initializer_list.
209	* @param __l An initializer_list.
210	* @param __comp A comparison functor.
211	* @param __a An allocator object.
212	*
213	* Create a %multimap consisting of copies of the elements from
214	* the initializer_list. This is linear in N if the list is already
215	* sorted, and NlogN otherwise (where N is @a __l.size()).
216	*/
217	multimap(initializer_list<value_type> __l,
218	const _Compare& __comp = _Compare(),
219	const allocator_type& __a = allocator_type())
220	: _M_t(__comp, _Pair_alloc_type(__a))
221	{ _M_t._M_insert_equal(__l.begin(), __l.end()); }
222
223	/// Allocator-extended default constructor.
224	explicit
225	multimap(const allocator_type& __a)
226	: _M_t(_Compare(), _Pair_alloc_type(__a)) { }
227
228	/// Allocator-extended copy constructor.
229	multimap(const multimap& __m, const allocator_type& __a)
230	: _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
231
232	/// Allocator-extended move constructor.
233	multimap(multimap&& __m, const allocator_type& __a)
234	noexcept(is_nothrow_copy_constructible<_Compare>::value
235	&& _Alloc_traits::_S_always_equal())
236	: _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
237
238	/// Allocator-extended initialier-list constructor.
239	multimap(initializer_list<value_type> __l, const allocator_type& __a)
240	: _M_t(_Compare(), _Pair_alloc_type(__a))
241	{ _M_t._M_insert_equal(__l.begin(), __l.end()); }
242
243	/// Allocator-extended range constructor.
244	template<typename _InputIterator>
245	multimap(_InputIterator __first, _InputIterator __last,
246	const allocator_type& __a)
247	: _M_t(_Compare(), _Pair_alloc_type(__a))
248	{ _M_t._M_insert_equal(__first, __last); }
249	#endif
250
251	/**
252	* @brief Builds a %multimap from a range.
253	* @param __first An input iterator.
254	* @param __last An input iterator.
255	*
256	* Create a %multimap consisting of copies of the elements from
257	* [__first,__last). This is linear in N if the range is already sorted,
258	* and NlogN otherwise (where N is distance(__first,__last)).
259	*/
260	template<typename _InputIterator>
261	multimap(_InputIterator __first, _InputIterator __last)
262	: _M_t()
263	{ _M_t._M_insert_equal(__first, __last); }
264
265	/**
266	* @brief Builds a %multimap from a range.
267	* @param __first An input iterator.
268	* @param __last An input iterator.
269	* @param __comp A comparison functor.
270	* @param __a An allocator object.
271	*
272	* Create a %multimap consisting of copies of the elements from
273	* [__first,__last). This is linear in N if the range is already sorted,
274	* and NlogN otherwise (where N is distance(__first,__last)).
275	*/
276	template<typename _InputIterator>
277	multimap(_InputIterator __first, _InputIterator __last,
278	const _Compare& __comp,
279	const allocator_type& __a = allocator_type())
280	: _M_t(__comp, _Pair_alloc_type(__a))
281	{ _M_t._M_insert_equal(__first, __last); }
282
283	#if __cplusplus >= 201103L
284	/**
285	* The dtor only erases the elements, and note that if the elements
286	* themselves are pointers, the pointed-to memory is not touched in any
287	* way. Managing the pointer is the user's responsibility.
288	*/
289	~multimap() = default;
290	#endif
291
292	/**
293	* @brief %Multimap assignment operator.
294	*
295	* Whether the allocator is copied depends on the allocator traits.
296	*/
297	#if __cplusplus < 201103L
298	multimap&
299	operator=(const multimap& __x)
300	{
301	_M_t = __x._M_t;
302	return *this;
303	}
304	#else
305	multimap&
306	operator=(const multimap&) = default;
307
308	/// Move assignment operator.
309	multimap&
310	operator=(multimap&&) = default;
311
312	/**
313	* @brief %Multimap list assignment operator.
314	* @param __l An initializer_list.
315	*
316	* This function fills a %multimap with copies of the elements
317	* in the initializer list @a __l.
318	*
319	* Note that the assignment completely changes the %multimap and
320	* that the resulting %multimap's size is the same as the number
321	* of elements assigned.
322	*/
323	multimap&
324	operator=(initializer_list<value_type> __l)
325	{
326	_M_t._M_assign_equal(__l.begin(), __l.end());
327	return *this;
328	}
329	#endif
330
331	/// Get a copy of the memory allocation object.
332	allocator_type
333	get_allocator() const _GLIBCXX_NOEXCEPT
334	{ return allocator_type(_M_t.get_allocator()); }
335
336	// iterators
337	/**
338	* Returns a read/write iterator that points to the first pair in the
339	* %multimap. Iteration is done in ascending order according to the
340	* keys.
341	*/
342	iterator
343	begin() _GLIBCXX_NOEXCEPT
344	{ return _M_t.begin(); }
345
346	/**
347	* Returns a read-only (constant) iterator that points to the first pair
348	* in the %multimap. Iteration is done in ascending order according to
349	* the keys.
350	*/
351	const_iterator
352	begin() const _GLIBCXX_NOEXCEPT
353	{ return _M_t.begin(); }
354
355	/**
356	* Returns a read/write iterator that points one past the last pair in
357	* the %multimap. Iteration is done in ascending order according to the
358	* keys.
359	*/
360	iterator
361	end() _GLIBCXX_NOEXCEPT
362	{ return _M_t.end(); }
363
364	/**
365	* Returns a read-only (constant) iterator that points one past the last
366	* pair in the %multimap. Iteration is done in ascending order according
367	* to the keys.
368	*/
369	const_iterator
370	end() const _GLIBCXX_NOEXCEPT
371	{ return _M_t.end(); }
372
373	/**
374	* Returns a read/write reverse iterator that points to the last pair in
375	* the %multimap. Iteration is done in descending order according to the
376	* keys.
377	*/
378	reverse_iterator
379	rbegin() _GLIBCXX_NOEXCEPT
380	{ return _M_t.rbegin(); }
381
382	/**
383	* Returns a read-only (constant) reverse iterator that points to the
384	* last pair in the %multimap. Iteration is done in descending order
385	* according to the keys.
386	*/
387	const_reverse_iterator
388	rbegin() const _GLIBCXX_NOEXCEPT
389	{ return _M_t.rbegin(); }
390
391	/**
392	* Returns a read/write reverse iterator that points to one before the
393	* first pair in the %multimap. Iteration is done in descending order
394	* according to the keys.
395	*/
396	reverse_iterator
397	rend() _GLIBCXX_NOEXCEPT
398	{ return _M_t.rend(); }
399
400	/**
401	* Returns a read-only (constant) reverse iterator that points to one
402	* before the first pair in the %multimap. Iteration is done in
403	* descending order according to the keys.
404	*/
405	const_reverse_iterator
406	rend() const _GLIBCXX_NOEXCEPT
407	{ return _M_t.rend(); }
408
409	#if __cplusplus >= 201103L
410	/**
411	* Returns a read-only (constant) iterator that points to the first pair
412	* in the %multimap. Iteration is done in ascending order according to
413	* the keys.
414	*/
415	const_iterator
416	cbegin() const noexcept
417	{ return _M_t.begin(); }
418
419	/**
420	* Returns a read-only (constant) iterator that points one past the last
421	* pair in the %multimap. Iteration is done in ascending order according
422	* to the keys.
423	*/
424	const_iterator
425	cend() const noexcept
426	{ return _M_t.end(); }
427
428	/**
429	* Returns a read-only (constant) reverse iterator that points to the
430	* last pair in the %multimap. Iteration is done in descending order
431	* according to the keys.
432	*/
433	const_reverse_iterator
434	crbegin() const noexcept
435	{ return _M_t.rbegin(); }
436
437	/**
438	* Returns a read-only (constant) reverse iterator that points to one
439	* before the first pair in the %multimap. Iteration is done in
440	* descending order according to the keys.
441	*/
442	const_reverse_iterator
443	crend() const noexcept
444	{ return _M_t.rend(); }
445	#endif
446
447	// capacity
448	/** Returns true if the %multimap is empty. */
449	bool
450	empty() const _GLIBCXX_NOEXCEPT
451	{ return _M_t.empty(); }
452
453	/** Returns the size of the %multimap. */
454	size_type
455	size() const _GLIBCXX_NOEXCEPT
456	{ return _M_t.size(); }
457
458	/** Returns the maximum size of the %multimap. */
459	size_type
460	max_size() const _GLIBCXX_NOEXCEPT
461	{ return _M_t.max_size(); }
462
463	// modifiers
464	#if __cplusplus >= 201103L
465	/**
466	* @brief Build and insert a std::pair into the %multimap.
467	*
468	* @param __args Arguments used to generate a new pair instance (see
469	* std::piecewise_contruct for passing arguments to each
470	* part of the pair constructor).
471	*
472	* @return An iterator that points to the inserted (key,value) pair.
473	*
474	* This function builds and inserts a (key, value) %pair into the
475	* %multimap.
476	* Contrary to a std::map the %multimap does not rely on unique keys and
477	* thus multiple pairs with the same key can be inserted.
478	*
479	* Insertion requires logarithmic time.
480	*/
481	template<typename... _Args>
482	iterator
483	emplace(_Args&&... __args)
484	{ return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
485
486	/**
487	* @brief Builds and inserts a std::pair into the %multimap.
488	*
489	* @param __pos An iterator that serves as a hint as to where the pair
490	* should be inserted.
491	* @param __args Arguments used to generate a new pair instance (see
492	* std::piecewise_contruct for passing arguments to each
493	* part of the pair constructor).
494	* @return An iterator that points to the inserted (key,value) pair.
495	*
496	* This function inserts a (key, value) pair into the %multimap.
497	* Contrary to a std::map the %multimap does not rely on unique keys and
498	* thus multiple pairs with the same key can be inserted.
499	* Note that the first parameter is only a hint and can potentially
500	* improve the performance of the insertion process. A bad hint would
501	* cause no gains in efficiency.
502	*
503	* For more on @a hinting, see:
504	* https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
505	*
506	* Insertion requires logarithmic time (if the hint is not taken).
507	*/
508	template<typename... _Args>
509	iterator
510	emplace_hint(const_iterator __pos, _Args&&... __args)
511	{
512	return _M_t._M_emplace_hint_equal(__pos,
513	std::forward<_Args>(__args)...);
514	}
515	#endif
516
517	/**
518	* @brief Inserts a std::pair into the %multimap.
519	* @param __x Pair to be inserted (see std::make_pair for easy creation
520	* of pairs).
521	* @return An iterator that points to the inserted (key,value) pair.
522	*
523	* This function inserts a (key, value) pair into the %multimap.
524	* Contrary to a std::map the %multimap does not rely on unique keys and
525	* thus multiple pairs with the same key can be inserted.
526	*
527	* Insertion requires logarithmic time.
528	* @{
529	*/
530	iterator
531	insert(const value_type& __x)
532	{ return _M_t._M_insert_equal(__x); }
533
534	#if __cplusplus >= 201103L
535	// _GLIBCXX_RESOLVE_LIB_DEFECTS
536	// 2354. Unnecessary copying when inserting into maps with braced-init
537	iterator
538	insert(value_type&& __x)
539	{ return _M_t._M_insert_equal(std::move(__x)); }
540
541	template<typename _Pair>
542	__enable_if_t<is_constructible<value_type, _Pair>::value, iterator>
543	insert(_Pair&& __x)
544	{ return _M_t._M_emplace_equal(std::forward<_Pair>(__x)); }
545	#endif
546	// @}
547
548	/**
549	* @brief Inserts a std::pair into the %multimap.
550	* @param __position An iterator that serves as a hint as to where the
551	* pair should be inserted.
552	* @param __x Pair to be inserted (see std::make_pair for easy creation
553	* of pairs).
554	* @return An iterator that points to the inserted (key,value) pair.
555	*
556	* This function inserts a (key, value) pair into the %multimap.
557	* Contrary to a std::map the %multimap does not rely on unique keys and
558	* thus multiple pairs with the same key can be inserted.
559	* Note that the first parameter is only a hint and can potentially
560	* improve the performance of the insertion process. A bad hint would
561	* cause no gains in efficiency.
562	*
563	* For more on @a hinting, see:
564	* https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
565	*
566	* Insertion requires logarithmic time (if the hint is not taken).
567	* @{
568	*/
569	iterator
570	#if __cplusplus >= 201103L
571	insert(const_iterator __position, const value_type& __x)
572	#else
573	insert(iterator __position, const value_type& __x)
574	#endif
575	{ return _M_t._M_insert_equal_(__position, __x); }
576
577	#if __cplusplus >= 201103L
578	// _GLIBCXX_RESOLVE_LIB_DEFECTS
579	// 2354. Unnecessary copying when inserting into maps with braced-init
580	iterator
581	insert(const_iterator __position, value_type&& __x)
582	{ return _M_t._M_insert_equal_(__position, std::move(__x)); }
583
584	template<typename _Pair>
585	__enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
586	insert(const_iterator __position, _Pair&& __x)
587	{
588	return _M_t._M_emplace_hint_equal(__position,
589	std::forward<_Pair>(__x));
590	}
591	#endif
592	// @}
593
594	/**
595	* @brief A template function that attempts to insert a range
596	* of elements.
597	* @param __first Iterator pointing to the start of the range to be
598	* inserted.
599	* @param __last Iterator pointing to the end of the range.
600	*
601	* Complexity similar to that of the range constructor.
602	*/
603	template<typename _InputIterator>
604	void
605	insert(_InputIterator __first, _InputIterator __last)
606	{ _M_t._M_insert_equal(__first, __last); }
607
608	#if __cplusplus >= 201103L
609	/**
610	* @brief Attempts to insert a list of std::pairs into the %multimap.
611	* @param __l A std::initializer_list<value_type> of pairs to be
612	* inserted.
613	*
614	* Complexity similar to that of the range constructor.
615	*/
616	void
617	insert(initializer_list<value_type> __l)
618	{ this->insert(__l.begin(), __l.end()); }
619	#endif
620
621	#if __cplusplus > 201402L
622	/// Extract a node.
623	node_type
624	extract(const_iterator __pos)
625	{
626	__glibcxx_assert(__pos != end());
627	return _M_t.extract(__pos);
628	}
629
630	/// Extract a node.
631	node_type
632	extract(const key_type& __x)
633	{ return _M_t.extract(__x); }
634
635	/// Re-insert an extracted node.
636	iterator
637	insert(node_type&& __nh)
638	{ return _M_t._M_reinsert_node_equal(std::move(__nh)); }
639
640	/// Re-insert an extracted node.
641	iterator
642	insert(const_iterator __hint, node_type&& __nh)
643	{ return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); }
644
645	template<typename, typename>
646	friend class _Rb_tree_merge_helper;
647
648	template<typename _C2>
649	void
650	merge(multimap<_Key, _Tp, _C2, _Alloc>& __source)
651	{
652	using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>;
653	_M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
654	}
655
656	template<typename _C2>
657	void
658	merge(multimap<_Key, _Tp, _C2, _Alloc>&& __source)
659	{ merge(__source); }
660
661	template<typename _C2>
662	void
663	merge(map<_Key, _Tp, _C2, _Alloc>& __source)
664	{
665	using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>;
666	_M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
667	}
668
669	template<typename _C2>
670	void
671	merge(map<_Key, _Tp, _C2, _Alloc>&& __source)
672	{ merge(__source); }
673	#endif // C++17
674
675	#if __cplusplus >= 201103L
676	// _GLIBCXX_RESOLVE_LIB_DEFECTS
677	// DR 130. Associative erase should return an iterator.
678	/**
679	* @brief Erases an element from a %multimap.
680	* @param __position An iterator pointing to the element to be erased.
681	* @return An iterator pointing to the element immediately following
682	* @a position prior to the element being erased. If no such
683	* element exists, end() is returned.
684	*
685	* This function erases an element, pointed to by the given iterator,
686	* from a %multimap. Note that this function only erases the element,
687	* and that if the element is itself a pointer, the pointed-to memory is
688	* not touched in any way. Managing the pointer is the user's
689	* responsibility.
690	*
691	* @{
692	*/
693	iterator
694	erase(const_iterator __position)
695	{ return _M_t.erase(__position); }
696
697	// LWG 2059.
698	_GLIBCXX_ABI_TAG_CXX11
699	iterator
700	erase(iterator __position)
701	{ return _M_t.erase(__position); }
702	// @}
703	#else
704	/**
705	* @brief Erases an element from a %multimap.
706	* @param __position An iterator pointing to the element to be erased.
707	*
708	* This function erases an element, pointed to by the given iterator,
709	* from a %multimap. Note that this function only erases the element,
710	* and that if the element is itself a pointer, the pointed-to memory is
711	* not touched in any way. Managing the pointer is the user's
712	* responsibility.
713	*/
714	void
715	erase(iterator __position)
716	{ _M_t.erase(__position); }
717	#endif
718
719	/**
720	* @brief Erases elements according to the provided key.
721	* @param __x Key of element to be erased.
722	* @return The number of elements erased.
723	*
724	* This function erases all elements located by the given key from a
725	* %multimap.
726	* Note that this function only erases the element, and that if
727	* the element is itself a pointer, the pointed-to memory is not touched
728	* in any way. Managing the pointer is the user's responsibility.
729	*/
730	size_type
731	erase(const key_type& __x)
732	{ return _M_t.erase(__x); }
733
734	#if __cplusplus >= 201103L
735	// _GLIBCXX_RESOLVE_LIB_DEFECTS
736	// DR 130. Associative erase should return an iterator.
737	/**
738	* @brief Erases a [first,last) range of elements from a %multimap.
739	* @param __first Iterator pointing to the start of the range to be
740	* erased.
741	* @param __last Iterator pointing to the end of the range to be
742	* erased .
743	* @return The iterator @a __last.
744	*
745	* This function erases a sequence of elements from a %multimap.
746	* Note that this function only erases the elements, and that if
747	* the elements themselves are pointers, the pointed-to memory is not
748	* touched in any way. Managing the pointer is the user's
749	* responsibility.
750	*/
751	iterator
752	erase(const_iterator __first, const_iterator __last)
753	{ return _M_t.erase(__first, __last); }
754	#else
755	// _GLIBCXX_RESOLVE_LIB_DEFECTS
756	// DR 130. Associative erase should return an iterator.
757	/**
758	* @brief Erases a [first,last) range of elements from a %multimap.
759	* @param __first Iterator pointing to the start of the range to be
760	* erased.
761	* @param __last Iterator pointing to the end of the range to
762	* be erased.
763	*
764	* This function erases a sequence of elements from a %multimap.
765	* Note that this function only erases the elements, and that if
766	* the elements themselves are pointers, the pointed-to memory is not
767	* touched in any way. Managing the pointer is the user's
768	* responsibility.
769	*/
770	void
771	erase(iterator __first, iterator __last)
772	{ _M_t.erase(__first, __last); }
773	#endif
774
775	/**
776	* @brief Swaps data with another %multimap.
777	* @param __x A %multimap of the same element and allocator types.
778	*
779	* This exchanges the elements between two multimaps in constant time.
780	* (It is only swapping a pointer, an integer, and an instance of
781	* the @c Compare type (which itself is often stateless and empty), so it
782	* should be quite fast.)
783	* Note that the global std::swap() function is specialized such that
784	* std::swap(m1,m2) will feed to this function.
785	*
786	* Whether the allocators are swapped depends on the allocator traits.
787	*/
788	void
789	swap(multimap& __x)
790	_GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
791	{ _M_t.swap(__x._M_t); }
792
793	/**
794	* Erases all elements in a %multimap. Note that this function only
795	* erases the elements, and that if the elements themselves are pointers,
796	* the pointed-to memory is not touched in any way. Managing the pointer
797	* is the user's responsibility.
798	*/
799	void
800	clear() _GLIBCXX_NOEXCEPT
801	{ _M_t.clear(); }
802
803	// observers
804	/**
805	* Returns the key comparison object out of which the %multimap
806	* was constructed.
807	*/
808	key_compare
809	key_comp() const
810	{ return _M_t.key_comp(); }
811
812	/**
813	* Returns a value comparison object, built from the key comparison
814	* object out of which the %multimap was constructed.
815	*/
816	value_compare
817	value_comp() const
818	{ return value_compare(_M_t.key_comp()); }
819
820	// multimap operations
821
822	//@{
823	/**
824	* @brief Tries to locate an element in a %multimap.
825	* @param __x Key of (key, value) pair to be located.
826	* @return Iterator pointing to sought-after element,
827	* or end() if not found.
828	*
829	* This function takes a key and tries to locate the element with which
830	* the key matches. If successful the function returns an iterator
831	* pointing to the sought after %pair. If unsuccessful it returns the
832	* past-the-end ( @c end() ) iterator.
833	*/
834	iterator
835	find(const key_type& __x)
836	{ return _M_t.find(__x); }
837
838	#if __cplusplus > 201103L
839	template<typename _Kt>
840	auto
841	find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
842	{ return _M_t._M_find_tr(__x); }
843	#endif
844	//@}
845
846	//@{
847	/**
848	* @brief Tries to locate an element in a %multimap.
849	* @param __x Key of (key, value) pair to be located.
850	* @return Read-only (constant) iterator pointing to sought-after
851	* element, or end() if not found.
852	*
853	* This function takes a key and tries to locate the element with which
854	* the key matches. If successful the function returns a constant
855	* iterator pointing to the sought after %pair. If unsuccessful it
856	* returns the past-the-end ( @c end() ) iterator.
857	*/
858	const_iterator
859	find(const key_type& __x) const
860	{ return _M_t.find(__x); }
861
862	#if __cplusplus > 201103L
863	template<typename _Kt>
864	auto
865	find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
866	{ return _M_t._M_find_tr(__x); }
867	#endif
868	//@}
869
870	//@{
871	/**
872	* @brief Finds the number of elements with given key.
873	* @param __x Key of (key, value) pairs to be located.
874	* @return Number of elements with specified key.
875	*/
876	size_type
877	count(const key_type& __x) const
878	{ return _M_t.count(__x); }
879
880	#if __cplusplus > 201103L
881	template<typename _Kt>
882	auto
883	count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
884	{ return _M_t._M_count_tr(__x); }
885	#endif
886	//@}
887
888	//@{
889	/**
890	* @brief Finds the beginning of a subsequence matching given key.
891	* @param __x Key of (key, value) pair to be located.
892	* @return Iterator pointing to first element equal to or greater
893	* than key, or end().
894	*
895	* This function returns the first element of a subsequence of elements
896	* that matches the given key. If unsuccessful it returns an iterator
897	* pointing to the first element that has a greater value than given key
898	* or end() if no such element exists.
899	*/
900	iterator
901	lower_bound(const key_type& __x)
902	{ return _M_t.lower_bound(__x); }
903
904	#if __cplusplus > 201103L
905	template<typename _Kt>
906	auto
907	lower_bound(const _Kt& __x)
908	-> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
909	{ return iterator(_M_t._M_lower_bound_tr(__x)); }
910	#endif
911	//@}
912
913	//@{
914	/**
915	* @brief Finds the beginning of a subsequence matching given key.
916	* @param __x Key of (key, value) pair to be located.
917	* @return Read-only (constant) iterator pointing to first element
918	* equal to or greater than key, or end().
919	*
920	* This function returns the first element of a subsequence of
921	* elements that matches the given key. If unsuccessful the
922	* iterator will point to the next greatest element or, if no
923	* such greater element exists, to end().
924	*/
925	const_iterator
926	lower_bound(const key_type& __x) const
927	{ return _M_t.lower_bound(__x); }
928
929	#if __cplusplus > 201103L
930	template<typename _Kt>
931	auto
932	lower_bound(const _Kt& __x) const
933	-> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
934	{ return const_iterator(_M_t._M_lower_bound_tr(__x)); }
935	#endif
936	//@}
937
938	//@{
939	/**
940	* @brief Finds the end of a subsequence matching given key.
941	* @param __x Key of (key, value) pair to be located.
942	* @return Iterator pointing to the first element
943	* greater than key, or end().
944	*/
945	iterator
946	upper_bound(const key_type& __x)
947	{ return _M_t.upper_bound(__x); }
948
949	#if __cplusplus > 201103L
950	template<typename _Kt>
951	auto
952	upper_bound(const _Kt& __x)
953	-> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
954	{ return iterator(_M_t._M_upper_bound_tr(__x)); }
955	#endif
956	//@}
957
958	//@{
959	/**
960	* @brief Finds the end of a subsequence matching given key.
961	* @param __x Key of (key, value) pair to be located.
962	* @return Read-only (constant) iterator pointing to first iterator
963	* greater than key, or end().
964	*/
965	const_iterator
966	upper_bound(const key_type& __x) const
967	{ return _M_t.upper_bound(__x); }
968
969	#if __cplusplus > 201103L
970	template<typename _Kt>
971	auto
972	upper_bound(const _Kt& __x) const
973	-> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
974	{ return const_iterator(_M_t._M_upper_bound_tr(__x)); }
975	#endif
976	//@}
977
978	//@{
979	/**
980	* @brief Finds a subsequence matching given key.
981	* @param __x Key of (key, value) pairs to be located.
982	* @return Pair of iterators that possibly points to the subsequence
983	* matching given key.
984	*
985	* This function is equivalent to
986	* @code
987	* std::make_pair(c.lower_bound(val),
988	* c.upper_bound(val))
989	* @endcode
990	* (but is faster than making the calls separately).
991	*/
992	std::pair<iterator, iterator>
993	equal_range(const key_type& __x)
994	{ return _M_t.equal_range(__x); }
995
996	#if __cplusplus > 201103L
997	template<typename _Kt>
998	auto
999	equal_range(const _Kt& __x)
1000	-> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
1001	{ return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
1002	#endif
1003	//@}
1004
1005	//@{
1006	/**
1007	* @brief Finds a subsequence matching given key.
1008	* @param __x Key of (key, value) pairs to be located.
1009	* @return Pair of read-only (constant) iterators that possibly points
1010	* to the subsequence matching given key.
1011	*
1012	* This function is equivalent to
1013	* @code
1014	* std::make_pair(c.lower_bound(val),
1015	* c.upper_bound(val))
1016	* @endcode
1017	* (but is faster than making the calls separately).
1018	*/
1019	std::pair<const_iterator, const_iterator>
1020	equal_range(const key_type& __x) const
1021	{ return _M_t.equal_range(__x); }
1022
1023	#if __cplusplus > 201103L
1024	template<typename _Kt>
1025	auto
1026	equal_range(const _Kt& __x) const
1027	-> decltype(pair<const_iterator, const_iterator>(
1028	_M_t._M_equal_range_tr(__x)))
1029	{
1030	return pair<const_iterator, const_iterator>(
1031	_M_t._M_equal_range_tr(__x));
1032	}
1033	#endif
1034	//@}
1035
1036	template<typename _K1, typename _T1, typename _C1, typename _A1>
1037	friend bool
1038	operator==(const multimap<_K1, _T1, _C1, _A1>&,
1039	const multimap<_K1, _T1, _C1, _A1>&);
1040
1041	template<typename _K1, typename _T1, typename _C1, typename _A1>
1042	friend bool
1043	operator<(const multimap<_K1, _T1, _C1, _A1>&,
1044	const multimap<_K1, _T1, _C1, _A1>&);
1045	};
1046
1047	/**
1048	* @brief Multimap equality comparison.
1049	* @param __x A %multimap.
1050	* @param __y A %multimap of the same type as @a __x.
1051	* @return True iff the size and elements of the maps are equal.
1052	*
1053	* This is an equivalence relation. It is linear in the size of the
1054	* multimaps. Multimaps are considered equivalent if their sizes are equal,
1055	* and if corresponding elements compare equal.
1056	*/
1057	template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1058	inline bool
1059	operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1060	const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1061	{ return __x._M_t == __y._M_t; }
1062
1063	/**
1064	* @brief Multimap ordering relation.
1065	* @param __x A %multimap.
1066	* @param __y A %multimap of the same type as @a __x.
1067	* @return True iff @a x is lexicographically less than @a y.
1068	*
1069	* This is a total ordering relation. It is linear in the size of the
1070	* multimaps. The elements must be comparable with @c <.
1071	*
1072	* See std::lexicographical_compare() for how the determination is made.
1073	*/
1074	template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1075	inline bool
1076	operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1077	const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1078	{ return __x._M_t < __y._M_t; }
1079
1080	/// Based on operator==
1081	template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1082	inline bool
1083	operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1084	const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1085	{ return !(__x == __y); }
1086
1087	/// Based on operator<
1088	template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1089	inline bool
1090	operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1091	const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1092	{ return __y < __x; }
1093
1094	/// Based on operator<
1095	template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1096	inline bool
1097	operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1098	const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1099	{ return !(__y < __x); }
1100
1101	/// Based on operator<
1102	template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1103	inline bool
1104	operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1105	const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1106	{ return !(__x < __y); }
1107
1108	/// See std::multimap::swap().
1109	template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1110	inline void
1111	swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1112	multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1113	_GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1114	{ __x.swap(__y); }
1115
1116	_GLIBCXX_END_NAMESPACE_CONTAINER
1117
1118	#if __cplusplus > 201402L
1119	_GLIBCXX_BEGIN_NAMESPACE_VERSION
1120	// Allow std::multimap access to internals of compatible maps.
1121	template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc,
1122	typename _Cmp2>
1123	struct
1124	_Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>,
1125	_Cmp2>
1126	{
1127	private:
1128	friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>;
1129
1130	static auto&
1131	_S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1132	{ return __map._M_t; }
1133
1134	static auto&
1135	_S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1136	{ return __map._M_t; }
1137	};
1138	_GLIBCXX_END_NAMESPACE_VERSION
1139	#endif // C++17
1140
1141	} // namespace std
1142
1143	#endif /* _STL_MULTIMAP_H */
1144