Line data Source code
1 : // Multimap implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 : // Free Software Foundation, Inc.
5 : //
6 : // This file is part of the GNU ISO C++ Library. This library is free
7 : // software; you can redistribute it and/or modify it under the
8 : // terms of the GNU General Public License as published by the
9 : // Free Software Foundation; either version 3, or (at your option)
10 : // any later version.
11 :
12 : // This library is distributed in the hope that it will be useful,
13 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : // GNU General Public License for more details.
16 :
17 : // Under Section 7 of GPL version 3, you are granted additional
18 : // permissions described in the GCC Runtime Library Exception, version
19 : // 3.1, as published by the Free Software Foundation.
20 :
21 : // You should have received a copy of the GNU General Public License and
22 : // a copy of the GCC Runtime Library Exception along with this program;
23 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 : // <http://www.gnu.org/licenses/>.
25 :
26 : /*
27 : *
28 : * Copyright (c) 1994
29 : * Hewlett-Packard Company
30 : *
31 : * Permission to use, copy, modify, distribute and sell this software
32 : * and its documentation for any purpose is hereby granted without fee,
33 : * provided that the above copyright notice appear in all copies and
34 : * that both that copyright notice and this permission notice appear
35 : * in supporting documentation. Hewlett-Packard Company makes no
36 : * representations about the suitability of this software for any
37 : * purpose. It is provided "as is" without express or implied warranty.
38 : *
39 : *
40 : * Copyright (c) 1996,1997
41 : * Silicon Graphics Computer Systems, Inc.
42 : *
43 : * Permission to use, copy, modify, distribute and sell this software
44 : * and its documentation for any purpose is hereby granted without fee,
45 : * provided that the above copyright notice appear in all copies and
46 : * that both that copyright notice and this permission notice appear
47 : * in supporting documentation. Silicon Graphics makes no
48 : * representations about the suitability of this software for any
49 : * purpose. It is provided "as is" without express or implied warranty.
50 : */
51 :
52 : /** @file stl_multimap.h
53 : * This is an internal header file, included by other library headers.
54 : * You should not attempt to use it directly.
55 : */
56 :
57 : #ifndef _STL_MULTIMAP_H
58 : #define _STL_MULTIMAP_H 1
59 :
60 : #include <bits/concept_check.h>
61 : #include <initializer_list>
62 :
63 : _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
64 :
65 : /**
66 : * @brief A standard container made up of (key,value) pairs, which can be
67 : * retrieved based on a key, in logarithmic time.
68 : *
69 : * @ingroup associative_containers
70 : *
71 : * Meets the requirements of a <a href="tables.html#65">container</a>, a
72 : * <a href="tables.html#66">reversible container</a>, and an
73 : * <a href="tables.html#69">associative container</a> (using equivalent
74 : * keys). For a @c multimap<Key,T> the key_type is Key, the mapped_type
75 : * is T, and the value_type is std::pair<const Key,T>.
76 : *
77 : * Multimaps support bidirectional iterators.
78 : *
79 : * The private tree data is declared exactly the same way for map and
80 : * multimap; the distinction is made entirely in how the tree functions are
81 : * called (*_unique versus *_equal, same as the standard).
82 : */
83 : template <typename _Key, typename _Tp,
84 : typename _Compare = std::less<_Key>,
85 : typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
86 : class multimap
87 0 : {
88 : public:
89 : typedef _Key key_type;
90 : typedef _Tp mapped_type;
91 : typedef std::pair<const _Key, _Tp> value_type;
92 : typedef _Compare key_compare;
93 : typedef _Alloc allocator_type;
94 :
95 : private:
96 : // concept requirements
97 : typedef typename _Alloc::value_type _Alloc_value_type;
98 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
99 : __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
100 : _BinaryFunctionConcept)
101 : __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
102 :
103 : public:
104 : class value_compare
105 : : public std::binary_function<value_type, value_type, bool>
106 : {
107 : friend class multimap<_Key, _Tp, _Compare, _Alloc>;
108 : protected:
109 : _Compare comp;
110 :
111 : value_compare(_Compare __c)
112 : : comp(__c) { }
113 :
114 : public:
115 : bool operator()(const value_type& __x, const value_type& __y) const
116 : { return comp(__x.first, __y.first); }
117 : };
118 :
119 : private:
120 : /// This turns a red-black tree into a [multi]map.
121 : typedef typename _Alloc::template rebind<value_type>::other
122 : _Pair_alloc_type;
123 :
124 : typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
125 : key_compare, _Pair_alloc_type> _Rep_type;
126 : /// The actual tree structure.
127 : _Rep_type _M_t;
128 :
129 : public:
130 : // many of these are specified differently in ISO, but the following are
131 : // "functionally equivalent"
132 : typedef typename _Pair_alloc_type::pointer pointer;
133 : typedef typename _Pair_alloc_type::const_pointer const_pointer;
134 : typedef typename _Pair_alloc_type::reference reference;
135 : typedef typename _Pair_alloc_type::const_reference const_reference;
136 : typedef typename _Rep_type::iterator iterator;
137 : typedef typename _Rep_type::const_iterator const_iterator;
138 : typedef typename _Rep_type::size_type size_type;
139 : typedef typename _Rep_type::difference_type difference_type;
140 : typedef typename _Rep_type::reverse_iterator reverse_iterator;
141 : typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
142 :
143 : // [23.3.2] construct/copy/destroy
144 : // (get_allocator() is also listed in this section)
145 : /**
146 : * @brief Default constructor creates no elements.
147 : */
148 328 : multimap()
149 328 : : _M_t() { }
150 :
151 : /**
152 : * @brief Creates a %multimap with no elements.
153 : * @param comp A comparison object.
154 : * @param a An allocator object.
155 : */
156 : explicit
157 : multimap(const _Compare& __comp,
158 : const allocator_type& __a = allocator_type())
159 : : _M_t(__comp, __a) { }
160 :
161 : /**
162 : * @brief %Multimap copy constructor.
163 : * @param x A %multimap of identical element and allocator types.
164 : *
165 : * The newly-created %multimap uses a copy of the allocation object
166 : * used by @a x.
167 : */
168 : multimap(const multimap& __x)
169 : : _M_t(__x._M_t) { }
170 :
171 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
172 : /**
173 : * @brief %Multimap move constructor.
174 : * @param x A %multimap of identical element and allocator types.
175 : *
176 : * The newly-created %multimap contains the exact contents of @a x.
177 : * The contents of @a x are a valid, but unspecified %multimap.
178 : */
179 : multimap(multimap&& __x)
180 : : _M_t(std::forward<_Rep_type>(__x._M_t)) { }
181 :
182 : /**
183 : * @brief Builds a %multimap from an initializer_list.
184 : * @param l An initializer_list.
185 : * @param comp A comparison functor.
186 : * @param a An allocator object.
187 : *
188 : * Create a %multimap consisting of copies of the elements from
189 : * the initializer_list. This is linear in N if the list is already
190 : * sorted, and NlogN otherwise (where N is @a __l.size()).
191 : */
192 : multimap(initializer_list<value_type> __l,
193 : const _Compare& __comp = _Compare(),
194 : const allocator_type& __a = allocator_type())
195 : : _M_t(__comp, __a)
196 : { _M_t._M_insert_equal(__l.begin(), __l.end()); }
197 : #endif
198 :
199 : /**
200 : * @brief Builds a %multimap from a range.
201 : * @param first An input iterator.
202 : * @param last An input iterator.
203 : *
204 : * Create a %multimap consisting of copies of the elements from
205 : * [first,last). This is linear in N if the range is already sorted,
206 : * and NlogN otherwise (where N is distance(first,last)).
207 : */
208 : template<typename _InputIterator>
209 : multimap(_InputIterator __first, _InputIterator __last)
210 : : _M_t()
211 : { _M_t._M_insert_equal(__first, __last); }
212 :
213 : /**
214 : * @brief Builds a %multimap from a range.
215 : * @param first An input iterator.
216 : * @param last An input iterator.
217 : * @param comp A comparison functor.
218 : * @param a An allocator object.
219 : *
220 : * Create a %multimap consisting of copies of the elements from
221 : * [first,last). This is linear in N if the range is already sorted,
222 : * and NlogN otherwise (where N is distance(first,last)).
223 : */
224 : template<typename _InputIterator>
225 : multimap(_InputIterator __first, _InputIterator __last,
226 : const _Compare& __comp,
227 : const allocator_type& __a = allocator_type())
228 : : _M_t(__comp, __a)
229 : { _M_t._M_insert_equal(__first, __last); }
230 :
231 : // FIXME There is no dtor declared, but we should have something generated
232 : // by Doxygen. I don't know what tags to add to this paragraph to make
233 : // that happen:
234 : /**
235 : * The dtor only erases the elements, and note that if the elements
236 : * themselves are pointers, the pointed-to memory is not touched in any
237 : * way. Managing the pointer is the user's responsibility.
238 : */
239 :
240 : /**
241 : * @brief %Multimap assignment operator.
242 : * @param x A %multimap of identical element and allocator types.
243 : *
244 : * All the elements of @a x are copied, but unlike the copy constructor,
245 : * the allocator object is not copied.
246 : */
247 : multimap&
248 : operator=(const multimap& __x)
249 : {
250 : _M_t = __x._M_t;
251 : return *this;
252 : }
253 :
254 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
255 : /**
256 : * @brief %Multimap move assignment operator.
257 : * @param x A %multimap of identical element and allocator types.
258 : *
259 : * The contents of @a x are moved into this multimap (without copying).
260 : * @a x is a valid, but unspecified multimap.
261 : */
262 : multimap&
263 : operator=(multimap&& __x)
264 : {
265 : // NB: DR 675.
266 : this->clear();
267 : this->swap(__x);
268 : return *this;
269 : }
270 :
271 : /**
272 : * @brief %Multimap list assignment operator.
273 : * @param l An initializer_list.
274 : *
275 : * This function fills a %multimap with copies of the elements
276 : * in the initializer list @a l.
277 : *
278 : * Note that the assignment completely changes the %multimap and
279 : * that the resulting %multimap's size is the same as the number
280 : * of elements assigned. Old data may be lost.
281 : */
282 : multimap&
283 : operator=(initializer_list<value_type> __l)
284 : {
285 : this->clear();
286 : this->insert(__l.begin(), __l.end());
287 : return *this;
288 : }
289 : #endif
290 :
291 : /// Get a copy of the memory allocation object.
292 : allocator_type
293 : get_allocator() const
294 : { return _M_t.get_allocator(); }
295 :
296 : // iterators
297 : /**
298 : * Returns a read/write iterator that points to the first pair in the
299 : * %multimap. Iteration is done in ascending order according to the
300 : * keys.
301 : */
302 : iterator
303 : begin()
304 : { return _M_t.begin(); }
305 :
306 : /**
307 : * Returns a read-only (constant) iterator that points to the first pair
308 : * in the %multimap. Iteration is done in ascending order according to
309 : * the keys.
310 : */
311 : const_iterator
312 : begin() const
313 : { return _M_t.begin(); }
314 :
315 : /**
316 : * Returns a read/write iterator that points one past the last pair in
317 : * the %multimap. Iteration is done in ascending order according to the
318 : * keys.
319 : */
320 : iterator
321 18287 : end()
322 18287 : { return _M_t.end(); }
323 :
324 : /**
325 : * Returns a read-only (constant) iterator that points one past the last
326 : * pair in the %multimap. Iteration is done in ascending order according
327 : * to the keys.
328 : */
329 : const_iterator
330 : end() const
331 : { return _M_t.end(); }
332 :
333 : /**
334 : * Returns a read/write reverse iterator that points to the last pair in
335 : * the %multimap. Iteration is done in descending order according to the
336 : * keys.
337 : */
338 : reverse_iterator
339 : rbegin()
340 : { return _M_t.rbegin(); }
341 :
342 : /**
343 : * Returns a read-only (constant) reverse iterator that points to the
344 : * last pair in the %multimap. Iteration is done in descending order
345 : * according to the keys.
346 : */
347 : const_reverse_iterator
348 : rbegin() const
349 : { return _M_t.rbegin(); }
350 :
351 : /**
352 : * Returns a read/write reverse iterator that points to one before the
353 : * first pair in the %multimap. Iteration is done in descending order
354 : * according to the keys.
355 : */
356 : reverse_iterator
357 : rend()
358 : { return _M_t.rend(); }
359 :
360 : /**
361 : * Returns a read-only (constant) reverse iterator that points to one
362 : * before the first pair in the %multimap. Iteration is done in
363 : * descending order according to the keys.
364 : */
365 : const_reverse_iterator
366 : rend() const
367 : { return _M_t.rend(); }
368 :
369 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
370 : /**
371 : * Returns a read-only (constant) iterator that points to the first pair
372 : * in the %multimap. Iteration is done in ascending order according to
373 : * the keys.
374 : */
375 : const_iterator
376 : cbegin() const
377 : { return _M_t.begin(); }
378 :
379 : /**
380 : * Returns a read-only (constant) iterator that points one past the last
381 : * pair in the %multimap. Iteration is done in ascending order according
382 : * to the keys.
383 : */
384 : const_iterator
385 : cend() const
386 : { return _M_t.end(); }
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 : crbegin() const
395 : { return _M_t.rbegin(); }
396 :
397 : /**
398 : * Returns a read-only (constant) reverse iterator that points to one
399 : * before the first pair in the %multimap. Iteration is done in
400 : * descending order according to the keys.
401 : */
402 : const_reverse_iterator
403 : crend() const
404 : { return _M_t.rend(); }
405 : #endif
406 :
407 : // capacity
408 : /** Returns true if the %multimap is empty. */
409 : bool
410 : empty() const
411 : { return _M_t.empty(); }
412 :
413 : /** Returns the size of the %multimap. */
414 : size_type
415 : size() const
416 : { return _M_t.size(); }
417 :
418 : /** Returns the maximum size of the %multimap. */
419 : size_type
420 : max_size() const
421 : { return _M_t.max_size(); }
422 :
423 : // modifiers
424 : /**
425 : * @brief Inserts a std::pair into the %multimap.
426 : * @param x Pair to be inserted (see std::make_pair for easy creation
427 : * of pairs).
428 : * @return An iterator that points to the inserted (key,value) pair.
429 : *
430 : * This function inserts a (key, value) pair into the %multimap.
431 : * Contrary to a std::map the %multimap does not rely on unique keys and
432 : * thus multiple pairs with the same key can be inserted.
433 : *
434 : * Insertion requires logarithmic time.
435 : */
436 : iterator
437 428 : insert(const value_type& __x)
438 428 : { return _M_t._M_insert_equal(__x); }
439 :
440 : /**
441 : * @brief Inserts a std::pair into the %multimap.
442 : * @param position An iterator that serves as a hint as to where the
443 : * pair should be inserted.
444 : * @param x Pair to be inserted (see std::make_pair for easy creation
445 : * of pairs).
446 : * @return An iterator that points to the inserted (key,value) pair.
447 : *
448 : * This function inserts a (key, value) pair into the %multimap.
449 : * Contrary to a std::map the %multimap does not rely on unique keys and
450 : * thus multiple pairs with the same key can be inserted.
451 : * Note that the first parameter is only a hint and can potentially
452 : * improve the performance of the insertion process. A bad hint would
453 : * cause no gains in efficiency.
454 : *
455 : * For more on "hinting," see:
456 : * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
457 : *
458 : * Insertion requires logarithmic time (if the hint is not taken).
459 : */
460 : iterator
461 20506 : insert(iterator __position, const value_type& __x)
462 20506 : { return _M_t._M_insert_equal_(__position, __x); }
463 :
464 : /**
465 : * @brief A template function that attempts to insert a range
466 : * of elements.
467 : * @param first Iterator pointing to the start of the range to be
468 : * inserted.
469 : * @param last Iterator pointing to the end of the range.
470 : *
471 : * Complexity similar to that of the range constructor.
472 : */
473 : template<typename _InputIterator>
474 : void
475 : insert(_InputIterator __first, _InputIterator __last)
476 : { _M_t._M_insert_equal(__first, __last); }
477 :
478 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
479 : /**
480 : * @brief Attempts to insert a list of std::pairs into the %multimap.
481 : * @param list A std::initializer_list<value_type> of pairs to be
482 : * inserted.
483 : *
484 : * Complexity similar to that of the range constructor.
485 : */
486 : void
487 : insert(initializer_list<value_type> __l)
488 : { this->insert(__l.begin(), __l.end()); }
489 : #endif
490 :
491 : /**
492 : * @brief Erases an element from a %multimap.
493 : * @param position An iterator pointing to the element to be erased.
494 : *
495 : * This function erases an element, pointed to by the given iterator,
496 : * from a %multimap. Note that this function only erases the element,
497 : * and that if the element is itself a pointer, the pointed-to memory is
498 : * not touched in any way. Managing the pointer is the user's
499 : * responsibility.
500 : */
501 : void
502 : erase(iterator __position)
503 : { _M_t.erase(__position); }
504 :
505 : /**
506 : * @brief Erases elements according to the provided key.
507 : * @param x Key of element to be erased.
508 : * @return The number of elements erased.
509 : *
510 : * This function erases all elements located by the given key from a
511 : * %multimap.
512 : * Note that this function only erases the element, and that if
513 : * the element is itself a pointer, the pointed-to memory is not touched
514 : * in any way. Managing the pointer is the user's responsibility.
515 : */
516 : size_type
517 : erase(const key_type& __x)
518 : { return _M_t.erase(__x); }
519 :
520 : /**
521 : * @brief Erases a [first,last) range of elements from a %multimap.
522 : * @param first Iterator pointing to the start of the range to be
523 : * erased.
524 : * @param last Iterator pointing to the end of the range to be erased.
525 : *
526 : * This function erases a sequence of elements from a %multimap.
527 : * Note that this function only erases the elements, and that if
528 : * the elements themselves are pointers, the pointed-to memory is not
529 : * touched in any way. Managing the pointer is the user's responsibility.
530 : */
531 : void
532 0 : erase(iterator __first, iterator __last)
533 0 : { _M_t.erase(__first, __last); }
534 :
535 : /**
536 : * @brief Swaps data with another %multimap.
537 : * @param x A %multimap of the same element and allocator types.
538 : *
539 : * This exchanges the elements between two multimaps in constant time.
540 : * (It is only swapping a pointer, an integer, and an instance of
541 : * the @c Compare type (which itself is often stateless and empty), so it
542 : * should be quite fast.)
543 : * Note that the global std::swap() function is specialized such that
544 : * std::swap(m1,m2) will feed to this function.
545 : */
546 : void
547 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
548 : swap(multimap&& __x)
549 : #else
550 : swap(multimap& __x)
551 : #endif
552 : { _M_t.swap(__x._M_t); }
553 :
554 : /**
555 : * Erases all elements in a %multimap. Note that this function only
556 : * erases the elements, and that if the elements themselves are pointers,
557 : * the pointed-to memory is not touched in any way. Managing the pointer
558 : * is the user's responsibility.
559 : */
560 : void
561 : clear()
562 : { _M_t.clear(); }
563 :
564 : // observers
565 : /**
566 : * Returns the key comparison object out of which the %multimap
567 : * was constructed.
568 : */
569 : key_compare
570 : key_comp() const
571 : { return _M_t.key_comp(); }
572 :
573 : /**
574 : * Returns a value comparison object, built from the key comparison
575 : * object out of which the %multimap was constructed.
576 : */
577 : value_compare
578 : value_comp() const
579 : { return value_compare(_M_t.key_comp()); }
580 :
581 : // multimap operations
582 : /**
583 : * @brief Tries to locate an element in a %multimap.
584 : * @param x Key of (key, value) pair to be located.
585 : * @return Iterator pointing to sought-after element,
586 : * or end() if not found.
587 : *
588 : * This function takes a key and tries to locate the element with which
589 : * the key matches. If successful the function returns an iterator
590 : * pointing to the sought after %pair. If unsuccessful it returns the
591 : * past-the-end ( @c end() ) iterator.
592 : */
593 : iterator
594 18287 : find(const key_type& __x)
595 18287 : { return _M_t.find(__x); }
596 :
597 : /**
598 : * @brief Tries to locate an element in a %multimap.
599 : * @param x Key of (key, value) pair to be located.
600 : * @return Read-only (constant) iterator pointing to sought-after
601 : * element, or end() if not found.
602 : *
603 : * This function takes a key and tries to locate the element with which
604 : * the key matches. If successful the function returns a constant
605 : * iterator pointing to the sought after %pair. If unsuccessful it
606 : * returns the past-the-end ( @c end() ) iterator.
607 : */
608 : const_iterator
609 : find(const key_type& __x) const
610 : { return _M_t.find(__x); }
611 :
612 : /**
613 : * @brief Finds the number of elements with given key.
614 : * @param x Key of (key, value) pairs to be located.
615 : * @return Number of elements with specified key.
616 : */
617 : size_type
618 : count(const key_type& __x) const
619 : { return _M_t.count(__x); }
620 :
621 : /**
622 : * @brief Finds the beginning of a subsequence matching given key.
623 : * @param x Key of (key, value) pair to be located.
624 : * @return Iterator pointing to first element equal to or greater
625 : * than key, or end().
626 : *
627 : * This function returns the first element of a subsequence of elements
628 : * that matches the given key. If unsuccessful it returns an iterator
629 : * pointing to the first element that has a greater value than given key
630 : * or end() if no such element exists.
631 : */
632 : iterator
633 0 : lower_bound(const key_type& __x)
634 0 : { return _M_t.lower_bound(__x); }
635 :
636 : /**
637 : * @brief Finds the beginning of a subsequence matching given key.
638 : * @param x Key of (key, value) pair to be located.
639 : * @return Read-only (constant) iterator pointing to first element
640 : * equal to or greater than key, or end().
641 : *
642 : * This function returns the first element of a subsequence of elements
643 : * that matches the given key. If unsuccessful the iterator will point
644 : * to the next greatest element or, if no such greater element exists, to
645 : * end().
646 : */
647 : const_iterator
648 : lower_bound(const key_type& __x) const
649 : { return _M_t.lower_bound(__x); }
650 :
651 : /**
652 : * @brief Finds the end of a subsequence matching given key.
653 : * @param x Key of (key, value) pair to be located.
654 : * @return Iterator pointing to the first element
655 : * greater than key, or end().
656 : */
657 : iterator
658 : upper_bound(const key_type& __x)
659 : { return _M_t.upper_bound(__x); }
660 :
661 : /**
662 : * @brief Finds the end of a subsequence matching given key.
663 : * @param x Key of (key, value) pair to be located.
664 : * @return Read-only (constant) iterator pointing to first iterator
665 : * greater than key, or end().
666 : */
667 : const_iterator
668 : upper_bound(const key_type& __x) const
669 : { return _M_t.upper_bound(__x); }
670 :
671 : /**
672 : * @brief Finds a subsequence matching given key.
673 : * @param x Key of (key, value) pairs to be located.
674 : * @return Pair of iterators that possibly points to the subsequence
675 : * matching given key.
676 : *
677 : * This function is equivalent to
678 : * @code
679 : * std::make_pair(c.lower_bound(val),
680 : * c.upper_bound(val))
681 : * @endcode
682 : * (but is faster than making the calls separately).
683 : */
684 : std::pair<iterator, iterator>
685 23142 : equal_range(const key_type& __x)
686 23142 : { return _M_t.equal_range(__x); }
687 :
688 : /**
689 : * @brief Finds a subsequence matching given key.
690 : * @param x Key of (key, value) pairs to be located.
691 : * @return Pair of read-only (constant) iterators that possibly points
692 : * to the subsequence matching given key.
693 : *
694 : * This function is equivalent to
695 : * @code
696 : * std::make_pair(c.lower_bound(val),
697 : * c.upper_bound(val))
698 : * @endcode
699 : * (but is faster than making the calls separately).
700 : */
701 : std::pair<const_iterator, const_iterator>
702 : equal_range(const key_type& __x) const
703 : { return _M_t.equal_range(__x); }
704 :
705 : template<typename _K1, typename _T1, typename _C1, typename _A1>
706 : friend bool
707 : operator==(const multimap<_K1, _T1, _C1, _A1>&,
708 : const multimap<_K1, _T1, _C1, _A1>&);
709 :
710 : template<typename _K1, typename _T1, typename _C1, typename _A1>
711 : friend bool
712 : operator<(const multimap<_K1, _T1, _C1, _A1>&,
713 : const multimap<_K1, _T1, _C1, _A1>&);
714 : };
715 :
716 : /**
717 : * @brief Multimap equality comparison.
718 : * @param x A %multimap.
719 : * @param y A %multimap of the same type as @a x.
720 : * @return True iff the size and elements of the maps are equal.
721 : *
722 : * This is an equivalence relation. It is linear in the size of the
723 : * multimaps. Multimaps are considered equivalent if their sizes are equal,
724 : * and if corresponding elements compare equal.
725 : */
726 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
727 : inline bool
728 : operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
729 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
730 : { return __x._M_t == __y._M_t; }
731 :
732 : /**
733 : * @brief Multimap ordering relation.
734 : * @param x A %multimap.
735 : * @param y A %multimap of the same type as @a x.
736 : * @return True iff @a x is lexicographically less than @a y.
737 : *
738 : * This is a total ordering relation. It is linear in the size of the
739 : * multimaps. The elements must be comparable with @c <.
740 : *
741 : * See std::lexicographical_compare() for how the determination is made.
742 : */
743 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
744 : inline bool
745 : operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
746 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
747 : { return __x._M_t < __y._M_t; }
748 :
749 : /// Based on operator==
750 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
751 : inline bool
752 : operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
753 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
754 : { return !(__x == __y); }
755 :
756 : /// Based on operator<
757 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
758 : inline bool
759 : operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
760 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
761 : { return __y < __x; }
762 :
763 : /// Based on operator<
764 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
765 : inline bool
766 : operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
767 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
768 : { return !(__y < __x); }
769 :
770 : /// Based on operator<
771 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
772 : inline bool
773 : operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
774 : const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
775 : { return !(__x < __y); }
776 :
777 : /// See std::multimap::swap().
778 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
779 : inline void
780 : swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
781 : multimap<_Key, _Tp, _Compare, _Alloc>& __y)
782 : { __x.swap(__y); }
783 :
784 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
785 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
786 : inline void
787 : swap(multimap<_Key, _Tp, _Compare, _Alloc>&& __x,
788 : multimap<_Key, _Tp, _Compare, _Alloc>& __y)
789 : { __x.swap(__y); }
790 :
791 : template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
792 : inline void
793 : swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
794 : multimap<_Key, _Tp, _Compare, _Alloc>&& __y)
795 : { __x.swap(__y); }
796 : #endif
797 :
798 : _GLIBCXX_END_NESTED_NAMESPACE
799 :
800 : #endif /* _STL_MULTIMAP_H */
|
