1 : // Set implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2002, 2004, 2005 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 2, or (at your option)
9 : // any later version.
10 :
11 : // This library is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 :
16 : // You should have received a copy of the GNU General Public License along
17 : // with this library; see the file COPYING. If not, write to the Free
18 : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19 : // USA.
20 :
21 : // As a special exception, you may use this file as part of a free software
22 : // library without restriction. Specifically, if other files instantiate
23 : // templates or use macros or inline functions from this file, or you compile
24 : // this file and link it with other files to produce an executable, this
25 : // file does not by itself cause the resulting executable to be covered by
26 : // the GNU General Public License. This exception does not however
27 : // invalidate any other reasons why the executable file might be covered by
28 : // the GNU General Public License.
29 :
30 : /*
31 : *
32 : * Copyright (c) 1994
33 : * Hewlett-Packard Company
34 : *
35 : * Permission to use, copy, modify, distribute and sell this software
36 : * and its documentation for any purpose is hereby granted without fee,
37 : * provided that the above copyright notice appear in all copies and
38 : * that both that copyright notice and this permission notice appear
39 : * in supporting documentation. Hewlett-Packard Company makes no
40 : * representations about the suitability of this software for any
41 : * purpose. It is provided "as is" without express or implied warranty.
42 : *
43 : *
44 : * Copyright (c) 1996,1997
45 : * Silicon Graphics Computer Systems, Inc.
46 : *
47 : * Permission to use, copy, modify, distribute and sell this software
48 : * and its documentation for any purpose is hereby granted without fee,
49 : * provided that the above copyright notice appear in all copies and
50 : * that both that copyright notice and this permission notice appear
51 : * in supporting documentation. Silicon Graphics makes no
52 : * representations about the suitability of this software for any
53 : * purpose. It is provided "as is" without express or implied warranty.
54 : */
55 :
56 : /** @file stl_set.h
57 : * This is an internal header file, included by other library headers.
58 : * You should not attempt to use it directly.
59 : */
60 :
61 : #ifndef _SET_H
62 : #define _SET_H 1
63 :
64 : #include <bits/concept_check.h>
65 :
66 : namespace _GLIBCXX_STD
67 : {
68 : // Forward declarations of operators < and ==, needed for friend declaration.
69 : template<class _Key, class _Compare = std::less<_Key>,
70 : class _Alloc = std::allocator<_Key> >
71 : class set;
72 :
73 : template<class _Key, class _Compare, class _Alloc>
74 : inline bool
75 : operator==(const set<_Key, _Compare, _Alloc>& __x,
76 : const set<_Key, _Compare, _Alloc>& __y);
77 :
78 : template<class _Key, class _Compare, class _Alloc>
79 : inline bool
80 : operator<(const set<_Key, _Compare, _Alloc>& __x,
81 : const set<_Key, _Compare, _Alloc>& __y);
82 :
83 : /**
84 : * @brief A standard container made up of unique keys, which can be
85 : * retrieved in logarithmic time.
86 : *
87 : * @ingroup Containers
88 : * @ingroup Assoc_containers
89 : *
90 : * Meets the requirements of a <a href="tables.html#65">container</a>, a
91 : * <a href="tables.html#66">reversible container</a>, and an
92 : * <a href="tables.html#69">associative container</a> (using unique keys).
93 : *
94 : * Sets support bidirectional iterators.
95 : *
96 : * @param Key Type of key objects.
97 : * @param Compare Comparison function object type, defaults to less<Key>.
98 : * @param Alloc Allocator type, defaults to allocator<Key>.
99 : *
100 : * @if maint
101 : * The private tree data is declared exactly the same way for set and
102 : * multiset; the distinction is made entirely in how the tree functions are
103 : * called (*_unique versus *_equal, same as the standard).
104 : * @endif
105 : */
106 : template<class _Key, class _Compare, class _Alloc>
107 : class set
108 3871810 : {
109 : // concept requirements
110 : typedef typename _Alloc::value_type _Alloc_value_type;
111 : __glibcxx_class_requires(_Key, _SGIAssignableConcept)
112 : __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
113 : _BinaryFunctionConcept)
114 : __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
115 :
116 : public:
117 : // typedefs:
118 : //@{
119 : /// Public typedefs.
120 : typedef _Key key_type;
121 : typedef _Key value_type;
122 : typedef _Compare key_compare;
123 : typedef _Compare value_compare;
124 : typedef _Alloc allocator_type;
125 : //@}
126 :
127 : private:
128 : typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
129 :
130 : typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
131 : key_compare, _Key_alloc_type> _Rep_type;
132 : _Rep_type _M_t; // red-black tree representing set
133 :
134 : public:
135 : //@{
136 : /// Iterator-related typedefs.
137 : typedef typename _Key_alloc_type::pointer pointer;
138 : typedef typename _Key_alloc_type::const_pointer const_pointer;
139 : typedef typename _Key_alloc_type::reference reference;
140 : typedef typename _Key_alloc_type::const_reference const_reference;
141 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
142 : // DR 103. set::iterator is required to be modifiable,
143 : // but this allows modification of keys.
144 : typedef typename _Rep_type::const_iterator iterator;
145 : typedef typename _Rep_type::const_iterator const_iterator;
146 : typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
147 : typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
148 : typedef typename _Rep_type::size_type size_type;
149 : typedef typename _Rep_type::difference_type difference_type;
150 : //@}
151 :
152 : // allocation/deallocation
153 : /// Default constructor creates no elements.
154 3879476 : set()
155 3879476 : : _M_t(_Compare(), allocator_type()) {}
156 :
157 : /**
158 : * @brief Default constructor creates no elements.
159 : *
160 : * @param comp Comparator to use.
161 : * @param a Allocator to use.
162 : */
163 : explicit
164 : set(const _Compare& __comp,
165 : const allocator_type& __a = allocator_type())
166 : : _M_t(__comp, __a) {}
167 :
168 : /**
169 : * @brief Builds a %set from a range.
170 : * @param first An input iterator.
171 : * @param last An input iterator.
172 : *
173 : * Create a %set consisting of copies of the elements from [first,last).
174 : * This is linear in N if the range is already sorted, and NlogN
175 : * otherwise (where N is distance(first,last)).
176 : */
177 : template<class _InputIterator>
178 : set(_InputIterator __first, _InputIterator __last)
179 : : _M_t(_Compare(), allocator_type())
180 : { _M_t.insert_unique(__first, __last); }
181 :
182 : /**
183 : * @brief Builds a %set from a range.
184 : * @param first An input iterator.
185 : * @param last An input iterator.
186 : * @param comp A comparison functor.
187 : * @param a An allocator object.
188 : *
189 : * Create a %set consisting of copies of the elements from [first,last).
190 : * This is linear in N if the range is already sorted, and NlogN
191 : * otherwise (where N is distance(first,last)).
192 : */
193 : template<class _InputIterator>
194 : set(_InputIterator __first, _InputIterator __last,
195 : const _Compare& __comp,
196 : const allocator_type& __a = allocator_type())
197 : : _M_t(__comp, __a)
198 : { _M_t.insert_unique(__first, __last); }
199 :
200 : /**
201 : * @brief Set copy constructor.
202 : * @param x A %set of identical element and allocator types.
203 : *
204 : * The newly-created %set uses a copy of the allocation object used
205 : * by @a x.
206 : */
207 : set(const set<_Key,_Compare,_Alloc>& __x)
208 : : _M_t(__x._M_t) { }
209 :
210 : /**
211 : * @brief Set assignment operator.
212 : * @param x A %set of identical element and allocator types.
213 : *
214 : * All the elements of @a x are copied, but unlike the copy constructor,
215 : * the allocator object is not copied.
216 : */
217 : set<_Key,_Compare,_Alloc>&
218 : operator=(const set<_Key, _Compare, _Alloc>& __x)
219 : {
220 : _M_t = __x._M_t;
221 : return *this;
222 : }
223 :
224 : // accessors:
225 :
226 : /// Returns the comparison object with which the %set was constructed.
227 : key_compare
228 : key_comp() const
229 : { return _M_t.key_comp(); }
230 : /// Returns the comparison object with which the %set was constructed.
231 : value_compare
232 : value_comp() const
233 : { return _M_t.key_comp(); }
234 : /// Returns the allocator object with which the %set was constructed.
235 : allocator_type
236 : get_allocator() const
237 : { return _M_t.get_allocator(); }
238 :
239 : /**
240 : * Returns a read/write iterator that points to the first element in the
241 : * %set. Iteration is done in ascending order according to the keys.
242 : */
243 : iterator
244 2674662 : begin() const
245 2674662 : { return _M_t.begin(); }
246 :
247 : /**
248 : * Returns a read/write iterator that points one past the last element in
249 : * the %set. Iteration is done in ascending order according to the keys.
250 : */
251 : iterator
252 6118358 : end() const
253 6118358 : { return _M_t.end(); }
254 :
255 : /**
256 : * Returns a read/write reverse iterator that points to the last element
257 : * in the %set. Iteration is done in descending order according to the
258 : * keys.
259 : */
260 : reverse_iterator
261 : rbegin() const
262 : { return _M_t.rbegin(); }
263 :
264 : /**
265 : * Returns a read-only (constant) reverse iterator that points to the
266 : * last pair in the %map. Iteration is done in descending order
267 : * according to the keys.
268 : */
269 : reverse_iterator
270 : rend() const
271 : { return _M_t.rend(); }
272 :
273 : /// Returns true if the %set is empty.
274 : bool
275 1004861 : empty() const
276 1004861 : { return _M_t.empty(); }
277 :
278 : /// Returns the size of the %set.
279 : size_type
280 2433 : size() const
281 2433 : { return _M_t.size(); }
282 :
283 : /// Returns the maximum size of the %set.
284 : size_type
285 : max_size() const
286 : { return _M_t.max_size(); }
287 :
288 : /**
289 : * @brief Swaps data with another %set.
290 : * @param x A %set of the same element and allocator types.
291 : *
292 : * This exchanges the elements between two sets in constant time.
293 : * (It is only swapping a pointer, an integer, and an instance of
294 : * the @c Compare type (which itself is often stateless and empty), so it
295 : * should be quite fast.)
296 : * Note that the global std::swap() function is specialized such that
297 : * std::swap(s1,s2) will feed to this function.
298 : */
299 : void
300 : swap(set<_Key,_Compare,_Alloc>& __x)
301 : { _M_t.swap(__x._M_t); }
302 :
303 : // insert/erase
304 : /**
305 : * @brief Attempts to insert an element into the %set.
306 : * @param x Element to be inserted.
307 : * @return A pair, of which the first element is an iterator that points
308 : * to the possibly inserted element, and the second is a bool
309 : * that is true if the element was actually inserted.
310 : *
311 : * This function attempts to insert an element into the %set. A %set
312 : * relies on unique keys and thus an element is only inserted if it is
313 : * not already present in the %set.
314 : *
315 : * Insertion requires logarithmic time.
316 : */
317 : std::pair<iterator,bool>
318 6285652 : insert(const value_type& __x)
319 : {
320 : std::pair<typename _Rep_type::iterator, bool> __p =
321 6285652 : _M_t.insert_unique(__x);
322 6285652 : return std::pair<iterator, bool>(__p.first, __p.second);
323 : }
324 :
325 : /**
326 : * @brief Attempts to insert an element into the %set.
327 : * @param position An iterator that serves as a hint as to where the
328 : * element should be inserted.
329 : * @param x Element to be inserted.
330 : * @return An iterator that points to the element with key of @a x (may
331 : * or may not be the element passed in).
332 : *
333 : * This function is not concerned about whether the insertion took place,
334 : * and thus does not return a boolean like the single-argument insert()
335 : * does. Note that the first parameter is only a hint and can
336 : * potentially improve the performance of the insertion process. A bad
337 : * hint would cause no gains in efficiency.
338 : *
339 : * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4
340 : * for more on "hinting".
341 : *
342 : * Insertion requires logarithmic time (if the hint is not taken).
343 : */
344 : iterator
345 536881 : insert(iterator __position, const value_type& __x)
346 536881 : { return _M_t.insert_unique(__position, __x); }
347 :
348 : /**
349 : * @brief A template function that attemps to insert a range of elements.
350 : * @param first Iterator pointing to the start of the range to be
351 : * inserted.
352 : * @param last Iterator pointing to the end of the range.
353 : *
354 : * Complexity similar to that of the range constructor.
355 : */
356 : template<class _InputIterator>
357 : void
358 1945044 : insert(_InputIterator __first, _InputIterator __last)
359 1945044 : { _M_t.insert_unique(__first, __last); }
360 :
361 : /**
362 : * @brief Erases an element from a %set.
363 : * @param position An iterator pointing to the element to be erased.
364 : *
365 : * This function erases an element, pointed to by the given iterator,
366 : * from a %set. Note that this function only erases the element, and
367 : * that if the element is itself a pointer, the pointed-to memory is not
368 : * touched in any way. Managing the pointer is the user's responsibilty.
369 : */
370 : void
371 : erase(iterator __position)
372 : { _M_t.erase(__position); }
373 :
374 : /**
375 : * @brief Erases elements according to the provided key.
376 : * @param x Key of element to be erased.
377 : * @return The number of elements erased.
378 : *
379 : * This function erases all the elements located by the given key from
380 : * a %set.
381 : * Note that this function only erases the element, and that if
382 : * the element is itself a pointer, the pointed-to memory is not touched
383 : * in any way. Managing the pointer is the user's responsibilty.
384 : */
385 : size_type
386 23 : erase(const key_type& __x)
387 23 : { return _M_t.erase(__x); }
388 :
389 : /**
390 : * @brief Erases a [first,last) range of elements from a %set.
391 : * @param first Iterator pointing to the start of the range to be
392 : * erased.
393 : * @param last Iterator pointing to the end of the range to be erased.
394 : *
395 : * This function erases a sequence of elements from a %set.
396 : * Note that this function only erases the element, and that if
397 : * the element is itself a pointer, the pointed-to memory is not touched
398 : * in any way. Managing the pointer is the user's responsibilty.
399 : */
400 : void
401 : erase(iterator __first, iterator __last)
402 : { _M_t.erase(__first, __last); }
403 :
404 : /**
405 : * Erases all elements in a %set. Note that this function only erases
406 : * the elements, and that if the elements themselves are pointers, the
407 : * pointed-to memory is not touched in any way. Managing the pointer is
408 : * the user's responsibilty.
409 : */
410 : void
411 52189567 : clear()
412 52189567 : { _M_t.clear(); }
413 :
414 : // set operations:
415 :
416 : /**
417 : * @brief Finds the number of elements.
418 : * @param x Element to located.
419 : * @return Number of elements with specified key.
420 : *
421 : * This function only makes sense for multisets; for set the result will
422 : * either be 0 (not present) or 1 (present).
423 : */
424 : size_type
425 310 : count(const key_type& __x) const
426 310 : { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
427 :
428 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
429 : // 214. set::find() missing const overload
430 : //@{
431 : /**
432 : * @brief Tries to locate an element in a %set.
433 : * @param x Element to be located.
434 : * @return Iterator pointing to sought-after element, or end() if not
435 : * found.
436 : *
437 : * This function takes a key and tries to locate the element with which
438 : * the key matches. If successful the function returns an iterator
439 : * pointing to the sought after element. If unsuccessful it returns the
440 : * past-the-end ( @c end() ) iterator.
441 : */
442 : iterator
443 3833210 : find(const key_type& __x)
444 3833210 : { return _M_t.find(__x); }
445 :
446 : const_iterator
447 501834 : find(const key_type& __x) const
448 501834 : { return _M_t.find(__x); }
449 : //@}
450 :
451 : //@{
452 : /**
453 : * @brief Finds the beginning of a subsequence matching given key.
454 : * @param x Key to be located.
455 : * @return Iterator pointing to first element equal to or greater
456 : * than key, or end().
457 : *
458 : * This function returns the first element of a subsequence of elements
459 : * that matches the given key. If unsuccessful it returns an iterator
460 : * pointing to the first element that has a greater value than given key
461 : * or end() if no such element exists.
462 : */
463 : iterator
464 : lower_bound(const key_type& __x)
465 : { return _M_t.lower_bound(__x); }
466 :
467 : const_iterator
468 : lower_bound(const key_type& __x) const
469 : { return _M_t.lower_bound(__x); }
470 : //@}
471 :
472 : //@{
473 : /**
474 : * @brief Finds the end of a subsequence matching given key.
475 : * @param x Key to be located.
476 : * @return Iterator pointing to the first element
477 : * greater than key, or end().
478 : */
479 : iterator
480 : upper_bound(const key_type& __x)
481 : { return _M_t.upper_bound(__x); }
482 :
483 : const_iterator
484 : upper_bound(const key_type& __x) const
485 : { return _M_t.upper_bound(__x); }
486 : //@}
487 :
488 : //@{
489 : /**
490 : * @brief Finds a subsequence matching given key.
491 : * @param x Key to be located.
492 : * @return Pair of iterators that possibly points to the subsequence
493 : * matching given key.
494 : *
495 : * This function is equivalent to
496 : * @code
497 : * std::make_pair(c.lower_bound(val),
498 : * c.upper_bound(val))
499 : * @endcode
500 : * (but is faster than making the calls separately).
501 : *
502 : * This function probably only makes sense for multisets.
503 : */
504 : std::pair<iterator, iterator>
505 : equal_range(const key_type& __x)
506 : { return _M_t.equal_range(__x); }
507 :
508 : std::pair<const_iterator, const_iterator>
509 : equal_range(const key_type& __x) const
510 : { return _M_t.equal_range(__x); }
511 : //@}
512 :
513 : template<class _K1, class _C1, class _A1>
514 : friend bool
515 : operator== (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
516 :
517 : template<class _K1, class _C1, class _A1>
518 : friend bool
519 : operator< (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
520 : };
521 :
522 :
523 : /**
524 : * @brief Set equality comparison.
525 : * @param x A %set.
526 : * @param y A %set of the same type as @a x.
527 : * @return True iff the size and elements of the sets are equal.
528 : *
529 : * This is an equivalence relation. It is linear in the size of the sets.
530 : * Sets are considered equivalent if their sizes are equal, and if
531 : * corresponding elements compare equal.
532 : */
533 : template<class _Key, class _Compare, class _Alloc>
534 : inline bool
535 : operator==(const set<_Key, _Compare, _Alloc>& __x,
536 : const set<_Key, _Compare, _Alloc>& __y)
537 : { return __x._M_t == __y._M_t; }
538 :
539 : /**
540 : * @brief Set ordering relation.
541 : * @param x A %set.
542 : * @param y A %set of the same type as @a x.
543 : * @return True iff @a x is lexicographically less than @a y.
544 : *
545 : * This is a total ordering relation. It is linear in the size of the
546 : * maps. The elements must be comparable with @c <.
547 : *
548 : * See std::lexicographical_compare() for how the determination is made.
549 : */
550 : template<class _Key, class _Compare, class _Alloc>
551 : inline bool
552 : operator<(const set<_Key, _Compare, _Alloc>& __x,
553 : const set<_Key, _Compare, _Alloc>& __y)
554 : { return __x._M_t < __y._M_t; }
555 :
556 : /// Returns !(x == y).
557 : template<class _Key, class _Compare, class _Alloc>
558 : inline bool
559 : operator!=(const set<_Key, _Compare, _Alloc>& __x,
560 : const set<_Key, _Compare, _Alloc>& __y)
561 : { return !(__x == __y); }
562 :
563 : /// Returns y < x.
564 : template<class _Key, class _Compare, class _Alloc>
565 : inline bool
566 : operator>(const set<_Key, _Compare, _Alloc>& __x,
567 : const set<_Key, _Compare, _Alloc>& __y)
568 : { return __y < __x; }
569 :
570 : /// Returns !(y < x)
571 : template<class _Key, class _Compare, class _Alloc>
572 : inline bool
573 : operator<=(const set<_Key, _Compare, _Alloc>& __x,
574 : const set<_Key, _Compare, _Alloc>& __y)
575 : { return !(__y < __x); }
576 :
577 : /// Returns !(x < y)
578 : template<class _Key, class _Compare, class _Alloc>
579 : inline bool
580 : operator>=(const set<_Key, _Compare, _Alloc>& __x,
581 : const set<_Key, _Compare, _Alloc>& __y)
582 : { return !(__x < __y); }
583 :
584 : /// See std::set::swap().
585 : template<class _Key, class _Compare, class _Alloc>
586 : inline void
587 : swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y)
588 : { __x.swap(__y); }
589 :
590 : } // namespace std
591 :
592 : #endif /* _SET_H */
|
