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