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