]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Map implementation -*- C++ -*- |
2 | ||
f6592a9e | 3 | // Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc. |
42526146 PE |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 2, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
18 | // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
19 | // USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
725dc051 BK |
30 | /* |
31 | * | |
32 | * Copyright (c) 1994 | |
33 | * Hewlett-Packard Company | |
34 | * | |
35 | * Permission to use, copy, modify, distribute and sell this software | |
36 | * and its documentation for any purpose is hereby granted without fee, | |
37 | * provided that the above copyright notice appear in all copies and | |
38 | * that both that copyright notice and this permission notice appear | |
39 | * in supporting documentation. Hewlett-Packard Company makes no | |
40 | * representations about the suitability of this software for any | |
41 | * purpose. It is provided "as is" without express or implied warranty. | |
42 | * | |
43 | * | |
44 | * Copyright (c) 1996,1997 | |
45 | * Silicon Graphics Computer Systems, Inc. | |
46 | * | |
47 | * Permission to use, copy, modify, distribute and sell this software | |
48 | * and its documentation for any purpose is hereby granted without fee, | |
49 | * provided that the above copyright notice appear in all copies and | |
50 | * that both that copyright notice and this permission notice appear | |
51 | * in supporting documentation. Silicon Graphics makes no | |
52 | * representations about the suitability of this software for any | |
53 | * purpose. It is provided "as is" without express or implied warranty. | |
54 | */ | |
55 | ||
729e3d3f PE |
56 | /** @file stl_map.h |
57 | * This is an internal header file, included by other library headers. | |
58 | * You should not attempt to use it directly. | |
725dc051 BK |
59 | */ |
60 | ||
3d7c150e BK |
61 | #ifndef _MAP_H |
62 | #define _MAP_H 1 | |
725dc051 | 63 | |
30a20a1e | 64 | #include <bits/concept_check.h> |
725dc051 | 65 | |
285b36d6 | 66 | namespace __gnu_norm |
d53d7f6e | 67 | { |
224a45d0 | 68 | /** |
3971a4d2 PE |
69 | * @brief A standard container made up of (key,value) pairs, which can be |
70 | * retrieved based on a key, in logarithmic time. | |
224a45d0 | 71 | * |
3971a4d2 PE |
72 | * @ingroup Containers |
73 | * @ingroup Assoc_containers | |
224a45d0 | 74 | * |
3971a4d2 PE |
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 unique keys). | |
78 | * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the | |
79 | * value_type is std::pair<const Key,T>. | |
224a45d0 | 80 | * |
3971a4d2 | 81 | * Maps support bidirectional iterators. |
224a45d0 | 82 | * |
3971a4d2 PE |
83 | * @if maint |
84 | * The private tree data is declared exactly the same way for map and | |
85 | * multimap; the distinction is made entirely in how the tree functions are | |
86 | * called (*_unique versus *_equal, same as the standard). | |
87 | * @endif | |
88 | */ | |
89 | template <typename _Key, typename _Tp, typename _Compare = less<_Key>, | |
90 | typename _Alloc = allocator<pair<const _Key, _Tp> > > | |
91 | class map | |
f6592a9e PC |
92 | { |
93 | // concept requirements | |
94 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) | |
95 | __glibcxx_class_requires4(_Compare, bool, _Key, _Key, | |
96 | _BinaryFunctionConcept) | |
3971a4d2 | 97 | |
f6592a9e PC |
98 | public: |
99 | typedef _Key key_type; | |
100 | typedef _Tp mapped_type; | |
101 | typedef pair<const _Key, _Tp> value_type; | |
102 | typedef _Compare key_compare; | |
3971a4d2 | 103 | |
f6592a9e | 104 | class value_compare |
3971a4d2 PE |
105 | : public binary_function<value_type, value_type, bool> |
106 | { | |
f6592a9e | 107 | friend class map<_Key,_Tp,_Compare,_Alloc>; |
3971a4d2 | 108 | protected: |
f6592a9e PC |
109 | _Compare comp; |
110 | ||
111 | value_compare(_Compare __c) | |
112 | : comp(__c) { } | |
113 | ||
3971a4d2 | 114 | public: |
f6592a9e PC |
115 | bool operator()(const value_type& __x, const value_type& __y) const |
116 | { return comp(__x.first, __y.first); } | |
3971a4d2 PE |
117 | }; |
118 | ||
f6592a9e PC |
119 | private: |
120 | /// @if maint This turns a red-black tree into a [multi]map. @endif | |
121 | typedef _Rb_tree<key_type, value_type, | |
122 | _Select1st<value_type>, key_compare, _Alloc> _Rep_type; | |
123 | /// @if maint The actual tree structure. @endif | |
124 | _Rep_type _M_t; | |
125 | ||
126 | public: | |
127 | // many of these are specified differently in ISO, but the following are | |
128 | // "functionally equivalent" | |
129 | typedef typename _Rep_type::allocator_type allocator_type; | |
130 | typedef typename _Rep_type::reference reference; | |
131 | typedef typename _Rep_type::const_reference const_reference; | |
132 | typedef typename _Rep_type::iterator iterator; | |
133 | typedef typename _Rep_type::const_iterator const_iterator; | |
134 | typedef typename _Rep_type::size_type size_type; | |
135 | typedef typename _Rep_type::difference_type difference_type; | |
136 | typedef typename _Rep_type::pointer pointer; | |
137 | typedef typename _Rep_type::const_pointer const_pointer; | |
138 | typedef typename _Rep_type::reverse_iterator reverse_iterator; | |
139 | typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; | |
140 | ||
141 | // [23.3.1.1] construct/copy/destroy | |
142 | // (get_allocator() is normally listed in this section, but seems to have | |
143 | // been accidentally omitted in the printed standard) | |
144 | /** | |
145 | * @brief Default constructor creates no elements. | |
146 | */ | |
147 | map() | |
148 | : _M_t(_Compare(), allocator_type()) { } | |
149 | ||
150 | // for some reason this was made a separate function | |
151 | /** | |
152 | * @brief Default constructor creates no elements. | |
153 | */ | |
154 | explicit | |
155 | map(const _Compare& __comp, const allocator_type& __a = allocator_type()) | |
3971a4d2 PE |
156 | : _M_t(__comp, __a) { } |
157 | ||
f6592a9e PC |
158 | /** |
159 | * @brief Map copy constructor. | |
160 | * @param x A %map of identical element and allocator types. | |
161 | * | |
162 | * The newly-created %map uses a copy of the allocation object used | |
163 | * by @a x. | |
164 | */ | |
165 | map(const map& __x) | |
3971a4d2 PE |
166 | : _M_t(__x._M_t) { } |
167 | ||
f6592a9e PC |
168 | /** |
169 | * @brief Builds a %map from a range. | |
170 | * @param first An input iterator. | |
171 | * @param last An input iterator. | |
172 | * | |
173 | * Create a %map consisting of copies of the elements from [first,last). | |
174 | * This is linear in N if the range is already sorted, and NlogN | |
175 | * otherwise (where N is distance(first,last)). | |
176 | */ | |
177 | template <typename _InputIterator> | |
178 | map(_InputIterator __first, _InputIterator __last) | |
179 | : _M_t(_Compare(), allocator_type()) | |
180 | { _M_t.insert_unique(__first, __last); } | |
181 | ||
182 | /** | |
183 | * @brief Builds a %map from a range. | |
184 | * @param first An input iterator. | |
185 | * @param last An input iterator. | |
186 | * @param comp A comparison functor. | |
187 | * @param a An allocator object. | |
188 | * | |
189 | * Create a %map consisting of copies of the elements from [first,last). | |
190 | * This is linear in N if the range is already sorted, and NlogN | |
191 | * otherwise (where N is distance(first,last)). | |
192 | */ | |
193 | template <typename _InputIterator> | |
194 | map(_InputIterator __first, _InputIterator __last, | |
195 | const _Compare& __comp, const allocator_type& __a = allocator_type()) | |
196 | : _M_t(__comp, __a) | |
197 | { _M_t.insert_unique(__first, __last); } | |
198 | ||
199 | // FIXME There is no dtor declared, but we should have something generated | |
200 | // by Doxygen. I don't know what tags to add to this paragraph to make | |
201 | // that happen: | |
202 | /** | |
203 | * The dtor only erases the elements, and note that if the elements | |
204 | * themselves are pointers, the pointed-to memory is not touched in any | |
205 | * way. Managing the pointer is the user's responsibilty. | |
206 | */ | |
207 | ||
208 | /** | |
209 | * @brief Map assignment operator. | |
210 | * @param x A %map of identical element and allocator types. | |
211 | * | |
212 | * All the elements of @a x are copied, but unlike the copy constructor, | |
213 | * the allocator object is not copied. | |
214 | */ | |
215 | map& | |
216 | operator=(const map& __x) | |
217 | { | |
218 | _M_t = __x._M_t; | |
219 | return *this; | |
220 | } | |
221 | ||
222 | /// Get a copy of the memory allocation object. | |
223 | allocator_type | |
224 | get_allocator() const | |
225 | { return _M_t.get_allocator(); } | |
226 | ||
227 | // iterators | |
228 | /** | |
229 | * Returns a read/write iterator that points to the first pair in the | |
230 | * %map. | |
231 | * Iteration is done in ascending order according to the keys. | |
232 | */ | |
233 | iterator | |
234 | begin() | |
235 | { return _M_t.begin(); } | |
236 | ||
237 | /** | |
238 | * Returns a read-only (constant) iterator that points to the first pair | |
239 | * in the %map. Iteration is done in ascending order according to the | |
240 | * keys. | |
241 | */ | |
242 | const_iterator | |
243 | begin() const | |
244 | { return _M_t.begin(); } | |
245 | ||
246 | /** | |
247 | * Returns a read/write iterator that points one past the last pair in | |
248 | * the %map. Iteration is done in ascending order according to the keys. | |
249 | */ | |
250 | iterator | |
251 | end() | |
252 | { return _M_t.end(); } | |
253 | ||
254 | /** | |
255 | * Returns a read-only (constant) iterator that points one past the last | |
256 | * pair in the %map. Iteration is done in ascending order according to | |
257 | * the keys. | |
258 | */ | |
259 | const_iterator | |
260 | end() const | |
261 | { return _M_t.end(); } | |
262 | ||
263 | /** | |
264 | * Returns a read/write reverse iterator that points to the last pair in | |
265 | * the %map. Iteration is done in descending order according to the | |
266 | * keys. | |
267 | */ | |
268 | reverse_iterator | |
269 | rbegin() | |
270 | { return _M_t.rbegin(); } | |
271 | ||
272 | /** | |
273 | * Returns a read-only (constant) reverse iterator that points to the | |
274 | * last pair in the %map. Iteration is done in descending order | |
275 | * according to the keys. | |
276 | */ | |
277 | const_reverse_iterator | |
278 | rbegin() const | |
279 | { return _M_t.rbegin(); } | |
280 | ||
281 | /** | |
282 | * Returns a read/write reverse iterator that points to one before the | |
283 | * first pair in the %map. Iteration is done in descending order | |
284 | * according to the keys. | |
285 | */ | |
286 | reverse_iterator | |
287 | rend() | |
288 | { return _M_t.rend(); } | |
289 | ||
290 | /** | |
291 | * Returns a read-only (constant) reverse iterator that points to one | |
292 | * before the first pair in the %map. Iteration is done in descending | |
293 | * order according to the keys. | |
294 | */ | |
295 | const_reverse_iterator | |
296 | rend() const | |
297 | { return _M_t.rend(); } | |
298 | ||
299 | // capacity | |
300 | /** Returns true if the %map is empty. (Thus begin() would equal | |
301 | * end().) | |
302 | */ | |
303 | bool | |
304 | empty() const | |
305 | { return _M_t.empty(); } | |
306 | ||
307 | /** Returns the size of the %map. */ | |
308 | size_type | |
309 | size() const | |
310 | { return _M_t.size(); } | |
311 | ||
312 | /** Returns the maximum size of the %map. */ | |
313 | size_type | |
314 | max_size() const | |
315 | { return _M_t.max_size(); } | |
316 | ||
317 | // [23.3.1.2] element access | |
318 | /** | |
319 | * @brief Subscript ( @c [] ) access to %map data. | |
320 | * @param k The key for which data should be retrieved. | |
321 | * @return A reference to the data of the (key,data) %pair. | |
322 | * | |
323 | * Allows for easy lookup with the subscript ( @c [] ) operator. Returns | |
324 | * data associated with the key specified in subscript. If the key does | |
325 | * not exist, a pair with that key is created using default values, which | |
326 | * is then returned. | |
327 | * | |
328 | * Lookup requires logarithmic time. | |
329 | */ | |
330 | mapped_type& | |
331 | operator[](const key_type& __k) | |
332 | { | |
333 | // concept requirements | |
334 | __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) | |
335 | ||
336 | iterator __i = lower_bound(__k); | |
337 | // __i->first is greater than or equivalent to __k. | |
338 | if (__i == end() || key_comp()(__k, (*__i).first)) | |
3971a4d2 | 339 | __i = insert(__i, value_type(__k, mapped_type())); |
f6592a9e PC |
340 | return (*__i).second; |
341 | } | |
342 | ||
343 | // modifiers | |
344 | /** | |
345 | * @brief Attempts to insert a std::pair into the %map. | |
346 | * @param x Pair to be inserted (see std::make_pair for easy creation of | |
347 | * pairs). | |
348 | * @return A pair, of which the first element is an iterator that points | |
349 | * to the possibly inserted pair, and the second is a bool that | |
350 | * is true if the pair was actually inserted. | |
351 | * | |
352 | * This function attempts to insert a (key, value) %pair into the %map. | |
353 | * A %map relies on unique keys and thus a %pair is only inserted if its | |
354 | * first element (the key) is not already present in the %map. | |
355 | * | |
356 | * Insertion requires logarithmic time. | |
357 | */ | |
358 | pair<iterator,bool> | |
359 | insert(const value_type& __x) | |
360 | { return _M_t.insert_unique(__x); } | |
361 | ||
362 | /** | |
363 | * @brief Attempts to insert a std::pair into the %map. | |
364 | * @param position An iterator that serves as a hint as to where the | |
365 | * pair should be inserted. | |
366 | * @param x Pair to be inserted (see std::make_pair for easy creation of | |
367 | * pairs). | |
368 | * @return An iterator that points to the element with key of @a x (may | |
369 | * or may not be the %pair passed in). | |
370 | * | |
371 | * This function is not concerned about whether the insertion took place, | |
372 | * and thus does not return a boolean like the single-argument | |
373 | * insert() does. Note that the first parameter is only a hint and can | |
374 | * potentially improve the performance of the insertion process. A bad | |
375 | * hint would cause no gains in efficiency. | |
376 | * | |
377 | * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4 | |
378 | * for more on "hinting". | |
379 | * | |
380 | * Insertion requires logarithmic time (if the hint is not taken). | |
381 | */ | |
382 | iterator | |
383 | insert(iterator position, const value_type& __x) | |
384 | { return _M_t.insert_unique(position, __x); } | |
385 | ||
386 | /** | |
387 | * @brief A template function that attemps to insert a range of elements. | |
388 | * @param first Iterator pointing to the start of the range to be | |
389 | * inserted. | |
390 | * @param last Iterator pointing to the end of the range. | |
391 | * | |
392 | * Complexity similar to that of the range constructor. | |
393 | */ | |
394 | template <typename _InputIterator> | |
395 | void | |
396 | insert(_InputIterator __first, _InputIterator __last) | |
397 | { _M_t.insert_unique(__first, __last); } | |
398 | ||
399 | /** | |
400 | * @brief Erases an element from a %map. | |
401 | * @param position An iterator pointing to the element to be erased. | |
402 | * | |
403 | * This function erases an element, pointed to by the given iterator, | |
404 | * from a %map. Note that this function only erases the element, and | |
405 | * that if the element is itself a pointer, the pointed-to memory is not | |
406 | * touched in any way. Managing the pointer is the user's responsibilty. | |
407 | */ | |
3971a4d2 | 408 | void |
f6592a9e PC |
409 | erase(iterator __position) |
410 | { _M_t.erase(__position); } | |
411 | ||
412 | /** | |
413 | * @brief Erases elements according to the provided key. | |
414 | * @param x Key of element to be erased. | |
415 | * @return The number of elements erased. | |
416 | * | |
417 | * This function erases all the elements located by the given key from | |
418 | * a %map. | |
419 | * Note that this function only erases the element, and that if | |
420 | * the element is itself a pointer, the pointed-to memory is not touched | |
421 | * in any way. Managing the pointer is the user's responsibilty. | |
422 | */ | |
423 | size_type | |
424 | erase(const key_type& __x) | |
425 | { return _M_t.erase(__x); } | |
426 | ||
427 | /** | |
428 | * @brief Erases a [first,last) range of elements from a %map. | |
429 | * @param first Iterator pointing to the start of the range to be | |
430 | * erased. | |
431 | * @param last Iterator pointing to the end of the range to be erased. | |
432 | * | |
433 | * This function erases a sequence of elements from a %map. | |
434 | * Note that this function only erases the element, and that if | |
435 | * the element is itself a pointer, the pointed-to memory is not touched | |
436 | * in any way. Managing the pointer is the user's responsibilty. | |
437 | */ | |
438 | void | |
439 | erase(iterator __first, iterator __last) | |
440 | { _M_t.erase(__first, __last); } | |
441 | ||
442 | /** | |
443 | * @brief Swaps data with another %map. | |
444 | * @param x A %map of the same element and allocator types. | |
445 | * | |
446 | * This exchanges the elements between two maps in constant time. | |
447 | * (It is only swapping a pointer, an integer, and an instance of | |
448 | * the @c Compare type (which itself is often stateless and empty), so it | |
449 | * should be quite fast.) | |
450 | * Note that the global std::swap() function is specialized such that | |
451 | * std::swap(m1,m2) will feed to this function. | |
452 | */ | |
453 | void | |
454 | swap(map& __x) | |
455 | { _M_t.swap(__x._M_t); } | |
456 | ||
457 | /** | |
458 | * Erases all elements in a %map. Note that this function only erases | |
459 | * the elements, and that if the elements themselves are pointers, the | |
460 | * pointed-to memory is not touched in any way. Managing the pointer is | |
461 | * the user's responsibilty. | |
462 | */ | |
463 | void | |
464 | clear() | |
465 | { _M_t.clear(); } | |
466 | ||
467 | // observers | |
468 | /** | |
469 | * Returns the key comparison object out of which the %map was | |
470 | * constructed. | |
471 | */ | |
472 | key_compare | |
473 | key_comp() const | |
474 | { return _M_t.key_comp(); } | |
475 | ||
476 | /** | |
477 | * Returns a value comparison object, built from the key comparison | |
478 | * object out of which the %map was constructed. | |
479 | */ | |
480 | value_compare | |
481 | value_comp() const | |
482 | { return value_compare(_M_t.key_comp()); } | |
483 | ||
484 | // [23.3.1.3] map operations | |
485 | /** | |
486 | * @brief Tries to locate an element in a %map. | |
487 | * @param x Key of (key, value) %pair to be located. | |
488 | * @return Iterator pointing to sought-after element, or end() if not | |
489 | * found. | |
490 | * | |
491 | * This function takes a key and tries to locate the element with which | |
492 | * the key matches. If successful the function returns an iterator | |
493 | * pointing to the sought after %pair. If unsuccessful it returns the | |
494 | * past-the-end ( @c end() ) iterator. | |
495 | */ | |
496 | iterator | |
497 | find(const key_type& __x) | |
498 | { return _M_t.find(__x); } | |
499 | ||
500 | /** | |
501 | * @brief Tries to locate an element in a %map. | |
502 | * @param x Key of (key, value) %pair to be located. | |
503 | * @return Read-only (constant) iterator pointing to sought-after | |
504 | * element, or end() if not found. | |
505 | * | |
506 | * This function takes a key and tries to locate the element with which | |
507 | * the key matches. If successful the function returns a constant | |
508 | * iterator pointing to the sought after %pair. If unsuccessful it | |
509 | * returns the past-the-end ( @c end() ) iterator. | |
510 | */ | |
511 | const_iterator | |
512 | find(const key_type& __x) const | |
513 | { return _M_t.find(__x); } | |
514 | ||
515 | /** | |
516 | * @brief Finds the number of elements with given key. | |
517 | * @param x Key of (key, value) pairs to be located. | |
518 | * @return Number of elements with specified key. | |
519 | * | |
520 | * This function only makes sense for multimaps; for map the result will | |
521 | * either be 0 (not present) or 1 (present). | |
522 | */ | |
523 | size_type | |
524 | count(const key_type& __x) const | |
525 | { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } | |
526 | ||
527 | /** | |
528 | * @brief Finds the beginning of a subsequence matching given key. | |
529 | * @param x Key of (key, value) pair to be located. | |
530 | * @return Iterator pointing to first element equal to or greater | |
531 | * than key, or end(). | |
532 | * | |
533 | * This function returns the first element of a subsequence of elements | |
534 | * that matches the given key. If unsuccessful it returns an iterator | |
535 | * pointing to the first element that has a greater value than given key | |
536 | * or end() if no such element exists. | |
537 | */ | |
538 | iterator | |
539 | lower_bound(const key_type& __x) | |
540 | { return _M_t.lower_bound(__x); } | |
541 | ||
542 | /** | |
543 | * @brief Finds the beginning of a subsequence matching given key. | |
544 | * @param x Key of (key, value) pair to be located. | |
545 | * @return Read-only (constant) iterator pointing to first element | |
546 | * equal to or greater than key, or end(). | |
547 | * | |
548 | * This function returns the first element of a subsequence of elements | |
549 | * that matches the given key. If unsuccessful it returns an iterator | |
550 | * pointing to the first element that has a greater value than given key | |
551 | * or end() if no such element exists. | |
552 | */ | |
553 | const_iterator | |
554 | lower_bound(const key_type& __x) const | |
555 | { return _M_t.lower_bound(__x); } | |
556 | ||
557 | /** | |
558 | * @brief Finds the end of a subsequence matching given key. | |
559 | * @param x Key of (key, value) pair to be located. | |
560 | * @return Iterator pointing to the first element | |
561 | * greater than key, or end(). | |
562 | */ | |
563 | iterator | |
564 | upper_bound(const key_type& __x) | |
565 | { return _M_t.upper_bound(__x); } | |
566 | ||
567 | /** | |
568 | * @brief Finds the end of a subsequence matching given key. | |
569 | * @param x Key of (key, value) pair to be located. | |
570 | * @return Read-only (constant) iterator pointing to first iterator | |
571 | * greater than key, or end(). | |
572 | */ | |
573 | const_iterator | |
574 | upper_bound(const key_type& __x) const | |
575 | { return _M_t.upper_bound(__x); } | |
576 | ||
577 | /** | |
578 | * @brief Finds a subsequence matching given key. | |
579 | * @param x Key of (key, value) pairs to be located. | |
580 | * @return Pair of iterators that possibly points to the subsequence | |
581 | * matching given key. | |
582 | * | |
583 | * This function is equivalent to | |
584 | * @code | |
585 | * std::make_pair(c.lower_bound(val), | |
586 | * c.upper_bound(val)) | |
587 | * @endcode | |
588 | * (but is faster than making the calls separately). | |
589 | * | |
590 | * This function probably only makes sense for multimaps. | |
591 | */ | |
592 | pair<iterator,iterator> | |
593 | equal_range(const key_type& __x) | |
594 | { return _M_t.equal_range(__x); } | |
595 | ||
596 | /** | |
597 | * @brief Finds a subsequence matching given key. | |
598 | * @param x Key of (key, value) pairs to be located. | |
599 | * @return Pair of read-only (constant) iterators that possibly points | |
600 | * to the subsequence matching given key. | |
601 | * | |
602 | * This function is equivalent to | |
603 | * @code | |
604 | * std::make_pair(c.lower_bound(val), | |
605 | * c.upper_bound(val)) | |
606 | * @endcode | |
607 | * (but is faster than making the calls separately). | |
608 | * | |
609 | * This function probably only makes sense for multimaps. | |
610 | */ | |
611 | pair<const_iterator,const_iterator> | |
612 | equal_range(const key_type& __x) const | |
613 | { return _M_t.equal_range(__x); } | |
614 | ||
615 | template <typename _K1, typename _T1, typename _C1, typename _A1> | |
616 | friend bool operator== (const map<_K1,_T1,_C1,_A1>&, | |
617 | const map<_K1,_T1,_C1,_A1>&); | |
618 | template <typename _K1, typename _T1, typename _C1, typename _A1> | |
619 | friend bool operator< (const map<_K1,_T1,_C1,_A1>&, | |
620 | const map<_K1,_T1,_C1,_A1>&); | |
621 | }; | |
3971a4d2 PE |
622 | |
623 | /** | |
624 | * @brief Map equality comparison. | |
625 | * @param x A %map. | |
626 | * @param y A %map of the same type as @a x. | |
627 | * @return True iff the size and elements of the maps are equal. | |
fd58f127 | 628 | * |
3971a4d2 PE |
629 | * This is an equivalence relation. It is linear in the size of the |
630 | * maps. Maps are considered equivalent if their sizes are equal, | |
631 | * and if corresponding elements compare equal. | |
632 | */ | |
633 | template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> | |
634 | inline bool | |
635 | operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x, | |
636 | const map<_Key,_Tp,_Compare,_Alloc>& __y) | |
637 | { return __x._M_t == __y._M_t; } | |
638 | ||
639 | /** | |
640 | * @brief Map ordering relation. | |
641 | * @param x A %map. | |
642 | * @param y A %map of the same type as @a x. | |
9536ca34 | 643 | * @return True iff @a x is lexicographically less than @a y. |
fd58f127 | 644 | * |
3971a4d2 PE |
645 | * This is a total ordering relation. It is linear in the size of the |
646 | * maps. The elements must be comparable with @c <. | |
fd58f127 | 647 | * |
9536ca34 | 648 | * See std::lexicographical_compare() for how the determination is made. |
3971a4d2 PE |
649 | */ |
650 | template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> | |
651 | inline bool | |
652 | operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x, | |
653 | const map<_Key,_Tp,_Compare,_Alloc>& __y) | |
654 | { return __x._M_t < __y._M_t; } | |
655 | ||
656 | /// Based on operator== | |
657 | template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> | |
658 | inline bool | |
659 | operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x, | |
660 | const map<_Key,_Tp,_Compare,_Alloc>& __y) | |
661 | { return !(__x == __y); } | |
662 | ||
663 | /// Based on operator< | |
664 | template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> | |
665 | inline bool | |
666 | operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x, | |
667 | const map<_Key,_Tp,_Compare,_Alloc>& __y) | |
668 | { return __y < __x; } | |
669 | ||
670 | /// Based on operator< | |
671 | template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> | |
672 | inline bool | |
673 | operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x, | |
674 | const map<_Key,_Tp,_Compare,_Alloc>& __y) | |
675 | { return !(__y < __x); } | |
676 | ||
677 | /// Based on operator< | |
678 | template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> | |
679 | inline bool | |
680 | operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x, | |
681 | const map<_Key,_Tp,_Compare,_Alloc>& __y) | |
682 | { return !(__x < __y); } | |
683 | ||
684 | /// See std::map::swap(). | |
685 | template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> | |
686 | inline void | |
687 | swap(map<_Key,_Tp,_Compare,_Alloc>& __x, map<_Key,_Tp,_Compare,_Alloc>& __y) | |
688 | { __x.swap(__y); } | |
285b36d6 | 689 | } // namespace __gnu_norm |
725dc051 | 690 | |
3d7c150e | 691 | #endif /* _MAP_H */ |