1 // Set implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 // Free Software Foundation, Inc.
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 2, or (at your option)
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.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
34 * Hewlett-Packard Company
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
45 * Copyright (c) 1996,1997
46 * Silicon Graphics Computer Systems, Inc.
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Silicon Graphics makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
58 * This is an internal header file, included by other library headers.
59 * You should not attempt to use it directly.
65 #include <bits/concept_check.h>
67 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
70 * @brief A standard container made up of unique keys, which can be
71 * retrieved in logarithmic time.
74 * @ingroup Assoc_containers
76 * Meets the requirements of a <a href="tables.html#65">container</a>, a
77 * <a href="tables.html#66">reversible container</a>, and an
78 * <a href="tables.html#69">associative container</a> (using unique keys).
80 * Sets support bidirectional iterators.
82 * @param Key Type of key objects.
83 * @param Compare Comparison function object type, defaults to less<Key>.
84 * @param Alloc Allocator type, defaults to allocator<Key>.
87 * The private tree data is declared exactly the same way for set and
88 * multiset; the distinction is made entirely in how the tree functions are
89 * called (*_unique versus *_equal, same as the standard).
92 template<typename _Key, typename _Compare = std::less<_Key>,
93 typename _Alloc = std::allocator<_Key> >
96 // concept requirements
97 typedef typename _Alloc::value_type _Alloc_value_type;
98 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
99 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
100 _BinaryFunctionConcept)
101 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
107 typedef _Key key_type;
108 typedef _Key value_type;
109 typedef _Compare key_compare;
110 typedef _Compare value_compare;
111 typedef _Alloc allocator_type;
115 typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
117 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
118 key_compare, _Key_alloc_type> _Rep_type;
119 _Rep_type _M_t; // red-black tree representing set
123 /// Iterator-related typedefs.
124 typedef typename _Key_alloc_type::pointer pointer;
125 typedef typename _Key_alloc_type::const_pointer const_pointer;
126 typedef typename _Key_alloc_type::reference reference;
127 typedef typename _Key_alloc_type::const_reference const_reference;
128 // _GLIBCXX_RESOLVE_LIB_DEFECTS
129 // DR 103. set::iterator is required to be modifiable,
130 // but this allows modification of keys.
131 typedef typename _Rep_type::const_iterator iterator;
132 typedef typename _Rep_type::const_iterator const_iterator;
133 typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
134 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
135 typedef typename _Rep_type::size_type size_type;
136 typedef typename _Rep_type::difference_type difference_type;
139 // allocation/deallocation
141 * @brief Default constructor creates no elements.
147 * @brief Creates a %set with no elements.
148 * @param comp Comparator to use.
149 * @param a An allocator object.
152 set(const _Compare& __comp,
153 const allocator_type& __a = allocator_type())
154 : _M_t(__comp, __a) { }
157 * @brief Builds a %set from a range.
158 * @param first An input iterator.
159 * @param last An input iterator.
161 * Create a %set consisting of copies of the elements from [first,last).
162 * This is linear in N if the range is already sorted, and NlogN
163 * otherwise (where N is distance(first,last)).
165 template<typename _InputIterator>
166 set(_InputIterator __first, _InputIterator __last)
168 { _M_t._M_insert_unique(__first, __last); }
171 * @brief Builds a %set from a range.
172 * @param first An input iterator.
173 * @param last An input iterator.
174 * @param comp A comparison functor.
175 * @param a An allocator object.
177 * Create a %set consisting of copies of the elements from [first,last).
178 * This is linear in N if the range is already sorted, and NlogN
179 * otherwise (where N is distance(first,last)).
181 template<typename _InputIterator>
182 set(_InputIterator __first, _InputIterator __last,
183 const _Compare& __comp,
184 const allocator_type& __a = allocator_type())
186 { _M_t._M_insert_unique(__first, __last); }
189 * @brief %Set copy constructor.
190 * @param x A %set of identical element and allocator types.
192 * The newly-created %set uses a copy of the allocation object used
198 #ifdef __GXX_EXPERIMENTAL_CXX0X__
200 * @brief %Set move constructor
201 * @param x A %set of identical element and allocator types.
203 * The newly-created %set contains the exact contents of @a x.
204 * The contents of @a x are a valid, but unspecified %set.
207 : _M_t(__x._M_t.key_comp(),
208 __x._M_t._M_get_Node_allocator())
213 * @brief %Set assignment operator.
214 * @param x A %set of identical element and allocator types.
216 * All the elements of @a x are copied, but unlike the copy constructor,
217 * the allocator object is not copied.
220 operator=(const set& __x)
226 #ifdef __GXX_EXPERIMENTAL_CXX0X__
228 * @brief %Set move assignment operator.
229 * @param x A %set of identical element and allocator types.
231 * The contents of @a x are moved into this %set (without copying).
232 * @a x is a valid, but unspecified %set.
244 /// Returns the comparison object with which the %set was constructed.
247 { return _M_t.key_comp(); }
248 /// Returns the comparison object with which the %set was constructed.
251 { return _M_t.key_comp(); }
252 /// Returns the allocator object with which the %set was constructed.
254 get_allocator() const
255 { return _M_t.get_allocator(); }
258 * Returns a read/write iterator that points to the first element in the
259 * %set. Iteration is done in ascending order according to the keys.
263 { return _M_t.begin(); }
266 * Returns a read/write iterator that points one past the last element in
267 * the %set. Iteration is done in ascending order according to the keys.
271 { return _M_t.end(); }
274 * Returns a read/write reverse iterator that points to the last element
275 * in the %set. Iteration is done in descending order according to the
280 { return _M_t.rbegin(); }
283 * Returns a read-only (constant) reverse iterator that points to the
284 * last pair in the %map. Iteration is done in descending order
285 * according to the keys.
289 { return _M_t.rend(); }
291 /// Returns true if the %set is empty.
294 { return _M_t.empty(); }
296 /// Returns the size of the %set.
299 { return _M_t.size(); }
301 /// Returns the maximum size of the %set.
304 { return _M_t.max_size(); }
307 * @brief Swaps data with another %set.
308 * @param x A %set of the same element and allocator types.
310 * This exchanges the elements between two sets in constant time.
311 * (It is only swapping a pointer, an integer, and an instance of
312 * the @c Compare type (which itself is often stateless and empty), so it
313 * should be quite fast.)
314 * Note that the global std::swap() function is specialized such that
315 * std::swap(s1,s2) will feed to this function.
318 #ifdef __GXX_EXPERIMENTAL_CXX0X__
323 { _M_t.swap(__x._M_t); }
327 * @brief Attempts to insert an element into the %set.
328 * @param x Element to be inserted.
329 * @return A pair, of which the first element is an iterator that points
330 * to the possibly inserted element, and the second is a bool
331 * that is true if the element was actually inserted.
333 * This function attempts to insert an element into the %set. A %set
334 * relies on unique keys and thus an element is only inserted if it is
335 * not already present in the %set.
337 * Insertion requires logarithmic time.
339 std::pair<iterator, bool>
340 insert(const value_type& __x)
342 std::pair<typename _Rep_type::iterator, bool> __p =
343 _M_t._M_insert_unique(__x);
344 return std::pair<iterator, bool>(__p.first, __p.second);
348 * @brief Attempts to insert an element into the %set.
349 * @param position An iterator that serves as a hint as to where the
350 * element should be inserted.
351 * @param x Element to be inserted.
352 * @return An iterator that points to the element with key of @a x (may
353 * or may not be the element passed in).
355 * This function is not concerned about whether the insertion took place,
356 * and thus does not return a boolean like the single-argument insert()
357 * does. Note that the first parameter is only a hint and can
358 * potentially improve the performance of the insertion process. A bad
359 * hint would cause no gains in efficiency.
361 * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4
362 * for more on "hinting".
364 * Insertion requires logarithmic time (if the hint is not taken).
367 insert(iterator __position, const value_type& __x)
368 { return _M_t._M_insert_unique_(__position, __x); }
371 * @brief A template function that attemps to insert a range of elements.
372 * @param first Iterator pointing to the start of the range to be
374 * @param last Iterator pointing to the end of the range.
376 * Complexity similar to that of the range constructor.
378 template<typename _InputIterator>
380 insert(_InputIterator __first, _InputIterator __last)
381 { _M_t._M_insert_unique(__first, __last); }
384 * @brief Erases an element from a %set.
385 * @param position An iterator pointing to the element to be erased.
387 * This function erases an element, pointed to by the given iterator,
388 * from a %set. Note that this function only erases the element, and
389 * that if the element is itself a pointer, the pointed-to memory is not
390 * touched in any way. Managing the pointer is the user's responsibilty.
393 erase(iterator __position)
394 { _M_t.erase(__position); }
397 * @brief Erases elements according to the provided key.
398 * @param x Key of element to be erased.
399 * @return The number of elements erased.
401 * This function erases all the elements located by the given key from
403 * Note that this function only erases the element, and that if
404 * the element is itself a pointer, the pointed-to memory is not touched
405 * in any way. Managing the pointer is the user's responsibilty.
408 erase(const key_type& __x)
409 { return _M_t.erase(__x); }
412 * @brief Erases a [first,last) range of elements from a %set.
413 * @param first Iterator pointing to the start of the range to be
415 * @param last Iterator pointing to the end of the range to be erased.
417 * This function erases a sequence of elements from a %set.
418 * Note that this function only erases the element, and that if
419 * the element is itself a pointer, the pointed-to memory is not touched
420 * in any way. Managing the pointer is the user's responsibilty.
423 erase(iterator __first, iterator __last)
424 { _M_t.erase(__first, __last); }
427 * Erases all elements in a %set. Note that this function only erases
428 * the elements, and that if the elements themselves are pointers, the
429 * pointed-to memory is not touched in any way. Managing the pointer is
430 * the user's responsibilty.
439 * @brief Finds the number of elements.
440 * @param x Element to located.
441 * @return Number of elements with specified key.
443 * This function only makes sense for multisets; for set the result will
444 * either be 0 (not present) or 1 (present).
447 count(const key_type& __x) const
448 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
450 // _GLIBCXX_RESOLVE_LIB_DEFECTS
451 // 214. set::find() missing const overload
454 * @brief Tries to locate an element in a %set.
455 * @param x Element to be located.
456 * @return Iterator pointing to sought-after element, or end() if not
459 * This function takes a key and tries to locate the element with which
460 * the key matches. If successful the function returns an iterator
461 * pointing to the sought after element. If unsuccessful it returns the
462 * past-the-end ( @c end() ) iterator.
465 find(const key_type& __x)
466 { return _M_t.find(__x); }
469 find(const key_type& __x) const
470 { return _M_t.find(__x); }
475 * @brief Finds the beginning of a subsequence matching given key.
476 * @param x Key to be located.
477 * @return Iterator pointing to first element equal to or greater
478 * than key, or end().
480 * This function returns the first element of a subsequence of elements
481 * that matches the given key. If unsuccessful it returns an iterator
482 * pointing to the first element that has a greater value than given key
483 * or end() if no such element exists.
486 lower_bound(const key_type& __x)
487 { return _M_t.lower_bound(__x); }
490 lower_bound(const key_type& __x) const
491 { return _M_t.lower_bound(__x); }
496 * @brief Finds the end of a subsequence matching given key.
497 * @param x Key to be located.
498 * @return Iterator pointing to the first element
499 * greater than key, or end().
502 upper_bound(const key_type& __x)
503 { return _M_t.upper_bound(__x); }
506 upper_bound(const key_type& __x) const
507 { return _M_t.upper_bound(__x); }
512 * @brief Finds a subsequence matching given key.
513 * @param x Key to be located.
514 * @return Pair of iterators that possibly points to the subsequence
515 * matching given key.
517 * This function is equivalent to
519 * std::make_pair(c.lower_bound(val),
520 * c.upper_bound(val))
522 * (but is faster than making the calls separately).
524 * This function probably only makes sense for multisets.
526 std::pair<iterator, iterator>
527 equal_range(const key_type& __x)
528 { return _M_t.equal_range(__x); }
530 std::pair<const_iterator, const_iterator>
531 equal_range(const key_type& __x) const
532 { return _M_t.equal_range(__x); }
535 template<typename _K1, typename _C1, typename _A1>
537 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
539 template<typename _K1, typename _C1, typename _A1>
541 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
546 * @brief Set equality comparison.
548 * @param y A %set of the same type as @a x.
549 * @return True iff the size and elements of the sets are equal.
551 * This is an equivalence relation. It is linear in the size of the sets.
552 * Sets are considered equivalent if their sizes are equal, and if
553 * corresponding elements compare equal.
555 template<typename _Key, typename _Compare, typename _Alloc>
557 operator==(const set<_Key, _Compare, _Alloc>& __x,
558 const set<_Key, _Compare, _Alloc>& __y)
559 { return __x._M_t == __y._M_t; }
562 * @brief Set ordering relation.
564 * @param y A %set of the same type as @a x.
565 * @return True iff @a x is lexicographically less than @a y.
567 * This is a total ordering relation. It is linear in the size of the
568 * maps. The elements must be comparable with @c <.
570 * See std::lexicographical_compare() for how the determination is made.
572 template<typename _Key, typename _Compare, typename _Alloc>
574 operator<(const set<_Key, _Compare, _Alloc>& __x,
575 const set<_Key, _Compare, _Alloc>& __y)
576 { return __x._M_t < __y._M_t; }
578 /// Returns !(x == y).
579 template<typename _Key, typename _Compare, typename _Alloc>
581 operator!=(const set<_Key, _Compare, _Alloc>& __x,
582 const set<_Key, _Compare, _Alloc>& __y)
583 { return !(__x == __y); }
586 template<typename _Key, typename _Compare, typename _Alloc>
588 operator>(const set<_Key, _Compare, _Alloc>& __x,
589 const set<_Key, _Compare, _Alloc>& __y)
590 { return __y < __x; }
593 template<typename _Key, typename _Compare, typename _Alloc>
595 operator<=(const set<_Key, _Compare, _Alloc>& __x,
596 const set<_Key, _Compare, _Alloc>& __y)
597 { return !(__y < __x); }
600 template<typename _Key, typename _Compare, typename _Alloc>
602 operator>=(const set<_Key, _Compare, _Alloc>& __x,
603 const set<_Key, _Compare, _Alloc>& __y)
604 { return !(__x < __y); }
606 /// See std::set::swap().
607 template<typename _Key, typename _Compare, typename _Alloc>
609 swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y)
612 #ifdef __GXX_EXPERIMENTAL_CXX0X__
613 template<typename _Key, typename _Compare, typename _Alloc>
615 swap(set<_Key, _Compare, _Alloc>&& __x, set<_Key, _Compare, _Alloc>& __y)
618 template<typename _Key, typename _Compare, typename _Alloc>
620 swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>&& __y)
624 _GLIBCXX_END_NESTED_NAMESPACE
626 #endif /* _STL_SET_H */