libstdc++: stl_set.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#ifndef _STL_SET_H
57#define _STL_SET_H 1
58
60#if __cplusplus >= 201103L
62#endif
63
64namespace std _GLIBCXX_VISIBILITY(default)
65{
66_GLIBCXX_BEGIN_NAMESPACE_VERSION
67_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
68
69 template<typename _Key, typename _Compare, typename _Alloc>
70 class multiset;
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94 template<typename _Key, typename _Compare = std::less<_Key>,
95 typename _Alloc = std::allocator<_Key> >
97 {
98#ifdef _GLIBCXX_CONCEPT_CHECKS
99
100 typedef typename _Alloc::value_type _Alloc_value_type;
101# if __cplusplus < 201103L
102 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
103# endif
104 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
105 _BinaryFunctionConcept)
106 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
107#endif
108
109#if __cplusplus >= 201103L
111 "std::set must have a non-const, non-volatile value_type");
112# if __cplusplus > 201703L || defined __STRICT_ANSI__
114 "std::set must have the same value_type as its allocator");
115# endif
116#endif
117
118 public:
119
120
121
127
128
129 private:
131 rebind<_Key>::other _Key_alloc_type;
132
133 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
135 _Rep_type _M_t;
136
138
139 public:
140
141
142 typedef typename _Alloc_traits::pointer pointer;
144 typedef typename _Alloc_traits::reference reference;
146
147
148
149 typedef typename _Rep_type::const_iterator iterator;
153 typedef typename _Rep_type::size_type size_type;
155
156
157#if __cplusplus > 201402L
160#endif
161
162
163
164
165
166#if __cplusplus < 201103L
167 set() : _M_t() { }
168#else
170#endif
171
172
173
174
175
176
177 explicit
178 set(const _Compare& __comp,
180 : _M_t(__comp, _Key_alloc_type(__a)) { }
181
182
183
184
185
186
187
188
189
190
191
192 template<typename _InputIterator>
193 set(_InputIterator __first, _InputIterator __last)
194 : _M_t()
195 { _M_t._M_insert_range_unique(__first, __last); }
196
197
198
199
200
201
202
203
204
205
206
207
208
209 template<typename _InputIterator>
210 set(_InputIterator __first, _InputIterator __last,
211 const _Compare& __comp,
213 : _M_t(__comp, _Key_alloc_type(__a))
214 { _M_t._M_insert_range_unique(__first, __last); }
215
216
217
218
219
220
221#if __cplusplus < 201103L
223 : _M_t(__x._M_t) { }
224#else
226
227
228
229
230
231
232
234
235
236
237
238
239
240
241
242
243
244
246 const _Compare& __comp = _Compare(),
248 : _M_t(__comp, _Key_alloc_type(__a))
249 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }
250
251
252 explicit
254 : _M_t(_Key_alloc_type(__a)) { }
255
256
257 set(const set& __x, const __type_identity_t<allocator_type>& __a)
258 : _M_t(__x._M_t, _Key_alloc_type(__a)) { }
259
260
261 set(set&& __x, const __type_identity_t<allocator_type>& __a)
263 && _Alloc_traits::_S_always_equal())
264 : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
265
266
268 : _M_t(_Key_alloc_type(__a))
269 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }
270
271
272 template<typename _InputIterator>
273 set(_InputIterator __first, _InputIterator __last,
275 : _M_t(_Key_alloc_type(__a))
276 { _M_t._M_insert_range_unique(__first, __last); }
277
278
279
280
281
282
284#endif
285
286
287
288
289
290
291#if __cplusplus < 201103L
294 {
295 _M_t = __x._M_t;
296 return *this;
297 }
298#else
301
302
305
306
307
308
309
310
311
312
313
314
315
316
319 {
320 _M_t._M_assign_unique(__l.begin(), __l.end());
321 return *this;
322 }
323#endif
324
325
326
327
330 { return _M_t.key_comp(); }
331
334 { return _M_t.key_comp(); }
335
339
340
341
342
343
344
346 begin() const _GLIBCXX_NOEXCEPT
347 { return _M_t.begin(); }
348
349
350
351
352
353
355 end() const _GLIBCXX_NOEXCEPT
356 { return _M_t.end(); }
357
358
359
360
361
362
365 { return _M_t.rbegin(); }
366
367
368
369
370
371
373 rend() const _GLIBCXX_NOEXCEPT
374 { return _M_t.rend(); }
375
376#if __cplusplus >= 201103L
377
378
379
380
381
384 { return _M_t.begin(); }
385
386
387
388
389
390
393 { return _M_t.end(); }
394
395
396
397
398
399
402 { return _M_t.rbegin(); }
403
404
405
406
407
408
411 { return _M_t.rend(); }
412#endif
413
414
415 _GLIBCXX_NODISCARD bool
416 empty() const _GLIBCXX_NOEXCEPT
417 { return _M_t.empty(); }
418
419
421 size() const _GLIBCXX_NOEXCEPT
422 { return _M_t.size(); }
423
424
427 { return _M_t.max_size(); }
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442 void
444 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
445 { _M_t.swap(__x._M_t); }
446
447
448#if __cplusplus >= 201103L
449
450
451
452
453
454
455
456
457
458
459
460
461
462 template<typename... _Args>
465 { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488 template<typename... _Args>
491 {
492 return _M_t._M_emplace_hint_unique(__pos,
493 std::forward<_Args>(__args)...);
494 }
495#endif
496
497
498
499
500
501
502
503
504
505
506
507
508
509
512 {
514 _M_t._M_insert_unique(__x);
516 }
517
518#if __cplusplus >= 201103L
521 {
523 _M_t._M_insert_unique(std::move(__x));
525 }
526#endif
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
549 { return _M_t._M_insert_unique_(__position, __x); }
550
551#if __cplusplus >= 201103L
554 { return _M_t._M_insert_unique_(__position, std::move(__x)); }
555#endif
556
557
558
559
560
561
562
563
564
565
566 template<typename _InputIterator>
567 void
568 insert(_InputIterator __first, _InputIterator __last)
569 { _M_t._M_insert_range_unique(__first, __last); }
570
571#if __cplusplus >= 201103L
572
573
574
575
576
577
578
579 void
581 { this->insert(__l.begin(), __l.end()); }
582#endif
583
584#if __cplusplus > 201402L
585
586 node_type
588 {
589 __glibcxx_assert(__pos != end());
590 return _M_t.extract(__pos);
591 }
592
593
594 node_type
596 { return _M_t.extract(__x); }
597
598
599 insert_return_type
601 { return _M_t._M_reinsert_node_unique(std::move(__nh)); }
602
603
606 { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
607
608 template<typename, typename>
609 friend struct std::_Rb_tree_merge_helper;
610
611 template<typename _Compare1>
612 void
614 {
615 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>;
616 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
617 }
618
619 template<typename _Compare1>
620 void
621 merge(set<_Key, _Compare1, _Alloc>&& __source)
622 { merge(__source); }
623
624 template<typename _Compare1>
625 void
626 merge(multiset<_Key, _Compare1, _Alloc>& __source)
627 {
628 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>;
629 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
630 }
631
632 template<typename _Compare1>
633 void
634 merge(multiset<_Key, _Compare1, _Alloc>&& __source)
635 { merge(__source); }
636#endif
637
638#if __cplusplus >= 201103L
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654 _GLIBCXX_ABI_TAG_CXX11
657 { return _M_t.erase(__position); }
658#else
659
660
661
662
663
664
665
666
667
668
669 void
671 { _M_t.erase(__position); }
672#endif
673
674
675
676
677
678
679
680
681
682
683
684
687 { return _M_t.erase(__x); }
688
689#if __cplusplus >= 201103L
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706 _GLIBCXX_ABI_TAG_CXX11
709 { return _M_t.erase(__first, __last); }
710#else
711
712
713
714
715
716
717
718
719
720
721
722
723 void
725 { _M_t.erase(__first, __last); }
726#endif
727
728
729
730
731
732
733
734 void
736 { _M_t.clear(); }
737
738
739
740
741
742
743
744
745
746
747
748
751 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
752
753#if __cplusplus > 201103L
754 template<typename _Kt>
755 auto
757 -> decltype(_M_t._M_count_tr(__x))
758 { return _M_t._M_count_tr(__x); }
759#endif
760
761
762#if __cplusplus > 201703L
763
764
765
766
767
768
769 bool
771 { return _M_t.find(__x) != _M_t.end(); }
772
773 template<typename _Kt>
774 auto
776 -> decltype(_M_t._M_find_tr(__x), void(), true)
777 { return _M_t._M_find_tr(__x) != _M_t.end(); }
778
779#endif
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
797 { return _M_t.find(__x); }
798
801 { return _M_t.find(__x); }
802
803#if __cplusplus > 201103L
804 template<typename _Kt>
805 auto
807 -> decltype(iterator{_M_t._M_find_tr(__x)})
808 { return iterator{_M_t._M_find_tr(__x)}; }
809
810 template<typename _Kt>
811 auto
812 find(const _Kt& __x) const
815#endif
816
817
818
819
820
821
822
823
824
825
826
827
828
829
832 { return _M_t.lower_bound(__x); }
833
836 { return _M_t.lower_bound(__x); }
837
838#if __cplusplus > 201103L
839 template<typename _Kt>
840 auto
842 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
843 { return iterator(_M_t._M_lower_bound_tr(__x)); }
844
845 template<typename _Kt>
846 auto
848 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
849 { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
850#endif
851
852
853
854
855
856
857
858
859
862 { return _M_t.upper_bound(__x); }
863
866 { return _M_t.upper_bound(__x); }
867
868#if __cplusplus > 201103L
869 template<typename _Kt>
870 auto
872 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
873 { return iterator(_M_t._M_upper_bound_tr(__x)); }
874
875 template<typename _Kt>
876 auto
878 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
879 { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
880#endif
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
901 { return _M_t.equal_range(__x); }
902
905 { return _M_t.equal_range(__x); }
906
907#if __cplusplus > 201103L
908 template<typename _Kt>
909 auto
913
914 template<typename _Kt>
915 auto
919#endif
920
921
922 template<typename _K1, typename _C1, typename _A1>
923 friend bool
925
926#if __cpp_lib_three_way_comparison
927 template<typename _K1, typename _C1, typename _A1>
928 friend __detail::__synth3way_t<_K1>
930#else
931 template<typename _K1, typename _C1, typename _A1>
932 friend bool
934#endif
935 };
936
937#if __cpp_deduction_guides >= 201606
938
939 template<typename _InputIterator,
940 typename _Compare =
941 less<typename iterator_traits<_InputIterator>::value_type>,
942 typename _Allocator =
943 allocator<typename iterator_traits<_InputIterator>::value_type>,
944 typename = _RequireInputIter<_InputIterator>,
945 typename = _RequireNotAllocator<_Compare>,
946 typename = _RequireAllocator<_Allocator>>
947 set(_InputIterator, _InputIterator,
948 _Compare = _Compare(), _Allocator = _Allocator())
949 -> set<typename iterator_traits<_InputIterator>::value_type,
950 _Compare, _Allocator>;
951
952 template<typename _Key, typename _Compare = less<_Key>,
953 typename _Allocator = allocator<_Key>,
954 typename = _RequireNotAllocator<_Compare>,
955 typename = _RequireAllocator<_Allocator>>
956 set(initializer_list<_Key>,
957 _Compare = _Compare(), _Allocator = _Allocator())
958 -> set<_Key, _Compare, _Allocator>;
959
960 template<typename _InputIterator, typename _Allocator,
961 typename = _RequireInputIter<_InputIterator>,
962 typename = _RequireAllocator<_Allocator>>
963 set(_InputIterator, _InputIterator, _Allocator)
964 -> set<typename iterator_traits<_InputIterator>::value_type,
965 less<typename iterator_traits<_InputIterator>::value_type>,
966 _Allocator>;
967
968 template<typename _Key, typename _Allocator,
969 typename = _RequireAllocator<_Allocator>>
970 set(initializer_list<_Key>, _Allocator)
971 -> set<_Key, less<_Key>, _Allocator>;
972
973#endif
974
975
976
977
978
979
980
981
982
983
984
985 template<typename _Key, typename _Compare, typename _Alloc>
986 inline bool
989 { return __x._M_t == __y._M_t; }
990
991#if __cpp_lib_three_way_comparison
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006 template<typename _Key, typename _Compare, typename _Alloc>
1007 inline __detail::__synth3way_t<_Key>
1008 operator<=>(const set<_Key, _Compare, _Alloc>& __x,
1009 const set<_Key, _Compare, _Alloc>& __y)
1010 { return __x._M_t <=> __y._M_t; }
1011#else
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023 template<typename _Key, typename _Compare, typename _Alloc>
1027 { return __x._M_t < __y._M_t; }
1028
1029
1030 template<typename _Key, typename _Compare, typename _Alloc>
1031 inline bool
1034 { return !(__x == __y); }
1035
1036
1037 template<typename _Key, typename _Compare, typename _Alloc>
1038 inline bool
1041 { return __y < __x; }
1042
1043
1044 template<typename _Key, typename _Compare, typename _Alloc>
1048 { return !(__y < __x); }
1049
1050
1051 template<typename _Key, typename _Compare, typename _Alloc>
1052 inline bool
1055 { return !(__x < __y); }
1056#endif
1057
1058
1059 template<typename _Key, typename _Compare, typename _Alloc>
1060 inline void
1062 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1063 { __x.swap(__y); }
1064
1065_GLIBCXX_END_NAMESPACE_CONTAINER
1066
1067#if __cplusplus > 201402L
1068
1069 template<typename _Val, typename _Cmp1, typename _Alloc, typename _Cmp2>
1070 struct
1071 _Rb_tree_merge_helper<_GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>, _Cmp2>
1072 {
1073 private:
1074 friend class _GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>;
1075
1076 static auto&
1077 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set)
1078 { return __set._M_t; }
1079
1080 static auto&
1081 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set)
1082 { return __set._M_t; }
1083 };
1084#endif
1085
1086_GLIBCXX_END_NAMESPACE_VERSION
1087}
1088#endif
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
ISO C++ entities toplevel namespace is std.
is_nothrow_copy_constructible
Node handle type for maps.
Return type of insert(node_handle&&) on unique maps/sets.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
A standard container made up of unique keys, which can be retrieved in logarithmic time.
set(set &&__x, const __type_identity_t< allocator_type > &__a) noexcept(is_nothrow_copy_constructible< _Compare >::value &&_Alloc_traits::_S_always_equal())
Allocator-extended move constructor.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
set(_InputIterator __first, _InputIterator __last, const _Compare &__comp, const allocator_type &__a=allocator_type())
Builds a set from a range.
size_type count(const key_type &__x) const
Finds the number of elements.
_Rep_type::difference_type difference_type
Iterator-related typedefs.
node_type extract(const_iterator __pos)
Extract a node.
set & operator=(initializer_list< value_type > __l)
Set list assignment operator.
_GLIBCXX_ABI_TAG_CXX11 iterator erase(const_iterator __position)
Erases an element from a set.
set(set &&)=default
Set move constructor
void swap(set &__x) noexcept(/*conditional */)
Swaps data with another set.
_Compare value_compare
Public typedefs.
value_compare value_comp() const
Returns the comparison object with which the set was constructed.
iterator cbegin() const noexcept
_Alloc allocator_type
Public typedefs.
_Rep_type::const_iterator const_iterator
Iterator-related typedefs.
_Alloc_traits::const_pointer const_pointer
Iterator-related typedefs.
_Key value_type
Public typedefs.
auto contains(const _Kt &__x) const -> decltype(_M_t._M_find_tr(__x), void(), true)
Finds whether an element with the given key exists.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
auto lower_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
Finds the beginning of a subsequence matching given key.
const_iterator upper_bound(const key_type &__x) const
Finds the end of a subsequence matching given key.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the set.
set(_InputIterator __first, _InputIterator __last)
Builds a set from a range.
iterator cend() const noexcept
auto count(const _Kt &__x) const -> decltype(_M_t._M_count_tr(__x))
Finds the number of elements.
insert_return_type insert(node_type &&__nh)
Re-insert an extracted node.
iterator insert(const_iterator __hint, node_type &&__nh)
Re-insert an extracted node.
iterator end() const noexcept
_Compare key_compare
Public typedefs.
size_type max_size() const noexcept
Returns the maximum size of the set.
_Key key_type
Public typedefs.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the set.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
auto find(const _Kt &__x) -> decltype(iterator{_M_t._M_find_tr(__x)})
Tries to locate an element in a set.
_Alloc_traits::const_reference const_reference
Iterator-related typedefs.
auto find(const _Kt &__x) const -> decltype(const_iterator{_M_t._M_find_tr(__x)})
Tries to locate an element in a set.
set()=default
Default constructor creates no elements.
auto lower_bound(const _Kt &__x) const -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
Finds the beginning of a subsequence matching given key.
set(const allocator_type &__a)
Allocator-extended default constructor.
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert an element into the set.
key_compare key_comp() const
Returns the comparison object with which the set was constructed.
reverse_iterator rbegin() const noexcept
_Alloc_traits::reference reference
Iterator-related typedefs.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
_GLIBCXX_ABI_TAG_CXX11 iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from a set.
reverse_iterator crbegin() const noexcept
auto upper_bound(const _Kt &__x) const -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
Finds the end of a subsequence matching given key.
auto equal_range(const _Kt &__x) -> decltype(pair< iterator, iterator >(_M_t._M_equal_range_tr(__x)))
Finds a subsequence matching given key.
auto equal_range(const _Kt &__x) const -> decltype(pair< iterator, iterator >(_M_t._M_equal_range_tr(__x)))
Finds a subsequence matching given key.
set(initializer_list< value_type > __l, const allocator_type &__a)
Allocator-extended initialier-list constructor.
_Alloc_traits::pointer pointer
Iterator-related typedefs.
size_type size() const noexcept
Returns the size of the set.
_Rep_type::const_reverse_iterator const_reverse_iterator
Iterator-related typedefs.
_Rep_type::const_iterator iterator
Iterator-related typedefs.
_Rep_type::const_reverse_iterator reverse_iterator
Iterator-related typedefs.
reverse_iterator crend() const noexcept
iterator insert(const_iterator __position, const value_type &__x)
Attempts to insert an element into the set.
const_iterator lower_bound(const key_type &__x) const
Finds the beginning of a subsequence matching given key.
set(_InputIterator __first, _InputIterator __last, const allocator_type &__a)
Allocator-extended range constructor.
set(const set &__x, const __type_identity_t< allocator_type > &__a)
Allocator-extended copy constructor.
set(initializer_list< value_type > __l, const _Compare &__comp=_Compare(), const allocator_type &__a=allocator_type())
Builds a set from an initializer_list.
allocator_type get_allocator() const noexcept
Returns the allocator object with which the set was constructed.
_Rep_type::size_type size_type
Iterator-related typedefs.
set(const set &)=default
Set copy constructor.
iterator upper_bound(const key_type &__x)
Finds the end of a subsequence matching given key.
iterator lower_bound(const key_type &__x)
Finds the beginning of a subsequence matching given key.
auto upper_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
Finds the end of a subsequence matching given key.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to insert an element into the set.
set & operator=(const set &)=default
Set assignment operator.
iterator begin() const noexcept
node_type extract(const key_type &__x)
Extract a node.
set(const _Compare &__comp, const allocator_type &__a=allocator_type())
Creates a set with no elements.
iterator find(const key_type &__x)
Tries to locate an element in a set.
set & operator=(set &&)=default
Move assignment operator.
bool empty() const noexcept
Returns true if the set is empty.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
const_iterator find(const key_type &__x) const
Tries to locate an element in a set.
reverse_iterator rend() const noexcept
Uniform interface to C++98 and C++11 allocators.