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