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