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