Branch data Line data Source code
1 : : // Set implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 : : // 2011 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_set.h
53 : : * This is an internal header file, included by other library headers.
54 : : * Do not attempt to use it directly. @headername{set}
55 : : */
56 : :
57 : : #ifndef _STL_SET_H
58 : : #define _STL_SET_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 unique keys, which can be
71 : : * retrieved 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 unique keys).
78 : : *
79 : : * Sets support bidirectional iterators.
80 : : *
81 : : * @tparam _Key Type of key objects.
82 : : * @tparam _Compare Comparison function object type, defaults to less<Key>.
83 : : * @tparam _Alloc Allocator type, defaults to allocator<Key>.
84 : : *
85 : : * The private tree data is declared exactly the same way for set and
86 : : * multiset; the distinction is made entirely in how the tree functions are
87 : : * called (*_unique versus *_equal, same as the standard).
88 : : */
89 : : template<typename _Key, typename _Compare = std::less<_Key>,
90 : : typename _Alloc = std::allocator<_Key> >
91 : 9176031 : class set
92 : : {
93 : : // concept requirements
94 : : typedef typename _Alloc::value_type _Alloc_value_type;
95 : : __glibcxx_class_requires(_Key, _SGIAssignableConcept)
96 : : __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
97 : : _BinaryFunctionConcept)
98 : : __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
99 : :
100 : : public:
101 : : // typedefs:
102 : : //@{
103 : : /// Public typedefs.
104 : : typedef _Key key_type;
105 : : typedef _Key value_type;
106 : : typedef _Compare key_compare;
107 : : typedef _Compare value_compare;
108 : : typedef _Alloc allocator_type;
109 : : //@}
110 : :
111 : : private:
112 : : typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
113 : :
114 : : typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
115 : : key_compare, _Key_alloc_type> _Rep_type;
116 : : _Rep_type _M_t; // Red-black tree representing set.
117 : :
118 : : public:
119 : : //@{
120 : : /// Iterator-related typedefs.
121 : : typedef typename _Key_alloc_type::pointer pointer;
122 : : typedef typename _Key_alloc_type::const_pointer const_pointer;
123 : : typedef typename _Key_alloc_type::reference reference;
124 : : typedef typename _Key_alloc_type::const_reference const_reference;
125 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
126 : : // DR 103. set::iterator is required to be modifiable,
127 : : // but this allows modification of keys.
128 : : typedef typename _Rep_type::const_iterator iterator;
129 : : typedef typename _Rep_type::const_iterator const_iterator;
130 : : typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
131 : : typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
132 : : typedef typename _Rep_type::size_type size_type;
133 : : typedef typename _Rep_type::difference_type difference_type;
134 : : //@}
135 : :
136 : : // allocation/deallocation
137 : : /**
138 : : * @brief Default constructor creates no elements.
139 : : */
140 : 9604974 : set()
141 : 9604974 : : _M_t() { }
142 : :
143 : : /**
144 : : * @brief Creates a %set with no elements.
145 : : * @param __comp Comparator to use.
146 : : * @param __a An allocator object.
147 : : */
148 : : explicit
149 : : set(const _Compare& __comp,
150 : : const allocator_type& __a = allocator_type())
151 : : : _M_t(__comp, _Key_alloc_type(__a)) { }
152 : :
153 : : /**
154 : : * @brief Builds a %set from a range.
155 : : * @param __first An input iterator.
156 : : * @param __last An input iterator.
157 : : *
158 : : * Create a %set consisting of copies of the elements from
159 : : * [__first,__last). This is linear in N if the range is
160 : : * already sorted, and NlogN otherwise (where N is
161 : : * distance(__first,__last)).
162 : : */
163 : : template<typename _InputIterator>
164 : 153 : set(_InputIterator __first, _InputIterator __last)
165 : 153 : : _M_t()
166 [ + - ]: 153 : { _M_t._M_insert_unique(__first, __last); }
167 : :
168 : : /**
169 : : * @brief Builds a %set from a range.
170 : : * @param __first An input iterator.
171 : : * @param __last An input iterator.
172 : : * @param __comp A comparison functor.
173 : : * @param __a An allocator object.
174 : : *
175 : : * Create a %set consisting of copies of the elements from
176 : : * [__first,__last). This is linear in N if the range is
177 : : * already sorted, and NlogN otherwise (where N is
178 : : * distance(__first,__last)).
179 : : */
180 : : template<typename _InputIterator>
181 : : set(_InputIterator __first, _InputIterator __last,
182 : : const _Compare& __comp,
183 : : const allocator_type& __a = allocator_type())
184 : : : _M_t(__comp, _Key_alloc_type(__a))
185 : : { _M_t._M_insert_unique(__first, __last); }
186 : :
187 : : /**
188 : : * @brief %Set copy constructor.
189 : : * @param __x A %set of identical element and allocator types.
190 : : *
191 : : * The newly-created %set uses a copy of the allocation object used
192 : : * by @a __x.
193 : : */
194 : 10942 : set(const set& __x)
195 : 10942 : : _M_t(__x._M_t) { }
196 : :
197 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
198 : : /**
199 : : * @brief %Set move constructor
200 : : * @param __x A %set of identical element and allocator types.
201 : : *
202 : : * The newly-created %set contains the exact contents of @a x.
203 : : * The contents of @a x are a valid, but unspecified %set.
204 : : */
205 : : set(set&& __x)
206 : : noexcept(is_nothrow_copy_constructible<_Compare>::value)
207 : : : _M_t(std::move(__x._M_t)) { }
208 : :
209 : : /**
210 : : * @brief Builds a %set from an initializer_list.
211 : : * @param __l An initializer_list.
212 : : * @param __comp A comparison functor.
213 : : * @param __a An allocator object.
214 : : *
215 : : * Create a %set consisting of copies of the elements in the list.
216 : : * This is linear in N if the list is already sorted, and NlogN
217 : : * otherwise (where N is @a __l.size()).
218 : : */
219 : : set(initializer_list<value_type> __l,
220 : : const _Compare& __comp = _Compare(),
221 : : const allocator_type& __a = allocator_type())
222 : : : _M_t(__comp, _Key_alloc_type(__a))
223 : : { _M_t._M_insert_unique(__l.begin(), __l.end()); }
224 : : #endif
225 : :
226 : : /**
227 : : * @brief %Set assignment operator.
228 : : * @param __x A %set of identical element and allocator types.
229 : : *
230 : : * All the elements of @a __x are copied, but unlike the copy
231 : : * constructor, the allocator object is not copied.
232 : : */
233 : : set&
234 : 331501 : operator=(const set& __x)
235 : : {
236 : 331501 : _M_t = __x._M_t;
237 : 331501 : return *this;
238 : : }
239 : :
240 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
241 : : /**
242 : : * @brief %Set move assignment operator.
243 : : * @param __x A %set of identical element and allocator types.
244 : : *
245 : : * The contents of @a __x are moved into this %set (without copying).
246 : : * @a __x is a valid, but unspecified %set.
247 : : */
248 : : set&
249 : : operator=(set&& __x)
250 : : {
251 : : // NB: DR 1204.
252 : : // NB: DR 675.
253 : : this->clear();
254 : : this->swap(__x);
255 : : return *this;
256 : : }
257 : :
258 : : /**
259 : : * @brief %Set list assignment operator.
260 : : * @param __l An initializer_list.
261 : : *
262 : : * This function fills a %set with copies of the elements in the
263 : : * initializer list @a __l.
264 : : *
265 : : * Note that the assignment completely changes the %set and
266 : : * that the resulting %set's size is the same as the number
267 : : * of elements assigned. Old data may be lost.
268 : : */
269 : : set&
270 : : operator=(initializer_list<value_type> __l)
271 : : {
272 : : this->clear();
273 : : this->insert(__l.begin(), __l.end());
274 : : return *this;
275 : : }
276 : : #endif
277 : :
278 : : // accessors:
279 : :
280 : : /// Returns the comparison object with which the %set was constructed.
281 : : key_compare
282 : : key_comp() const
283 : : { return _M_t.key_comp(); }
284 : : /// Returns the comparison object with which the %set was constructed.
285 : : value_compare
286 : : value_comp() const
287 : : { return _M_t.key_comp(); }
288 : : /// Returns the allocator object with which the %set was constructed.
289 : : allocator_type
290 : : get_allocator() const _GLIBCXX_NOEXCEPT
291 : : { return allocator_type(_M_t.get_allocator()); }
292 : :
293 : : /**
294 : : * Returns a read-only (constant) iterator that points to the first
295 : : * element in the %set. Iteration is done in ascending order according
296 : : * to the keys.
297 : : */
298 : : iterator
299 : 5000167 : begin() const _GLIBCXX_NOEXCEPT
300 : 5000167 : { return _M_t.begin(); }
301 : :
302 : : /**
303 : : * Returns a read-only (constant) iterator that points one past the last
304 : : * element in the %set. Iteration is done in ascending order according
305 : : * to the keys.
306 : : */
307 : : iterator
308 : 16885608 : end() const _GLIBCXX_NOEXCEPT
309 : 16885608 : { return _M_t.end(); }
310 : :
311 : : /**
312 : : * Returns a read-only (constant) iterator that points to the last
313 : : * element in the %set. Iteration is done in descending order according
314 : : * to the keys.
315 : : */
316 : : reverse_iterator
317 : : rbegin() const _GLIBCXX_NOEXCEPT
318 : : { return _M_t.rbegin(); }
319 : :
320 : : /**
321 : : * Returns a read-only (constant) reverse iterator that points to the
322 : : * last pair in the %set. Iteration is done in descending order
323 : : * according to the keys.
324 : : */
325 : : reverse_iterator
326 : : rend() const _GLIBCXX_NOEXCEPT
327 : : { return _M_t.rend(); }
328 : :
329 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
330 : : /**
331 : : * Returns a read-only (constant) iterator that points to the first
332 : : * element in the %set. Iteration is done in ascending order according
333 : : * to the keys.
334 : : */
335 : : iterator
336 : : cbegin() const noexcept
337 : : { return _M_t.begin(); }
338 : :
339 : : /**
340 : : * Returns a read-only (constant) iterator that points one past the last
341 : : * element in the %set. Iteration is done in ascending order according
342 : : * to the keys.
343 : : */
344 : : iterator
345 : : cend() const noexcept
346 : : { return _M_t.end(); }
347 : :
348 : : /**
349 : : * Returns a read-only (constant) iterator that points to the last
350 : : * element in the %set. Iteration is done in descending order according
351 : : * to the keys.
352 : : */
353 : : reverse_iterator
354 : : crbegin() const noexcept
355 : : { return _M_t.rbegin(); }
356 : :
357 : : /**
358 : : * Returns a read-only (constant) reverse iterator that points to the
359 : : * last pair in the %set. Iteration is done in descending order
360 : : * according to the keys.
361 : : */
362 : : reverse_iterator
363 : : crend() const noexcept
364 : : { return _M_t.rend(); }
365 : : #endif
366 : :
367 : : /// Returns true if the %set is empty.
368 : : bool
369 : 2139968 : empty() const _GLIBCXX_NOEXCEPT
370 : 2139968 : { return _M_t.empty(); }
371 : :
372 : : /// Returns the size of the %set.
373 : : size_type
374 : 76173 : size() const _GLIBCXX_NOEXCEPT
375 : 76173 : { return _M_t.size(); }
376 : :
377 : : /// Returns the maximum size of the %set.
378 : : size_type
379 : : max_size() const _GLIBCXX_NOEXCEPT
380 : : { return _M_t.max_size(); }
381 : :
382 : : /**
383 : : * @brief Swaps data with another %set.
384 : : * @param __x A %set of the same element and allocator types.
385 : : *
386 : : * This exchanges the elements between two sets in constant
387 : : * time. (It is only swapping a pointer, an integer, and an
388 : : * instance of the @c Compare type (which itself is often
389 : : * stateless and empty), so it should be quite fast.) Note
390 : : * that the global std::swap() function is specialized such
391 : : * that std::swap(s1,s2) will feed to this function.
392 : : */
393 : : void
394 : : swap(set& __x)
395 : : { _M_t.swap(__x._M_t); }
396 : :
397 : : // insert/erase
398 : : /**
399 : : * @brief Attempts to insert an element into the %set.
400 : : * @param __x Element to be inserted.
401 : : * @return A pair, of which the first element is an iterator that points
402 : : * to the possibly inserted element, and the second is a bool
403 : : * that is true if the element was actually inserted.
404 : : *
405 : : * This function attempts to insert an element into the %set. A %set
406 : : * relies on unique keys and thus an element is only inserted if it is
407 : : * not already present in the %set.
408 : : *
409 : : * Insertion requires logarithmic time.
410 : : */
411 : : std::pair<iterator, bool>
412 : 103524182 : insert(const value_type& __x)
413 : : {
414 : : std::pair<typename _Rep_type::iterator, bool> __p =
415 [ + - ][ + - ]: 103524182 : _M_t._M_insert_unique(__x);
[ + - ][ + - ]
[ # # ]
416 : 103524182 : return std::pair<iterator, bool>(__p.first, __p.second);
417 : : }
418 : :
419 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
420 : : std::pair<iterator, bool>
421 : : insert(value_type&& __x)
422 : : {
423 : : std::pair<typename _Rep_type::iterator, bool> __p =
424 : : _M_t._M_insert_unique(std::move(__x));
425 : : return std::pair<iterator, bool>(__p.first, __p.second);
426 : : }
427 : : #endif
428 : :
429 : : /**
430 : : * @brief Attempts to insert an element into the %set.
431 : : * @param __position An iterator that serves as a hint as to where the
432 : : * element should be inserted.
433 : : * @param __x Element to be inserted.
434 : : * @return An iterator that points to the element with key of
435 : : * @a __x (may or may not be the element passed in).
436 : : *
437 : : * This function is not concerned about whether the insertion took place,
438 : : * and thus does not return a boolean like the single-argument insert()
439 : : * does. Note that the first parameter is only a hint and can
440 : : * potentially improve the performance of the insertion process. A bad
441 : : * hint would cause no gains in efficiency.
442 : : *
443 : : * For more on @a hinting, see:
444 : : * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
445 : : *
446 : : * Insertion requires logarithmic time (if the hint is not taken).
447 : : */
448 : : iterator
449 : 1358432 : insert(const_iterator __position, const value_type& __x)
450 : 1358432 : { return _M_t._M_insert_unique_(__position, __x); }
451 : :
452 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
453 : : iterator
454 : : insert(const_iterator __position, value_type&& __x)
455 : : { return _M_t._M_insert_unique_(__position, std::move(__x)); }
456 : : #endif
457 : :
458 : : /**
459 : : * @brief A template function that attempts to insert a range
460 : : * of elements.
461 : : * @param __first Iterator pointing to the start of the range to be
462 : : * inserted.
463 : : * @param __last Iterator pointing to the end of the range.
464 : : *
465 : : * Complexity similar to that of the range constructor.
466 : : */
467 : : template<typename _InputIterator>
468 : : void
469 : 2233597 : insert(_InputIterator __first, _InputIterator __last)
470 : 2233597 : { _M_t._M_insert_unique(__first, __last); }
471 : :
472 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
473 : : /**
474 : : * @brief Attempts to insert a list of elements into the %set.
475 : : * @param __l A std::initializer_list<value_type> of elements
476 : : * to be inserted.
477 : : *
478 : : * Complexity similar to that of the range constructor.
479 : : */
480 : : void
481 : : insert(initializer_list<value_type> __l)
482 : : { this->insert(__l.begin(), __l.end()); }
483 : : #endif
484 : :
485 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
486 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
487 : : // DR 130. Associative erase should return an iterator.
488 : : /**
489 : : * @brief Erases an element from a %set.
490 : : * @param __position An iterator pointing to the element to be erased.
491 : : * @return An iterator pointing to the element immediately following
492 : : * @a __position prior to the element being erased. If no such
493 : : * element exists, end() is returned.
494 : : *
495 : : * This function erases an element, pointed to by the given iterator,
496 : : * from a %set. Note that this function only erases the element, and
497 : : * that if the element is itself a pointer, the pointed-to memory is not
498 : : * touched in any way. Managing the pointer is the user's
499 : : * responsibility.
500 : : */
501 : : iterator
502 : : erase(const_iterator __position)
503 : : { return _M_t.erase(__position); }
504 : : #else
505 : : /**
506 : : * @brief Erases an element from a %set.
507 : : * @param position An iterator pointing to the element to be erased.
508 : : *
509 : : * This function erases an element, pointed to by the given iterator,
510 : : * from a %set. Note that this function only erases the element, and
511 : : * that if the element is itself a pointer, the pointed-to memory is not
512 : : * touched in any way. Managing the pointer is the user's
513 : : * responsibility.
514 : : */
515 : : void
516 : : erase(iterator __position)
517 : : { _M_t.erase(__position); }
518 : : #endif
519 : :
520 : : /**
521 : : * @brief Erases elements according to the provided key.
522 : : * @param __x Key of element to be erased.
523 : : * @return The number of elements erased.
524 : : *
525 : : * This function erases all the elements located by the given key from
526 : : * a %set.
527 : : * Note that this function only erases the element, and that if
528 : : * the element is itself a pointer, the pointed-to memory is not touched
529 : : * in any way. Managing the pointer is the user's responsibility.
530 : : */
531 : : size_type
532 : 4371 : erase(const key_type& __x)
533 : 4371 : { return _M_t.erase(__x); }
534 : :
535 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
536 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
537 : : // DR 130. Associative erase should return an iterator.
538 : : /**
539 : : * @brief Erases a [__first,__last) range of elements from a %set.
540 : : * @param __first Iterator pointing to the start of the range to be
541 : : * erased.
542 : :
543 : : * @param __last Iterator pointing to the end of the range to
544 : : * be erased.
545 : : * @return The iterator @a __last.
546 : : *
547 : : * This function erases a sequence of elements from a %set.
548 : : * Note that this function only erases the element, and that if
549 : : * the element is itself a pointer, the pointed-to memory is not touched
550 : : * in any way. Managing the pointer is the user's responsibility.
551 : : */
552 : : iterator
553 : : erase(const_iterator __first, const_iterator __last)
554 : : { return _M_t.erase(__first, __last); }
555 : : #else
556 : : /**
557 : : * @brief Erases a [first,last) range of elements from a %set.
558 : : * @param __first Iterator pointing to the start of the range to be
559 : : * erased.
560 : : * @param __last Iterator pointing to the end of the range to
561 : : * be erased.
562 : : *
563 : : * This function erases a sequence of elements from a %set.
564 : : * Note that this function only erases the element, and that if
565 : : * the element is itself a pointer, the pointed-to memory is not touched
566 : : * in any way. Managing the pointer is the user's responsibility.
567 : : */
568 : : void
569 : : erase(iterator __first, iterator __last)
570 : : { _M_t.erase(__first, __last); }
571 : : #endif
572 : :
573 : : /**
574 : : * Erases all elements in a %set. Note that this function only erases
575 : : * the elements, and that if the elements themselves are pointers, the
576 : : * pointed-to memory is not touched in any way. Managing the pointer is
577 : : * the user's responsibility.
578 : : */
579 : : void
580 : 1346490 : clear() _GLIBCXX_NOEXCEPT
581 : 1346490 : { _M_t.clear(); }
582 : :
583 : : // set operations:
584 : :
585 : : /**
586 : : * @brief Finds the number of elements.
587 : : * @param __x Element to located.
588 : : * @return Number of elements with specified key.
589 : : *
590 : : * This function only makes sense for multisets; for set the result will
591 : : * either be 0 (not present) or 1 (present).
592 : : */
593 : : size_type
594 : 98134651 : count(const key_type& __x) const
595 [ + - ][ + + ]: 98134651 : { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
596 : :
597 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
598 : : // 214. set::find() missing const overload
599 : : //@{
600 : : /**
601 : : * @brief Tries to locate an element in a %set.
602 : : * @param __x Element to be located.
603 : : * @return Iterator pointing to sought-after element, or end() if not
604 : : * found.
605 : : *
606 : : * This function takes a key and tries to locate the element with which
607 : : * the key matches. If successful the function returns an iterator
608 : : * pointing to the sought after element. If unsuccessful it returns the
609 : : * past-the-end ( @c end() ) iterator.
610 : : */
611 : : iterator
612 : 10900384 : find(const key_type& __x)
613 : 10900384 : { return _M_t.find(__x); }
614 : :
615 : : const_iterator
616 : 1835033 : find(const key_type& __x) const
617 : 1835033 : { return _M_t.find(__x); }
618 : : //@}
619 : :
620 : : //@{
621 : : /**
622 : : * @brief Finds the beginning of a subsequence matching given key.
623 : : * @param __x Key to be located.
624 : : * @return Iterator pointing to first element equal to or greater
625 : : * than key, or end().
626 : : *
627 : : * This function returns the first element of a subsequence of elements
628 : : * that matches the given key. If unsuccessful it returns an iterator
629 : : * pointing to the first element that has a greater value than given key
630 : : * or end() if no such element exists.
631 : : */
632 : : iterator
633 : : lower_bound(const key_type& __x)
634 : : { return _M_t.lower_bound(__x); }
635 : :
636 : : const_iterator
637 : : lower_bound(const key_type& __x) const
638 : : { return _M_t.lower_bound(__x); }
639 : : //@}
640 : :
641 : : //@{
642 : : /**
643 : : * @brief Finds the end of a subsequence matching given key.
644 : : * @param __x Key to be located.
645 : : * @return Iterator pointing to the first element
646 : : * greater than key, or end().
647 : : */
648 : : iterator
649 : : upper_bound(const key_type& __x)
650 : : { return _M_t.upper_bound(__x); }
651 : :
652 : : const_iterator
653 : : upper_bound(const key_type& __x) const
654 : : { return _M_t.upper_bound(__x); }
655 : : //@}
656 : :
657 : : //@{
658 : : /**
659 : : * @brief Finds a subsequence matching given key.
660 : : * @param __x Key to be located.
661 : : * @return Pair of iterators that possibly points to the subsequence
662 : : * matching given key.
663 : : *
664 : : * This function is equivalent to
665 : : * @code
666 : : * std::make_pair(c.lower_bound(val),
667 : : * c.upper_bound(val))
668 : : * @endcode
669 : : * (but is faster than making the calls separately).
670 : : *
671 : : * This function probably only makes sense for multisets.
672 : : */
673 : : std::pair<iterator, iterator>
674 : : equal_range(const key_type& __x)
675 : : { return _M_t.equal_range(__x); }
676 : :
677 : : std::pair<const_iterator, const_iterator>
678 : : equal_range(const key_type& __x) const
679 : : { return _M_t.equal_range(__x); }
680 : : //@}
681 : :
682 : : template<typename _K1, typename _C1, typename _A1>
683 : : friend bool
684 : : operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
685 : :
686 : : template<typename _K1, typename _C1, typename _A1>
687 : : friend bool
688 : : operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
689 : : };
690 : :
691 : :
692 : : /**
693 : : * @brief Set equality comparison.
694 : : * @param __x A %set.
695 : : * @param __y A %set of the same type as @a x.
696 : : * @return True iff the size and elements of the sets are equal.
697 : : *
698 : : * This is an equivalence relation. It is linear in the size of the sets.
699 : : * Sets are considered equivalent if their sizes are equal, and if
700 : : * corresponding elements compare equal.
701 : : */
702 : : template<typename _Key, typename _Compare, typename _Alloc>
703 : : inline bool
704 : 766 : operator==(const set<_Key, _Compare, _Alloc>& __x,
705 : : const set<_Key, _Compare, _Alloc>& __y)
706 : 766 : { return __x._M_t == __y._M_t; }
707 : :
708 : : /**
709 : : * @brief Set ordering relation.
710 : : * @param __x A %set.
711 : : * @param __y A %set of the same type as @a x.
712 : : * @return True iff @a __x is lexicographically less than @a __y.
713 : : *
714 : : * This is a total ordering relation. It is linear in the size of the
715 : : * maps. The elements must be comparable with @c <.
716 : : *
717 : : * See std::lexicographical_compare() for how the determination is made.
718 : : */
719 : : template<typename _Key, typename _Compare, typename _Alloc>
720 : : inline bool
721 : : operator<(const set<_Key, _Compare, _Alloc>& __x,
722 : : const set<_Key, _Compare, _Alloc>& __y)
723 : : { return __x._M_t < __y._M_t; }
724 : :
725 : : /// Returns !(x == y).
726 : : template<typename _Key, typename _Compare, typename _Alloc>
727 : : inline bool
728 : : operator!=(const set<_Key, _Compare, _Alloc>& __x,
729 : : const set<_Key, _Compare, _Alloc>& __y)
730 : : { return !(__x == __y); }
731 : :
732 : : /// Returns y < x.
733 : : template<typename _Key, typename _Compare, typename _Alloc>
734 : : inline bool
735 : : operator>(const set<_Key, _Compare, _Alloc>& __x,
736 : : const set<_Key, _Compare, _Alloc>& __y)
737 : : { return __y < __x; }
738 : :
739 : : /// Returns !(y < x)
740 : : template<typename _Key, typename _Compare, typename _Alloc>
741 : : inline bool
742 : : operator<=(const set<_Key, _Compare, _Alloc>& __x,
743 : : const set<_Key, _Compare, _Alloc>& __y)
744 : : { return !(__y < __x); }
745 : :
746 : : /// Returns !(x < y)
747 : : template<typename _Key, typename _Compare, typename _Alloc>
748 : : inline bool
749 : : operator>=(const set<_Key, _Compare, _Alloc>& __x,
750 : : const set<_Key, _Compare, _Alloc>& __y)
751 : : { return !(__x < __y); }
752 : :
753 : : /// See std::set::swap().
754 : : template<typename _Key, typename _Compare, typename _Alloc>
755 : : inline void
756 : : swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y)
757 : : { __x.swap(__y); }
758 : :
759 : : _GLIBCXX_END_NAMESPACE_CONTAINER
760 : : } //namespace std
761 : : #endif /* _STL_SET_H */
|
