]>
Commit | Line | Data |
---|---|---|
285b36d6 BK |
1 | // Debugging set implementation -*- C++ -*- |
2 | ||
99dee823 | 3 | // Copyright (C) 2003-2021 Free Software Foundation, Inc. |
285b36d6 BK |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
285b36d6 BK |
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 | ||
748086b7 JJ |
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. | |
285b36d6 | 19 | |
748086b7 JJ |
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/>. | |
285b36d6 | 24 | |
78a53887 BK |
25 | /** @file debug/set.h |
26 | * This file is a GNU debug extension to the Standard C++ Library. | |
27 | */ | |
28 | ||
285b36d6 BK |
29 | #ifndef _GLIBCXX_DEBUG_SET_H |
30 | #define _GLIBCXX_DEBUG_SET_H 1 | |
31 | ||
32 | #include <debug/safe_sequence.h> | |
15ee1a77 | 33 | #include <debug/safe_container.h> |
285b36d6 BK |
34 | #include <debug/safe_iterator.h> |
35 | #include <utility> | |
36 | ||
15ee1a77 | 37 | namespace std _GLIBCXX_VISIBILITY(default) |
3cbc7af0 | 38 | { |
45f388bb | 39 | namespace __debug |
285b36d6 | 40 | { |
1ceb9e06 | 41 | /// Class std::set with safety/checking/debug instrumentation. |
285b36d6 BK |
42 | template<typename _Key, typename _Compare = std::less<_Key>, |
43 | typename _Allocator = std::allocator<_Key> > | |
44 | class set | |
15ee1a77 FD |
45 | : public __gnu_debug::_Safe_container< |
46 | set<_Key, _Compare, _Allocator>, _Allocator, | |
47 | __gnu_debug::_Safe_node_sequence>, | |
48 | public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator> | |
285b36d6 | 49 | { |
15ee1a77 FD |
50 | typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base; |
51 | typedef __gnu_debug::_Safe_container< | |
52 | set, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; | |
526da49c | 53 | |
15ee1a77 FD |
54 | typedef typename _Base::const_iterator _Base_const_iterator; |
55 | typedef typename _Base::iterator _Base_iterator; | |
afe96d41 | 56 | typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; |
15ee1a77 | 57 | |
e9afbed0 FD |
58 | template<typename _ItT, typename _SeqT, typename _CatT> |
59 | friend class ::__gnu_debug::_Safe_iterator; | |
60 | ||
eca833b8 JW |
61 | // Reference wrapper for base class. Disambiguates set(const _Base&) |
62 | // from copy constructor by requiring a user-defined conversion. | |
63 | // See PR libstdc++/90102. | |
64 | struct _Base_ref | |
65 | { | |
66 | _Base_ref(const _Base& __r) : _M_ref(__r) { } | |
67 | ||
68 | const _Base& _M_ref; | |
69 | }; | |
70 | ||
285b36d6 BK |
71 | public: |
72 | // types: | |
15ee1a77 FD |
73 | typedef _Key key_type; |
74 | typedef _Key value_type; | |
75 | typedef _Compare key_compare; | |
76 | typedef _Compare value_compare; | |
77 | typedef _Allocator allocator_type; | |
78 | typedef typename _Base::reference reference; | |
79 | typedef typename _Base::const_reference const_reference; | |
526da49c | 80 | |
afe96d41 | 81 | typedef __gnu_debug::_Safe_iterator<_Base_iterator, set> |
15ee1a77 | 82 | iterator; |
afe96d41 | 83 | typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set> |
15ee1a77 | 84 | const_iterator; |
285b36d6 | 85 | |
15ee1a77 FD |
86 | typedef typename _Base::size_type size_type; |
87 | typedef typename _Base::difference_type difference_type; | |
88 | typedef typename _Base::pointer pointer; | |
89 | typedef typename _Base::const_pointer const_pointer; | |
90 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
91 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
526da49c | 92 | |
285b36d6 | 93 | // 23.3.3.1 construct/copy/destroy: |
c3cdd71f | 94 | |
15ee1a77 | 95 | #if __cplusplus < 201103L |
c3cdd71f JW |
96 | set() : _Base() { } |
97 | ||
ed540c0a | 98 | set(const set& __x) |
4c2d93db | 99 | : _Base(__x) { } |
526da49c | 100 | |
15ee1a77 FD |
101 | ~set() { } |
102 | #else | |
103 | set() = default; | |
104 | set(const set&) = default; | |
105 | set(set&&) = default; | |
988499f4 JM |
106 | |
107 | set(initializer_list<value_type> __l, | |
108 | const _Compare& __comp = _Compare(), | |
109 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 110 | : _Base(__l, __comp, __a) { } |
51835a80 FD |
111 | |
112 | explicit | |
113 | set(const allocator_type& __a) | |
114 | : _Base(__a) { } | |
115 | ||
116 | set(const set& __x, const allocator_type& __a) | |
117 | : _Base(__x, __a) { } | |
118 | ||
119 | set(set&& __x, const allocator_type& __a) | |
8b0cd47a | 120 | noexcept( noexcept(_Base(std::move(__x._M_base()), __a)) ) |
15ee1a77 FD |
121 | : _Safe(std::move(__x._M_safe()), __a), |
122 | _Base(std::move(__x._M_base()), __a) { } | |
51835a80 FD |
123 | |
124 | set(initializer_list<value_type> __l, const allocator_type& __a) | |
15ee1a77 | 125 | : _Base(__l, __a) { } |
51835a80 FD |
126 | |
127 | template<typename _InputIterator> | |
15ee1a77 | 128 | set(_InputIterator __first, _InputIterator __last, |
51835a80 | 129 | const allocator_type& __a) |
90aabc7e FD |
130 | : _Base(__gnu_debug::__base( |
131 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
15ee1a77 FD |
132 | __gnu_debug::__base(__last), __a) { } |
133 | ||
134 | ~set() = default; | |
ed540c0a | 135 | #endif |
526da49c | 136 | |
15ee1a77 FD |
137 | explicit set(const _Compare& __comp, |
138 | const _Allocator& __a = _Allocator()) | |
139 | : _Base(__comp, __a) { } | |
140 | ||
141 | template<typename _InputIterator> | |
142 | set(_InputIterator __first, _InputIterator __last, | |
143 | const _Compare& __comp = _Compare(), | |
144 | const _Allocator& __a = _Allocator()) | |
90aabc7e FD |
145 | : _Base(__gnu_debug::__base( |
146 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
15ee1a77 FD |
147 | __gnu_debug::__base(__last), |
148 | __comp, __a) { } | |
526da49c | 149 | |
eca833b8 JW |
150 | set(_Base_ref __x) |
151 | : _Base(__x._M_ref) { } | |
15ee1a77 FD |
152 | |
153 | #if __cplusplus < 201103L | |
ed540c0a CJ |
154 | set& |
155 | operator=(const set& __x) | |
285b36d6 | 156 | { |
15ee1a77 | 157 | this->_M_safe() = __x; |
51835a80 | 158 | _M_base() = __x; |
285b36d6 BK |
159 | return *this; |
160 | } | |
15ee1a77 FD |
161 | #else |
162 | set& | |
163 | operator=(const set&) = default; | |
526da49c | 164 | |
ed540c0a | 165 | set& |
15ee1a77 | 166 | operator=(set&&) = default; |
988499f4 JM |
167 | |
168 | set& | |
169 | operator=(initializer_list<value_type> __l) | |
170 | { | |
51835a80 FD |
171 | _M_base() = __l; |
172 | this->_M_invalidate_all(); | |
988499f4 JM |
173 | return *this; |
174 | } | |
ed540c0a CJ |
175 | #endif |
176 | ||
285b36d6 | 177 | using _Base::get_allocator; |
526da49c | 178 | |
285b36d6 | 179 | // iterators: |
526da49c | 180 | iterator |
d3677132 | 181 | begin() _GLIBCXX_NOEXCEPT |
285b36d6 | 182 | { return iterator(_Base::begin(), this); } |
526da49c BI |
183 | |
184 | const_iterator | |
d3677132 | 185 | begin() const _GLIBCXX_NOEXCEPT |
285b36d6 | 186 | { return const_iterator(_Base::begin(), this); } |
526da49c BI |
187 | |
188 | iterator | |
d3677132 | 189 | end() _GLIBCXX_NOEXCEPT |
285b36d6 | 190 | { return iterator(_Base::end(), this); } |
526da49c BI |
191 | |
192 | const_iterator | |
d3677132 | 193 | end() const _GLIBCXX_NOEXCEPT |
285b36d6 | 194 | { return const_iterator(_Base::end(), this); } |
526da49c BI |
195 | |
196 | reverse_iterator | |
d3677132 | 197 | rbegin() _GLIBCXX_NOEXCEPT |
285b36d6 | 198 | { return reverse_iterator(end()); } |
526da49c BI |
199 | |
200 | const_reverse_iterator | |
d3677132 | 201 | rbegin() const _GLIBCXX_NOEXCEPT |
285b36d6 | 202 | { return const_reverse_iterator(end()); } |
526da49c BI |
203 | |
204 | reverse_iterator | |
d3677132 | 205 | rend() _GLIBCXX_NOEXCEPT |
285b36d6 | 206 | { return reverse_iterator(begin()); } |
526da49c BI |
207 | |
208 | const_reverse_iterator | |
d3677132 | 209 | rend() const _GLIBCXX_NOEXCEPT |
285b36d6 | 210 | { return const_reverse_iterator(begin()); } |
526da49c | 211 | |
734f5023 | 212 | #if __cplusplus >= 201103L |
0cd50f89 | 213 | const_iterator |
d3677132 | 214 | cbegin() const noexcept |
0cd50f89 PC |
215 | { return const_iterator(_Base::begin(), this); } |
216 | ||
217 | const_iterator | |
d3677132 | 218 | cend() const noexcept |
0cd50f89 PC |
219 | { return const_iterator(_Base::end(), this); } |
220 | ||
221 | const_reverse_iterator | |
d3677132 | 222 | crbegin() const noexcept |
0cd50f89 PC |
223 | { return const_reverse_iterator(end()); } |
224 | ||
225 | const_reverse_iterator | |
d3677132 | 226 | crend() const noexcept |
0cd50f89 PC |
227 | { return const_reverse_iterator(begin()); } |
228 | #endif | |
229 | ||
285b36d6 BK |
230 | // capacity: |
231 | using _Base::empty; | |
232 | using _Base::size; | |
233 | using _Base::max_size; | |
526da49c | 234 | |
285b36d6 | 235 | // modifiers: |
734f5023 | 236 | #if __cplusplus >= 201103L |
55826ab6 FD |
237 | template<typename... _Args> |
238 | std::pair<iterator, bool> | |
239 | emplace(_Args&&... __args) | |
240 | { | |
241 | auto __res = _Base::emplace(std::forward<_Args>(__args)...); | |
784779d4 | 242 | return { { __res.first, this }, __res.second }; |
55826ab6 FD |
243 | } |
244 | ||
245 | template<typename... _Args> | |
246 | iterator | |
247 | emplace_hint(const_iterator __pos, _Args&&... __args) | |
248 | { | |
249 | __glibcxx_check_insert(__pos); | |
784779d4 FD |
250 | return |
251 | { | |
252 | _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...), | |
253 | this | |
254 | }; | |
55826ab6 FD |
255 | } |
256 | #endif | |
257 | ||
526da49c | 258 | std::pair<iterator, bool> |
285b36d6 BK |
259 | insert(const value_type& __x) |
260 | { | |
285b36d6 BK |
261 | std::pair<_Base_iterator, bool> __res = _Base::insert(__x); |
262 | return std::pair<iterator, bool>(iterator(__res.first, this), | |
263 | __res.second); | |
264 | } | |
526da49c | 265 | |
734f5023 | 266 | #if __cplusplus >= 201103L |
e6a05448 PC |
267 | std::pair<iterator, bool> |
268 | insert(value_type&& __x) | |
269 | { | |
784779d4 FD |
270 | auto __res = _Base::insert(std::move(__x)); |
271 | return { { __res.first, this }, __res.second }; | |
e6a05448 PC |
272 | } |
273 | #endif | |
274 | ||
526da49c | 275 | iterator |
6b6d5d09 | 276 | insert(const_iterator __position, const value_type& __x) |
285b36d6 BK |
277 | { |
278 | __glibcxx_check_insert(__position); | |
279 | return iterator(_Base::insert(__position.base(), __x), this); | |
280 | } | |
526da49c | 281 | |
734f5023 | 282 | #if __cplusplus >= 201103L |
e6a05448 PC |
283 | iterator |
284 | insert(const_iterator __position, value_type&& __x) | |
285 | { | |
286 | __glibcxx_check_insert(__position); | |
784779d4 | 287 | return { _Base::insert(__position.base(), std::move(__x)), this }; |
e6a05448 PC |
288 | } |
289 | #endif | |
290 | ||
285b36d6 | 291 | template <typename _InputIterator> |
15ee1a77 FD |
292 | void |
293 | insert(_InputIterator __first, _InputIterator __last) | |
294 | { | |
24167c42 FD |
295 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
296 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
297 | ||
298 | if (__dist.second >= __gnu_debug::__dp_sign) | |
299 | _Base::insert(__gnu_debug::__unsafe(__first), | |
300 | __gnu_debug::__unsafe(__last)); | |
301 | else | |
302 | _Base::insert(__first, __last); | |
285b36d6 | 303 | } |
526da49c | 304 | |
734f5023 | 305 | #if __cplusplus >= 201103L |
988499f4 JM |
306 | void |
307 | insert(initializer_list<value_type> __l) | |
308 | { _Base::insert(__l); } | |
309 | #endif | |
310 | ||
2dbe56bd JW |
311 | #if __cplusplus > 201402L |
312 | using node_type = typename _Base::node_type; | |
adaefe2a | 313 | using insert_return_type = _Node_insert_return<iterator, node_type>; |
2dbe56bd JW |
314 | |
315 | node_type | |
316 | extract(const_iterator __position) | |
317 | { | |
318 | __glibcxx_check_erase(__position); | |
319 | this->_M_invalidate_if(_Equal(__position.base())); | |
320 | return _Base::extract(__position.base()); | |
321 | } | |
322 | ||
323 | node_type | |
324 | extract(const key_type& __key) | |
325 | { | |
326 | const auto __position = find(__key); | |
327 | if (__position != end()) | |
328 | return extract(__position); | |
329 | return {}; | |
330 | } | |
331 | ||
332 | insert_return_type | |
333 | insert(node_type&& __nh) | |
334 | { | |
335 | auto __ret = _Base::insert(std::move(__nh)); | |
336 | iterator __pos = iterator(__ret.position, this); | |
adaefe2a | 337 | return { __pos, __ret.inserted, std::move(__ret.node) }; |
2dbe56bd JW |
338 | } |
339 | ||
340 | iterator | |
341 | insert(const_iterator __hint, node_type&& __nh) | |
342 | { | |
343 | __glibcxx_check_insert(__hint); | |
784779d4 | 344 | return { _Base::insert(__hint.base(), std::move(__nh)), this }; |
2dbe56bd JW |
345 | } |
346 | ||
347 | using _Base::merge; | |
348 | #endif // C++17 | |
349 | ||
734f5023 | 350 | #if __cplusplus >= 201103L |
7b1e8acf | 351 | _GLIBCXX_ABI_TAG_CXX11 |
5ab06c6d | 352 | iterator |
6b6d5d09 | 353 | erase(const_iterator __position) |
5ab06c6d PC |
354 | { |
355 | __glibcxx_check_erase(__position); | |
afe96d41 | 356 | this->_M_invalidate_if(_Equal(__position.base())); |
784779d4 | 357 | return { _Base::erase(__position.base()), this }; |
5ab06c6d PC |
358 | } |
359 | #else | |
526da49c | 360 | void |
285b36d6 BK |
361 | erase(iterator __position) |
362 | { | |
363 | __glibcxx_check_erase(__position); | |
afe96d41 | 364 | this->_M_invalidate_if(_Equal(__position.base())); |
285b36d6 BK |
365 | _Base::erase(__position.base()); |
366 | } | |
5ab06c6d | 367 | #endif |
526da49c BI |
368 | |
369 | size_type | |
285b36d6 BK |
370 | erase(const key_type& __x) |
371 | { | |
afe96d41 FD |
372 | _Base_iterator __victim = _Base::find(__x); |
373 | if (__victim == _Base::end()) | |
15ee1a77 | 374 | return 0; |
285b36d6 | 375 | else |
afe96d41 FD |
376 | { |
377 | this->_M_invalidate_if(_Equal(__victim)); | |
378 | _Base::erase(__victim); | |
379 | return 1; | |
380 | } | |
285b36d6 | 381 | } |
526da49c | 382 | |
734f5023 | 383 | #if __cplusplus >= 201103L |
7b1e8acf | 384 | _GLIBCXX_ABI_TAG_CXX11 |
5ab06c6d | 385 | iterator |
6b6d5d09 | 386 | erase(const_iterator __first, const_iterator __last) |
5ab06c6d PC |
387 | { |
388 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
389 | // 151. can't currently clear() empty container | |
390 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
391 | for (_Base_const_iterator __victim = __first.base(); |
392 | __victim != __last.base(); ++__victim) | |
393 | { | |
e0b9bc23 | 394 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(), |
afe96d41 FD |
395 | _M_message(__gnu_debug::__msg_valid_range) |
396 | ._M_iterator(__first, "first") | |
397 | ._M_iterator(__last, "last")); | |
398 | this->_M_invalidate_if(_Equal(__victim)); | |
399 | } | |
784779d4 FD |
400 | |
401 | return { _Base::erase(__first.base(), __last.base()), this }; | |
5ab06c6d PC |
402 | } |
403 | #else | |
526da49c | 404 | void |
285b36d6 BK |
405 | erase(iterator __first, iterator __last) |
406 | { | |
407 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
408 | // 151. can't currently clear() empty container | |
409 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
410 | for (_Base_iterator __victim = __first.base(); |
411 | __victim != __last.base(); ++__victim) | |
412 | { | |
413 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), | |
414 | _M_message(__gnu_debug::__msg_valid_range) | |
415 | ._M_iterator(__first, "first") | |
416 | ._M_iterator(__last, "last")); | |
417 | this->_M_invalidate_if(_Equal(__victim)); | |
418 | } | |
419 | _Base::erase(__first.base(), __last.base()); | |
285b36d6 | 420 | } |
5ab06c6d | 421 | #endif |
526da49c BI |
422 | |
423 | void | |
ed540c0a | 424 | swap(set& __x) |
c5d9ec56 | 425 | _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) |
285b36d6 | 426 | { |
15ee1a77 | 427 | _Safe::_M_swap(__x); |
285b36d6 | 428 | _Base::swap(__x); |
285b36d6 | 429 | } |
526da49c BI |
430 | |
431 | void | |
d3677132 | 432 | clear() _GLIBCXX_NOEXCEPT |
afe96d41 FD |
433 | { |
434 | this->_M_invalidate_all(); | |
435 | _Base::clear(); | |
436 | } | |
526da49c | 437 | |
285b36d6 BK |
438 | // observers: |
439 | using _Base::key_comp; | |
440 | using _Base::value_comp; | |
526da49c | 441 | |
285b36d6 | 442 | // set operations: |
526da49c | 443 | iterator |
285b36d6 BK |
444 | find(const key_type& __x) |
445 | { return iterator(_Base::find(__x), this); } | |
526da49c | 446 | |
285b36d6 BK |
447 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
448 | // 214. set::find() missing const overload | |
526da49c | 449 | const_iterator |
285b36d6 BK |
450 | find(const key_type& __x) const |
451 | { return const_iterator(_Base::find(__x), this); } | |
526da49c | 452 | |
d7b35f22 FD |
453 | #if __cplusplus > 201103L |
454 | template<typename _Kt, | |
455 | typename _Req = | |
456 | typename __has_is_transparent<_Compare, _Kt>::type> | |
457 | iterator | |
458 | find(const _Kt& __x) | |
459 | { return { _Base::find(__x), this }; } | |
460 | ||
461 | template<typename _Kt, | |
462 | typename _Req = | |
463 | typename __has_is_transparent<_Compare, _Kt>::type> | |
464 | const_iterator | |
465 | find(const _Kt& __x) const | |
466 | { return { _Base::find(__x), this }; } | |
467 | #endif | |
468 | ||
285b36d6 | 469 | using _Base::count; |
526da49c BI |
470 | |
471 | iterator | |
285b36d6 BK |
472 | lower_bound(const key_type& __x) |
473 | { return iterator(_Base::lower_bound(__x), this); } | |
526da49c | 474 | |
285b36d6 BK |
475 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
476 | // 214. set::find() missing const overload | |
526da49c | 477 | const_iterator |
285b36d6 BK |
478 | lower_bound(const key_type& __x) const |
479 | { return const_iterator(_Base::lower_bound(__x), this); } | |
526da49c | 480 | |
d7b35f22 FD |
481 | #if __cplusplus > 201103L |
482 | template<typename _Kt, | |
483 | typename _Req = | |
484 | typename __has_is_transparent<_Compare, _Kt>::type> | |
485 | iterator | |
486 | lower_bound(const _Kt& __x) | |
487 | { return { _Base::lower_bound(__x), this }; } | |
488 | ||
489 | template<typename _Kt, | |
490 | typename _Req = | |
491 | typename __has_is_transparent<_Compare, _Kt>::type> | |
492 | const_iterator | |
493 | lower_bound(const _Kt& __x) const | |
494 | { return { _Base::lower_bound(__x), this }; } | |
495 | #endif | |
496 | ||
526da49c | 497 | iterator |
285b36d6 BK |
498 | upper_bound(const key_type& __x) |
499 | { return iterator(_Base::upper_bound(__x), this); } | |
526da49c | 500 | |
285b36d6 BK |
501 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
502 | // 214. set::find() missing const overload | |
526da49c | 503 | const_iterator |
285b36d6 BK |
504 | upper_bound(const key_type& __x) const |
505 | { return const_iterator(_Base::upper_bound(__x), this); } | |
526da49c | 506 | |
d7b35f22 FD |
507 | #if __cplusplus > 201103L |
508 | template<typename _Kt, | |
509 | typename _Req = | |
510 | typename __has_is_transparent<_Compare, _Kt>::type> | |
511 | iterator | |
512 | upper_bound(const _Kt& __x) | |
513 | { return { _Base::upper_bound(__x), this }; } | |
514 | ||
515 | template<typename _Kt, | |
516 | typename _Req = | |
517 | typename __has_is_transparent<_Compare, _Kt>::type> | |
518 | const_iterator | |
519 | upper_bound(const _Kt& __x) const | |
520 | { return { _Base::upper_bound(__x), this }; } | |
521 | #endif | |
522 | ||
523 | std::pair<iterator, iterator> | |
285b36d6 BK |
524 | equal_range(const key_type& __x) |
525 | { | |
285b36d6 | 526 | std::pair<_Base_iterator, _Base_iterator> __res = |
15ee1a77 | 527 | _Base::equal_range(__x); |
285b36d6 BK |
528 | return std::make_pair(iterator(__res.first, this), |
529 | iterator(__res.second, this)); | |
530 | } | |
526da49c | 531 | |
285b36d6 BK |
532 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
533 | // 214. set::find() missing const overload | |
d7b35f22 | 534 | std::pair<const_iterator, const_iterator> |
285b36d6 BK |
535 | equal_range(const key_type& __x) const |
536 | { | |
d7b35f22 | 537 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
15ee1a77 | 538 | _Base::equal_range(__x); |
285b36d6 BK |
539 | return std::make_pair(const_iterator(__res.first, this), |
540 | const_iterator(__res.second, this)); | |
541 | } | |
526da49c | 542 | |
d7b35f22 FD |
543 | #if __cplusplus > 201103L |
544 | template<typename _Kt, | |
545 | typename _Req = | |
546 | typename __has_is_transparent<_Compare, _Kt>::type> | |
547 | std::pair<iterator, iterator> | |
548 | equal_range(const _Kt& __x) | |
549 | { | |
550 | auto __res = _Base::equal_range(__x); | |
551 | return { { __res.first, this }, { __res.second, this } }; | |
552 | } | |
553 | ||
554 | template<typename _Kt, | |
555 | typename _Req = | |
556 | typename __has_is_transparent<_Compare, _Kt>::type> | |
557 | std::pair<const_iterator, const_iterator> | |
558 | equal_range(const _Kt& __x) const | |
559 | { | |
560 | auto __res = _Base::equal_range(__x); | |
561 | return { { __res.first, this }, { __res.second, this } }; | |
562 | } | |
563 | #endif | |
564 | ||
526da49c | 565 | _Base& |
15ee1a77 | 566 | _M_base() _GLIBCXX_NOEXCEPT { return *this; } |
285b36d6 | 567 | |
526da49c | 568 | const _Base& |
15ee1a77 | 569 | _M_base() const _GLIBCXX_NOEXCEPT { return *this; } |
285b36d6 | 570 | }; |
526da49c | 571 | |
957f5fea VV |
572 | #if __cpp_deduction_guides >= 201606 |
573 | ||
574 | template<typename _InputIterator, | |
575 | typename _Compare = | |
576 | less<typename iterator_traits<_InputIterator>::value_type>, | |
577 | typename _Allocator = | |
578 | allocator<typename iterator_traits<_InputIterator>::value_type>, | |
579 | typename = _RequireInputIter<_InputIterator>, | |
c0cb38c2 | 580 | typename = _RequireNotAllocator<_Compare>, |
957f5fea VV |
581 | typename = _RequireAllocator<_Allocator>> |
582 | set(_InputIterator, _InputIterator, | |
c0cb38c2 FD |
583 | _Compare = _Compare(), _Allocator = _Allocator()) |
584 | -> set<typename iterator_traits<_InputIterator>::value_type, | |
585 | _Compare, _Allocator>; | |
586 | ||
587 | template<typename _Key, typename _Compare = less<_Key>, | |
588 | typename _Allocator = allocator<_Key>, | |
589 | typename = _RequireNotAllocator<_Compare>, | |
590 | typename = _RequireAllocator<_Allocator>> | |
591 | set(initializer_list<_Key>, | |
592 | _Compare = _Compare(), _Allocator = _Allocator()) | |
593 | -> set<_Key, _Compare, _Allocator>; | |
594 | ||
595 | template<typename _InputIterator, typename _Allocator, | |
596 | typename = _RequireInputIter<_InputIterator>, | |
597 | typename = _RequireAllocator<_Allocator>> | |
598 | set(_InputIterator, _InputIterator, _Allocator) | |
599 | -> set<typename iterator_traits<_InputIterator>::value_type, | |
600 | less<typename iterator_traits<_InputIterator>::value_type>, | |
601 | _Allocator>; | |
602 | ||
603 | template<typename _Key, typename _Allocator, | |
604 | typename = _RequireAllocator<_Allocator>> | |
605 | set(initializer_list<_Key>, _Allocator) | |
606 | -> set<_Key, less<_Key>, _Allocator>; | |
957f5fea | 607 | |
93843da6 | 608 | #endif // deduction guides |
957f5fea | 609 | |
285b36d6 | 610 | template<typename _Key, typename _Compare, typename _Allocator> |
526da49c | 611 | inline bool |
ed540c0a CJ |
612 | operator==(const set<_Key, _Compare, _Allocator>& __lhs, |
613 | const set<_Key, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
614 | { return __lhs._M_base() == __rhs._M_base(); } |
615 | ||
93843da6 JW |
616 | #if __cpp_lib_three_way_comparison |
617 | template<typename _Key, typename _Compare, typename _Alloc> | |
618 | inline __detail::__synth3way_t<_Key> | |
619 | operator<=>(const set<_Key, _Compare, _Alloc>& __lhs, | |
620 | const set<_Key, _Compare, _Alloc>& __rhs) | |
621 | { return __lhs._M_base() <=> __rhs._M_base(); } | |
622 | #else | |
285b36d6 | 623 | template<typename _Key, typename _Compare, typename _Allocator> |
526da49c | 624 | inline bool |
ed540c0a CJ |
625 | operator!=(const set<_Key, _Compare, _Allocator>& __lhs, |
626 | const set<_Key, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
627 | { return __lhs._M_base() != __rhs._M_base(); } |
628 | ||
629 | template<typename _Key, typename _Compare, typename _Allocator> | |
526da49c | 630 | inline bool |
ed540c0a CJ |
631 | operator<(const set<_Key, _Compare, _Allocator>& __lhs, |
632 | const set<_Key, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
633 | { return __lhs._M_base() < __rhs._M_base(); } |
634 | ||
635 | template<typename _Key, typename _Compare, typename _Allocator> | |
526da49c | 636 | inline bool |
ed540c0a CJ |
637 | operator<=(const set<_Key, _Compare, _Allocator>& __lhs, |
638 | const set<_Key, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
639 | { return __lhs._M_base() <= __rhs._M_base(); } |
640 | ||
641 | template<typename _Key, typename _Compare, typename _Allocator> | |
526da49c | 642 | inline bool |
ed540c0a CJ |
643 | operator>=(const set<_Key, _Compare, _Allocator>& __lhs, |
644 | const set<_Key, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
645 | { return __lhs._M_base() >= __rhs._M_base(); } |
646 | ||
647 | template<typename _Key, typename _Compare, typename _Allocator> | |
526da49c | 648 | inline bool |
ed540c0a CJ |
649 | operator>(const set<_Key, _Compare, _Allocator>& __lhs, |
650 | const set<_Key, _Compare, _Allocator>& __rhs) | |
285b36d6 | 651 | { return __lhs._M_base() > __rhs._M_base(); } |
93843da6 | 652 | #endif // three-way comparison |
285b36d6 BK |
653 | |
654 | template<typename _Key, typename _Compare, typename _Allocator> | |
655 | void | |
ed540c0a CJ |
656 | swap(set<_Key, _Compare, _Allocator>& __x, |
657 | set<_Key, _Compare, _Allocator>& __y) | |
c5d9ec56 | 658 | _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) |
285b36d6 | 659 | { return __x.swap(__y); } |
ed540c0a | 660 | |
45f388bb | 661 | } // namespace __debug |
3cbc7af0 | 662 | } // namespace std |
285b36d6 BK |
663 | |
664 | #endif |