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
64namespace 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, typename = typename
542 std::enable_if<std::is_constructible<value_type,
543 _Pair&&>::value>::type>
544 iterator
545 insert(_Pair&& __x)
546 { return _M_t._M_insert_equal(std::forward<_Pair>(__x)); }
547#endif
548 // @}
549
550 /**
551 * @brief Inserts a std::pair into the %multimap.
552 * @param __position An iterator that serves as a hint as to where the
553 * pair should be inserted.
554 * @param __x Pair to be inserted (see std::make_pair for easy creation
555 * of pairs).
556 * @return An iterator that points to the inserted (key,value) pair.
557 *
558 * This function inserts a (key, value) pair into the %multimap.
559 * Contrary to a std::map the %multimap does not rely on unique keys and
560 * thus multiple pairs with the same key can be inserted.
561 * Note that the first parameter is only a hint and can potentially
562 * improve the performance of the insertion process. A bad hint would
563 * cause no gains in efficiency.
564 *
565 * For more on @a hinting, see:
566 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
567 *
568 * Insertion requires logarithmic time (if the hint is not taken).
569 * @{
570 */
571 iterator
572#if __cplusplus >= 201103L
573 insert(const_iterator __position, const value_type& __x)
574#else
575 insert(iterator __position, const value_type& __x)
576#endif
577 { return _M_t._M_insert_equal_(__position, __x); }
578
579#if __cplusplus >= 201103L
580 // _GLIBCXX_RESOLVE_LIB_DEFECTS
581 // 2354. Unnecessary copying when inserting into maps with braced-init
582 iterator
583 insert(const_iterator __position, value_type&& __x)
584 { return _M_t._M_insert_equal_(__position, std::move(__x)); }
585
586 template<typename _Pair, typename = typename
587 std::enable_if<std::is_constructible<value_type,
588 _Pair&&>::value>::type>
589 iterator
590 insert(const_iterator __position, _Pair&& __x)
591 { return _M_t._M_insert_equal_(__position,
592 std::forward<_Pair>(__x)); }
593#endif
594 // @}
595
596 /**
597 * @brief A template function that attempts to insert a range
598 * of elements.
599 * @param __first Iterator pointing to the start of the range to be
600 * inserted.
601 * @param __last Iterator pointing to the end of the range.
602 *
603 * Complexity similar to that of the range constructor.
604 */
605 template<typename _InputIterator>
606 void
607 insert(_InputIterator __first, _InputIterator __last)
608 { _M_t._M_insert_equal(__first, __last); }
609
610#if __cplusplus >= 201103L
611 /**
612 * @brief Attempts to insert a list of std::pairs into the %multimap.
613 * @param __l A std::initializer_list<value_type> of pairs to be
614 * inserted.
615 *
616 * Complexity similar to that of the range constructor.
617 */
618 void
619 insert(initializer_list<value_type> __l)
620 { this->insert(__l.begin(), __l.end()); }
621#endif
622
623#if __cplusplus > 201402L
624 /// Extract a node.
625 node_type
626 extract(const_iterator __pos)
627 {
628 __glibcxx_assert(__pos != end());
629 return _M_t.extract(__pos);
630 }
631
632 /// Extract a node.
633 node_type
634 extract(const key_type& __x)
635 { return _M_t.extract(__x); }
636
637 /// Re-insert an extracted node.
638 iterator
639 insert(node_type&& __nh)
640 { return _M_t._M_reinsert_node_equal(std::move(__nh)); }
641
642 /// Re-insert an extracted node.
643 iterator
644 insert(const_iterator __hint, node_type&& __nh)
645 { return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); }
646
647 template<typename, typename>
648 friend class _Rb_tree_merge_helper;
649
650 template<typename _C2>
651 void
652 merge(multimap<_Key, _Tp, _C2, _Alloc>& __source)
653 {
654 using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>;
655 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
656 }
657
658 template<typename _C2>
659 void
660 merge(multimap<_Key, _Tp, _C2, _Alloc>&& __source)
661 { merge(__source); }
662
663 template<typename _C2>
664 void
665 merge(map<_Key, _Tp, _C2, _Alloc>& __source)
666 {
667 using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>;
668 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
669 }
670
671 template<typename _C2>
672 void
673 merge(map<_Key, _Tp, _C2, _Alloc>&& __source)
674 { merge(__source); }
675#endif // C++17
676
677#if __cplusplus >= 201103L
678 // _GLIBCXX_RESOLVE_LIB_DEFECTS
679 // DR 130. Associative erase should return an iterator.
680 /**
681 * @brief Erases an element from a %multimap.
682 * @param __position An iterator pointing to the element to be erased.
683 * @return An iterator pointing to the element immediately following
684 * @a position prior to the element being erased. If no such
685 * element exists, end() is returned.
686 *
687 * This function erases an element, pointed to by the given iterator,
688 * from a %multimap. Note that this function only erases the element,
689 * and that if the element is itself a pointer, the pointed-to memory is
690 * not touched in any way. Managing the pointer is the user's
691 * responsibility.
692 *
693 * @{
694 */
695 iterator
696 erase(const_iterator __position)
697 { return _M_t.erase(__position); }
698
699 // LWG 2059.
700 _GLIBCXX_ABI_TAG_CXX11
701 iterator
702 erase(iterator __position)
703 { return _M_t.erase(__position); }
704 // @}
705#else
706 /**
707 * @brief Erases an element from a %multimap.
708 * @param __position An iterator pointing to the element to be erased.
709 *
710 * This function erases an element, pointed to by the given iterator,
711 * from a %multimap. Note that this function only erases the element,
712 * and that if the element is itself a pointer, the pointed-to memory is
713 * not touched in any way. Managing the pointer is the user's
714 * responsibility.
715 */
716 void
717 erase(iterator __position)
718 { _M_t.erase(__position); }
719#endif
720
721 /**
722 * @brief Erases elements according to the provided key.
723 * @param __x Key of element to be erased.
724 * @return The number of elements erased.
725 *
726 * This function erases all elements located by the given key from a
727 * %multimap.
728 * Note that this function only erases the element, and that if
729 * the element is itself a pointer, the pointed-to memory is not touched
730 * in any way. Managing the pointer is the user's responsibility.
731 */
732 size_type
733 erase(const key_type& __x)
734 { return _M_t.erase(__x); }
735
736#if __cplusplus >= 201103L
737 // _GLIBCXX_RESOLVE_LIB_DEFECTS
738 // DR 130. Associative erase should return an iterator.
739 /**
740 * @brief Erases a [first,last) range of elements from a %multimap.
741 * @param __first Iterator pointing to the start of the range to be
742 * erased.
743 * @param __last Iterator pointing to the end of the range to be
744 * erased .
745 * @return The iterator @a __last.
746 *
747 * This function erases a sequence of elements from a %multimap.
748 * Note that this function only erases the elements, and that if
749 * the elements themselves are pointers, the pointed-to memory is not
750 * touched in any way. Managing the pointer is the user's
751 * responsibility.
752 */
753 iterator
754 erase(const_iterator __first, const_iterator __last)
755 { return _M_t.erase(__first, __last); }
756#else
757 // _GLIBCXX_RESOLVE_LIB_DEFECTS
758 // DR 130. Associative erase should return an iterator.
759 /**
760 * @brief Erases a [first,last) range of elements from a %multimap.
761 * @param __first Iterator pointing to the start of the range to be
762 * erased.
763 * @param __last Iterator pointing to the end of the range to
764 * be erased.
765 *
766 * This function erases a sequence of elements from a %multimap.
767 * Note that this function only erases the elements, and that if
768 * the elements themselves are pointers, the pointed-to memory is not
769 * touched in any way. Managing the pointer is the user's
770 * responsibility.
771 */
772 void
773 erase(iterator __first, iterator __last)
774 { _M_t.erase(__first, __last); }
775#endif
776
777 /**
778 * @brief Swaps data with another %multimap.
779 * @param __x A %multimap of the same element and allocator types.
780 *
781 * This exchanges the elements between two multimaps in constant time.
782 * (It is only swapping a pointer, an integer, and an instance of
783 * the @c Compare type (which itself is often stateless and empty), so it
784 * should be quite fast.)
785 * Note that the global std::swap() function is specialized such that
786 * std::swap(m1,m2) will feed to this function.
787 *
788 * Whether the allocators are swapped depends on the allocator traits.
789 */
790 void
791 swap(multimap& __x)
792 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
793 { _M_t.swap(__x._M_t); }
794
795 /**
796 * Erases all elements in a %multimap. Note that this function only
797 * erases the elements, and that if the elements themselves are pointers,
798 * the pointed-to memory is not touched in any way. Managing the pointer
799 * is the user's responsibility.
800 */
801 void
802 clear() _GLIBCXX_NOEXCEPT
803 { _M_t.clear(); }
804
805 // observers
806 /**
807 * Returns the key comparison object out of which the %multimap
808 * was constructed.
809 */
810 key_compare
811 key_comp() const
812 { return _M_t.key_comp(); }
813
814 /**
815 * Returns a value comparison object, built from the key comparison
816 * object out of which the %multimap was constructed.
817 */
818 value_compare
819 value_comp() const
820 { return value_compare(_M_t.key_comp()); }
821
822 // multimap operations
823
824 //@{
825 /**
826 * @brief Tries to locate an element in a %multimap.
827 * @param __x Key of (key, value) pair to be located.
828 * @return Iterator pointing to sought-after element,
829 * or end() if not found.
830 *
831 * This function takes a key and tries to locate the element with which
832 * the key matches. If successful the function returns an iterator
833 * pointing to the sought after %pair. If unsuccessful it returns the
834 * past-the-end ( @c end() ) iterator.
835 */
836 iterator
837 find(const key_type& __x)
838 { return _M_t.find(__x); }
839
840#if __cplusplus > 201103L
841 template<typename _Kt>
842 auto
843 find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
844 { return _M_t._M_find_tr(__x); }
845#endif
846 //@}
847
848 //@{
849 /**
850 * @brief Tries to locate an element in a %multimap.
851 * @param __x Key of (key, value) pair to be located.
852 * @return Read-only (constant) iterator pointing to sought-after
853 * element, or end() if not found.
854 *
855 * This function takes a key and tries to locate the element with which
856 * the key matches. If successful the function returns a constant
857 * iterator pointing to the sought after %pair. If unsuccessful it
858 * returns the past-the-end ( @c end() ) iterator.
859 */
860 const_iterator
861 find(const key_type& __x) const
862 { return _M_t.find(__x); }
863
864#if __cplusplus > 201103L
865 template<typename _Kt>
866 auto
867 find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
868 { return _M_t._M_find_tr(__x); }
869#endif
870 //@}
871
872 //@{
873 /**
874 * @brief Finds the number of elements with given key.
875 * @param __x Key of (key, value) pairs to be located.
876 * @return Number of elements with specified key.
877 */
878 size_type
879 count(const key_type& __x) const
880 { return _M_t.count(__x); }
881
882#if __cplusplus > 201103L
883 template<typename _Kt>
884 auto
885 count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
886 { return _M_t._M_count_tr(__x); }
887#endif
888 //@}
889
890 //@{
891 /**
892 * @brief Finds the beginning of a subsequence matching given key.
893 * @param __x Key of (key, value) pair to be located.
894 * @return Iterator pointing to first element equal to or greater
895 * than key, or end().
896 *
897 * This function returns the first element of a subsequence of elements
898 * that matches the given key. If unsuccessful it returns an iterator
899 * pointing to the first element that has a greater value than given key
900 * or end() if no such element exists.
901 */
902 iterator
903 lower_bound(const key_type& __x)
904 { return _M_t.lower_bound(__x); }
905
906#if __cplusplus > 201103L
907 template<typename _Kt>
908 auto
909 lower_bound(const _Kt& __x)
910 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
911 { return iterator(_M_t._M_lower_bound_tr(__x)); }
912#endif
913 //@}
914
915 //@{
916 /**
917 * @brief Finds the beginning of a subsequence matching given key.
918 * @param __x Key of (key, value) pair to be located.
919 * @return Read-only (constant) iterator pointing to first element
920 * equal to or greater than key, or end().
921 *
922 * This function returns the first element of a subsequence of
923 * elements that matches the given key. If unsuccessful the
924 * iterator will point to the next greatest element or, if no
925 * such greater element exists, to end().
926 */
927 const_iterator
928 lower_bound(const key_type& __x) const
929 { return _M_t.lower_bound(__x); }
930
931#if __cplusplus > 201103L
932 template<typename _Kt>
933 auto
934 lower_bound(const _Kt& __x) const
935 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
936 { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
937#endif
938 //@}
939
940 //@{
941 /**
942 * @brief Finds the end of a subsequence matching given key.
943 * @param __x Key of (key, value) pair to be located.
944 * @return Iterator pointing to the first element
945 * greater than key, or end().
946 */
947 iterator
948 upper_bound(const key_type& __x)
949 { return _M_t.upper_bound(__x); }
950
951#if __cplusplus > 201103L
952 template<typename _Kt>
953 auto
954 upper_bound(const _Kt& __x)
955 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
956 { return iterator(_M_t._M_upper_bound_tr(__x)); }
957#endif
958 //@}
959
960 //@{
961 /**
962 * @brief Finds the end of a subsequence matching given key.
963 * @param __x Key of (key, value) pair to be located.
964 * @return Read-only (constant) iterator pointing to first iterator
965 * greater than key, or end().
966 */
967 const_iterator
968 upper_bound(const key_type& __x) const
969 { return _M_t.upper_bound(__x); }
970
971#if __cplusplus > 201103L
972 template<typename _Kt>
973 auto
974 upper_bound(const _Kt& __x) const
975 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
976 { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
977#endif
978 //@}
979
980 //@{
981 /**
982 * @brief Finds a subsequence matching given key.
983 * @param __x Key of (key, value) pairs to be located.
984 * @return Pair of iterators that possibly points to the subsequence
985 * matching given key.
986 *
987 * This function is equivalent to
988 * @code
989 * std::make_pair(c.lower_bound(val),
990 * c.upper_bound(val))
991 * @endcode
992 * (but is faster than making the calls separately).
993 */
994 std::pair<iterator, iterator>
995 equal_range(const key_type& __x)
996 { return _M_t.equal_range(__x); }
997
998#if __cplusplus > 201103L
999 template<typename _Kt>
1000 auto
1001 equal_range(const _Kt& __x)
1002 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
1003 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
1004#endif
1005 //@}
1006
1007 //@{
1008 /**
1009 * @brief Finds a subsequence matching given key.
1010 * @param __x Key of (key, value) pairs to be located.
1011 * @return Pair of read-only (constant) iterators that possibly points
1012 * to the subsequence matching given key.
1013 *
1014 * This function is equivalent to
1015 * @code
1016 * std::make_pair(c.lower_bound(val),
1017 * c.upper_bound(val))
1018 * @endcode
1019 * (but is faster than making the calls separately).
1020 */
1021 std::pair<const_iterator, const_iterator>
1022 equal_range(const key_type& __x) const
1023 { return _M_t.equal_range(__x); }
1024
1025#if __cplusplus > 201103L
1026 template<typename _Kt>
1027 auto
1028 equal_range(const _Kt& __x) const
1029 -> decltype(pair<const_iterator, const_iterator>(
1030 _M_t._M_equal_range_tr(__x)))
1031 {
1032 return pair<const_iterator, const_iterator>(
1033 _M_t._M_equal_range_tr(__x));
1034 }
1035#endif
1036 //@}
1037
1038 template<typename _K1, typename _T1, typename _C1, typename _A1>
1039 friend bool
1040 operator==(const multimap<_K1, _T1, _C1, _A1>&,
1041 const multimap<_K1, _T1, _C1, _A1>&);
1042
1043 template<typename _K1, typename _T1, typename _C1, typename _A1>
1044 friend bool
1045 operator<(const multimap<_K1, _T1, _C1, _A1>&,
1046 const multimap<_K1, _T1, _C1, _A1>&);
1047 };
1048
1049 /**
1050 * @brief Multimap equality comparison.
1051 * @param __x A %multimap.
1052 * @param __y A %multimap of the same type as @a __x.
1053 * @return True iff the size and elements of the maps are equal.
1054 *
1055 * This is an equivalence relation. It is linear in the size of the
1056 * multimaps. Multimaps are considered equivalent if their sizes are equal,
1057 * and if corresponding elements compare equal.
1058 */
1059 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1060 inline bool
1061 operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1062 const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1063 { return __x._M_t == __y._M_t; }
1064
1065 /**
1066 * @brief Multimap ordering relation.
1067 * @param __x A %multimap.
1068 * @param __y A %multimap of the same type as @a __x.
1069 * @return True iff @a x is lexicographically less than @a y.
1070 *
1071 * This is a total ordering relation. It is linear in the size of the
1072 * multimaps. The elements must be comparable with @c <.
1073 *
1074 * See std::lexicographical_compare() for how the determination is made.
1075 */
1076 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1077 inline bool
1078 operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1079 const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1080 { return __x._M_t < __y._M_t; }
1081
1082 /// Based on operator==
1083 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1084 inline bool
1085 operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1086 const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1087 { return !(__x == __y); }
1088
1089 /// Based on operator<
1090 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1091 inline bool
1092 operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1093 const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1094 { return __y < __x; }
1095
1096 /// Based on operator<
1097 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1098 inline bool
1099 operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1100 const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1101 { return !(__y < __x); }
1102
1103 /// Based on operator<
1104 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1105 inline bool
1106 operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1107 const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1108 { return !(__x < __y); }
1109
1110 /// See std::multimap::swap().
1111 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1112 inline void
1113 swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1114 multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1115 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1116 { __x.swap(__y); }
1117
1118_GLIBCXX_END_NAMESPACE_CONTAINER
1119
1120#if __cplusplus > 201402L
1121_GLIBCXX_BEGIN_NAMESPACE_VERSION
1122 // Allow std::multimap access to internals of compatible maps.
1123 template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc,
1124 typename _Cmp2>
1125 struct
1126 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>,
1127 _Cmp2>
1128 {
1129 private:
1130 friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>;
1131
1132 static auto&
1133 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1134 { return __map._M_t; }
1135
1136 static auto&
1137 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1138 { return __map._M_t; }
1139 };
1140_GLIBCXX_END_NAMESPACE_VERSION
1141#endif // C++17
1142
1143} // namespace std
1144
1145#endif /* _STL_MULTIMAP_H */
1146