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