Branch data 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 : 6 : 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 : 3 : set()
140 : 3 : : _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 : 0 : begin() const _GLIBCXX_NOEXCEPT
299 : 0 : { 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 : 2 : end() const _GLIBCXX_NOEXCEPT
308 : 2 : { 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 : 1 : insert(const value_type& __x)
461 : : {
462 : : std::pair<typename _Rep_type::iterator, bool> __p =
463 [ + - ]: 1 : _M_t._M_insert_unique(__x);
464 : 1 : 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 : 0 : count(const key_type& __x) const
645 [ # # ][ # # ]: 0 : { 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 : : { return _M_t.find(__x); }
664 : :
665 : : const_iterator
666 : 2 : find(const key_type& __x) const
667 : 2 : { 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 */
|