Line data Source code
1 : // Multimap implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2013 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_CONTAINER
67 :
68 : /**
69 : * @brief A standard container made up of (key,value) pairs, which can be
70 : * retrieved based on a key, in logarithmic time.
71 : *
72 : * @ingroup associative_containers
73 : *
74 : * @tparam _Key Type of key objects.
75 : * @tparam _Tp Type of mapped objects.
76 : * @tparam _Compare Comparison function object type, defaults to less<_Key>.
77 : * @tparam _Alloc Allocator type, defaults to
78 : * allocator<pair<const _Key, _Tp>.
79 : *
80 : * Meets the requirements of a <a href="tables.html#65">container</a>, a
81 : * <a href="tables.html#66">reversible container</a>, and an
82 : * <a href="tables.html#69">associative container</a> (using equivalent
83 : * keys). For a @c multimap<Key,T> the key_type is Key, the mapped_type
84 : * is T, and the value_type is std::pair<const Key,T>.
85 : *
86 : * Multimaps support bidirectional iterators.
87 : *
88 : * The private tree data is declared exactly the same way for map and
89 : * multimap; the distinction is made entirely in how the tree functions are
90 : * called (*_unique versus *_equal, same as the standard).
91 : */
92 : template <typename _Key, typename _Tp,
93 : typename _Compare = std::less<_Key>,
94 : typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
95 24275 : class multimap
96 : {
97 : public:
98 : typedef _Key key_type;
99 : typedef _Tp mapped_type;
100 : typedef std::pair<const _Key, _Tp> value_type;
101 : typedef _Compare key_compare;
102 : typedef _Alloc allocator_type;
103 :
104 : private:
105 : // concept requirements
106 : typedef typename _Alloc::value_type _Alloc_value_type;
107 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
108 : __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
109 : _BinaryFunctionConcept)
110 : __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
111 :
112 : public:
113 : class value_compare
114 : : public std::binary_function<value_type, value_type, bool>
115 : {
116 : friend class multimap<_Key, _Tp, _Compare, _Alloc>;
117 : protected:
118 : _Compare comp;
119 :
120 : value_compare(_Compare __c)
121 : : comp(__c) { }
122 :
123 : public:
124 : bool operator()(const value_type& __x, const value_type& __y) const
125 : { return comp(__x.first, __y.first); }
126 : };
127 :
128 : private:
129 : /// This turns a red-black tree into a [multi]map.
130 : typedef typename _Alloc::template rebind<value_type>::other
131 : _Pair_alloc_type;
132 :
133 : typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
134 : key_compare, _Pair_alloc_type> _Rep_type;
135 : /// The actual tree structure.
136 : _Rep_type _M_t;
137 :
138 : public:
139 : // many of these are specified differently in ISO, but the following are
140 : // "functionally equivalent"
141 : typedef typename _Pair_alloc_type::pointer pointer;
142 : typedef typename _Pair_alloc_type::const_pointer const_pointer;
143 : typedef typename _Pair_alloc_type::reference reference;
144 : typedef typename _Pair_alloc_type::const_reference const_reference;
145 : typedef typename _Rep_type::iterator iterator;
146 : typedef typename _Rep_type::const_iterator const_iterator;
147 : typedef typename _Rep_type::size_type size_type;
148 : typedef typename _Rep_type::difference_type difference_type;
149 : typedef typename _Rep_type::reverse_iterator reverse_iterator;
150 : typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
151 :
152 : // [23.3.2] construct/copy/destroy
153 : // (get_allocator() is also listed in this section)
154 : /**
155 : * @brief Default constructor creates no elements.
156 : */
157 : multimap()
158 23852 : : _M_t() { }
159 :
160 : /**
161 : * @brief Creates a %multimap with no elements.
162 : * @param __comp A comparison object.
163 : * @param __a An allocator object.
164 : */
165 : explicit
166 : multimap(const _Compare& __comp,
167 : const allocator_type& __a = allocator_type())
168 : : _M_t(__comp, _Pair_alloc_type(__a)) { }
169 :
170 : /**
171 : * @brief %Multimap copy constructor.
172 : * @param __x A %multimap of identical element and allocator types.
173 : *
174 : * The newly-created %multimap uses a copy of the allocation object
175 : * used by @a __x.
176 : */
177 : multimap(const multimap& __x)
178 423 : : _M_t(__x._M_t) { }
179 :
180 : #if __cplusplus >= 201103L
181 : /**
182 : * @brief %Multimap move constructor.
183 : * @param __x A %multimap of identical element and allocator types.
184 : *
185 : * The newly-created %multimap contains the exact contents of @a __x.
186 : * The contents of @a __x are a valid, but unspecified %multimap.
187 : */
188 : multimap(multimap&& __x)
189 : noexcept(is_nothrow_copy_constructible<_Compare>::value)
190 : : _M_t(std::move(__x._M_t)) { }
191 :
192 : /**
193 : * @brief Builds a %multimap from an initializer_list.
194 : * @param __l An initializer_list.
195 : * @param __comp A comparison functor.
196 : * @param __a An allocator object.
197 : *
198 : * Create a %multimap consisting of copies of the elements from
199 : * the initializer_list. This is linear in N if the list is already
200 : * sorted, and NlogN otherwise (where N is @a __l.size()).
201 : */
202 : multimap(initializer_list<value_type> __l,
203 : const _Compare& __comp = _Compare(),
204 : const allocator_type& __a = allocator_type())
205 : : _M_t(__comp, _Pair_alloc_type(__a))
206 : { _M_t._M_insert_equal(__l.begin(), __l.end()); }
207 : #endif
208 :
209 : /**
210 : * @brief Builds a %multimap from a range.
211 : * @param __first An input iterator.
212 : * @param __last An input iterator.
213 : *
214 : * Create a %multimap consisting of copies of the elements from
215 : * [__first,__last). This is linear in N if the range is already sorted,
216 : * and NlogN otherwise (where N is distance(__first,__last)).
217 : */
218 : template<typename _InputIterator>
219 : multimap(_InputIterator __first, _InputIterator __last)
220 : : _M_t()
221 : { _M_t._M_insert_equal(__first, __last); }
222 :
223 : /**
224 : * @brief Builds a %multimap from a range.
225 : * @param __first An input iterator.
226 : * @param __last An input iterator.
227 : * @param __comp A comparison functor.
228 : * @param __a An allocator object.
229 : *
230 : * Create a %multimap consisting of copies of the elements from
231 : * [__first,__last). This is linear in N if the range is already sorted,
232 : * and NlogN otherwise (where N is distance(__first,__last)).
233 : */
234 : template<typename _InputIterator>
235 : multimap(_InputIterator __first, _InputIterator __last,
236 : const _Compare& __comp,
237 : const allocator_type& __a = allocator_type())
238 : : _M_t(__comp, _Pair_alloc_type(__a))
239 : { _M_t._M_insert_equal(__first, __last); }
240 :
241 : // FIXME There is no dtor declared, but we should have something generated
242 : // by Doxygen. I don't know what tags to add to this paragraph to make
243 : // that happen:
244 : /**
245 : * The dtor only erases the elements, and note that if the elements
246 : * themselves are pointers, the pointed-to memory is not touched in any
247 : * way. Managing the pointer is the user's responsibility.
248 : */
249 :
250 : /**
251 : * @brief %Multimap assignment operator.
252 : * @param __x A %multimap of identical element and allocator types.
253 : *
254 : * All the elements of @a __x are copied, but unlike the copy
255 : * constructor, the allocator object is not copied.
256 : */
257 : multimap&
258 : operator=(const multimap& __x)
259 : {
260 : _M_t = __x._M_t;
261 : return *this;
262 : }
263 :
264 : #if __cplusplus >= 201103L
265 : /**
266 : * @brief %Multimap move assignment operator.
267 : * @param __x A %multimap of identical element and allocator types.
268 : *
269 : * The contents of @a __x are moved into this multimap (without copying).
270 : * @a __x is a valid, but unspecified multimap.
271 : */
272 : multimap&
273 : operator=(multimap&& __x)
274 : {
275 : // NB: DR 1204.
276 : // NB: DR 675.
277 : this->clear();
278 : this->swap(__x);
279 : return *this;
280 : }
281 :
282 : /**
283 : * @brief %Multimap list assignment operator.
284 : * @param __l An initializer_list.
285 : *
286 : * This function fills a %multimap with copies of the elements
287 : * in the initializer list @a __l.
288 : *
289 : * Note that the assignment completely changes the %multimap and
290 : * that the resulting %multimap's size is the same as the number
291 : * of elements assigned. Old data may be lost.
292 : */
293 : multimap&
294 : operator=(initializer_list<value_type> __l)
295 : {
296 : this->clear();
297 : this->insert(__l.begin(), __l.end());
298 : return *this;
299 : }
300 : #endif
301 :
302 : /// Get a copy of the memory allocation object.
303 : allocator_type
304 : get_allocator() const _GLIBCXX_NOEXCEPT
305 : { return allocator_type(_M_t.get_allocator()); }
306 :
307 : // iterators
308 : /**
309 : * Returns a read/write iterator that points to the first pair in the
310 : * %multimap. Iteration is done in ascending order according to the
311 : * keys.
312 : */
313 : iterator
314 : begin() _GLIBCXX_NOEXCEPT
315 25643 : { return _M_t.begin(); }
316 :
317 : /**
318 : * Returns a read-only (constant) iterator that points to the first pair
319 : * in the %multimap. Iteration is done in ascending order according to
320 : * the keys.
321 : */
322 : const_iterator
323 : begin() const _GLIBCXX_NOEXCEPT
324 : { return _M_t.begin(); }
325 :
326 : /**
327 : * Returns a read/write iterator that points one past the last pair in
328 : * the %multimap. Iteration is done in ascending order according to the
329 : * keys.
330 : */
331 : iterator
332 : end() _GLIBCXX_NOEXCEPT
333 40021 : { return _M_t.end(); }
334 :
335 : /**
336 : * Returns a read-only (constant) iterator that points one past the last
337 : * pair in the %multimap. Iteration is done in ascending order according
338 : * to the keys.
339 : */
340 : const_iterator
341 : end() const _GLIBCXX_NOEXCEPT
342 : { return _M_t.end(); }
343 :
344 : /**
345 : * Returns a read/write reverse iterator that points to the last pair in
346 : * the %multimap. Iteration is done in descending order according to the
347 : * keys.
348 : */
349 : reverse_iterator
350 : rbegin() _GLIBCXX_NOEXCEPT
351 : { return _M_t.rbegin(); }
352 :
353 : /**
354 : * Returns a read-only (constant) reverse iterator that points to the
355 : * last pair in the %multimap. Iteration is done in descending order
356 : * according to the keys.
357 : */
358 : const_reverse_iterator
359 : rbegin() const _GLIBCXX_NOEXCEPT
360 : { return _M_t.rbegin(); }
361 :
362 : /**
363 : * Returns a read/write reverse iterator that points to one before the
364 : * first pair in the %multimap. Iteration is done in descending order
365 : * according to the keys.
366 : */
367 : reverse_iterator
368 : rend() _GLIBCXX_NOEXCEPT
369 : { return _M_t.rend(); }
370 :
371 : /**
372 : * Returns a read-only (constant) reverse iterator that points to one
373 : * before the first pair in the %multimap. Iteration is done in
374 : * descending order according to the keys.
375 : */
376 : const_reverse_iterator
377 : rend() const _GLIBCXX_NOEXCEPT
378 : { return _M_t.rend(); }
379 :
380 : #if __cplusplus >= 201103L
381 : /**
382 : * Returns a read-only (constant) iterator that points to the first pair
383 : * in the %multimap. Iteration is done in ascending order according to
384 : * the keys.
385 : */
386 : const_iterator
387 : cbegin() const noexcept
388 : { return _M_t.begin(); }
389 :
390 : /**
391 : * Returns a read-only (constant) iterator that points one past the last
392 : * pair in the %multimap. Iteration is done in ascending order according
393 : * to the keys.
394 : */
395 : const_iterator
396 : cend() const noexcept
397 : { return _M_t.end(); }
398 :
399 : /**
400 : * Returns a read-only (constant) reverse iterator that points to the
401 : * last pair in the %multimap. Iteration is done in descending order
402 : * according to the keys.
403 : */
404 : const_reverse_iterator
405 : crbegin() const noexcept
406 : { return _M_t.rbegin(); }
407 :
408 : /**
409 : * Returns a read-only (constant) reverse iterator that points to one
410 : * before the first pair in the %multimap. Iteration is done in
411 : * descending order according to the keys.
412 : */
413 : const_reverse_iterator
414 : crend() const noexcept
415 : { return _M_t.rend(); }
416 : #endif
417 :
418 : // capacity
419 : /** Returns true if the %multimap is empty. */
420 : bool
421 : empty() const _GLIBCXX_NOEXCEPT
422 34014 : { return _M_t.empty(); }
423 :
424 : /** Returns the size of the %multimap. */
425 : size_type
426 : size() const _GLIBCXX_NOEXCEPT
427 : { return _M_t.size(); }
428 :
429 : /** Returns the maximum size of the %multimap. */
430 : size_type
431 : max_size() const _GLIBCXX_NOEXCEPT
432 : { return _M_t.max_size(); }
433 :
434 : // modifiers
435 : #if __cplusplus >= 201103L
436 : /**
437 : * @brief Build and insert a std::pair into the %multimap.
438 : *
439 : * @param __args Arguments used to generate a new pair instance (see
440 : * std::piecewise_contruct for passing arguments to each
441 : * part of the pair constructor).
442 : *
443 : * @return An iterator that points to the inserted (key,value) pair.
444 : *
445 : * This function builds and inserts a (key, value) %pair into the
446 : * %multimap.
447 : * Contrary to a std::map the %multimap does not rely on unique keys and
448 : * thus multiple pairs with the same key can be inserted.
449 : *
450 : * Insertion requires logarithmic time.
451 : */
452 : template<typename... _Args>
453 : iterator
454 : emplace(_Args&&... __args)
455 : { return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
456 :
457 : /**
458 : * @brief Builds and inserts a std::pair into the %multimap.
459 : *
460 : * @param __pos An iterator that serves as a hint as to where the pair
461 : * should be inserted.
462 : * @param __args Arguments used to generate a new pair instance (see
463 : * std::piecewise_contruct for passing arguments to each
464 : * part of the pair constructor).
465 : * @return An iterator that points to the inserted (key,value) pair.
466 : *
467 : * This function inserts a (key, value) pair into the %multimap.
468 : * Contrary to a std::map the %multimap does not rely on unique keys and
469 : * thus multiple pairs with the same key can be inserted.
470 : * Note that the first parameter is only a hint and can potentially
471 : * improve the performance of the insertion process. A bad hint would
472 : * cause no gains in efficiency.
473 : *
474 : * For more on @a hinting, see:
475 : * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
476 : *
477 : * Insertion requires logarithmic time (if the hint is not taken).
478 : */
479 : template<typename... _Args>
480 : iterator
481 : emplace_hint(const_iterator __pos, _Args&&... __args)
482 : {
483 : return _M_t._M_emplace_hint_equal(__pos,
484 : std::forward<_Args>(__args)...);
485 : }
486 : #endif
487 :
488 : /**
489 : * @brief Inserts a std::pair into the %multimap.
490 : * @param __x Pair to be inserted (see std::make_pair for easy creation
491 : * of pairs).
492 : * @return An iterator that points to the inserted (key,value) pair.
493 : *
494 : * This function inserts a (key, value) pair into the %multimap.
495 : * Contrary to a std::map the %multimap does not rely on unique keys and
496 : * thus multiple pairs with the same key can be inserted.
497 : *
498 : * Insertion requires logarithmic time.
499 : */
500 : iterator
501 : insert(const value_type& __x)
502 : { return _M_t._M_insert_equal(__x); }
503 :
504 : #if __cplusplus >= 201103L
505 : template<typename _Pair, typename = typename
506 : std::enable_if<std::is_constructible<value_type,
507 : _Pair&&>::value>::type>
508 : iterator
509 : insert(_Pair&& __x)
510 12225 : { return _M_t._M_insert_equal(std::forward<_Pair>(__x)); }
511 : #endif
512 :
513 : /**
514 : * @brief Inserts a std::pair into the %multimap.
515 : * @param __position An iterator that serves as a hint as to where the
516 : * pair should be inserted.
517 : * @param __x Pair to be inserted (see std::make_pair for easy creation
518 : * of pairs).
519 : * @return An iterator that points to the inserted (key,value) pair.
520 : *
521 : * This function inserts a (key, value) pair into the %multimap.
522 : * Contrary to a std::map the %multimap does not rely on unique keys and
523 : * thus multiple pairs with the same key can be inserted.
524 : * Note that the first parameter is only a hint and can potentially
525 : * improve the performance of the insertion process. A bad hint would
526 : * cause no gains in efficiency.
527 : *
528 : * For more on @a hinting, see:
529 : * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
530 : *
531 : * Insertion requires logarithmic time (if the hint is not taken).
532 : */
533 : iterator
534 : #if __cplusplus >= 201103L
535 : insert(const_iterator __position, const value_type& __x)
536 : #else
537 : insert(iterator __position, const value_type& __x)
538 : #endif
539 : { return _M_t._M_insert_equal_(__position, __x); }
540 :
541 : #if __cplusplus >= 201103L
542 : template<typename _Pair, typename = typename
543 : std::enable_if<std::is_constructible<value_type,
544 : _Pair&&>::value>::type>
545 : iterator
546 : insert(const_iterator __position, _Pair&& __x)
547 : { return _M_t._M_insert_equal_(__position,
548 : std::forward<_Pair>(__x)); }
549 : #endif
550 :
551 : /**
552 : * @brief A template function that attempts to insert a range
553 : * of elements.
554 : * @param __first Iterator pointing to the start of the range to be
555 : * inserted.
556 : * @param __last Iterator pointing to the end of the range.
557 : *
558 : * Complexity similar to that of the range constructor.
559 : */
560 : template<typename _InputIterator>
561 : void
562 : insert(_InputIterator __first, _InputIterator __last)
563 : { _M_t._M_insert_equal(__first, __last); }
564 :
565 : #if __cplusplus >= 201103L
566 : /**
567 : * @brief Attempts to insert a list of std::pairs into the %multimap.
568 : * @param __l A std::initializer_list<value_type> of pairs to be
569 : * inserted.
570 : *
571 : * Complexity similar to that of the range constructor.
572 : */
573 : void
574 : insert(initializer_list<value_type> __l)
575 : { this->insert(__l.begin(), __l.end()); }
576 : #endif
577 :
578 : #if __cplusplus >= 201103L
579 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
580 : // DR 130. Associative erase should return an iterator.
581 : /**
582 : * @brief Erases an element from a %multimap.
583 : * @param __position An iterator pointing to the element to be erased.
584 : * @return An iterator pointing to the element immediately following
585 : * @a position prior to the element being erased. If no such
586 : * element exists, end() is returned.
587 : *
588 : * This function erases an element, pointed to by the given iterator,
589 : * from a %multimap. Note that this function only erases the element,
590 : * and that if the element is itself a pointer, the pointed-to memory is
591 : * not touched in any way. Managing the pointer is the user's
592 : * responsibility.
593 : */
594 : iterator
595 : erase(const_iterator __position)
596 : { return _M_t.erase(__position); }
597 :
598 : // LWG 2059.
599 : _GLIBCXX_ABI_TAG_CXX11
600 : iterator
601 : erase(iterator __position)
602 7878 : { return _M_t.erase(__position); }
603 : #else
604 : /**
605 : * @brief Erases an element from a %multimap.
606 : * @param __position An iterator pointing to the element to be erased.
607 : *
608 : * This function erases an element, pointed to by the given iterator,
609 : * from a %multimap. Note that this function only erases the element,
610 : * and that if the element is itself a pointer, the pointed-to memory is
611 : * not touched in any way. Managing the pointer is the user's
612 : * responsibility.
613 : */
614 : void
615 : erase(iterator __position)
616 : { _M_t.erase(__position); }
617 : #endif
618 :
619 : /**
620 : * @brief Erases elements according to the provided key.
621 : * @param __x Key of element to be erased.
622 : * @return The number of elements erased.
623 : *
624 : * This function erases all elements located by the given key from a
625 : * %multimap.
626 : * Note that this function only erases the element, and that if
627 : * the element is itself a pointer, the pointed-to memory is not touched
628 : * in any way. Managing the pointer is the user's responsibility.
629 : */
630 : size_type
631 : erase(const key_type& __x)
632 : { return _M_t.erase(__x); }
633 :
634 : #if __cplusplus >= 201103L
635 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
636 : // DR 130. Associative erase should return an iterator.
637 : /**
638 : * @brief Erases a [first,last) range of elements from a %multimap.
639 : * @param __first Iterator pointing to the start of the range to be
640 : * erased.
641 : * @param __last Iterator pointing to the end of the range to be
642 : * erased .
643 : * @return The iterator @a __last.
644 : *
645 : * This function erases a sequence of elements from a %multimap.
646 : * Note that this function only erases the elements, and that if
647 : * the elements themselves are pointers, the pointed-to memory is not
648 : * touched in any way. Managing the pointer is the user's
649 : * responsibility.
650 : */
651 : iterator
652 : erase(const_iterator __first, const_iterator __last)
653 430 : { return _M_t.erase(__first, __last); }
654 : #else
655 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
656 : // DR 130. Associative erase should return an iterator.
657 : /**
658 : * @brief Erases a [first,last) range of elements from a %multimap.
659 : * @param __first Iterator pointing to the start of the range to be
660 : * erased.
661 : * @param __last Iterator pointing to the end of the range to
662 : * be erased.
663 : *
664 : * This function erases a sequence of elements from a %multimap.
665 : * Note that this function only erases the elements, and that if
666 : * the elements themselves are pointers, the pointed-to memory is not
667 : * touched in any way. Managing the pointer is the user's
668 : * responsibility.
669 : */
670 : void
671 : erase(iterator __first, iterator __last)
672 : { _M_t.erase(__first, __last); }
673 : #endif
674 :
675 : /**
676 : * @brief Swaps data with another %multimap.
677 : * @param __x A %multimap of the same element and allocator types.
678 : *
679 : * This exchanges the elements between two multimaps in constant time.
680 : * (It is only swapping a pointer, an integer, and an instance of
681 : * the @c Compare type (which itself is often stateless and empty), so it
682 : * should be quite fast.)
683 : * Note that the global std::swap() function is specialized such that
684 : * std::swap(m1,m2) will feed to this function.
685 : */
686 : void
687 : swap(multimap& __x)
688 : { _M_t.swap(__x._M_t); }
689 :
690 : /**
691 : * Erases all elements in a %multimap. Note that this function only
692 : * erases the elements, and that if the elements themselves are pointers,
693 : * the pointed-to memory is not touched in any way. Managing the pointer
694 : * is the user's responsibility.
695 : */
696 : void
697 : clear() _GLIBCXX_NOEXCEPT
698 : { _M_t.clear(); }
699 :
700 : // observers
701 : /**
702 : * Returns the key comparison object out of which the %multimap
703 : * was constructed.
704 : */
705 : key_compare
706 : key_comp() const
707 : { return _M_t.key_comp(); }
708 :
709 : /**
710 : * Returns a value comparison object, built from the key comparison
711 : * object out of which the %multimap was constructed.
712 : */
713 : value_compare
714 : value_comp() const
715 : { return value_compare(_M_t.key_comp()); }
716 :
717 : // multimap operations
718 : /**
719 : * @brief Tries to locate an element in a %multimap.
720 : * @param __x Key of (key, value) pair to be located.
721 : * @return Iterator pointing to sought-after element,
722 : * or end() if not found.
723 : *
724 : * This function takes a key and tries to locate the element with which
725 : * the key matches. If successful the function returns an iterator
726 : * pointing to the sought after %pair. If unsuccessful it returns the
727 : * past-the-end ( @c end() ) iterator.
728 : */
729 : iterator
730 : find(const key_type& __x)
731 3542 : { return _M_t.find(__x); }
732 :
733 : /**
734 : * @brief Tries to locate an element in a %multimap.
735 : * @param __x Key of (key, value) pair to be located.
736 : * @return Read-only (constant) iterator pointing to sought-after
737 : * element, or end() if not found.
738 : *
739 : * This function takes a key and tries to locate the element with which
740 : * the key matches. If successful the function returns a constant
741 : * iterator pointing to the sought after %pair. If unsuccessful it
742 : * returns the past-the-end ( @c end() ) iterator.
743 : */
744 : const_iterator
745 : find(const key_type& __x) const
746 : { return _M_t.find(__x); }
747 :
748 : /**
749 : * @brief Finds the number of elements with given key.
750 : * @param __x Key of (key, value) pairs to be located.
751 : * @return Number of elements with specified key.
752 : */
753 : size_type
754 : count(const key_type& __x) const
755 : { return _M_t.count(__x); }
756 :
757 : /**
758 : * @brief Finds the beginning of a subsequence matching given key.
759 : * @param __x Key of (key, value) pair to be located.
760 : * @return Iterator pointing to first element equal to or greater
761 : * than key, or end().
762 : *
763 : * This function returns the first element of a subsequence of elements
764 : * that matches the given key. If unsuccessful it returns an iterator
765 : * pointing to the first element that has a greater value than given key
766 : * or end() if no such element exists.
767 : */
768 : iterator
769 : lower_bound(const key_type& __x)
770 : { return _M_t.lower_bound(__x); }
771 :
772 : /**
773 : * @brief Finds the beginning of a subsequence matching given key.
774 : * @param __x Key of (key, value) pair to be located.
775 : * @return Read-only (constant) iterator pointing to first element
776 : * equal to or greater than key, or end().
777 : *
778 : * This function returns the first element of a subsequence of
779 : * elements that matches the given key. If unsuccessful the
780 : * iterator will point to the next greatest element or, if no
781 : * such greater element exists, to end().
782 : */
783 : const_iterator
784 : lower_bound(const key_type& __x) const
785 : { return _M_t.lower_bound(__x); }
786 :
787 : /**
788 : * @brief Finds the end of a subsequence matching given key.
789 : * @param __x Key of (key, value) pair to be located.
790 : * @return Iterator pointing to the first element
791 : * greater than key, or end().
792 : */
793 : iterator
794 : upper_bound(const key_type& __x)
795 : { return _M_t.upper_bound(__x); }
796 :
797 : /**
798 : * @brief Finds the end of a subsequence matching given key.
799 : * @param __x Key of (key, value) pair to be located.
800 : * @return Read-only (constant) iterator pointing to first iterator
801 : * greater than key, or end().
802 : */
803 : const_iterator
804 : upper_bound(const key_type& __x) const
805 : { return _M_t.upper_bound(__x); }
806 :
807 : /**
808 : * @brief Finds a subsequence matching given key.
809 : * @param __x Key of (key, value) pairs to be located.
810 : * @return Pair of iterators that possibly points to the subsequence
811 : * matching given key.
812 : *
813 : * This function is equivalent to
814 : * @code
815 : * std::make_pair(c.lower_bound(val),
816 : * c.upper_bound(val))
817 : * @endcode
818 : * (but is faster than making the calls separately).
819 : */
820 : std::pair<iterator, iterator>
821 : equal_range(const key_type& __x)
822 532 : { return _M_t.equal_range(__x); }
823 :
824 : /**
825 : * @brief Finds a subsequence matching given key.
826 : * @param __x Key of (key, value) pairs to be located.
827 : * @return Pair of read-only (constant) iterators that possibly points
828 : * to the subsequence matching given key.
829 : *
830 : * This function is equivalent to
831 : * @code
832 : * std::make_pair(c.lower_bound(val),
833 : * c.upper_bound(val))
834 : * @endcode
835 : * (but is faster than making the calls separately).
836 : */
837 : std::pair<const_iterator, const_iterator>
838 : equal_range(const key_type& __x) const
839 : { return _M_t.equal_range(__x); }
840 :
841 : template<typename _K1, typename _T1, typename _C1, typename _A1>
842 : friend bool
843 : operator==(const multimap<_K1, _T1, _C1, _A1>&,
844 : const multimap<_K1, _T1, _C1, _A1>&);
845 :
846 : template<typename _K1, typename _T1, typename _C1, typename _A1>
847 : friend bool
848 : operator<(const multimap<_K1, _T1, _C1, _A1>&,
849 : const multimap<_K1, _T1, _C1, _A1>&);
850 : };
851 :
852 : /**
853 : * @brief Multimap equality comparison.
854 : * @param __x A %multimap.
855 : * @param __y A %multimap of the same type as @a __x.
856 : * @return True iff the size and elements of the maps are equal.
857 : *
858 : * This is an equivalence relation. It is linear in the size of the
859 : * multimaps. Multimaps are considered equivalent if their sizes are equal,
860 : * and if corresponding elements compare equal.
861 : */
862 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
863 : inline bool
864 : operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
865 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
866 : { return __x._M_t == __y._M_t; }
867 :
868 : /**
869 : * @brief Multimap ordering relation.
870 : * @param __x A %multimap.
871 : * @param __y A %multimap of the same type as @a __x.
872 : * @return True iff @a x is lexicographically less than @a y.
873 : *
874 : * This is a total ordering relation. It is linear in the size of the
875 : * multimaps. The elements must be comparable with @c <.
876 : *
877 : * See std::lexicographical_compare() for how the determination is made.
878 : */
879 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
880 : inline bool
881 : operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
882 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
883 : { return __x._M_t < __y._M_t; }
884 :
885 : /// Based on operator==
886 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
887 : inline bool
888 : operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
889 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
890 : { return !(__x == __y); }
891 :
892 : /// Based on operator<
893 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
894 : inline bool
895 : operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
896 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
897 : { return __y < __x; }
898 :
899 : /// Based on operator<
900 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
901 : inline bool
902 : operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
903 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
904 : { return !(__y < __x); }
905 :
906 : /// Based on operator<
907 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
908 : inline bool
909 : operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
910 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
911 : { return !(__x < __y); }
912 :
913 : /// See std::multimap::swap().
914 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
915 : inline void
916 : swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
917 : multimap<_Key, _Tp, _Compare, _Alloc>& __y)
918 : { __x.swap(__y); }
919 :
920 : _GLIBCXX_END_NAMESPACE_CONTAINER
921 : } // namespace std
922 :
923 : #endif /* _STL_MULTIMAP_H */
|
