Line data Source code
1 : // Multimap implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2018 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 697 : 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_equal(__l.begin(), __l.end()); }
228 :
229 : /// Allocator-extended default constructor.
230 : explicit
231 : multimap(const allocator_type& __a)
232 : : _M_t(_Compare(), _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(_Compare(), _Pair_alloc_type(__a))
247 : { _M_t._M_insert_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(_Compare(), _Pair_alloc_type(__a))
254 : { _M_t._M_insert_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_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_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 697 : ~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 697 : begin() _GLIBCXX_NOEXCEPT
350 697 : { 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 6915437 : end() _GLIBCXX_NOEXCEPT
368 6915437 : { 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 0 : cbegin() const noexcept
423 0 : { 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 0 : cend() const noexcept
432 0 : { 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 : bool
456 : empty() const _GLIBCXX_NOEXCEPT
457 : { return _M_t.empty(); }
458 :
459 : /** Returns the size of the %multimap. */
460 : size_type
461 0 : size() const _GLIBCXX_NOEXCEPT
462 0 : { 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 6914740 : insert(_Pair&& __x)
550 6914740 : { 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_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 : //@{
895 : /**
896 : * @brief Finds the beginning of a subsequence matching given key.
897 : * @param __x Key of (key, value) pair to be located.
898 : * @return Iterator pointing to first element equal to or greater
899 : * than key, or end().
900 : *
901 : * This function returns the first element of a subsequence of elements
902 : * that matches the given key. If unsuccessful it returns an iterator
903 : * pointing to the first element that has a greater value than given key
904 : * or end() if no such element exists.
905 : */
906 : iterator
907 : lower_bound(const key_type& __x)
908 : { return _M_t.lower_bound(__x); }
909 :
910 : #if __cplusplus > 201103L
911 : template<typename _Kt>
912 : auto
913 : lower_bound(const _Kt& __x)
914 : -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
915 : { return iterator(_M_t._M_lower_bound_tr(__x)); }
916 : #endif
917 : //@}
918 :
919 : //@{
920 : /**
921 : * @brief Finds the beginning of a subsequence matching given key.
922 : * @param __x Key of (key, value) pair to be located.
923 : * @return Read-only (constant) iterator pointing to first element
924 : * equal to or greater than key, or end().
925 : *
926 : * This function returns the first element of a subsequence of
927 : * elements that matches the given key. If unsuccessful the
928 : * iterator will point to the next greatest element or, if no
929 : * such greater element exists, to end().
930 : */
931 : const_iterator
932 : lower_bound(const key_type& __x) const
933 : { return _M_t.lower_bound(__x); }
934 :
935 : #if __cplusplus > 201103L
936 : template<typename _Kt>
937 : auto
938 : lower_bound(const _Kt& __x) const
939 : -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
940 : { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
941 : #endif
942 : //@}
943 :
944 : //@{
945 : /**
946 : * @brief Finds the end of a subsequence matching given key.
947 : * @param __x Key of (key, value) pair to be located.
948 : * @return Iterator pointing to the first element
949 : * greater than key, or end().
950 : */
951 : iterator
952 : upper_bound(const key_type& __x)
953 : { return _M_t.upper_bound(__x); }
954 :
955 : #if __cplusplus > 201103L
956 : template<typename _Kt>
957 : auto
958 : upper_bound(const _Kt& __x)
959 : -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
960 : { return iterator(_M_t._M_upper_bound_tr(__x)); }
961 : #endif
962 : //@}
963 :
964 : //@{
965 : /**
966 : * @brief Finds the end of a subsequence matching given key.
967 : * @param __x Key of (key, value) pair to be located.
968 : * @return Read-only (constant) iterator pointing to first iterator
969 : * greater than key, or end().
970 : */
971 : const_iterator
972 : upper_bound(const key_type& __x) const
973 : { return _M_t.upper_bound(__x); }
974 :
975 : #if __cplusplus > 201103L
976 : template<typename _Kt>
977 : auto
978 : upper_bound(const _Kt& __x) const
979 : -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
980 : { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
981 : #endif
982 : //@}
983 :
984 : //@{
985 : /**
986 : * @brief Finds a subsequence matching given key.
987 : * @param __x Key of (key, value) pairs to be located.
988 : * @return Pair of iterators that possibly points to the subsequence
989 : * matching given key.
990 : *
991 : * This function is equivalent to
992 : * @code
993 : * std::make_pair(c.lower_bound(val),
994 : * c.upper_bound(val))
995 : * @endcode
996 : * (but is faster than making the calls separately).
997 : */
998 : std::pair<iterator, iterator>
999 : equal_range(const key_type& __x)
1000 : { return _M_t.equal_range(__x); }
1001 :
1002 : #if __cplusplus > 201103L
1003 : template<typename _Kt>
1004 : auto
1005 : equal_range(const _Kt& __x)
1006 : -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
1007 : { return pair<iterator, iterator>(_M_t._M_equal_range_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 read-only (constant) iterators that possibly points
1016 : * to the subsequence 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<const_iterator, const_iterator>
1026 : equal_range(const key_type& __x) const
1027 : { return _M_t.equal_range(__x); }
1028 :
1029 : #if __cplusplus > 201103L
1030 : template<typename _Kt>
1031 : auto
1032 : equal_range(const _Kt& __x) const
1033 : -> decltype(pair<const_iterator, const_iterator>(
1034 : _M_t._M_equal_range_tr(__x)))
1035 : {
1036 : return pair<const_iterator, const_iterator>(
1037 : _M_t._M_equal_range_tr(__x));
1038 : }
1039 : #endif
1040 : //@}
1041 :
1042 : template<typename _K1, typename _T1, typename _C1, typename _A1>
1043 : friend bool
1044 : operator==(const multimap<_K1, _T1, _C1, _A1>&,
1045 : const multimap<_K1, _T1, _C1, _A1>&);
1046 :
1047 : template<typename _K1, typename _T1, typename _C1, typename _A1>
1048 : friend bool
1049 : operator<(const multimap<_K1, _T1, _C1, _A1>&,
1050 : const multimap<_K1, _T1, _C1, _A1>&);
1051 : };
1052 :
1053 : #if __cpp_deduction_guides >= 201606
1054 :
1055 : template<typename _InputIterator,
1056 : typename _Compare = less<__iter_key_t<_InputIterator>>,
1057 : typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1058 : typename = _RequireInputIter<_InputIterator>,
1059 : typename = _RequireAllocator<_Allocator>>
1060 : multimap(_InputIterator, _InputIterator,
1061 : _Compare = _Compare(), _Allocator = _Allocator())
1062 : -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
1063 : _Compare, _Allocator>;
1064 :
1065 : template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
1066 : typename _Allocator = allocator<pair<const _Key, _Tp>>,
1067 : typename = _RequireAllocator<_Allocator>>
1068 : multimap(initializer_list<pair<_Key, _Tp>>,
1069 : _Compare = _Compare(), _Allocator = _Allocator())
1070 : -> multimap<_Key, _Tp, _Compare, _Allocator>;
1071 :
1072 : template<typename _InputIterator, typename _Allocator,
1073 : typename = _RequireInputIter<_InputIterator>,
1074 : typename = _RequireAllocator<_Allocator>>
1075 : multimap(_InputIterator, _InputIterator, _Allocator)
1076 : -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
1077 : less<__iter_key_t<_InputIterator>>, _Allocator>;
1078 :
1079 : template<typename _Key, typename _Tp, typename _Allocator,
1080 : typename = _RequireAllocator<_Allocator>>
1081 : multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1082 : -> multimap<_Key, _Tp, less<_Key>, _Allocator>;
1083 :
1084 : #endif
1085 :
1086 : /**
1087 : * @brief Multimap equality comparison.
1088 : * @param __x A %multimap.
1089 : * @param __y A %multimap of the same type as @a __x.
1090 : * @return True iff the size and elements of the maps are equal.
1091 : *
1092 : * This is an equivalence relation. It is linear in the size of the
1093 : * multimaps. Multimaps are considered equivalent if their sizes are equal,
1094 : * and if corresponding elements compare equal.
1095 : */
1096 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1097 : inline bool
1098 : operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1099 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1100 : { return __x._M_t == __y._M_t; }
1101 :
1102 : /**
1103 : * @brief Multimap ordering relation.
1104 : * @param __x A %multimap.
1105 : * @param __y A %multimap of the same type as @a __x.
1106 : * @return True iff @a x is lexicographically less than @a y.
1107 : *
1108 : * This is a total ordering relation. It is linear in the size of the
1109 : * multimaps. The elements must be comparable with @c <.
1110 : *
1111 : * See std::lexicographical_compare() for how the determination is made.
1112 : */
1113 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1114 : inline bool
1115 : operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1116 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1117 : { return __x._M_t < __y._M_t; }
1118 :
1119 : /// Based on operator==
1120 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1121 : inline bool
1122 : operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1123 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1124 : { return !(__x == __y); }
1125 :
1126 : /// Based on operator<
1127 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1128 : inline bool
1129 : operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1130 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1131 : { return __y < __x; }
1132 :
1133 : /// Based on operator<
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 !(__y < __x); }
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 : /// See std::multimap::swap().
1148 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1149 : inline void
1150 : swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1151 : multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1152 : _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1153 : { __x.swap(__y); }
1154 :
1155 : _GLIBCXX_END_NAMESPACE_CONTAINER
1156 :
1157 : #if __cplusplus > 201402L
1158 : // Allow std::multimap access to internals of compatible maps.
1159 : template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc,
1160 : typename _Cmp2>
1161 : struct
1162 : _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>,
1163 : _Cmp2>
1164 : {
1165 : private:
1166 : friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>;
1167 :
1168 : static auto&
1169 : _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1170 : { return __map._M_t; }
1171 :
1172 : static auto&
1173 : _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1174 : { return __map._M_t; }
1175 : };
1176 : #endif // C++17
1177 :
1178 : _GLIBCXX_END_NAMESPACE_VERSION
1179 : } // namespace std
1180 :
1181 : #endif /* _STL_MULTIMAP_H */
|
