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