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