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