Line data Source code
1 : // Multimap implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2024 Free Software Foundation, Inc.
4 : //
5 : // This file is part of the GNU ISO C++ Library. This library is free
6 : // software; you can redistribute it and/or modify it under the
7 : // terms of the GNU General Public License as published by the
8 : // Free Software Foundation; either version 3, or (at your option)
9 : // any later version.
10 :
11 : // This library is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 :
16 : // Under Section 7 of GPL version 3, you are granted additional
17 : // permissions described in the GCC Runtime Library Exception, version
18 : // 3.1, as published by the Free Software Foundation.
19 :
20 : // You should have received a copy of the GNU General Public License and
21 : // a copy of the GCC Runtime Library Exception along with this program;
22 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : // <http://www.gnu.org/licenses/>.
24 :
25 : /*
26 : *
27 : * Copyright (c) 1994
28 : * Hewlett-Packard Company
29 : *
30 : * Permission to use, copy, modify, distribute and sell this software
31 : * and its documentation for any purpose is hereby granted without fee,
32 : * provided that the above copyright notice appear in all copies and
33 : * that both that copyright notice and this permission notice appear
34 : * in supporting documentation. Hewlett-Packard Company makes no
35 : * representations about the suitability of this software for any
36 : * purpose. It is provided "as is" without express or implied warranty.
37 : *
38 : *
39 : * Copyright (c) 1996,1997
40 : * Silicon Graphics Computer Systems, Inc.
41 : *
42 : * Permission to use, copy, modify, distribute and sell this software
43 : * and its documentation for any purpose is hereby granted without fee,
44 : * provided that the above copyright notice appear in all copies and
45 : * that both that copyright notice and this permission notice appear
46 : * in supporting documentation. Silicon Graphics makes no
47 : * representations about the suitability of this software for any
48 : * purpose. It is provided "as is" without express or implied warranty.
49 : */
50 :
51 : /** @file bits/stl_multimap.h
52 : * This is an internal header file, included by other library headers.
53 : * Do not attempt to use it directly. @headername{map}
54 : */
55 :
56 : #ifndef _STL_MULTIMAP_H
57 : #define _STL_MULTIMAP_H 1
58 :
59 : #include <bits/concept_check.h>
60 : #if __cplusplus >= 201103L
61 : #include <initializer_list>
62 : #endif
63 :
64 : namespace std _GLIBCXX_VISIBILITY(default)
65 : {
66 : _GLIBCXX_BEGIN_NAMESPACE_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 0 : ~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 */
|
