libstdc++
debug/list
Go to the documentation of this file.
1// Debugging list implementation -*- C++ -*-
2
3// Copyright (C) 2003-2024 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/** @file debug/list
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_LIST
30#define _GLIBCXX_DEBUG_LIST 1
31
32#pragma GCC system_header
33
34#include <bits/c++config.h>
35namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
36 template<typename _Tp, typename _Allocator> class list;
37} } // namespace std::__debug
38
39#include <list>
40#include <debug/safe_sequence.h>
41#include <debug/safe_container.h>
42#include <debug/safe_iterator.h>
43
44namespace std _GLIBCXX_VISIBILITY(default)
45{
46namespace __debug
47{
48 /// Class std::list with safety/checking/debug instrumentation.
49 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
50 class list
51 : public __gnu_debug::_Safe_container<
52 list<_Tp, _Allocator>, _Allocator,
53 __gnu_debug::_Safe_node_sequence>,
54 public _GLIBCXX_STD_C::list<_Tp, _Allocator>
55 {
56 typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
57 typedef __gnu_debug::_Safe_container<
58 list, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
59
60 typedef typename _Base::iterator _Base_iterator;
61 typedef typename _Base::const_iterator _Base_const_iterator;
62 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
63 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
64
65 template<typename _ItT, typename _SeqT, typename _CatT>
66 friend class ::__gnu_debug::_Safe_iterator;
67
68 // Reference wrapper for base class. Disambiguates list(const _Base&)
69 // from copy constructor by requiring a user-defined conversion.
70 // See PR libstdc++/90102.
71 struct _Base_ref
72 {
73 _Base_ref(const _Base& __r) : _M_ref(__r) { }
74
75 const _Base& _M_ref;
76 };
77
78 public:
79 typedef typename _Base::reference reference;
80 typedef typename _Base::const_reference const_reference;
81
82 typedef __gnu_debug::_Safe_iterator<_Base_iterator, list>
83 iterator;
84 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
85 const_iterator;
86
87 typedef typename _Base::size_type size_type;
88 typedef typename _Base::difference_type difference_type;
89
90 typedef _Tp value_type;
91 typedef _Allocator allocator_type;
92 typedef typename _Base::pointer pointer;
93 typedef typename _Base::const_pointer const_pointer;
94 typedef std::reverse_iterator<iterator> reverse_iterator;
95 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
96
97 // 23.2.2.1 construct/copy/destroy:
98
99#if __cplusplus < 201103L
100 list()
101 : _Base() { }
102
103 list(const list& __x)
104 : _Base(__x) { }
105
106 ~list() { }
107#else
108 list() = default;
109 list(const list&) = default;
110 list(list&&) = default;
111
112 list(initializer_list<value_type> __l,
113 const allocator_type& __a = allocator_type())
114 : _Base(__l, __a) { }
115
116 ~list() = default;
117
118 list(const list& __x, const __type_identity_t<allocator_type>& __a)
119 : _Base(__x, __a) { }
120
121 list(list&& __x, const __type_identity_t<allocator_type>& __a)
122 noexcept(
123 std::is_nothrow_constructible<_Base,
124 _Base, const allocator_type&>::value )
125 : _Safe(std::move(__x), __a),
126 _Base(std::move(__x), __a) { }
127#endif
128
129 explicit
130 list(const _Allocator& __a) _GLIBCXX_NOEXCEPT
131 : _Base(__a) { }
132
133#if __cplusplus >= 201103L
134 explicit
135 list(size_type __n, const allocator_type& __a = allocator_type())
136 : _Base(__n, __a) { }
137
138 list(size_type __n, const __type_identity_t<_Tp>& __value,
139 const _Allocator& __a = _Allocator())
140 : _Base(__n, __value, __a) { }
141#else
142 explicit
143 list(size_type __n, const _Tp& __value = _Tp(),
144 const _Allocator& __a = _Allocator())
145 : _Base(__n, __value, __a) { }
146#endif
147
148#if __cplusplus >= 201103L
149 template<class _InputIterator,
150 typename = std::_RequireInputIter<_InputIterator>>
151#else
152 template<class _InputIterator>
153#endif
154 list(_InputIterator __first, _InputIterator __last,
155 const _Allocator& __a = _Allocator())
156 : _Base(__gnu_debug::__base(
157 __glibcxx_check_valid_constructor_range(__first, __last)),
158 __gnu_debug::__base(__last), __a)
159 { }
160
161 list(_Base_ref __x)
162 : _Base(__x._M_ref) { }
163
164#if __cplusplus >= 201103L
165 list&
166 operator=(const list&) = default;
167
168 list&
169 operator=(list&&) = default;
170
171 list&
172 operator=(initializer_list<value_type> __l)
173 {
174 this->_M_invalidate_all();
175 _Base::operator=(__l);
176 return *this;
177 }
178
179 void
180 assign(initializer_list<value_type> __l)
181 {
182 _Base::assign(__l);
183 this->_M_invalidate_all();
184 }
185#endif
186
187#if __cplusplus >= 201103L
188 template<class _InputIterator,
189 typename = std::_RequireInputIter<_InputIterator>>
190#else
191 template<class _InputIterator>
192#endif
193 void
194 assign(_InputIterator __first, _InputIterator __last)
195 {
196 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
197 __glibcxx_check_valid_range2(__first, __last, __dist);
198
199 if (__dist.second >= __gnu_debug::__dp_sign)
200 _Base::assign(__gnu_debug::__unsafe(__first),
201 __gnu_debug::__unsafe(__last));
202 else
203 _Base::assign(__first, __last);
204
205 this->_M_invalidate_all();
206 }
207
208 void
209 assign(size_type __n, const _Tp& __t)
210 {
211 _Base::assign(__n, __t);
212 this->_M_invalidate_all();
213 }
214
215 using _Base::get_allocator;
216
217 // iterators:
218 _GLIBCXX_NODISCARD
219 iterator
220 begin() _GLIBCXX_NOEXCEPT
221 { return iterator(_Base::begin(), this); }
222
223 _GLIBCXX_NODISCARD
224 const_iterator
225 begin() const _GLIBCXX_NOEXCEPT
226 { return const_iterator(_Base::begin(), this); }
227
228 _GLIBCXX_NODISCARD
229 iterator
230 end() _GLIBCXX_NOEXCEPT
231 { return iterator(_Base::end(), this); }
232
233 _GLIBCXX_NODISCARD
234 const_iterator
235 end() const _GLIBCXX_NOEXCEPT
236 { return const_iterator(_Base::end(), this); }
237
238 _GLIBCXX_NODISCARD
239 reverse_iterator
240 rbegin() _GLIBCXX_NOEXCEPT
241 { return reverse_iterator(end()); }
242
243 _GLIBCXX_NODISCARD
244 const_reverse_iterator
245 rbegin() const _GLIBCXX_NOEXCEPT
246 { return const_reverse_iterator(end()); }
247
248 _GLIBCXX_NODISCARD
249 reverse_iterator
250 rend() _GLIBCXX_NOEXCEPT
251 { return reverse_iterator(begin()); }
252
253 _GLIBCXX_NODISCARD
254 const_reverse_iterator
255 rend() const _GLIBCXX_NOEXCEPT
256 { return const_reverse_iterator(begin()); }
257
258#if __cplusplus >= 201103L
259 [[__nodiscard__]]
260 const_iterator
261 cbegin() const noexcept
262 { return const_iterator(_Base::begin(), this); }
263
264 [[__nodiscard__]]
265 const_iterator
266 cend() const noexcept
267 { return const_iterator(_Base::end(), this); }
268
269 [[__nodiscard__]]
270 const_reverse_iterator
271 crbegin() const noexcept
272 { return const_reverse_iterator(end()); }
273
274 [[__nodiscard__]]
275 const_reverse_iterator
276 crend() const noexcept
277 { return const_reverse_iterator(begin()); }
278#endif
279
280 // 23.2.2.2 capacity:
281 using _Base::empty;
282 using _Base::size;
283 using _Base::max_size;
284
285#if __cplusplus >= 201103L
286 void
287 resize(size_type __sz)
288 {
289 this->_M_detach_singular();
290
291 // if __sz < size(), invalidate all iterators in [begin + __sz, end())
292 _Base_iterator __victim = _Base::begin();
293 _Base_iterator __end = _Base::end();
294 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
295 ++__victim;
296
297 for (; __victim != __end; ++__victim)
298 this->_M_invalidate_if(_Equal(__victim));
299
300 __try
301 {
302 _Base::resize(__sz);
303 }
304 __catch(...)
305 {
306 this->_M_revalidate_singular();
307 __throw_exception_again;
308 }
309 }
310
311 void
312 resize(size_type __sz, const _Tp& __c)
313 {
314 this->_M_detach_singular();
315
316 // if __sz < size(), invalidate all iterators in [begin + __sz, end())
317 _Base_iterator __victim = _Base::begin();
318 _Base_iterator __end = _Base::end();
319 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
320 ++__victim;
321
322 for (; __victim != __end; ++__victim)
323 this->_M_invalidate_if(_Equal(__victim));
324
325 __try
326 {
327 _Base::resize(__sz, __c);
328 }
329 __catch(...)
330 {
331 this->_M_revalidate_singular();
332 __throw_exception_again;
333 }
334 }
335#else
336 void
337 resize(size_type __sz, _Tp __c = _Tp())
338 {
339 this->_M_detach_singular();
340
341 // if __sz < size(), invalidate all iterators in [begin + __sz, end())
342 _Base_iterator __victim = _Base::begin();
343 _Base_iterator __end = _Base::end();
344 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
345 ++__victim;
346
347 for (; __victim != __end; ++__victim)
348 this->_M_invalidate_if(_Equal(__victim));
349
350 __try
351 {
352 _Base::resize(__sz, __c);
353 }
354 __catch(...)
355 {
356 this->_M_revalidate_singular();
357 __throw_exception_again;
358 }
359 }
360#endif
361
362 // element access:
363 _GLIBCXX_NODISCARD
364 reference
365 front() _GLIBCXX_NOEXCEPT
366 {
367 __glibcxx_check_nonempty();
368 return _Base::front();
369 }
370
371 _GLIBCXX_NODISCARD
372 const_reference
373 front() const _GLIBCXX_NOEXCEPT
374 {
375 __glibcxx_check_nonempty();
376 return _Base::front();
377 }
378
379 _GLIBCXX_NODISCARD
380 reference
381 back() _GLIBCXX_NOEXCEPT
382 {
383 __glibcxx_check_nonempty();
384 return _Base::back();
385 }
386
387 _GLIBCXX_NODISCARD
388 const_reference
389 back() const _GLIBCXX_NOEXCEPT
390 {
391 __glibcxx_check_nonempty();
392 return _Base::back();
393 }
394
395 // 23.2.2.3 modifiers:
396 using _Base::push_front;
397
398#if __cplusplus >= 201103L
399 using _Base::emplace_front;
400#endif
401
402 void
403 pop_front() _GLIBCXX_NOEXCEPT
404 {
405 __glibcxx_check_nonempty();
406 this->_M_invalidate_if(_Equal(_Base::begin()));
407 _Base::pop_front();
408 }
409
410 using _Base::push_back;
411
412#if __cplusplus >= 201103L
413 using _Base::emplace_back;
414#endif
415
416 void
417 pop_back() _GLIBCXX_NOEXCEPT
418 {
419 __glibcxx_check_nonempty();
420 this->_M_invalidate_if(_Equal(--_Base::end()));
421 _Base::pop_back();
422 }
423
424#if __cplusplus >= 201103L
425 template<typename... _Args>
426 iterator
427 emplace(const_iterator __position, _Args&&... __args)
428 {
429 __glibcxx_check_insert(__position);
430 return { _Base::emplace(__position.base(),
431 std::forward<_Args>(__args)...), this };
432 }
433#endif
434
435 iterator
436#if __cplusplus >= 201103L
437 insert(const_iterator __position, const _Tp& __x)
438#else
439 insert(iterator __position, const _Tp& __x)
440#endif
441 {
442 __glibcxx_check_insert(__position);
443 return iterator(_Base::insert(__position.base(), __x), this);
444 }
445
446#if __cplusplus >= 201103L
447 iterator
448 insert(const_iterator __position, _Tp&& __x)
449 { return emplace(__position, std::move(__x)); }
450
451 iterator
452 insert(const_iterator __p, initializer_list<value_type> __l)
453 {
454 __glibcxx_check_insert(__p);
455 return { _Base::insert(__p.base(), __l), this };
456 }
457#endif
458
459#if __cplusplus >= 201103L
460 iterator
461 insert(const_iterator __position, size_type __n, const _Tp& __x)
462 {
463 __glibcxx_check_insert(__position);
464 return { _Base::insert(__position.base(), __n, __x), this };
465 }
466#else
467 void
468 insert(iterator __position, size_type __n, const _Tp& __x)
469 {
470 __glibcxx_check_insert(__position);
471 _Base::insert(__position.base(), __n, __x);
472 }
473#endif
474
475#if __cplusplus >= 201103L
476 template<class _InputIterator,
477 typename = std::_RequireInputIter<_InputIterator>>
478 iterator
479 insert(const_iterator __position, _InputIterator __first,
480 _InputIterator __last)
481 {
482 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
483 __glibcxx_check_insert_range(__position, __first, __last, __dist);
484 if (__dist.second >= __gnu_debug::__dp_sign)
485 return
486 {
487 _Base::insert(__position.base(),
488 __gnu_debug::__unsafe(__first),
489 __gnu_debug::__unsafe(__last)),
490 this
491 };
492 else
493 return { _Base::insert(__position.base(), __first, __last), this };
494 }
495#else
496 template<class _InputIterator>
497 void
498 insert(iterator __position, _InputIterator __first,
499 _InputIterator __last)
500 {
501 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
502 __glibcxx_check_insert_range(__position, __first, __last, __dist);
503
504 if (__dist.second >= __gnu_debug::__dp_sign)
505 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
506 __gnu_debug::__unsafe(__last));
507 else
508 _Base::insert(__position.base(), __first, __last);
509 }
510#endif
511
512 private:
513 _Base_iterator
514#if __cplusplus >= 201103L
515 _M_erase(_Base_const_iterator __position) noexcept
516#else
517 _M_erase(_Base_iterator __position)
518#endif
519 {
520 this->_M_invalidate_if(_Equal(__position));
521 return _Base::erase(__position);
522 }
523
524 public:
525 iterator
526#if __cplusplus >= 201103L
527 erase(const_iterator __position) noexcept
528#else
529 erase(iterator __position)
530#endif
531 {
532 __glibcxx_check_erase(__position);
533 return iterator(_M_erase(__position.base()), this);
534 }
535
536 iterator
537#if __cplusplus >= 201103L
538 erase(const_iterator __first, const_iterator __last) noexcept
539#else
540 erase(iterator __first, iterator __last)
541#endif
542 {
543 // _GLIBCXX_RESOLVE_LIB_DEFECTS
544 // 151. can't currently clear() empty container
545 __glibcxx_check_erase_range(__first, __last);
546 for (_Base_const_iterator __victim = __first.base();
547 __victim != __last.base(); ++__victim)
548 {
549 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
550 _M_message(__gnu_debug::__msg_valid_range)
551 ._M_iterator(__first, "position")
552 ._M_iterator(__last, "last"));
553 this->_M_invalidate_if(_Equal(__victim));
554 }
555
556 return iterator(_Base::erase(__first.base(), __last.base()), this);
557 }
558
559 void
560 swap(list& __x)
561 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
562 {
563 _Safe::_M_swap(__x);
564 _Base::swap(__x);
565 }
566
567 void
568 clear() _GLIBCXX_NOEXCEPT
569 {
570 _Base::clear();
571 this->_M_invalidate_all();
572 }
573
574 // 23.2.2.4 list operations:
575 void
576#if __cplusplus >= 201103L
577 splice(const_iterator __position, list&& __x) noexcept
578#else
579 splice(iterator __position, list& __x)
580#endif
581 {
582 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this,
583 _M_message(__gnu_debug::__msg_self_splice)
584 ._M_sequence(*this, "this"));
585 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
586 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x));
587 }
588
589#if __cplusplus >= 201103L
590 void
591 splice(const_iterator __position, list& __x) noexcept
592 { splice(__position, std::move(__x)); }
593#endif
594
595 void
596#if __cplusplus >= 201103L
597 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
598#else
599 splice(iterator __position, list& __x, iterator __i)
600#endif
601 {
602 __glibcxx_check_insert(__position);
603
604 // We used to perform the splice_alloc check: not anymore, redundant
605 // after implementing the relevant bits of N1599.
606
607 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
608 _M_message(__gnu_debug::__msg_splice_bad)
609 ._M_iterator(__i, "__i"));
610 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__x)),
611 _M_message(__gnu_debug::__msg_splice_other)
612 ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
613
614 // _GLIBCXX_RESOLVE_LIB_DEFECTS
615 // 250. splicing invalidates iterators
616 this->_M_transfer_from_if(__x, _Equal(__i.base()));
617 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
618 __i.base());
619 }
620
621#if __cplusplus >= 201103L
622 void
623 splice(const_iterator __position, list& __x, const_iterator __i) noexcept
624 { splice(__position, std::move(__x), __i); }
625#endif
626
627 void
628#if __cplusplus >= 201103L
629 splice(const_iterator __position, list&& __x, const_iterator __first,
630 const_iterator __last) noexcept
631#else
632 splice(iterator __position, list& __x, iterator __first,
633 iterator __last)
634#endif
635 {
636 __glibcxx_check_insert(__position);
637 __glibcxx_check_valid_range(__first, __last);
638 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(std::__addressof(__x)),
639 _M_message(__gnu_debug::__msg_splice_other)
640 ._M_sequence(__x, "x")
641 ._M_iterator(__first, "first"));
642
643 // We used to perform the splice_alloc check: not anymore, redundant
644 // after implementing the relevant bits of N1599.
645
646 for (_Base_const_iterator __tmp = __first.base();
647 __tmp != __last.base(); ++__tmp)
648 {
649 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
650 _M_message(__gnu_debug::__msg_valid_range)
651 ._M_iterator(__first, "first")
652 ._M_iterator(__last, "last"));
653 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this
654 || __tmp != __position.base(),
655 _M_message(__gnu_debug::__msg_splice_overlap)
656 ._M_iterator(__tmp, "position")
657 ._M_iterator(__first, "first")
658 ._M_iterator(__last, "last"));
659
660 // _GLIBCXX_RESOLVE_LIB_DEFECTS
661 // 250. splicing invalidates iterators
662 this->_M_transfer_from_if(__x, _Equal(__tmp));
663 }
664
665 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x),
666 __first.base(), __last.base());
667 }
668
669#if __cplusplus >= 201103L
670 void
671 splice(const_iterator __position, list& __x,
672 const_iterator __first, const_iterator __last) noexcept
673 { splice(__position, std::move(__x), __first, __last); }
674#endif
675
676 private:
677#if __cplusplus > 201703L
678 typedef size_type __remove_return_type;
679# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
680 __attribute__((__abi_tag__("__cxx20")))
681# define _GLIBCXX20_ONLY(__expr) __expr
682#else
683 typedef void __remove_return_type;
684# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
685# define _GLIBCXX20_ONLY(__expr)
686#endif
687
688 public:
689 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
690 __remove_return_type
691 remove(const _Tp& __value)
692 {
693 if (!this->_M_iterators && !this->_M_const_iterators)
694 return _Base::remove(__value);
695
696#if !_GLIBCXX_USE_CXX11_ABI
697 size_type __removed __attribute__((__unused__)) = 0;
698#endif
699 _Base __to_destroy(get_allocator());
700 _Base_iterator __first = _Base::begin();
701 _Base_iterator __last = _Base::end();
702 while (__first != __last)
703 {
704 _Base_iterator __next = __first;
705 ++__next;
706 if (*__first == __value)
707 {
708 // _GLIBCXX_RESOLVE_LIB_DEFECTS
709 // 526. Is it undefined if a function in the standard changes
710 // in parameters?
711 this->_M_invalidate_if(_Equal(__first));
712 __to_destroy.splice(__to_destroy.begin(), *this, __first);
713#if !_GLIBCXX_USE_CXX11_ABI
714 _GLIBCXX20_ONLY( __removed++ );
715#endif
716 }
717
718 __first = __next;
719 }
720
721#if !_GLIBCXX_USE_CXX11_ABI
722 return _GLIBCXX20_ONLY( __removed );
723#else
724 return _GLIBCXX20_ONLY( __to_destroy.size() );
725#endif
726 }
727
728 template<class _Predicate>
729 __remove_return_type
730 remove_if(_Predicate __pred)
731 {
732 if (!this->_M_iterators && !this->_M_const_iterators)
733 return _Base::remove_if(__pred);
734
735#if !_GLIBCXX_USE_CXX11_ABI
736 size_type __removed __attribute__((__unused__)) = 0;
737#endif
738 _Base __to_destroy(get_allocator());
739 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
740 {
741 _Base_iterator __next = __x;
742 ++__next;
743 if (__pred(*__x))
744 {
745 this->_M_invalidate_if(_Equal(__x));
746 __to_destroy.splice(__to_destroy.begin(), *this, __x);
747#if !_GLIBCXX_USE_CXX11_ABI
748 _GLIBCXX20_ONLY( __removed++ );
749#endif
750 }
751
752 __x = __next;
753 }
754
755#if !_GLIBCXX_USE_CXX11_ABI
756 return _GLIBCXX20_ONLY( __removed );
757#else
758 return _GLIBCXX20_ONLY( __to_destroy.size() );
759#endif
760 }
761
762 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
763 __remove_return_type
764 unique()
765 {
766 if (!this->_M_iterators && !this->_M_const_iterators)
767 return _Base::unique();
768
769 if (empty())
770 return _GLIBCXX20_ONLY(0);
771
772#if !_GLIBCXX_USE_CXX11_ABI
773 size_type __removed __attribute__((__unused__)) = 0;
774#endif
775 _Base __to_destroy(get_allocator());
776 _Base_iterator __first = _Base::begin();
777 _Base_iterator __last = _Base::end();
778 _Base_iterator __next = __first;
779 while (++__next != __last)
780 if (*__first == *__next)
781 {
782 this->_M_invalidate_if(_Equal(__next));
783 __to_destroy.splice(__to_destroy.begin(), *this, __next);
784 __next = __first;
785#if !_GLIBCXX_USE_CXX11_ABI
786 _GLIBCXX20_ONLY( __removed++ );
787#endif
788 }
789 else
790 __first = __next;
791
792#if !_GLIBCXX_USE_CXX11_ABI
793 return _GLIBCXX20_ONLY( __removed );
794#else
795 return _GLIBCXX20_ONLY( __to_destroy.size() );
796#endif
797 }
798
799 template<class _BinaryPredicate>
800 __remove_return_type
801 unique(_BinaryPredicate __binary_pred)
802 {
803 if (!this->_M_iterators && !this->_M_const_iterators)
804 return _Base::unique(__binary_pred);
805
806 if (empty())
807 return _GLIBCXX20_ONLY(0);
808
809
810#if !_GLIBCXX_USE_CXX11_ABI
811 size_type __removed __attribute__((__unused__)) = 0;
812#endif
813 _Base __to_destroy(get_allocator());
814 _Base_iterator __first = _Base::begin();
815 _Base_iterator __last = _Base::end();
816 _Base_iterator __next = __first;
817 while (++__next != __last)
818 if (__binary_pred(*__first, *__next))
819 {
820 this->_M_invalidate_if(_Equal(__next));
821 __to_destroy.splice(__to_destroy.begin(), *this, __next);
822 __next = __first;
823#if !_GLIBCXX_USE_CXX11_ABI
824 _GLIBCXX20_ONLY( __removed++ );
825#endif
826 }
827 else
828 __first = __next;
829
830#if !_GLIBCXX_USE_CXX11_ABI
831 return _GLIBCXX20_ONLY( __removed );
832#else
833 return _GLIBCXX20_ONLY( __to_destroy.size() );
834#endif
835 }
836
837#undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
838#undef _GLIBCXX20_ONLY
839
840 void
841#if __cplusplus >= 201103L
842 merge(list&& __x)
843#else
844 merge(list& __x)
845#endif
846 {
847 // _GLIBCXX_RESOLVE_LIB_DEFECTS
848 // 300. list::merge() specification incomplete
849 if (this != std::__addressof(__x))
850 {
851 __glibcxx_check_sorted(_Base::begin(), _Base::end());
852 __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
853 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
854 _Base::merge(_GLIBCXX_MOVE(__x));
855 }
856 }
857
858#if __cplusplus >= 201103L
859 void
860 merge(list& __x)
861 { merge(std::move(__x)); }
862#endif
863
864 template<class _Compare>
865 void
866#if __cplusplus >= 201103L
867 merge(list&& __x, _Compare __comp)
868#else
869 merge(list& __x, _Compare __comp)
870#endif
871 {
872 // _GLIBCXX_RESOLVE_LIB_DEFECTS
873 // 300. list::merge() specification incomplete
874 if (this != std::__addressof(__x))
875 {
876 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
877 __comp);
878 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
879 __comp);
880 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
881 _Base::merge(_GLIBCXX_MOVE(__x), __comp);
882 }
883 }
884
885#if __cplusplus >= 201103L
886 template<typename _Compare>
887 void
888 merge(list& __x, _Compare __comp)
889 { merge(std::move(__x), __comp); }
890#endif
891
892 void
893 sort() { _Base::sort(); }
894
895 template<typename _StrictWeakOrdering>
896 void
897 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
898
899 using _Base::reverse;
900
901 _Base&
902 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
903
904 const _Base&
905 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
906 };
907
908#if __cpp_deduction_guides >= 201606
909 template<typename _InputIterator, typename _ValT
910 = typename iterator_traits<_InputIterator>::value_type,
911 typename _Allocator = allocator<_ValT>,
912 typename = _RequireInputIter<_InputIterator>,
913 typename = _RequireAllocator<_Allocator>>
914 list(_InputIterator, _InputIterator, _Allocator = _Allocator())
915 -> list<_ValT, _Allocator>;
916
917 template<typename _Tp, typename _Allocator = allocator<_Tp>,
918 typename = _RequireAllocator<_Allocator>>
919 list(size_t, _Tp, _Allocator = _Allocator())
920 -> list<_Tp, _Allocator>;
921#endif
922
923 template<typename _Tp, typename _Alloc>
924 inline bool
925 operator==(const list<_Tp, _Alloc>& __lhs,
926 const list<_Tp, _Alloc>& __rhs)
927 { return __lhs._M_base() == __rhs._M_base(); }
928
929#if __cpp_lib_three_way_comparison
930 template<typename _Tp, typename _Alloc>
931 constexpr __detail::__synth3way_t<_Tp>
932 operator<=>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
933 { return __x._M_base() <=> __y._M_base(); }
934#else
935 template<typename _Tp, typename _Alloc>
936 inline bool
937 operator!=(const list<_Tp, _Alloc>& __lhs,
938 const list<_Tp, _Alloc>& __rhs)
939 { return __lhs._M_base() != __rhs._M_base(); }
940
941 template<typename _Tp, typename _Alloc>
942 inline bool
943 operator<(const list<_Tp, _Alloc>& __lhs,
944 const list<_Tp, _Alloc>& __rhs)
945 { return __lhs._M_base() < __rhs._M_base(); }
946
947 template<typename _Tp, typename _Alloc>
948 inline bool
949 operator<=(const list<_Tp, _Alloc>& __lhs,
950 const list<_Tp, _Alloc>& __rhs)
951 { return __lhs._M_base() <= __rhs._M_base(); }
952
953 template<typename _Tp, typename _Alloc>
954 inline bool
955 operator>=(const list<_Tp, _Alloc>& __lhs,
956 const list<_Tp, _Alloc>& __rhs)
957 { return __lhs._M_base() >= __rhs._M_base(); }
958
959 template<typename _Tp, typename _Alloc>
960 inline bool
961 operator>(const list<_Tp, _Alloc>& __lhs,
962 const list<_Tp, _Alloc>& __rhs)
963 { return __lhs._M_base() > __rhs._M_base(); }
964#endif // three-way comparison
965
966 template<typename _Tp, typename _Alloc>
967 inline void
968 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
969 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
970 { __lhs.swap(__rhs); }
971
972} // namespace __debug
973} // namespace std
974
975namespace __gnu_debug
976{
977#ifndef _GLIBCXX_USE_CXX11_ABI
978 // If not using C++11 list::size() is not in O(1) so we do not use it.
979 template<typename _Tp, typename _Alloc>
980 struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> >
981 {
982 typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It;
983
984 static typename _Distance_traits<_It>::__type
985 _S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
986 {
987 return __seq.empty()
988 ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign);
989 }
990 };
991#endif
992
993#ifndef _GLIBCXX_DEBUG_PEDANTIC
994 template<class _Tp, class _Alloc>
995 struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
996 { enum { __value = 1 }; };
997#endif
998}
999
1000#endif
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition macros.h:143
__glibcxx_check_sorted_pred
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
Definition macros.h:356
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition macros.h:245
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition macros.h:209
__glibcxx_check_insert_range
#define __glibcxx_check_insert_range(_Position, _First, _Last, _Dist)
Definition macros.h:177
std::chrono::operator<=
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:855
std::chrono::operator>=
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:869
std::chrono::operator<
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:822
std::chrono::operator>
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:862
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:127
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:51
std
ISO C++ entities toplevel namespace is std.
std::empty
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition range_access.h:282
__gnu_debug
GNU debug classes for public use.
Definition boost_concept_check.h:58
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition helper_functions.h:315
std::initializer_list
initializer_list
Definition initializer_list:46
std::is_nothrow_constructible
is_nothrow_constructible
Definition type_traits:1225
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:129
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition safe_iterator.h:133
__gnu_debug::_Safe_iterator::base
constexpr _Iterator & base() noexcept
Return the underlying iterator.
Definition safe_iterator.h:433
__gnu_debug::_Safe_iterator::_M_dereferenceable
bool _M_dereferenceable() const
Is the iterator dereferenceable?
Definition safe_iterator.h:458
std::iterator_traits
Traits class for iterators.
Definition stl_iterator_base_types.h:178
std::pair
Struct holding two objects of arbitrary type.
Definition stl_pair.h:286
std::pair::second
_T2 second
The second member.
Definition stl_pair.h:291
std::list
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition stl_list.h:633
__gnu_debug::_Safe_iterator_base::_M_attached_to
bool _M_attached_to(const _Safe_sequence_base *__seq) const
Definition safe_base.h:145
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition safe_container.h:43
__gnu_debug::_Safe_node_sequence
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Definition safe_sequence.h:133
std::__debug::list
Class std::list with safety/checking/debug instrumentation.
Definition debug/list:55