1// Set implementation -*- C++ -*-
2
3// Copyright (C) 2001-2017 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
64namespace std _GLIBCXX_VISIBILITY(default)
65{
66_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
67
68 template<typename _Key, typename _Compare, typename _Alloc>
69 class multiset;
70
71 /**
72 * @brief A standard container made up of unique keys, which can be
73 * retrieved in logarithmic time.
74 *
75 * @ingroup associative_containers
76 *
77 * @tparam _Key Type of key objects.
78 * @tparam _Compare Comparison function object type, defaults to less<_Key>.
79 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
80 *
81 * Meets the requirements of a <a href="tables.html#65">container</a>, a
82 * <a href="tables.html#66">reversible container</a>, and an
83 * <a href="tables.html#69">associative container</a> (using unique keys).
84 *
85 * Sets support bidirectional iterators.
86 *
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).
90 */
91 template<typename _Key, typename _Compare = std::less<_Key>,
92 typename _Alloc = std::allocator<_Key> >
93 class set
94 {
95#ifdef _GLIBCXX_CONCEPT_CHECKS
96 // concept requirements
97 typedef typename _Alloc::value_type _Alloc_value_type;
98# if __cplusplus < 201103L
99 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
100# endif
101 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
102 _BinaryFunctionConcept)
103 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
104#endif
105
106 public:
107 // typedefs:
108 //@{
109 /// Public typedefs.
110 typedef _Key key_type;
111 typedef _Key value_type;
112 typedef _Compare key_compare;
113 typedef _Compare value_compare;
114 typedef _Alloc allocator_type;
115 //@}
116
117 private:
118 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
119 rebind<_Key>::other _Key_alloc_type;
120
121 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
122 key_compare, _Key_alloc_type> _Rep_type;
123 _Rep_type _M_t; // Red-black tree representing set.
124
125 typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;
126
127 public:
128 //@{
129 /// Iterator-related typedefs.
130 typedef typename _Alloc_traits::pointer pointer;
131 typedef typename _Alloc_traits::const_pointer const_pointer;
132 typedef typename _Alloc_traits::reference reference;
133 typedef typename _Alloc_traits::const_reference const_reference;
134 // _GLIBCXX_RESOLVE_LIB_DEFECTS
135 // DR 103. set::iterator is required to be modifiable,
136 // but this allows modification of keys.
137 typedef typename _Rep_type::const_iterator iterator;
138 typedef typename _Rep_type::const_iterator const_iterator;
139 typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
140 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
141 typedef typename _Rep_type::size_type size_type;
142 typedef typename _Rep_type::difference_type difference_type;
143 //@}
144
145#if __cplusplus > 201402L
146 using node_type = typename _Rep_type::node_type;
147 using insert_return_type = typename _Rep_type::insert_return_type;
148#endif
149
150 // allocation/deallocation
151 /**
152 * @brief Default constructor creates no elements.
153 */
154#if __cplusplus < 201103L
155 set() : _M_t() { }
156#else
157 set() = default;
158#endif
159
160 /**
161 * @brief Creates a %set with no elements.
162 * @param __comp Comparator to use.
163 * @param __a An allocator object.
164 */
165 explicit
166 set(const _Compare& __comp,
167 const allocator_type& __a = allocator_type())
168 : _M_t(__comp, _Key_alloc_type(__a)) { }
169
170 /**
171 * @brief Builds a %set from a range.
172 * @param __first An input iterator.
173 * @param __last An input iterator.
174 *
175 * Create a %set consisting of copies of the elements from
176 * [__first,__last). This is linear in N if the range is
177 * already sorted, and NlogN otherwise (where N is
178 * distance(__first,__last)).
179 */
180 template<typename _InputIterator>
181 set(_InputIterator __first, _InputIterator __last)
182 : _M_t()
183 { _M_t._M_insert_unique(__first, __last); }
184
185 /**
186 * @brief Builds a %set from a range.
187 * @param __first An input iterator.
188 * @param __last An input iterator.
189 * @param __comp A comparison functor.
190 * @param __a An allocator object.
191 *
192 * Create a %set consisting of copies of the elements from
193 * [__first,__last). This is linear in N if the range is
194 * already sorted, and NlogN otherwise (where N is
195 * distance(__first,__last)).
196 */
197 template<typename _InputIterator>
198 set(_InputIterator __first, _InputIterator __last,
199 const _Compare& __comp,
200 const allocator_type& __a = allocator_type())
201 : _M_t(__comp, _Key_alloc_type(__a))
202 { _M_t._M_insert_unique(__first, __last); }
203
204 /**
205 * @brief %Set copy constructor.
206 *
207 * Whether the allocator is copied depends on the allocator traits.
208 */
209#if __cplusplus < 201103L
210 set(const set& __x)
211 : _M_t(__x._M_t) { }
212#else
213 set(const set&) = default;
214
215 /**
216 * @brief %Set move constructor
217 *
218 * The newly-created %set contains the exact contents of the moved
219 * instance. The moved instance is a valid, but unspecified, %set.
220 */
221 set(set&&) = default;
222
223 /**
224 * @brief Builds a %set from an initializer_list.
225 * @param __l An initializer_list.
226 * @param __comp A comparison functor.
227 * @param __a An allocator object.
228 *
229 * Create a %set consisting of copies of the elements in the list.
230 * This is linear in N if the list is already sorted, and NlogN
231 * otherwise (where N is @a __l.size()).
232 */
233 set(initializer_list<value_type> __l,
234 const _Compare& __comp = _Compare(),
235 const allocator_type& __a = allocator_type())
236 : _M_t(__comp, _Key_alloc_type(__a))
237 { _M_t._M_insert_unique(__l.begin(), __l.end()); }
238
239 /// Allocator-extended default constructor.
240 explicit
241 set(const allocator_type& __a)
242 : _M_t(_Compare(), _Key_alloc_type(__a)) { }
243
244 /// Allocator-extended copy constructor.
245 set(const set& __x, const allocator_type& __a)
246 : _M_t(__x._M_t, _Key_alloc_type(__a)) { }
247
248 /// Allocator-extended move constructor.
249 set(set&& __x, const allocator_type& __a)
250 noexcept(is_nothrow_copy_constructible<_Compare>::value
251 && _Alloc_traits::_S_always_equal())
252 : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
253
254 /// Allocator-extended initialier-list constructor.
255 set(initializer_list<value_type> __l, const allocator_type& __a)
256 : _M_t(_Compare(), _Key_alloc_type(__a))
257 { _M_t._M_insert_unique(__l.begin(), __l.end()); }
258
259 /// Allocator-extended range constructor.
260 template<typename _InputIterator>
261 set(_InputIterator __first, _InputIterator __last,
262 const allocator_type& __a)
263 : _M_t(_Compare(), _Key_alloc_type(__a))
264 { _M_t._M_insert_unique(__first, __last); }
265
266 /**
267 * The dtor only erases the elements, and note that if the elements
268 * themselves are pointers, the pointed-to memory is not touched in any
269 * way. Managing the pointer is the user's responsibility.
270 */
271 ~set() = default;
272#endif
273
274 /**
275 * @brief %Set assignment operator.
276 *
277 * Whether the allocator is copied depends on the allocator traits.
278 */
279#if __cplusplus < 201103L
280 set&
281 operator=(const set& __x)
282 {
283 _M_t = __x._M_t;
284 return *this;
285 }
286#else
287 set&
288 operator=(const set&) = default;
289
290 /// Move assignment operator.
291 set&
292 operator=(set&&) = default;
293
294 /**
295 * @brief %Set list assignment operator.
296 * @param __l An initializer_list.
297 *
298 * This function fills a %set with copies of the elements in the
299 * initializer list @a __l.
300 *
301 * Note that the assignment completely changes the %set and
302 * that the resulting %set's size is the same as the number
303 * of elements assigned.
304 */
305 set&
306 operator=(initializer_list<value_type> __l)
307 {
308 _M_t._M_assign_unique(__l.begin(), __l.end());
309 return *this;
310 }
311#endif
312
313 // accessors:
314
315 /// Returns the comparison object with which the %set was constructed.
316 key_compare
317 key_comp() const
318 { return _M_t.key_comp(); }
319 /// Returns the comparison object with which the %set was constructed.
320 value_compare
321 value_comp() const
322 { return _M_t.key_comp(); }
323 /// Returns the allocator object with which the %set was constructed.
324 allocator_type
325 get_allocator() const _GLIBCXX_NOEXCEPT
326 { return allocator_type(_M_t.get_allocator()); }
327
328 /**
329 * Returns a read-only (constant) iterator that points to the first
330 * element in the %set. Iteration is done in ascending order according
331 * to the keys.
332 */
333 iterator
334 begin() const _GLIBCXX_NOEXCEPT
335 { return _M_t.begin(); }
336
337 /**
338 * Returns a read-only (constant) iterator that points one past the last
339 * element in the %set. Iteration is done in ascending order according
340 * to the keys.
341 */
342 iterator
343 end() const _GLIBCXX_NOEXCEPT
344 { return _M_t.end(); }
345
346 /**
347 * Returns a read-only (constant) iterator that points to the last
348 * element in the %set. Iteration is done in descending order according
349 * to the keys.
350 */
351 reverse_iterator
352 rbegin() const _GLIBCXX_NOEXCEPT
353 { return _M_t.rbegin(); }
354
355 /**
356 * Returns a read-only (constant) reverse iterator that points to the
357 * last pair in the %set. Iteration is done in descending order
358 * according to the keys.
359 */
360 reverse_iterator
361 rend() const _GLIBCXX_NOEXCEPT
362 { return _M_t.rend(); }
363
364#if __cplusplus >= 201103L
365 /**
366 * Returns a read-only (constant) iterator that points to the first
367 * element in the %set. Iteration is done in ascending order according
368 * to the keys.
369 */
370 iterator
371 cbegin() const noexcept
372 { return _M_t.begin(); }
373
374 /**
375 * Returns a read-only (constant) iterator that points one past the last
376 * element in the %set. Iteration is done in ascending order according
377 * to the keys.
378 */
379 iterator
380 cend() const noexcept
381 { return _M_t.end(); }
382
383 /**
384 * Returns a read-only (constant) iterator that points to the last
385 * element in the %set. Iteration is done in descending order according
386 * to the keys.
387 */
388 reverse_iterator
389 crbegin() const noexcept
390 { return _M_t.rbegin(); }
391
392 /**
393 * Returns a read-only (constant) reverse iterator that points to the
394 * last pair in the %set. Iteration is done in descending order
395 * according to the keys.
396 */
397 reverse_iterator
398 crend() const noexcept
399 { return _M_t.rend(); }
400#endif
401
402 /// Returns true if the %set is empty.
403 bool
404 empty() const _GLIBCXX_NOEXCEPT
405 { return _M_t.empty(); }
406
407 /// Returns the size of the %set.
408 size_type
409 size() const _GLIBCXX_NOEXCEPT
410 { return _M_t.size(); }
411
412 /// Returns the maximum size of the %set.
413 size_type
414 max_size() const _GLIBCXX_NOEXCEPT
415 { return _M_t.max_size(); }
416
417 /**
418 * @brief Swaps data with another %set.
419 * @param __x A %set of the same element and allocator types.
420 *
421 * This exchanges the elements between two sets in constant
422 * time. (It is only swapping a pointer, an integer, and an
423 * instance of the @c Compare type (which itself is often
424 * stateless and empty), so it should be quite fast.) Note
425 * that the global std::swap() function is specialized such
426 * that std::swap(s1,s2) will feed to this function.
427 *
428 * Whether the allocators are swapped depends on the allocator traits.
429 */
430 void
431 swap(set& __x)
432 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
433 { _M_t.swap(__x._M_t); }
434
435 // insert/erase
436#if __cplusplus >= 201103L
437 /**
438 * @brief Attempts to build and insert an element into the %set.
439 * @param __args Arguments used to generate an element.
440 * @return A pair, of which the first element is an iterator that points
441 * to the possibly inserted element, and the second is a bool
442 * that is true if the element was actually inserted.
443 *
444 * This function attempts to build and insert an element into the %set.
445 * A %set relies on unique keys and thus an element is only inserted if
446 * it is not already present in the %set.
447 *
448 * Insertion requires logarithmic time.
449 */
450 template<typename... _Args>
451 std::pair<iterator, bool>
452 emplace(_Args&&... __args)
453 { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
454
455 /**
456 * @brief Attempts to insert an element into the %set.
457 * @param __pos An iterator that serves as a hint as to where the
458 * element should be inserted.
459 * @param __args Arguments used to generate the element to be
460 * inserted.
461 * @return An iterator that points to the element with key equivalent to
462 * the one generated from @a __args (may or may not be the
463 * element itself).
464 *
465 * This function is not concerned about whether the insertion took place,
466 * and thus does not return a boolean like the single-argument emplace()
467 * does. Note that the first parameter is only a hint and can
468 * potentially improve the performance of the insertion process. A bad
469 * hint would cause no gains in efficiency.
470 *
471 * For more on @a hinting, see:
472 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
473 *
474 * Insertion requires logarithmic time (if the hint is not taken).
475 */
476 template<typename... _Args>
477 iterator
478 emplace_hint(const_iterator __pos, _Args&&... __args)
479 {
480 return _M_t._M_emplace_hint_unique(__pos,
481 std::forward<_Args>(__args)...);
482 }
483#endif
484
485 /**
486 * @brief Attempts to insert an element into the %set.
487 * @param __x Element to be inserted.
488 * @return A pair, of which the first element is an iterator that points
489 * to the possibly inserted element, and the second is a bool
490 * that is true if the element was actually inserted.
491 *
492 * This function attempts to insert an element into the %set. A %set
493 * relies on unique keys and thus an element is only inserted if it is
494 * not already present in the %set.
495 *
496 * Insertion requires logarithmic time.
497 */
498 std::pair<iterator, bool>
499 insert(const value_type& __x)
500 {
501 std::pair<typename _Rep_type::iterator, bool> __p =
502 _M_t._M_insert_unique(__x);
503 return std::pair<iterator, bool>(__p.first, __p.second);
504 }
505
506#if __cplusplus >= 201103L
507 std::pair<iterator, bool>
508 insert(value_type&& __x)
509 {
510 std::pair<typename _Rep_type::iterator, bool> __p =
511 _M_t._M_insert_unique(std::move(__x));
512 return std::pair<iterator, bool>(__p.first, __p.second);
513 }
514#endif
515
516 /**
517 * @brief Attempts to insert an element into the %set.
518 * @param __position An iterator that serves as a hint as to where the
519 * element should be inserted.
520 * @param __x Element to be inserted.
521 * @return An iterator that points to the element with key of
522 * @a __x (may or may not be the element passed in).
523 *
524 * This function is not concerned about whether the insertion took place,
525 * and thus does not return a boolean like the single-argument insert()
526 * does. Note that the first parameter is only a hint and can
527 * potentially improve the performance of the insertion process. A bad
528 * hint would cause no gains in efficiency.
529 *
530 * For more on @a hinting, see:
531 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
532 *
533 * Insertion requires logarithmic time (if the hint is not taken).
534 */
535 iterator
536 insert(const_iterator __position, const value_type& __x)
537 { return _M_t._M_insert_unique_(__position, __x); }
538
539#if __cplusplus >= 201103L
540 iterator
541 insert(const_iterator __position, value_type&& __x)
542 { return _M_t._M_insert_unique_(__position, std::move(__x)); }
543#endif
544
545 /**
546 * @brief A template function that attempts to insert a range
547 * of elements.
548 * @param __first Iterator pointing to the start of the range to be
549 * inserted.
550 * @param __last Iterator pointing to the end of the range.
551 *
552 * Complexity similar to that of the range constructor.
553 */
554 template<typename _InputIterator>
555 void
556 insert(_InputIterator __first, _InputIterator __last)
557 { _M_t._M_insert_unique(__first, __last); }
558
559#if __cplusplus >= 201103L
560 /**
561 * @brief Attempts to insert a list of elements into the %set.
562 * @param __l A std::initializer_list<value_type> of elements
563 * to be inserted.
564 *
565 * Complexity similar to that of the range constructor.
566 */
567 void
568 insert(initializer_list<value_type> __l)
569 { this->insert(__l.begin(), __l.end()); }
570#endif
571
572#if __cplusplus > 201402L
573 /// Extract a node.
574 node_type
575 extract(const_iterator __pos)
576 {
577 __glibcxx_assert(__pos != end());
578 return _M_t.extract(__pos);
579 }
580
581 /// Extract a node.
582 node_type
583 extract(const key_type& __x)
584 { return _M_t.extract(__x); }
585
586 /// Re-insert an extracted node.
587 insert_return_type
588 insert(node_type&& __nh)
589 { return _M_t._M_reinsert_node_unique(std::move(__nh)); }
590
591 /// Re-insert an extracted node.
592 iterator
593 insert(const_iterator __hint, node_type&& __nh)
594 { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
595
596 template<typename, typename>
597 friend class _Rb_tree_merge_helper;
598
599 template<typename _Compare1>
600 void
601 merge(set<_Key, _Compare1, _Alloc>& __source)
602 {
603 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>;
604 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
605 }
606
607 template<typename _Compare1>
608 void
609 merge(set<_Key, _Compare1, _Alloc>&& __source)
610 { merge(__source); }
611
612 template<typename _Compare1>
613 void
614 merge(multiset<_Key, _Compare1, _Alloc>& __source)
615 {
616 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>;
617 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
618 }
619
620 template<typename _Compare1>
621 void
622 merge(multiset<_Key, _Compare1, _Alloc>&& __source)
623 { merge(__source); }
624#endif // C++17
625
626#if __cplusplus >= 201103L
627 // _GLIBCXX_RESOLVE_LIB_DEFECTS
628 // DR 130. Associative erase should return an iterator.
629 /**
630 * @brief Erases an element from a %set.
631 * @param __position An iterator pointing to the element to be erased.
632 * @return An iterator pointing to the element immediately following
633 * @a __position prior to the element being erased. If no such
634 * element exists, end() is returned.
635 *
636 * This function erases an element, pointed to by the given iterator,
637 * from a %set. Note that this function only erases the element, and
638 * that if the element is itself a pointer, the pointed-to memory is not
639 * touched in any way. Managing the pointer is the user's
640 * responsibility.
641 */
642 _GLIBCXX_ABI_TAG_CXX11
643 iterator
644 erase(const_iterator __position)
645 { return _M_t.erase(__position); }
646#else
647 /**
648 * @brief Erases an element from a %set.
649 * @param position An iterator pointing to the element to be erased.
650 *
651 * This function erases an element, pointed to by the given iterator,
652 * from a %set. Note that this function only erases the element, and
653 * that if the element is itself a pointer, the pointed-to memory is not
654 * touched in any way. Managing the pointer is the user's
655 * responsibility.
656 */
657 void
658 erase(iterator __position)
659 { _M_t.erase(__position); }
660#endif
661
662 /**
663 * @brief Erases elements according to the provided key.
664 * @param __x Key of element to be erased.
665 * @return The number of elements erased.
666 *
667 * This function erases all the elements located by the given key from
668 * a %set.
669 * Note that this function only erases the element, and that if
670 * the element is itself a pointer, the pointed-to memory is not touched
671 * in any way. Managing the pointer is the user's responsibility.
672 */
673 size_type
674 erase(const key_type& __x)
675 { return _M_t.erase(__x); }
676
677#if __cplusplus >= 201103L
678 // _GLIBCXX_RESOLVE_LIB_DEFECTS
679 // DR 130. Associative erase should return an iterator.
680 /**
681 * @brief Erases a [__first,__last) range of elements from a %set.
682 * @param __first Iterator pointing to the start of the range to be
683 * erased.
684
685 * @param __last Iterator pointing to the end of the range to
686 * be erased.
687 * @return The iterator @a __last.
688 *
689 * This function erases a sequence of elements from a %set.
690 * Note that this function only erases the element, and that if
691 * the element is itself a pointer, the pointed-to memory is not touched
692 * in any way. Managing the pointer is the user's responsibility.
693 */
694 _GLIBCXX_ABI_TAG_CXX11
695 iterator
696 erase(const_iterator __first, const_iterator __last)
697 { return _M_t.erase(__first, __last); }
698#else
699 /**
700 * @brief Erases a [first,last) range of elements from a %set.
701 * @param __first Iterator pointing to the start of the range to be
702 * erased.
703 * @param __last Iterator pointing to the end of the range to
704 * be erased.
705 *
706 * This function erases a sequence of elements from a %set.
707 * Note that this function only erases the element, and that if
708 * the element is itself a pointer, the pointed-to memory is not touched
709 * in any way. Managing the pointer is the user's responsibility.
710 */
711 void
712 erase(iterator __first, iterator __last)
713 { _M_t.erase(__first, __last); }
714#endif
715
716 /**
717 * Erases all elements in a %set. Note that this function only erases
718 * the elements, and that if the elements themselves are pointers, the
719 * pointed-to memory is not touched in any way. Managing the pointer is
720 * the user's responsibility.
721 */
722 void
723 clear() _GLIBCXX_NOEXCEPT
724 { _M_t.clear(); }
725
726 // set operations:
727
728 //@{
729 /**
730 * @brief Finds the number of elements.
731 * @param __x Element to located.
732 * @return Number of elements with specified key.
733 *
734 * This function only makes sense for multisets; for set the result will
735 * either be 0 (not present) or 1 (present).
736 */
737 size_type
738 count(const key_type& __x) const
739 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
740
741#if __cplusplus > 201103L
742 template<typename _Kt>
743 auto
744 count(const _Kt& __x) const
745 -> decltype(_M_t._M_count_tr(__x))
746 { return _M_t._M_count_tr(__x); }
747#endif
748 //@}
749
750 // _GLIBCXX_RESOLVE_LIB_DEFECTS
751 // 214. set::find() missing const overload
752 //@{
753 /**
754 * @brief Tries to locate an element in a %set.
755 * @param __x Element to be located.
756 * @return Iterator pointing to sought-after element, or end() if not
757 * found.
758 *
759 * This function takes a key and tries to locate the element with which
760 * the key matches. If successful the function returns an iterator
761 * pointing to the sought after element. If unsuccessful it returns the
762 * past-the-end ( @c end() ) iterator.
763 */
764 iterator
765 find(const key_type& __x)
766 { return _M_t.find(__x); }
767
768 const_iterator
769 find(const key_type& __x) const
770 { return _M_t.find(__x); }
771
772#if __cplusplus > 201103L
773 template<typename _Kt>
774 auto
775 find(const _Kt& __x)
776 -> decltype(iterator{_M_t._M_find_tr(__x)})
777 { return iterator{_M_t._M_find_tr(__x)}; }
778
779 template<typename _Kt>
780 auto
781 find(const _Kt& __x) const
782 -> decltype(const_iterator{_M_t._M_find_tr(__x)})
783 { return const_iterator{_M_t._M_find_tr(__x)}; }
784#endif
785 //@}
786
787 //@{
788 /**
789 * @brief Finds the beginning of a subsequence matching given key.
790 * @param __x Key to be located.
791 * @return Iterator pointing to first element equal to or greater
792 * than key, or end().
793 *
794 * This function returns the first element of a subsequence of elements
795 * that matches the given key. If unsuccessful it returns an iterator
796 * pointing to the first element that has a greater value than given key
797 * or end() if no such element exists.
798 */
799 iterator
800 lower_bound(const key_type& __x)
801 { return _M_t.lower_bound(__x); }
802
803 const_iterator
804 lower_bound(const key_type& __x) const
805 { return _M_t.lower_bound(__x); }
806
807#if __cplusplus > 201103L
808 template<typename _Kt>
809 auto
810 lower_bound(const _Kt& __x)
811 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
812 { return iterator(_M_t._M_lower_bound_tr(__x)); }
813
814 template<typename _Kt>
815 auto
816 lower_bound(const _Kt& __x) const
817 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
818 { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
819#endif
820 //@}
821
822 //@{
823 /**
824 * @brief Finds the end of a subsequence matching given key.
825 * @param __x Key to be located.
826 * @return Iterator pointing to the first element
827 * greater than key, or end().
828 */
829 iterator
830 upper_bound(const key_type& __x)
831 { return _M_t.upper_bound(__x); }
832
833 const_iterator
834 upper_bound(const key_type& __x) const
835 { return _M_t.upper_bound(__x); }
836
837#if __cplusplus > 201103L
838 template<typename _Kt>
839 auto
840 upper_bound(const _Kt& __x)
841 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
842 { return iterator(_M_t._M_upper_bound_tr(__x)); }
843
844 template<typename _Kt>
845 auto
846 upper_bound(const _Kt& __x) const
847 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
848 { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
849#endif
850 //@}
851
852 //@{
853 /**
854 * @brief Finds a subsequence matching given key.
855 * @param __x Key to be located.
856 * @return Pair of iterators that possibly points to the subsequence
857 * matching given key.
858 *
859 * This function is equivalent to
860 * @code
861 * std::make_pair(c.lower_bound(val),
862 * c.upper_bound(val))
863 * @endcode
864 * (but is faster than making the calls separately).
865 *
866 * This function probably only makes sense for multisets.
867 */
868 std::pair<iterator, iterator>
869 equal_range(const key_type& __x)
870 { return _M_t.equal_range(__x); }
871
872 std::pair<const_iterator, const_iterator>
873 equal_range(const key_type& __x) const
874 { return _M_t.equal_range(__x); }
875
876#if __cplusplus > 201103L
877 template<typename _Kt>
878 auto
879 equal_range(const _Kt& __x)
880 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
881 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
882
883 template<typename _Kt>
884 auto
885 equal_range(const _Kt& __x) const
886 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
887 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
888#endif
889 //@}
890
891 template<typename _K1, typename _C1, typename _A1>
892 friend bool
893 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
894
895 template<typename _K1, typename _C1, typename _A1>
896 friend bool
897 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
898 };
899
900
901 /**
902 * @brief Set equality comparison.
903 * @param __x A %set.
904 * @param __y A %set of the same type as @a x.
905 * @return True iff the size and elements of the sets are equal.
906 *
907 * This is an equivalence relation. It is linear in the size of the sets.
908 * Sets are considered equivalent if their sizes are equal, and if
909 * corresponding elements compare equal.
910 */
911 template<typename _Key, typename _Compare, typename _Alloc>
912 inline bool
913 operator==(const set<_Key, _Compare, _Alloc>& __x,
914 const set<_Key, _Compare, _Alloc>& __y)
915 { return __x._M_t == __y._M_t; }
916
917 /**
918 * @brief Set ordering relation.
919 * @param __x A %set.
920 * @param __y A %set of the same type as @a x.
921 * @return True iff @a __x is lexicographically less than @a __y.
922 *
923 * This is a total ordering relation. It is linear in the size of the
924 * sets. The elements must be comparable with @c <.
925 *
926 * See std::lexicographical_compare() for how the determination is made.
927 */
928 template<typename _Key, typename _Compare, typename _Alloc>
929 inline bool
930 operator<(const set<_Key, _Compare, _Alloc>& __x,
931 const set<_Key, _Compare, _Alloc>& __y)
932 { return __x._M_t < __y._M_t; }
933
934 /// Returns !(x == y).
935 template<typename _Key, typename _Compare, typename _Alloc>
936 inline bool
937 operator!=(const set<_Key, _Compare, _Alloc>& __x,
938 const set<_Key, _Compare, _Alloc>& __y)
939 { return !(__x == __y); }
940
941 /// Returns y < x.
942 template<typename _Key, typename _Compare, typename _Alloc>
943 inline bool
944 operator>(const set<_Key, _Compare, _Alloc>& __x,
945 const set<_Key, _Compare, _Alloc>& __y)
946 { return __y < __x; }
947
948 /// Returns !(y < x)
949 template<typename _Key, typename _Compare, typename _Alloc>
950 inline bool
951 operator<=(const set<_Key, _Compare, _Alloc>& __x,
952 const set<_Key, _Compare, _Alloc>& __y)
953 { return !(__y < __x); }
954
955 /// Returns !(x < y)
956 template<typename _Key, typename _Compare, typename _Alloc>
957 inline bool
958 operator>=(const set<_Key, _Compare, _Alloc>& __x,
959 const set<_Key, _Compare, _Alloc>& __y)
960 { return !(__x < __y); }
961
962 /// See std::set::swap().
963 template<typename _Key, typename _Compare, typename _Alloc>
964 inline void
965 swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y)
966 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
967 { __x.swap(__y); }
968
969_GLIBCXX_END_NAMESPACE_CONTAINER
970
971#if __cplusplus > 201402L
972_GLIBCXX_BEGIN_NAMESPACE_VERSION
973 // Allow std::set access to internals of compatible sets.
974 template<typename _Val, typename _Cmp1, typename _Alloc, typename _Cmp2>
975 struct
976 _Rb_tree_merge_helper<_GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>, _Cmp2>
977 {
978 private:
979 friend class _GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>;
980
981 static auto&
982 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set)
983 { return __set._M_t; }
984
985 static auto&
986 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set)
987 { return __set._M_t; }
988 };
989_GLIBCXX_END_NAMESPACE_VERSION
990#endif // C++17
991
992} //namespace std
993#endif /* _STL_SET_H */
994