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