Line data Source code
1 : // List implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2022 Free Software Foundation, Inc.
4 : // Copyright The GNU Toolchain Authors.
5 : //
6 : // This file is part of the GNU ISO C++ Library. This library is free
7 : // software; you can redistribute it and/or modify it under the
8 : // terms of the GNU General Public License as published by the
9 : // Free Software Foundation; either version 3, or (at your option)
10 : // any later version.
11 :
12 : // This library is distributed in the hope that it will be useful,
13 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : // GNU General Public License for more details.
16 :
17 : // Under Section 7 of GPL version 3, you are granted additional
18 : // permissions described in the GCC Runtime Library Exception, version
19 : // 3.1, as published by the Free Software Foundation.
20 :
21 : // You should have received a copy of the GNU General Public License and
22 : // a copy of the GCC Runtime Library Exception along with this program;
23 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 : // <http://www.gnu.org/licenses/>.
25 :
26 : /*
27 : *
28 : * Copyright (c) 1994
29 : * Hewlett-Packard Company
30 : *
31 : * Permission to use, copy, modify, distribute and sell this software
32 : * and its documentation for any purpose is hereby granted without fee,
33 : * provided that the above copyright notice appear in all copies and
34 : * that both that copyright notice and this permission notice appear
35 : * in supporting documentation. Hewlett-Packard Company makes no
36 : * representations about the suitability of this software for any
37 : * purpose. It is provided "as is" without express or implied warranty.
38 : *
39 : *
40 : * Copyright (c) 1996,1997
41 : * Silicon Graphics Computer Systems, Inc.
42 : *
43 : * Permission to use, copy, modify, distribute and sell this software
44 : * and its documentation for any purpose is hereby granted without fee,
45 : * provided that the above copyright notice appear in all copies and
46 : * that both that copyright notice and this permission notice appear
47 : * in supporting documentation. Silicon Graphics makes no
48 : * representations about the suitability of this software for any
49 : * purpose. It is provided "as is" without express or implied warranty.
50 : */
51 :
52 : /** @file bits/stl_list.h
53 : * This is an internal header file, included by other library headers.
54 : * Do not attempt to use it directly. @headername{list}
55 : */
56 :
57 : #ifndef _STL_LIST_H
58 : #define _STL_LIST_H 1
59 :
60 : #include <bits/concept_check.h>
61 : #include <ext/alloc_traits.h>
62 : #if __cplusplus >= 201103L
63 : #include <initializer_list>
64 : #include <bits/allocated_ptr.h>
65 : #include <ext/aligned_buffer.h>
66 : #endif
67 :
68 : namespace std _GLIBCXX_VISIBILITY(default)
69 : {
70 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
71 :
72 : namespace __detail
73 : {
74 : // Supporting structures are split into common and templated
75 : // types; the latter publicly inherits from the former in an
76 : // effort to reduce code duplication. This results in some
77 : // "needless" static_cast'ing later on, but it's all safe
78 : // downcasting.
79 :
80 : /// Common part of a node in the %list.
81 : struct _List_node_base
82 : {
83 : _List_node_base* _M_next;
84 : _List_node_base* _M_prev;
85 :
86 : static void
87 : swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
88 :
89 : void
90 : _M_transfer(_List_node_base* const __first,
91 : _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
92 :
93 : void
94 : _M_reverse() _GLIBCXX_USE_NOEXCEPT;
95 :
96 : void
97 : _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
98 :
99 : void
100 : _M_unhook() _GLIBCXX_USE_NOEXCEPT;
101 : };
102 :
103 : /// The %list node header.
104 : struct _List_node_header : public _List_node_base
105 : {
106 : #if _GLIBCXX_USE_CXX11_ABI
107 : std::size_t _M_size;
108 : #endif
109 :
110 2968 : _List_node_header() _GLIBCXX_NOEXCEPT
111 2968 : { _M_init(); }
112 :
113 : #if __cplusplus >= 201103L
114 : _List_node_header(_List_node_header&& __x) noexcept
115 : : _List_node_base{ __x._M_next, __x._M_prev }
116 : # if _GLIBCXX_USE_CXX11_ABI
117 : , _M_size(__x._M_size)
118 : # endif
119 : {
120 : if (__x._M_base()->_M_next == __x._M_base())
121 : this->_M_next = this->_M_prev = this;
122 : else
123 : {
124 : this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base();
125 : __x._M_init();
126 : }
127 : }
128 :
129 : void
130 : _M_move_nodes(_List_node_header&& __x)
131 : {
132 : _List_node_base* const __xnode = __x._M_base();
133 : if (__xnode->_M_next == __xnode)
134 : _M_init();
135 : else
136 : {
137 : _List_node_base* const __node = this->_M_base();
138 : __node->_M_next = __xnode->_M_next;
139 : __node->_M_prev = __xnode->_M_prev;
140 : __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;
141 : # if _GLIBCXX_USE_CXX11_ABI
142 : _M_size = __x._M_size;
143 : # endif
144 : __x._M_init();
145 : }
146 : }
147 : #endif
148 :
149 : void
150 2968 : _M_init() _GLIBCXX_NOEXCEPT
151 : {
152 2968 : this->_M_next = this->_M_prev = this;
153 : #if _GLIBCXX_USE_CXX11_ABI
154 2968 : this->_M_size = 0;
155 : #endif
156 : }
157 :
158 : private:
159 : _List_node_base* _M_base() { return this; }
160 : };
161 :
162 : // Used by list::sort to hold nodes being sorted.
163 : struct _Scratch_list : _List_node_base
164 : {
165 : _Scratch_list() { _M_next = _M_prev = this; }
166 :
167 : bool empty() const { return _M_next == this; }
168 :
169 : void swap(_List_node_base& __l) { _List_node_base::swap(*this, __l); }
170 :
171 : template<typename _Iter, typename _Cmp>
172 : struct _Ptr_cmp
173 : {
174 : _Cmp _M_cmp;
175 :
176 : bool
177 : operator()(__detail::_List_node_base* __lhs,
178 : __detail::_List_node_base* __rhs) /* not const */
179 : { return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); }
180 : };
181 :
182 : template<typename _Iter>
183 : struct _Ptr_cmp<_Iter, void>
184 : {
185 : bool
186 : operator()(__detail::_List_node_base* __lhs,
187 : __detail::_List_node_base* __rhs) const
188 : { return *_Iter(__lhs) < *_Iter(__rhs); }
189 : };
190 :
191 : // Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp.
192 : template<typename _Cmp>
193 : void
194 : merge(_List_node_base& __x, _Cmp __comp)
195 : {
196 : _List_node_base* __first1 = _M_next;
197 : _List_node_base* const __last1 = this;
198 : _List_node_base* __first2 = __x._M_next;
199 : _List_node_base* const __last2 = std::__addressof(__x);
200 :
201 : while (__first1 != __last1 && __first2 != __last2)
202 : {
203 : if (__comp(__first2, __first1))
204 : {
205 : _List_node_base* __next = __first2->_M_next;
206 : __first1->_M_transfer(__first2, __next);
207 : __first2 = __next;
208 : }
209 : else
210 : __first1 = __first1->_M_next;
211 : }
212 : if (__first2 != __last2)
213 : this->_M_transfer(__first2, __last2);
214 : }
215 :
216 : // Splice the node at __i into *this.
217 : void _M_take_one(_List_node_base* __i)
218 : { this->_M_transfer(__i, __i->_M_next); }
219 :
220 : // Splice all nodes from *this after __i.
221 : void _M_put_all(_List_node_base* __i)
222 : {
223 : if (!empty())
224 : __i->_M_transfer(_M_next, this);
225 : }
226 : };
227 :
228 : } // namespace detail
229 :
230 : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
231 :
232 : /// An actual node in the %list.
233 : template<typename _Tp>
234 : struct _List_node : public __detail::_List_node_base
235 : {
236 : #if __cplusplus >= 201103L
237 : __gnu_cxx::__aligned_membuf<_Tp> _M_storage;
238 46809 : _Tp* _M_valptr() { return _M_storage._M_ptr(); }
239 228295 : _Tp const* _M_valptr() const { return _M_storage._M_ptr(); }
240 : #else
241 : _Tp _M_data;
242 : _Tp* _M_valptr() { return std::__addressof(_M_data); }
243 : _Tp const* _M_valptr() const { return std::__addressof(_M_data); }
244 : #endif
245 : };
246 :
247 : /**
248 : * @brief A list::iterator.
249 : *
250 : * All the functions are op overloads.
251 : */
252 : template<typename _Tp>
253 : struct _List_iterator
254 : {
255 : typedef _List_iterator<_Tp> _Self;
256 : typedef _List_node<_Tp> _Node;
257 :
258 : typedef ptrdiff_t difference_type;
259 : typedef std::bidirectional_iterator_tag iterator_category;
260 : typedef _Tp value_type;
261 : typedef _Tp* pointer;
262 : typedef _Tp& reference;
263 :
264 2852 : _List_iterator() _GLIBCXX_NOEXCEPT
265 1426 : : _M_node() { }
266 :
267 : explicit
268 305498 : _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
269 70588 : : _M_node(__x) { }
270 :
271 : _Self
272 : _M_const_cast() const _GLIBCXX_NOEXCEPT
273 : { return *this; }
274 :
275 : // Must downcast from _List_node_base to _List_node to get to value.
276 : _GLIBCXX_NODISCARD
277 : reference
278 1773 : operator*() const _GLIBCXX_NOEXCEPT
279 296329 : { return *static_cast<_Node*>(_M_node)->_M_valptr(); }
280 :
281 : _GLIBCXX_NODISCARD
282 : pointer
283 : operator->() const _GLIBCXX_NOEXCEPT
284 : { return static_cast<_Node*>(_M_node)->_M_valptr(); }
285 :
286 : _Self&
287 159930 : operator++() _GLIBCXX_NOEXCEPT
288 : {
289 159930 : _M_node = _M_node->_M_next;
290 113935 : return *this;
291 : }
292 :
293 : _Self
294 : operator++(int) _GLIBCXX_NOEXCEPT
295 : {
296 : _Self __tmp = *this;
297 : _M_node = _M_node->_M_next;
298 : return __tmp;
299 : }
300 :
301 : _Self&
302 0 : operator--() _GLIBCXX_NOEXCEPT
303 : {
304 3152 : _M_node = _M_node->_M_prev;
305 0 : return *this;
306 : }
307 :
308 : _Self
309 : operator--(int) _GLIBCXX_NOEXCEPT
310 : {
311 : _Self __tmp = *this;
312 : _M_node = _M_node->_M_prev;
313 : return __tmp;
314 : }
315 :
316 : _GLIBCXX_NODISCARD
317 : friend bool
318 : operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
319 : { return __x._M_node == __y._M_node; }
320 :
321 : #if __cpp_impl_three_way_comparison < 201907L
322 : _GLIBCXX_NODISCARD
323 : friend bool
324 798 : operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
325 798 : { return __x._M_node != __y._M_node; }
326 : #endif
327 :
328 : // The only member points to the %list element.
329 : __detail::_List_node_base* _M_node;
330 : };
331 :
332 : /**
333 : * @brief A list::const_iterator.
334 : *
335 : * All the functions are op overloads.
336 : */
337 : template<typename _Tp>
338 : struct _List_const_iterator
339 : {
340 : typedef _List_const_iterator<_Tp> _Self;
341 : typedef const _List_node<_Tp> _Node;
342 : typedef _List_iterator<_Tp> iterator;
343 :
344 : typedef ptrdiff_t difference_type;
345 : typedef std::bidirectional_iterator_tag iterator_category;
346 : typedef _Tp value_type;
347 : typedef const _Tp* pointer;
348 : typedef const _Tp& reference;
349 :
350 : _List_const_iterator() _GLIBCXX_NOEXCEPT
351 : : _M_node() { }
352 :
353 : explicit
354 276677 : _List_const_iterator(const __detail::_List_node_base* __x)
355 : _GLIBCXX_NOEXCEPT
356 : : _M_node(__x) { }
357 :
358 70588 : _List_const_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT
359 112935 : : _M_node(__x._M_node) { }
360 :
361 : iterator
362 183407 : _M_const_cast() const _GLIBCXX_NOEXCEPT
363 183407 : { return iterator(const_cast<__detail::_List_node_base*>(_M_node)); }
364 :
365 : // Must downcast from List_node_base to _List_node to get to value.
366 : _GLIBCXX_NODISCARD
367 : reference
368 1726 : operator*() const _GLIBCXX_NOEXCEPT
369 228295 : { return *static_cast<_Node*>(_M_node)->_M_valptr(); }
370 :
371 : _GLIBCXX_NODISCARD
372 : pointer
373 : operator->() const _GLIBCXX_NOEXCEPT
374 : { return static_cast<_Node*>(_M_node)->_M_valptr(); }
375 :
376 : _Self&
377 3452 : operator++() _GLIBCXX_NOEXCEPT
378 : {
379 3452 : _M_node = _M_node->_M_next;
380 1726 : return *this;
381 : }
382 :
383 : _Self
384 : operator++(int) _GLIBCXX_NOEXCEPT
385 : {
386 : _Self __tmp = *this;
387 : _M_node = _M_node->_M_next;
388 : return __tmp;
389 : }
390 :
391 : _Self&
392 : operator--() _GLIBCXX_NOEXCEPT
393 : {
394 : _M_node = _M_node->_M_prev;
395 : return *this;
396 : }
397 :
398 : _Self
399 : operator--(int) _GLIBCXX_NOEXCEPT
400 : {
401 : _Self __tmp = *this;
402 : _M_node = _M_node->_M_prev;
403 : return __tmp;
404 : }
405 :
406 : _GLIBCXX_NODISCARD
407 : friend bool
408 116 : operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
409 116 : { return __x._M_node == __y._M_node; }
410 :
411 : #if __cpp_impl_three_way_comparison < 201907L
412 : _GLIBCXX_NODISCARD
413 : friend bool
414 : operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
415 : { return __x._M_node != __y._M_node; }
416 : #endif
417 :
418 : // The only member points to the %list element.
419 : const __detail::_List_node_base* _M_node;
420 : };
421 :
422 : _GLIBCXX_BEGIN_NAMESPACE_CXX11
423 : /// See bits/stl_deque.h's _Deque_base for an explanation.
424 : template<typename _Tp, typename _Alloc>
425 : class _List_base
426 : {
427 : protected:
428 : typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
429 : rebind<_Tp>::other _Tp_alloc_type;
430 : typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tp_alloc_traits;
431 : typedef typename _Tp_alloc_traits::template
432 : rebind<_List_node<_Tp> >::other _Node_alloc_type;
433 : typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
434 :
435 : #if !_GLIBCXX_INLINE_VERSION
436 : static size_t
437 : _S_distance(const __detail::_List_node_base* __first,
438 : const __detail::_List_node_base* __last)
439 : {
440 : size_t __n = 0;
441 : while (__first != __last)
442 : {
443 : __first = __first->_M_next;
444 : ++__n;
445 : }
446 : return __n;
447 : }
448 : #endif
449 :
450 2968 : struct _List_impl
451 : : public _Node_alloc_type
452 : {
453 : __detail::_List_node_header _M_node;
454 :
455 2852 : _List_impl() _GLIBCXX_NOEXCEPT_IF(
456 : is_nothrow_default_constructible<_Node_alloc_type>::value)
457 2852 : : _Node_alloc_type()
458 : { }
459 :
460 : _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
461 : : _Node_alloc_type(__a)
462 : { }
463 :
464 : #if __cplusplus >= 201103L
465 : _List_impl(_List_impl&&) = default;
466 :
467 : _List_impl(_Node_alloc_type&& __a, _List_impl&& __x)
468 : : _Node_alloc_type(std::move(__a)), _M_node(std::move(__x._M_node))
469 : { }
470 :
471 116 : _List_impl(_Node_alloc_type&& __a) noexcept
472 116 : : _Node_alloc_type(std::move(__a))
473 : { }
474 : #endif
475 : };
476 :
477 : _List_impl _M_impl;
478 :
479 : #if _GLIBCXX_USE_CXX11_ABI
480 : size_t _M_get_size() const { return _M_impl._M_node._M_size; }
481 :
482 : void _M_set_size(size_t __n) { _M_impl._M_node._M_size = __n; }
483 :
484 117397 : void _M_inc_size(size_t __n) { _M_impl._M_node._M_size += __n; }
485 :
486 70588 : void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; }
487 :
488 : # if !_GLIBCXX_INLINE_VERSION
489 : size_t
490 : _M_distance(const __detail::_List_node_base* __first,
491 : const __detail::_List_node_base* __last) const
492 : { return _S_distance(__first, __last); }
493 :
494 : // return the stored size
495 : size_t _M_node_count() const { return _M_get_size(); }
496 : # endif
497 : #else
498 : // dummy implementations used when the size is not stored
499 : size_t _M_get_size() const { return 0; }
500 : void _M_set_size(size_t) { }
501 : void _M_inc_size(size_t) { }
502 : void _M_dec_size(size_t) { }
503 :
504 : # if !_GLIBCXX_INLINE_VERSION
505 : size_t _M_distance(const void*, const void*) const { return 0; }
506 :
507 : // count the number of nodes
508 : size_t _M_node_count() const
509 : {
510 : return _S_distance(_M_impl._M_node._M_next,
511 : std::__addressof(_M_impl._M_node));
512 : }
513 : # endif
514 : #endif
515 :
516 : typename _Node_alloc_traits::pointer
517 117397 : _M_get_node()
518 234794 : { return _Node_alloc_traits::allocate(_M_impl, 1); }
519 :
520 : void
521 117397 : _M_put_node(typename _Node_alloc_traits::pointer __p) _GLIBCXX_NOEXCEPT
522 46809 : { _Node_alloc_traits::deallocate(_M_impl, __p, 1); }
523 :
524 : public:
525 : typedef _Alloc allocator_type;
526 :
527 : _Node_alloc_type&
528 : _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
529 46809 : { return _M_impl; }
530 :
531 : const _Node_alloc_type&
532 116 : _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
533 116 : { return _M_impl; }
534 :
535 : #if __cplusplus >= 201103L
536 2852 : _List_base() = default;
537 : #else
538 : _List_base() { }
539 : #endif
540 :
541 : _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
542 : : _M_impl(__a)
543 : { }
544 :
545 : #if __cplusplus >= 201103L
546 : _List_base(_List_base&&) = default;
547 :
548 : # if !_GLIBCXX_INLINE_VERSION
549 : _List_base(_List_base&& __x, _Node_alloc_type&& __a)
550 : : _M_impl(std::move(__a))
551 : {
552 : if (__x._M_get_Node_allocator() == _M_get_Node_allocator())
553 : _M_move_nodes(std::move(__x));
554 : // else caller must move individual elements.
555 : }
556 : # endif
557 :
558 : // Used when allocator is_always_equal.
559 : _List_base(_Node_alloc_type&& __a, _List_base&& __x)
560 : : _M_impl(std::move(__a), std::move(__x._M_impl))
561 : { }
562 :
563 : // Used when allocator !is_always_equal.
564 116 : _List_base(_Node_alloc_type&& __a)
565 116 : : _M_impl(std::move(__a))
566 : { }
567 :
568 : void
569 : _M_move_nodes(_List_base&& __x)
570 : { _M_impl._M_node._M_move_nodes(std::move(__x._M_impl._M_node)); }
571 : #endif
572 :
573 : // This is what actually destroys the list.
574 2968 : ~_List_base() _GLIBCXX_NOEXCEPT
575 2968 : { _M_clear(); }
576 :
577 : void
578 : _M_clear() _GLIBCXX_NOEXCEPT;
579 :
580 : void
581 : _M_init() _GLIBCXX_NOEXCEPT
582 : { this->_M_impl._M_node._M_init(); }
583 : };
584 :
585 : /**
586 : * @brief A standard container with linear time access to elements,
587 : * and fixed time insertion/deletion at any point in the sequence.
588 : *
589 : * @ingroup sequences
590 : *
591 : * @tparam _Tp Type of element.
592 : * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
593 : *
594 : * Meets the requirements of a <a href="tables.html#65">container</a>, a
595 : * <a href="tables.html#66">reversible container</a>, and a
596 : * <a href="tables.html#67">sequence</a>, including the
597 : * <a href="tables.html#68">optional sequence requirements</a> with the
598 : * %exception of @c at and @c operator[].
599 : *
600 : * This is a @e doubly @e linked %list. Traversal up and down the
601 : * %list requires linear time, but adding and removing elements (or
602 : * @e nodes) is done in constant time, regardless of where the
603 : * change takes place. Unlike std::vector and std::deque,
604 : * random-access iterators are not provided, so subscripting ( @c
605 : * [] ) access is not allowed. For algorithms which only need
606 : * sequential access, this lack makes no difference.
607 : *
608 : * Also unlike the other standard containers, std::list provides
609 : * specialized algorithms %unique to linked lists, such as
610 : * splicing, sorting, and in-place reversal.
611 : *
612 : * A couple points on memory allocation for list<Tp>:
613 : *
614 : * First, we never actually allocate a Tp, we allocate
615 : * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure
616 : * that after elements from %list<X,Alloc1> are spliced into
617 : * %list<X,Alloc2>, destroying the memory of the second %list is a
618 : * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
619 : *
620 : * Second, a %list conceptually represented as
621 : * @code
622 : * A <---> B <---> C <---> D
623 : * @endcode
624 : * is actually circular; a link exists between A and D. The %list
625 : * class holds (as its only data member) a private list::iterator
626 : * pointing to @e D, not to @e A! To get to the head of the %list,
627 : * we start at the tail and move forward by one. When this member
628 : * iterator's next/previous pointers refer to itself, the %list is
629 : * %empty.
630 : */
631 : template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
632 : class list : protected _List_base<_Tp, _Alloc>
633 : {
634 : #ifdef _GLIBCXX_CONCEPT_CHECKS
635 : // concept requirements
636 : typedef typename _Alloc::value_type _Alloc_value_type;
637 : # if __cplusplus < 201103L
638 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
639 : # endif
640 : __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
641 : #endif
642 :
643 : #if __cplusplus >= 201103L
644 : static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
645 : "std::list must have a non-const, non-volatile value_type");
646 : # if __cplusplus > 201703L || defined __STRICT_ANSI__
647 : static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
648 : "std::list must have the same value_type as its allocator");
649 : # endif
650 : #endif
651 :
652 : typedef _List_base<_Tp, _Alloc> _Base;
653 : typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
654 : typedef typename _Base::_Tp_alloc_traits _Tp_alloc_traits;
655 : typedef typename _Base::_Node_alloc_type _Node_alloc_type;
656 : typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
657 :
658 : public:
659 : typedef _Tp value_type;
660 : typedef typename _Tp_alloc_traits::pointer pointer;
661 : typedef typename _Tp_alloc_traits::const_pointer const_pointer;
662 : typedef typename _Tp_alloc_traits::reference reference;
663 : typedef typename _Tp_alloc_traits::const_reference const_reference;
664 : typedef _List_iterator<_Tp> iterator;
665 : typedef _List_const_iterator<_Tp> const_iterator;
666 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
667 : typedef std::reverse_iterator<iterator> reverse_iterator;
668 : typedef size_t size_type;
669 : typedef ptrdiff_t difference_type;
670 : typedef _Alloc allocator_type;
671 :
672 : protected:
673 : // Note that pointers-to-_Node's can be ctor-converted to
674 : // iterator types.
675 : typedef _List_node<_Tp> _Node;
676 :
677 : using _Base::_M_impl;
678 : using _Base::_M_put_node;
679 : using _Base::_M_get_node;
680 : using _Base::_M_get_Node_allocator;
681 :
682 : /**
683 : * @param __args An instance of user data.
684 : *
685 : * Allocates space for a new node and constructs a copy of
686 : * @a __args in it.
687 : */
688 : #if __cplusplus < 201103L
689 : _Node*
690 : _M_create_node(const value_type& __x)
691 : {
692 : _Node* __p = this->_M_get_node();
693 : __try
694 : {
695 : _Tp_alloc_type __alloc(_M_get_Node_allocator());
696 : __alloc.construct(__p->_M_valptr(), __x);
697 : }
698 : __catch(...)
699 : {
700 : _M_put_node(__p);
701 : __throw_exception_again;
702 : }
703 : return __p;
704 : }
705 : #else
706 : template<typename... _Args>
707 : _Node*
708 117397 : _M_create_node(_Args&&... __args)
709 : {
710 117397 : auto __p = this->_M_get_node();
711 117397 : auto& __alloc = _M_get_Node_allocator();
712 117397 : __allocated_ptr<_Node_alloc_type> __guard{__alloc, __p};
713 117397 : _Node_alloc_traits::construct(__alloc, __p->_M_valptr(),
714 : std::forward<_Args>(__args)...);
715 117397 : __guard = nullptr;
716 117397 : return __p;
717 117397 : }
718 : #endif
719 :
720 : #if _GLIBCXX_USE_CXX11_ABI
721 : static size_t
722 : _S_distance(const_iterator __first, const_iterator __last)
723 : { return std::distance(__first, __last); }
724 :
725 : // return the stored size
726 : size_t
727 : _M_node_count() const
728 : { return this->_M_get_size(); }
729 : #else
730 : // dummy implementations used when the size is not stored
731 : static size_t
732 : _S_distance(const_iterator, const_iterator)
733 : { return 0; }
734 :
735 : // count the number of nodes
736 : size_t
737 : _M_node_count() const
738 : { return std::distance(begin(), end()); }
739 : #endif
740 :
741 : public:
742 : // [23.2.2.1] construct/copy/destroy
743 : // (assign() and get_allocator() are also listed in this section)
744 :
745 : /**
746 : * @brief Creates a %list with no elements.
747 : */
748 : #if __cplusplus >= 201103L
749 2852 : list() = default;
750 : #else
751 : list() { }
752 : #endif
753 :
754 : /**
755 : * @brief Creates a %list with no elements.
756 : * @param __a An allocator object.
757 : */
758 : explicit
759 : list(const allocator_type& __a) _GLIBCXX_NOEXCEPT
760 : : _Base(_Node_alloc_type(__a)) { }
761 :
762 : #if __cplusplus >= 201103L
763 : /**
764 : * @brief Creates a %list with default constructed elements.
765 : * @param __n The number of elements to initially create.
766 : * @param __a An allocator object.
767 : *
768 : * This constructor fills the %list with @a __n default
769 : * constructed elements.
770 : */
771 : explicit
772 : list(size_type __n, const allocator_type& __a = allocator_type())
773 : : _Base(_Node_alloc_type(__a))
774 : { _M_default_initialize(__n); }
775 :
776 : /**
777 : * @brief Creates a %list with copies of an exemplar element.
778 : * @param __n The number of elements to initially create.
779 : * @param __value An element to copy.
780 : * @param __a An allocator object.
781 : *
782 : * This constructor fills the %list with @a __n copies of @a __value.
783 : */
784 : list(size_type __n, const value_type& __value,
785 : const allocator_type& __a = allocator_type())
786 : : _Base(_Node_alloc_type(__a))
787 : { _M_fill_initialize(__n, __value); }
788 : #else
789 : /**
790 : * @brief Creates a %list with copies of an exemplar element.
791 : * @param __n The number of elements to initially create.
792 : * @param __value An element to copy.
793 : * @param __a An allocator object.
794 : *
795 : * This constructor fills the %list with @a __n copies of @a __value.
796 : */
797 : explicit
798 : list(size_type __n, const value_type& __value = value_type(),
799 : const allocator_type& __a = allocator_type())
800 : : _Base(_Node_alloc_type(__a))
801 : { _M_fill_initialize(__n, __value); }
802 : #endif
803 :
804 : /**
805 : * @brief %List copy constructor.
806 : * @param __x A %list of identical element and allocator types.
807 : *
808 : * The newly-created %list uses a copy of the allocation object used
809 : * by @a __x (unless the allocator traits dictate a different object).
810 : */
811 116 : list(const list& __x)
812 : : _Base(_Node_alloc_traits::
813 116 : _S_select_on_copy(__x._M_get_Node_allocator()))
814 232 : { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
815 :
816 : #if __cplusplus >= 201103L
817 : /**
818 : * @brief %List move constructor.
819 : *
820 : * The newly-created %list contains the exact contents of the moved
821 : * instance. The contents of the moved instance are a valid, but
822 : * unspecified %list.
823 : */
824 : list(list&&) = default;
825 :
826 : /**
827 : * @brief Builds a %list from an initializer_list
828 : * @param __l An initializer_list of value_type.
829 : * @param __a An allocator object.
830 : *
831 : * Create a %list consisting of copies of the elements in the
832 : * initializer_list @a __l. This is linear in __l.size().
833 : */
834 : list(initializer_list<value_type> __l,
835 : const allocator_type& __a = allocator_type())
836 : : _Base(_Node_alloc_type(__a))
837 : { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
838 :
839 : list(const list& __x, const __type_identity_t<allocator_type>& __a)
840 : : _Base(_Node_alloc_type(__a))
841 : { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
842 :
843 : private:
844 : list(list&& __x, const allocator_type& __a, true_type) noexcept
845 : : _Base(_Node_alloc_type(__a), std::move(__x))
846 : { }
847 :
848 : list(list&& __x, const allocator_type& __a, false_type)
849 : : _Base(_Node_alloc_type(__a))
850 : {
851 : if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator())
852 : this->_M_move_nodes(std::move(__x));
853 : else
854 : insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()),
855 : std::__make_move_if_noexcept_iterator(__x.end()));
856 : }
857 :
858 : public:
859 : list(list&& __x, const __type_identity_t<allocator_type>& __a)
860 : noexcept(_Node_alloc_traits::_S_always_equal())
861 : : list(std::move(__x), __a,
862 : typename _Node_alloc_traits::is_always_equal{})
863 : { }
864 : #endif
865 :
866 : /**
867 : * @brief Builds a %list from a range.
868 : * @param __first An input iterator.
869 : * @param __last An input iterator.
870 : * @param __a An allocator object.
871 : *
872 : * Create a %list consisting of copies of the elements from
873 : * [@a __first,@a __last). This is linear in N (where N is
874 : * distance(@a __first,@a __last)).
875 : */
876 : #if __cplusplus >= 201103L
877 : template<typename _InputIterator,
878 : typename = std::_RequireInputIter<_InputIterator>>
879 : list(_InputIterator __first, _InputIterator __last,
880 : const allocator_type& __a = allocator_type())
881 : : _Base(_Node_alloc_type(__a))
882 : { _M_initialize_dispatch(__first, __last, __false_type()); }
883 : #else
884 : template<typename _InputIterator>
885 : list(_InputIterator __first, _InputIterator __last,
886 : const allocator_type& __a = allocator_type())
887 : : _Base(_Node_alloc_type(__a))
888 : {
889 : // Check whether it's an integral type. If so, it's not an iterator.
890 : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
891 : _M_initialize_dispatch(__first, __last, _Integral());
892 : }
893 : #endif
894 :
895 : #if __cplusplus >= 201103L
896 : /**
897 : * No explicit dtor needed as the _Base dtor takes care of
898 : * things. The _Base dtor only erases the elements, and note
899 : * that if the elements themselves are pointers, the pointed-to
900 : * memory is not touched in any way. Managing the pointer is
901 : * the user's responsibility.
902 : */
903 2968 : ~list() = default;
904 : #endif
905 :
906 : /**
907 : * @brief %List assignment operator.
908 : * @param __x A %list of identical element and allocator types.
909 : *
910 : * All the elements of @a __x are copied.
911 : *
912 : * Whether the allocator is copied depends on the allocator traits.
913 : */
914 : list&
915 : operator=(const list& __x);
916 :
917 : #if __cplusplus >= 201103L
918 : /**
919 : * @brief %List move assignment operator.
920 : * @param __x A %list of identical element and allocator types.
921 : *
922 : * The contents of @a __x are moved into this %list (without copying).
923 : *
924 : * Afterwards @a __x is a valid, but unspecified %list
925 : *
926 : * Whether the allocator is moved depends on the allocator traits.
927 : */
928 : list&
929 : operator=(list&& __x)
930 : noexcept(_Node_alloc_traits::_S_nothrow_move())
931 : {
932 : constexpr bool __move_storage =
933 : _Node_alloc_traits::_S_propagate_on_move_assign()
934 : || _Node_alloc_traits::_S_always_equal();
935 : _M_move_assign(std::move(__x), __bool_constant<__move_storage>());
936 : return *this;
937 : }
938 :
939 : /**
940 : * @brief %List initializer list assignment operator.
941 : * @param __l An initializer_list of value_type.
942 : *
943 : * Replace the contents of the %list with copies of the elements
944 : * in the initializer_list @a __l. This is linear in l.size().
945 : */
946 : list&
947 : operator=(initializer_list<value_type> __l)
948 : {
949 : this->assign(__l.begin(), __l.end());
950 : return *this;
951 : }
952 : #endif
953 :
954 : /**
955 : * @brief Assigns a given value to a %list.
956 : * @param __n Number of elements to be assigned.
957 : * @param __val Value to be assigned.
958 : *
959 : * This function fills a %list with @a __n copies of the given
960 : * value. Note that the assignment completely changes the %list
961 : * and that the resulting %list's size is the same as the number
962 : * of elements assigned.
963 : */
964 : void
965 : assign(size_type __n, const value_type& __val)
966 : { _M_fill_assign(__n, __val); }
967 :
968 : /**
969 : * @brief Assigns a range to a %list.
970 : * @param __first An input iterator.
971 : * @param __last An input iterator.
972 : *
973 : * This function fills a %list with copies of the elements in the
974 : * range [@a __first,@a __last).
975 : *
976 : * Note that the assignment completely changes the %list and
977 : * that the resulting %list's size is the same as the number of
978 : * elements assigned.
979 : */
980 : #if __cplusplus >= 201103L
981 : template<typename _InputIterator,
982 : typename = std::_RequireInputIter<_InputIterator>>
983 : void
984 : assign(_InputIterator __first, _InputIterator __last)
985 : { _M_assign_dispatch(__first, __last, __false_type()); }
986 : #else
987 : template<typename _InputIterator>
988 : void
989 : assign(_InputIterator __first, _InputIterator __last)
990 : {
991 : // Check whether it's an integral type. If so, it's not an iterator.
992 : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
993 : _M_assign_dispatch(__first, __last, _Integral());
994 : }
995 : #endif
996 :
997 : #if __cplusplus >= 201103L
998 : /**
999 : * @brief Assigns an initializer_list to a %list.
1000 : * @param __l An initializer_list of value_type.
1001 : *
1002 : * Replace the contents of the %list with copies of the elements
1003 : * in the initializer_list @a __l. This is linear in __l.size().
1004 : */
1005 : void
1006 : assign(initializer_list<value_type> __l)
1007 : { this->_M_assign_dispatch(__l.begin(), __l.end(), __false_type()); }
1008 : #endif
1009 :
1010 : /// Get a copy of the memory allocation object.
1011 : allocator_type
1012 : get_allocator() const _GLIBCXX_NOEXCEPT
1013 : { return allocator_type(_Base::_M_get_Node_allocator()); }
1014 :
1015 : // iterators
1016 : /**
1017 : * Returns a read/write iterator that points to the first element in the
1018 : * %list. Iteration is done in ordinary element order.
1019 : */
1020 : _GLIBCXX_NODISCARD
1021 : iterator
1022 2968 : begin() _GLIBCXX_NOEXCEPT
1023 116 : { return iterator(this->_M_impl._M_node._M_next); }
1024 :
1025 : /**
1026 : * Returns a read-only (constant) iterator that points to the
1027 : * first element in the %list. Iteration is done in ordinary
1028 : * element order.
1029 : */
1030 : _GLIBCXX_NODISCARD
1031 : const_iterator
1032 232 : begin() const _GLIBCXX_NOEXCEPT
1033 116 : { return const_iterator(this->_M_impl._M_node._M_next); }
1034 :
1035 : /**
1036 : * Returns a read/write iterator that points one past the last
1037 : * element in the %list. Iteration is done in ordinary element
1038 : * order.
1039 : */
1040 : _GLIBCXX_NODISCARD
1041 : iterator
1042 7730 : end() _GLIBCXX_NOEXCEPT
1043 0 : { return iterator(&this->_M_impl._M_node); }
1044 :
1045 : /**
1046 : * Returns a read-only (constant) iterator that points one past
1047 : * the last element in the %list. Iteration is done in ordinary
1048 : * element order.
1049 : */
1050 : _GLIBCXX_NODISCARD
1051 : const_iterator
1052 276561 : end() const _GLIBCXX_NOEXCEPT
1053 276445 : { return const_iterator(&this->_M_impl._M_node); }
1054 :
1055 : /**
1056 : * Returns a read/write reverse iterator that points to the last
1057 : * element in the %list. Iteration is done in reverse element
1058 : * order.
1059 : */
1060 : _GLIBCXX_NODISCARD
1061 : reverse_iterator
1062 : rbegin() _GLIBCXX_NOEXCEPT
1063 : { return reverse_iterator(end()); }
1064 :
1065 : /**
1066 : * Returns a read-only (constant) reverse iterator that points to
1067 : * the last element in the %list. Iteration is done in reverse
1068 : * element order.
1069 : */
1070 : _GLIBCXX_NODISCARD
1071 : const_reverse_iterator
1072 : rbegin() const _GLIBCXX_NOEXCEPT
1073 : { return const_reverse_iterator(end()); }
1074 :
1075 : /**
1076 : * Returns a read/write reverse iterator that points to one
1077 : * before the first element in the %list. Iteration is done in
1078 : * reverse element order.
1079 : */
1080 : _GLIBCXX_NODISCARD
1081 : reverse_iterator
1082 : rend() _GLIBCXX_NOEXCEPT
1083 : { return reverse_iterator(begin()); }
1084 :
1085 : /**
1086 : * Returns a read-only (constant) reverse iterator that points to one
1087 : * before the first element in the %list. Iteration is done in reverse
1088 : * element order.
1089 : */
1090 : _GLIBCXX_NODISCARD
1091 : const_reverse_iterator
1092 : rend() const _GLIBCXX_NOEXCEPT
1093 : { return const_reverse_iterator(begin()); }
1094 :
1095 : #if __cplusplus >= 201103L
1096 : /**
1097 : * Returns a read-only (constant) iterator that points to the
1098 : * first element in the %list. Iteration is done in ordinary
1099 : * element order.
1100 : */
1101 : [[__nodiscard__]]
1102 : const_iterator
1103 : cbegin() const noexcept
1104 : { return const_iterator(this->_M_impl._M_node._M_next); }
1105 :
1106 : /**
1107 : * Returns a read-only (constant) iterator that points one past
1108 : * the last element in the %list. Iteration is done in ordinary
1109 : * element order.
1110 : */
1111 : [[__nodiscard__]]
1112 : const_iterator
1113 : cend() const noexcept
1114 : { return const_iterator(&this->_M_impl._M_node); }
1115 :
1116 : /**
1117 : * Returns a read-only (constant) reverse iterator that points to
1118 : * the last element in the %list. Iteration is done in reverse
1119 : * element order.
1120 : */
1121 : [[__nodiscard__]]
1122 : const_reverse_iterator
1123 : crbegin() const noexcept
1124 : { return const_reverse_iterator(end()); }
1125 :
1126 : /**
1127 : * Returns a read-only (constant) reverse iterator that points to one
1128 : * before the first element in the %list. Iteration is done in reverse
1129 : * element order.
1130 : */
1131 : [[__nodiscard__]]
1132 : const_reverse_iterator
1133 : crend() const noexcept
1134 : { return const_reverse_iterator(begin()); }
1135 : #endif
1136 :
1137 : // [23.2.2.2] capacity
1138 : /**
1139 : * Returns true if the %list is empty. (Thus begin() would equal
1140 : * end().)
1141 : */
1142 : _GLIBCXX_NODISCARD bool
1143 : empty() const _GLIBCXX_NOEXCEPT
1144 : { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
1145 :
1146 : /** Returns the number of elements in the %list. */
1147 : _GLIBCXX_NODISCARD
1148 : size_type
1149 : size() const _GLIBCXX_NOEXCEPT
1150 : { return _M_node_count(); }
1151 :
1152 : /** Returns the size() of the largest possible %list. */
1153 : _GLIBCXX_NODISCARD
1154 : size_type
1155 : max_size() const _GLIBCXX_NOEXCEPT
1156 : { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); }
1157 :
1158 : #if __cplusplus >= 201103L
1159 : /**
1160 : * @brief Resizes the %list to the specified number of elements.
1161 : * @param __new_size Number of elements the %list should contain.
1162 : *
1163 : * This function will %resize the %list to the specified number
1164 : * of elements. If the number is smaller than the %list's
1165 : * current size the %list is truncated, otherwise default
1166 : * constructed elements are appended.
1167 : */
1168 : void
1169 : resize(size_type __new_size);
1170 :
1171 : /**
1172 : * @brief Resizes the %list to the specified number of elements.
1173 : * @param __new_size Number of elements the %list should contain.
1174 : * @param __x Data with which new elements should be populated.
1175 : *
1176 : * This function will %resize the %list to the specified number
1177 : * of elements. If the number is smaller than the %list's
1178 : * current size the %list is truncated, otherwise the %list is
1179 : * extended and new elements are populated with given data.
1180 : */
1181 : void
1182 : resize(size_type __new_size, const value_type& __x);
1183 : #else
1184 : /**
1185 : * @brief Resizes the %list to the specified number of elements.
1186 : * @param __new_size Number of elements the %list should contain.
1187 : * @param __x Data with which new elements should be populated.
1188 : *
1189 : * This function will %resize the %list to the specified number
1190 : * of elements. If the number is smaller than the %list's
1191 : * current size the %list is truncated, otherwise the %list is
1192 : * extended and new elements are populated with given data.
1193 : */
1194 : void
1195 : resize(size_type __new_size, value_type __x = value_type());
1196 : #endif
1197 :
1198 : // element access
1199 : /**
1200 : * Returns a read/write reference to the data at the first
1201 : * element of the %list.
1202 : */
1203 : _GLIBCXX_NODISCARD
1204 : reference
1205 : front() _GLIBCXX_NOEXCEPT
1206 : { return *begin(); }
1207 :
1208 : /**
1209 : * Returns a read-only (constant) reference to the data at the first
1210 : * element of the %list.
1211 : */
1212 : _GLIBCXX_NODISCARD
1213 : const_reference
1214 : front() const _GLIBCXX_NOEXCEPT
1215 : { return *begin(); }
1216 :
1217 : /**
1218 : * Returns a read/write reference to the data at the last element
1219 : * of the %list.
1220 : */
1221 : _GLIBCXX_NODISCARD
1222 : reference
1223 3152 : back() _GLIBCXX_NOEXCEPT
1224 : {
1225 3152 : iterator __tmp = end();
1226 1426 : --__tmp;
1227 1426 : return *__tmp;
1228 : }
1229 :
1230 : /**
1231 : * Returns a read-only (constant) reference to the data at the last
1232 : * element of the %list.
1233 : */
1234 : _GLIBCXX_NODISCARD
1235 : const_reference
1236 : back() const _GLIBCXX_NOEXCEPT
1237 : {
1238 : const_iterator __tmp = end();
1239 : --__tmp;
1240 : return *__tmp;
1241 : }
1242 :
1243 : // [23.2.2.3] modifiers
1244 : /**
1245 : * @brief Add data to the front of the %list.
1246 : * @param __x Data to be added.
1247 : *
1248 : * This is a typical stack operation. The function creates an
1249 : * element at the front of the %list and assigns the given data
1250 : * to it. Due to the nature of a %list this operation can be
1251 : * done in constant time, and does not invalidate iterators and
1252 : * references.
1253 : */
1254 : void
1255 : push_front(const value_type& __x)
1256 : { this->_M_insert(begin(), __x); }
1257 :
1258 : #if __cplusplus >= 201103L
1259 : void
1260 : push_front(value_type&& __x)
1261 : { this->_M_insert(begin(), std::move(__x)); }
1262 :
1263 : template<typename... _Args>
1264 : #if __cplusplus > 201402L
1265 : reference
1266 : #else
1267 : void
1268 : #endif
1269 : emplace_front(_Args&&... __args)
1270 : {
1271 : this->_M_insert(begin(), std::forward<_Args>(__args)...);
1272 : #if __cplusplus > 201402L
1273 : return front();
1274 : #endif
1275 : }
1276 : #endif
1277 :
1278 : /**
1279 : * @brief Removes first element.
1280 : *
1281 : * This is a typical stack operation. It shrinks the %list by
1282 : * one. Due to the nature of a %list this operation can be done
1283 : * in constant time, and only invalidates iterators/references to
1284 : * the element being removed.
1285 : *
1286 : * Note that no data is returned, and if the first element's data
1287 : * is needed, it should be retrieved before pop_front() is
1288 : * called.
1289 : */
1290 : void
1291 : pop_front() _GLIBCXX_NOEXCEPT
1292 : { this->_M_erase(begin()); }
1293 :
1294 : /**
1295 : * @brief Add data to the end of the %list.
1296 : * @param __x Data to be added.
1297 : *
1298 : * This is a typical stack operation. The function creates an
1299 : * element at the end of the %list and assigns the given data to
1300 : * it. Due to the nature of a %list this operation can be done
1301 : * in constant time, and does not invalidate iterators and
1302 : * references.
1303 : */
1304 : void
1305 1426 : push_back(const value_type& __x)
1306 1426 : { this->_M_insert(end(), __x); }
1307 :
1308 : #if __cplusplus >= 201103L
1309 : void
1310 : push_back(value_type&& __x)
1311 : { this->_M_insert(end(), std::move(__x)); }
1312 :
1313 : template<typename... _Args>
1314 : #if __cplusplus > 201402L
1315 : reference
1316 : #else
1317 : void
1318 : #endif
1319 3152 : emplace_back(_Args&&... __args)
1320 : {
1321 1426 : this->_M_insert(end(), std::forward<_Args>(__args)...);
1322 : #if __cplusplus > 201402L
1323 3152 : return back();
1324 : #endif
1325 : }
1326 : #endif
1327 :
1328 : /**
1329 : * @brief Removes last element.
1330 : *
1331 : * This is a typical stack operation. It shrinks the %list by
1332 : * one. Due to the nature of a %list this operation can be done
1333 : * in constant time, and only invalidates iterators/references to
1334 : * the element being removed.
1335 : *
1336 : * Note that no data is returned, and if the last element's data
1337 : * is needed, it should be retrieved before pop_back() is called.
1338 : */
1339 : void
1340 : pop_back() _GLIBCXX_NOEXCEPT
1341 : { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
1342 :
1343 : #if __cplusplus >= 201103L
1344 : /**
1345 : * @brief Constructs object in %list before specified iterator.
1346 : * @param __position A const_iterator into the %list.
1347 : * @param __args Arguments.
1348 : * @return An iterator that points to the inserted data.
1349 : *
1350 : * This function will insert an object of type T constructed
1351 : * with T(std::forward<Args>(args)...) before the specified
1352 : * location. Due to the nature of a %list this operation can
1353 : * be done in constant time, and does not invalidate iterators
1354 : * and references.
1355 : */
1356 : template<typename... _Args>
1357 : iterator
1358 : emplace(const_iterator __position, _Args&&... __args);
1359 :
1360 : /**
1361 : * @brief Inserts given value into %list before specified iterator.
1362 : * @param __position A const_iterator into the %list.
1363 : * @param __x Data to be inserted.
1364 : * @return An iterator that points to the inserted data.
1365 : *
1366 : * This function will insert a copy of the given value before
1367 : * the specified location. Due to the nature of a %list this
1368 : * operation can be done in constant time, and does not
1369 : * invalidate iterators and references.
1370 : */
1371 : iterator
1372 : insert(const_iterator __position, const value_type& __x);
1373 : #else
1374 : /**
1375 : * @brief Inserts given value into %list before specified iterator.
1376 : * @param __position An iterator into the %list.
1377 : * @param __x Data to be inserted.
1378 : * @return An iterator that points to the inserted data.
1379 : *
1380 : * This function will insert a copy of the given value before
1381 : * the specified location. Due to the nature of a %list this
1382 : * operation can be done in constant time, and does not
1383 : * invalidate iterators and references.
1384 : */
1385 : iterator
1386 : insert(iterator __position, const value_type& __x);
1387 : #endif
1388 :
1389 : #if __cplusplus >= 201103L
1390 : /**
1391 : * @brief Inserts given rvalue into %list before specified iterator.
1392 : * @param __position A const_iterator into the %list.
1393 : * @param __x Data to be inserted.
1394 : * @return An iterator that points to the inserted data.
1395 : *
1396 : * This function will insert a copy of the given rvalue before
1397 : * the specified location. Due to the nature of a %list this
1398 : * operation can be done in constant time, and does not
1399 : * invalidate iterators and references.
1400 : */
1401 : iterator
1402 : insert(const_iterator __position, value_type&& __x)
1403 : { return emplace(__position, std::move(__x)); }
1404 :
1405 : /**
1406 : * @brief Inserts the contents of an initializer_list into %list
1407 : * before specified const_iterator.
1408 : * @param __p A const_iterator into the %list.
1409 : * @param __l An initializer_list of value_type.
1410 : * @return An iterator pointing to the first element inserted
1411 : * (or __position).
1412 : *
1413 : * This function will insert copies of the data in the
1414 : * initializer_list @a l into the %list before the location
1415 : * specified by @a p.
1416 : *
1417 : * This operation is linear in the number of elements inserted and
1418 : * does not invalidate iterators and references.
1419 : */
1420 : iterator
1421 : insert(const_iterator __p, initializer_list<value_type> __l)
1422 : { return this->insert(__p, __l.begin(), __l.end()); }
1423 : #endif
1424 :
1425 : #if __cplusplus >= 201103L
1426 : /**
1427 : * @brief Inserts a number of copies of given data into the %list.
1428 : * @param __position A const_iterator into the %list.
1429 : * @param __n Number of elements to be inserted.
1430 : * @param __x Data to be inserted.
1431 : * @return An iterator pointing to the first element inserted
1432 : * (or __position).
1433 : *
1434 : * This function will insert a specified number of copies of the
1435 : * given data before the location specified by @a position.
1436 : *
1437 : * This operation is linear in the number of elements inserted and
1438 : * does not invalidate iterators and references.
1439 : */
1440 : iterator
1441 : insert(const_iterator __position, size_type __n, const value_type& __x);
1442 : #else
1443 : /**
1444 : * @brief Inserts a number of copies of given data into the %list.
1445 : * @param __position An iterator into the %list.
1446 : * @param __n Number of elements to be inserted.
1447 : * @param __x Data to be inserted.
1448 : *
1449 : * This function will insert a specified number of copies of the
1450 : * given data before the location specified by @a position.
1451 : *
1452 : * This operation is linear in the number of elements inserted and
1453 : * does not invalidate iterators and references.
1454 : */
1455 : void
1456 : insert(iterator __position, size_type __n, const value_type& __x)
1457 : {
1458 : list __tmp(__n, __x, get_allocator());
1459 : splice(__position, __tmp);
1460 : }
1461 : #endif
1462 :
1463 : #if __cplusplus >= 201103L
1464 : /**
1465 : * @brief Inserts a range into the %list.
1466 : * @param __position A const_iterator into the %list.
1467 : * @param __first An input iterator.
1468 : * @param __last An input iterator.
1469 : * @return An iterator pointing to the first element inserted
1470 : * (or __position).
1471 : *
1472 : * This function will insert copies of the data in the range [@a
1473 : * first,@a last) into the %list before the location specified by
1474 : * @a position.
1475 : *
1476 : * This operation is linear in the number of elements inserted and
1477 : * does not invalidate iterators and references.
1478 : */
1479 : template<typename _InputIterator,
1480 : typename = std::_RequireInputIter<_InputIterator>>
1481 : iterator
1482 : insert(const_iterator __position, _InputIterator __first,
1483 : _InputIterator __last);
1484 : #else
1485 : /**
1486 : * @brief Inserts a range into the %list.
1487 : * @param __position An iterator into the %list.
1488 : * @param __first An input iterator.
1489 : * @param __last An input iterator.
1490 : *
1491 : * This function will insert copies of the data in the range [@a
1492 : * first,@a last) into the %list before the location specified by
1493 : * @a position.
1494 : *
1495 : * This operation is linear in the number of elements inserted and
1496 : * does not invalidate iterators and references.
1497 : */
1498 : template<typename _InputIterator>
1499 : void
1500 : insert(iterator __position, _InputIterator __first,
1501 : _InputIterator __last)
1502 : {
1503 : list __tmp(__first, __last, get_allocator());
1504 : splice(__position, __tmp);
1505 : }
1506 : #endif
1507 :
1508 : /**
1509 : * @brief Remove element at given position.
1510 : * @param __position Iterator pointing to element to be erased.
1511 : * @return An iterator pointing to the next element (or end()).
1512 : *
1513 : * This function will erase the element at the given position and thus
1514 : * shorten the %list by one.
1515 : *
1516 : * Due to the nature of a %list this operation can be done in
1517 : * constant time, and only invalidates iterators/references to
1518 : * the element being removed. The user is also cautioned that
1519 : * this function only erases the element, and that if the element
1520 : * is itself a pointer, the pointed-to memory is not touched in
1521 : * any way. Managing the pointer is the user's responsibility.
1522 : */
1523 : iterator
1524 : #if __cplusplus >= 201103L
1525 : erase(const_iterator __position) noexcept;
1526 : #else
1527 : erase(iterator __position);
1528 : #endif
1529 :
1530 : /**
1531 : * @brief Remove a range of elements.
1532 : * @param __first Iterator pointing to the first element to be erased.
1533 : * @param __last Iterator pointing to one past the last element to be
1534 : * erased.
1535 : * @return An iterator pointing to the element pointed to by @a last
1536 : * prior to erasing (or end()).
1537 : *
1538 : * This function will erase the elements in the range @a
1539 : * [first,last) and shorten the %list accordingly.
1540 : *
1541 : * This operation is linear time in the size of the range and only
1542 : * invalidates iterators/references to the element being removed.
1543 : * The user is also cautioned that this function only erases the
1544 : * elements, and that if the elements themselves are pointers, the
1545 : * pointed-to memory is not touched in any way. Managing the pointer
1546 : * is the user's responsibility.
1547 : */
1548 : iterator
1549 : #if __cplusplus >= 201103L
1550 : erase(const_iterator __first, const_iterator __last) noexcept
1551 : #else
1552 : erase(iterator __first, iterator __last)
1553 : #endif
1554 : {
1555 : while (__first != __last)
1556 : __first = erase(__first);
1557 : return __last._M_const_cast();
1558 : }
1559 :
1560 : /**
1561 : * @brief Swaps data with another %list.
1562 : * @param __x A %list of the same element and allocator types.
1563 : *
1564 : * This exchanges the elements between two lists in constant
1565 : * time. Note that the global std::swap() function is
1566 : * specialized such that std::swap(l1,l2) will feed to this
1567 : * function.
1568 : *
1569 : * Whether the allocators are swapped depends on the allocator traits.
1570 : */
1571 : void
1572 : swap(list& __x) _GLIBCXX_NOEXCEPT
1573 : {
1574 : __detail::_List_node_base::swap(this->_M_impl._M_node,
1575 : __x._M_impl._M_node);
1576 :
1577 : size_t __xsize = __x._M_get_size();
1578 : __x._M_set_size(this->_M_get_size());
1579 : this->_M_set_size(__xsize);
1580 :
1581 : _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1582 : __x._M_get_Node_allocator());
1583 : }
1584 :
1585 : /**
1586 : * Erases all the elements. Note that this function only erases
1587 : * the elements, and that if the elements themselves are
1588 : * pointers, the pointed-to memory is not touched in any way.
1589 : * Managing the pointer is the user's responsibility.
1590 : */
1591 : void
1592 : clear() _GLIBCXX_NOEXCEPT
1593 : {
1594 : _Base::_M_clear();
1595 : _Base::_M_init();
1596 : }
1597 :
1598 : // [23.2.2.4] list operations
1599 : /**
1600 : * @brief Insert contents of another %list.
1601 : * @param __position Iterator referencing the element to insert before.
1602 : * @param __x Source list.
1603 : *
1604 : * The elements of @a __x are inserted in constant time in front of
1605 : * the element referenced by @a __position. @a __x becomes an empty
1606 : * list.
1607 : *
1608 : * Requires this != @a __x.
1609 : */
1610 : void
1611 : #if __cplusplus >= 201103L
1612 : splice(const_iterator __position, list&& __x) noexcept
1613 : #else
1614 : splice(iterator __position, list& __x)
1615 : #endif
1616 : {
1617 : if (!__x.empty())
1618 : {
1619 : _M_check_equal_allocators(__x);
1620 :
1621 : this->_M_transfer(__position._M_const_cast(),
1622 : __x.begin(), __x.end());
1623 :
1624 : this->_M_inc_size(__x._M_get_size());
1625 : __x._M_set_size(0);
1626 : }
1627 : }
1628 :
1629 : #if __cplusplus >= 201103L
1630 : void
1631 : splice(const_iterator __position, list& __x) noexcept
1632 : { splice(__position, std::move(__x)); }
1633 : #endif
1634 :
1635 : #if __cplusplus >= 201103L
1636 : /**
1637 : * @brief Insert element from another %list.
1638 : * @param __position Const_iterator referencing the element to
1639 : * insert before.
1640 : * @param __x Source list.
1641 : * @param __i Const_iterator referencing the element to move.
1642 : *
1643 : * Removes the element in list @a __x referenced by @a __i and
1644 : * inserts it into the current list before @a __position.
1645 : */
1646 : void
1647 : splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
1648 : #else
1649 : /**
1650 : * @brief Insert element from another %list.
1651 : * @param __position Iterator referencing the element to insert before.
1652 : * @param __x Source list.
1653 : * @param __i Iterator referencing the element to move.
1654 : *
1655 : * Removes the element in list @a __x referenced by @a __i and
1656 : * inserts it into the current list before @a __position.
1657 : */
1658 : void
1659 : splice(iterator __position, list& __x, iterator __i)
1660 : #endif
1661 : {
1662 : iterator __j = __i._M_const_cast();
1663 : ++__j;
1664 : if (__position == __i || __position == __j)
1665 : return;
1666 :
1667 : if (this != std::__addressof(__x))
1668 : _M_check_equal_allocators(__x);
1669 :
1670 : this->_M_transfer(__position._M_const_cast(),
1671 : __i._M_const_cast(), __j);
1672 :
1673 : this->_M_inc_size(1);
1674 : __x._M_dec_size(1);
1675 : }
1676 :
1677 : #if __cplusplus >= 201103L
1678 : /**
1679 : * @brief Insert element from another %list.
1680 : * @param __position Const_iterator referencing the element to
1681 : * insert before.
1682 : * @param __x Source list.
1683 : * @param __i Const_iterator referencing the element to move.
1684 : *
1685 : * Removes the element in list @a __x referenced by @a __i and
1686 : * inserts it into the current list before @a __position.
1687 : */
1688 : void
1689 : splice(const_iterator __position, list& __x, const_iterator __i) noexcept
1690 : { splice(__position, std::move(__x), __i); }
1691 : #endif
1692 :
1693 : #if __cplusplus >= 201103L
1694 : /**
1695 : * @brief Insert range from another %list.
1696 : * @param __position Const_iterator referencing the element to
1697 : * insert before.
1698 : * @param __x Source list.
1699 : * @param __first Const_iterator referencing the start of range in x.
1700 : * @param __last Const_iterator referencing the end of range in x.
1701 : *
1702 : * Removes elements in the range [__first,__last) and inserts them
1703 : * before @a __position in constant time.
1704 : *
1705 : * Undefined if @a __position is in [__first,__last).
1706 : */
1707 : void
1708 : splice(const_iterator __position, list&& __x, const_iterator __first,
1709 : const_iterator __last) noexcept
1710 : #else
1711 : /**
1712 : * @brief Insert range from another %list.
1713 : * @param __position Iterator referencing the element to insert before.
1714 : * @param __x Source list.
1715 : * @param __first Iterator referencing the start of range in x.
1716 : * @param __last Iterator referencing the end of range in x.
1717 : *
1718 : * Removes elements in the range [__first,__last) and inserts them
1719 : * before @a __position in constant time.
1720 : *
1721 : * Undefined if @a __position is in [__first,__last).
1722 : */
1723 : void
1724 : splice(iterator __position, list& __x, iterator __first,
1725 : iterator __last)
1726 : #endif
1727 : {
1728 : if (__first != __last)
1729 : {
1730 : if (this != std::__addressof(__x))
1731 : _M_check_equal_allocators(__x);
1732 :
1733 : size_t __n = _S_distance(__first, __last);
1734 : this->_M_inc_size(__n);
1735 : __x._M_dec_size(__n);
1736 :
1737 : this->_M_transfer(__position._M_const_cast(),
1738 : __first._M_const_cast(),
1739 : __last._M_const_cast());
1740 : }
1741 : }
1742 :
1743 : #if __cplusplus >= 201103L
1744 : /**
1745 : * @brief Insert range from another %list.
1746 : * @param __position Const_iterator referencing the element to
1747 : * insert before.
1748 : * @param __x Source list.
1749 : * @param __first Const_iterator referencing the start of range in x.
1750 : * @param __last Const_iterator referencing the end of range in x.
1751 : *
1752 : * Removes elements in the range [__first,__last) and inserts them
1753 : * before @a __position in constant time.
1754 : *
1755 : * Undefined if @a __position is in [__first,__last).
1756 : */
1757 : void
1758 : splice(const_iterator __position, list& __x, const_iterator __first,
1759 : const_iterator __last) noexcept
1760 : { splice(__position, std::move(__x), __first, __last); }
1761 : #endif
1762 :
1763 : private:
1764 : #if __cplusplus > 201703L
1765 : # define __cpp_lib_list_remove_return_type 201806L
1766 : typedef size_type __remove_return_type;
1767 : # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
1768 : __attribute__((__abi_tag__("__cxx20")))
1769 : #else
1770 : typedef void __remove_return_type;
1771 : # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
1772 : #endif
1773 : public:
1774 :
1775 : /**
1776 : * @brief Remove all elements equal to value.
1777 : * @param __value The value to remove.
1778 : *
1779 : * Removes every element in the list equal to @a value.
1780 : * Remaining elements stay in list order. Note that this
1781 : * function only erases the elements, and that if the elements
1782 : * themselves are pointers, the pointed-to memory is not
1783 : * touched in any way. Managing the pointer is the user's
1784 : * responsibility.
1785 : */
1786 : _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
1787 : __remove_return_type
1788 : remove(const _Tp& __value);
1789 :
1790 : /**
1791 : * @brief Remove all elements satisfying a predicate.
1792 : * @tparam _Predicate Unary predicate function or object.
1793 : *
1794 : * Removes every element in the list for which the predicate
1795 : * returns true. Remaining elements stay in list order. Note
1796 : * that this function only erases the elements, and that if the
1797 : * elements themselves are pointers, the pointed-to memory is
1798 : * not touched in any way. Managing the pointer is the user's
1799 : * responsibility.
1800 : */
1801 : template<typename _Predicate>
1802 : __remove_return_type
1803 : remove_if(_Predicate);
1804 :
1805 : /**
1806 : * @brief Remove consecutive duplicate elements.
1807 : *
1808 : * For each consecutive set of elements with the same value,
1809 : * remove all but the first one. Remaining elements stay in
1810 : * list order. Note that this function only erases the
1811 : * elements, and that if the elements themselves are pointers,
1812 : * the pointed-to memory is not touched in any way. Managing
1813 : * the pointer is the user's responsibility.
1814 : */
1815 : _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
1816 : __remove_return_type
1817 : unique();
1818 :
1819 : /**
1820 : * @brief Remove consecutive elements satisfying a predicate.
1821 : * @tparam _BinaryPredicate Binary predicate function or object.
1822 : *
1823 : * For each consecutive set of elements [first,last) that
1824 : * satisfy predicate(first,i) where i is an iterator in
1825 : * [first,last), remove all but the first one. Remaining
1826 : * elements stay in list order. Note that this function only
1827 : * erases the elements, and that if the elements themselves are
1828 : * pointers, the pointed-to memory is not touched in any way.
1829 : * Managing the pointer is the user's responsibility.
1830 : */
1831 : template<typename _BinaryPredicate>
1832 : __remove_return_type
1833 : unique(_BinaryPredicate);
1834 :
1835 : #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
1836 :
1837 : /**
1838 : * @brief Merge sorted lists.
1839 : * @param __x Sorted list to merge.
1840 : *
1841 : * Assumes that both @a __x and this list are sorted according to
1842 : * operator<(). Merges elements of @a __x into this list in
1843 : * sorted order, leaving @a __x empty when complete. Elements in
1844 : * this list precede elements in @a __x that are equal.
1845 : */
1846 : #if __cplusplus >= 201103L
1847 : void
1848 : merge(list&& __x);
1849 :
1850 : void
1851 : merge(list& __x)
1852 : { merge(std::move(__x)); }
1853 : #else
1854 : void
1855 : merge(list& __x);
1856 : #endif
1857 :
1858 : /**
1859 : * @brief Merge sorted lists according to comparison function.
1860 : * @tparam _StrictWeakOrdering Comparison function defining
1861 : * sort order.
1862 : * @param __x Sorted list to merge.
1863 : * @param __comp Comparison functor.
1864 : *
1865 : * Assumes that both @a __x and this list are sorted according to
1866 : * StrictWeakOrdering. Merges elements of @a __x into this list
1867 : * in sorted order, leaving @a __x empty when complete. Elements
1868 : * in this list precede elements in @a __x that are equivalent
1869 : * according to StrictWeakOrdering().
1870 : */
1871 : #if __cplusplus >= 201103L
1872 : template<typename _StrictWeakOrdering>
1873 : void
1874 : merge(list&& __x, _StrictWeakOrdering __comp);
1875 :
1876 : template<typename _StrictWeakOrdering>
1877 : void
1878 : merge(list& __x, _StrictWeakOrdering __comp)
1879 : { merge(std::move(__x), __comp); }
1880 : #else
1881 : template<typename _StrictWeakOrdering>
1882 : void
1883 : merge(list& __x, _StrictWeakOrdering __comp);
1884 : #endif
1885 :
1886 : /**
1887 : * @brief Reverse the elements in list.
1888 : *
1889 : * Reverse the order of elements in the list in linear time.
1890 : */
1891 : void
1892 : reverse() _GLIBCXX_NOEXCEPT
1893 : { this->_M_impl._M_node._M_reverse(); }
1894 :
1895 : /**
1896 : * @brief Sort the elements.
1897 : *
1898 : * Sorts the elements of this list in NlogN time. Equivalent
1899 : * elements remain in list order.
1900 : */
1901 : void
1902 : sort();
1903 :
1904 : /**
1905 : * @brief Sort the elements according to comparison function.
1906 : *
1907 : * Sorts the elements of this list in NlogN time. Equivalent
1908 : * elements remain in list order.
1909 : */
1910 : template<typename _StrictWeakOrdering>
1911 : void
1912 : sort(_StrictWeakOrdering);
1913 :
1914 : protected:
1915 : // Internal constructor functions follow.
1916 :
1917 : // Called by the range constructor to implement [23.1.1]/9
1918 :
1919 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1920 : // 438. Ambiguity in the "do the right thing" clause
1921 : template<typename _Integer>
1922 : void
1923 : _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1924 : { _M_fill_initialize(static_cast<size_type>(__n), __x); }
1925 :
1926 : // Called by the range constructor to implement [23.1.1]/9
1927 : template<typename _InputIterator>
1928 : void
1929 116 : _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1930 : __false_type)
1931 : {
1932 1842 : for (; __first != __last; ++__first)
1933 : #if __cplusplus >= 201103L
1934 1726 : emplace_back(*__first);
1935 : #else
1936 : push_back(*__first);
1937 : #endif
1938 : }
1939 :
1940 : // Called by list(n,v,a), and the range constructor when it turns out
1941 : // to be the same thing.
1942 : void
1943 : _M_fill_initialize(size_type __n, const value_type& __x)
1944 : {
1945 : for (; __n; --__n)
1946 : push_back(__x);
1947 : }
1948 :
1949 : #if __cplusplus >= 201103L
1950 : // Called by list(n).
1951 : void
1952 : _M_default_initialize(size_type __n)
1953 : {
1954 : for (; __n; --__n)
1955 : emplace_back();
1956 : }
1957 :
1958 : // Called by resize(sz).
1959 : void
1960 : _M_default_append(size_type __n);
1961 : #endif
1962 :
1963 : // Internal assign functions follow.
1964 :
1965 : // Called by the range assign to implement [23.1.1]/9
1966 :
1967 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1968 : // 438. Ambiguity in the "do the right thing" clause
1969 : template<typename _Integer>
1970 : void
1971 : _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1972 : { _M_fill_assign(__n, __val); }
1973 :
1974 : // Called by the range assign to implement [23.1.1]/9
1975 : template<typename _InputIterator>
1976 : void
1977 : _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1978 : __false_type);
1979 :
1980 : // Called by assign(n,t), and the range assign when it turns out
1981 : // to be the same thing.
1982 : void
1983 : _M_fill_assign(size_type __n, const value_type& __val);
1984 :
1985 :
1986 : // Moves the elements from [first,last) before position.
1987 : void
1988 : _M_transfer(iterator __position, iterator __first, iterator __last)
1989 : { __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
1990 :
1991 : // Inserts new element at position given and with value given.
1992 : #if __cplusplus < 201103L
1993 : void
1994 : _M_insert(iterator __position, const value_type& __x)
1995 : {
1996 : _Node* __tmp = _M_create_node(__x);
1997 : __tmp->_M_hook(__position._M_node);
1998 : this->_M_inc_size(1);
1999 : }
2000 : #else
2001 : template<typename... _Args>
2002 : void
2003 4578 : _M_insert(iterator __position, _Args&&... __args)
2004 : {
2005 4578 : _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
2006 4578 : __tmp->_M_hook(__position._M_node);
2007 4578 : this->_M_inc_size(1);
2008 4578 : }
2009 : #endif
2010 :
2011 : // Erases element at position given.
2012 : void
2013 70588 : _M_erase(iterator __position) _GLIBCXX_NOEXCEPT
2014 : {
2015 70588 : this->_M_dec_size(1);
2016 70588 : __position._M_node->_M_unhook();
2017 70588 : _Node* __n = static_cast<_Node*>(__position._M_node);
2018 : #if __cplusplus >= 201103L
2019 70588 : _Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr());
2020 : #else
2021 : _Tp_alloc_type(_M_get_Node_allocator()).destroy(__n->_M_valptr());
2022 : #endif
2023 :
2024 70588 : _M_put_node(__n);
2025 70588 : }
2026 :
2027 : // To implement the splice (and merge) bits of N1599.
2028 : void
2029 : _M_check_equal_allocators(list& __x) _GLIBCXX_NOEXCEPT
2030 : {
2031 : if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
2032 : _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
2033 : __builtin_abort();
2034 : }
2035 :
2036 : // Used to implement resize.
2037 : const_iterator
2038 : _M_resize_pos(size_type& __new_size) const;
2039 :
2040 : #if __cplusplus >= 201103L
2041 : void
2042 : _M_move_assign(list&& __x, true_type) noexcept
2043 : {
2044 : this->clear();
2045 : this->_M_move_nodes(std::move(__x));
2046 : std::__alloc_on_move(this->_M_get_Node_allocator(),
2047 : __x._M_get_Node_allocator());
2048 : }
2049 :
2050 : void
2051 : _M_move_assign(list&& __x, false_type)
2052 : {
2053 : if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator())
2054 : _M_move_assign(std::move(__x), true_type{});
2055 : else
2056 : // The rvalue's allocator cannot be moved, or is not equal,
2057 : // so we need to individually move each element.
2058 : _M_assign_dispatch(std::make_move_iterator(__x.begin()),
2059 : std::make_move_iterator(__x.end()),
2060 : __false_type{});
2061 : }
2062 : #endif
2063 :
2064 : #if _GLIBCXX_USE_CXX11_ABI
2065 : // Update _M_size members after merging (some of) __src into __dest.
2066 : struct _Finalize_merge
2067 : {
2068 : explicit
2069 : _Finalize_merge(list& __dest, list& __src, const iterator& __src_next)
2070 : : _M_dest(__dest), _M_src(__src), _M_next(__src_next)
2071 : { }
2072 :
2073 : ~_Finalize_merge()
2074 : {
2075 : // For the common case, _M_next == _M_sec.end() and the std::distance
2076 : // call is fast. But if any *iter1 < *iter2 comparison throws then we
2077 : // have to count how many elements remain in _M_src.
2078 : const size_t __num_unmerged = std::distance(_M_next, _M_src.end());
2079 : const size_t __orig_size = _M_src._M_get_size();
2080 : _M_dest._M_inc_size(__orig_size - __num_unmerged);
2081 : _M_src._M_set_size(__num_unmerged);
2082 : }
2083 :
2084 : list& _M_dest;
2085 : list& _M_src;
2086 : const iterator& _M_next;
2087 :
2088 : #if __cplusplus >= 201103L
2089 : _Finalize_merge(const _Finalize_merge&) = delete;
2090 : #endif
2091 : };
2092 : #else
2093 : struct _Finalize_merge
2094 : { explicit _Finalize_merge(list&, list&, const iterator&) { } };
2095 : #endif
2096 :
2097 : };
2098 :
2099 : #if __cpp_deduction_guides >= 201606
2100 : template<typename _InputIterator, typename _ValT
2101 : = typename iterator_traits<_InputIterator>::value_type,
2102 : typename _Allocator = allocator<_ValT>,
2103 : typename = _RequireInputIter<_InputIterator>,
2104 : typename = _RequireAllocator<_Allocator>>
2105 : list(_InputIterator, _InputIterator, _Allocator = _Allocator())
2106 : -> list<_ValT, _Allocator>;
2107 : #endif
2108 :
2109 : _GLIBCXX_END_NAMESPACE_CXX11
2110 :
2111 : /**
2112 : * @brief List equality comparison.
2113 : * @param __x A %list.
2114 : * @param __y A %list of the same type as @a __x.
2115 : * @return True iff the size and elements of the lists are equal.
2116 : *
2117 : * This is an equivalence relation. It is linear in the size of
2118 : * the lists. Lists are considered equivalent if their sizes are
2119 : * equal, and if corresponding elements compare equal.
2120 : */
2121 : template<typename _Tp, typename _Alloc>
2122 : _GLIBCXX_NODISCARD
2123 : inline bool
2124 : operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2125 : {
2126 : #if _GLIBCXX_USE_CXX11_ABI
2127 : if (__x.size() != __y.size())
2128 : return false;
2129 : #endif
2130 :
2131 : typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
2132 : const_iterator __end1 = __x.end();
2133 : const_iterator __end2 = __y.end();
2134 :
2135 : const_iterator __i1 = __x.begin();
2136 : const_iterator __i2 = __y.begin();
2137 : while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
2138 : {
2139 : ++__i1;
2140 : ++__i2;
2141 : }
2142 : return __i1 == __end1 && __i2 == __end2;
2143 : }
2144 :
2145 : #if __cpp_lib_three_way_comparison
2146 : /**
2147 : * @brief List ordering relation.
2148 : * @param __x A `list`.
2149 : * @param __y A `list` of the same type as `__x`.
2150 : * @return A value indicating whether `__x` is less than, equal to,
2151 : * greater than, or incomparable with `__y`.
2152 : *
2153 : * See `std::lexicographical_compare_three_way()` for how the determination
2154 : * is made. This operator is used to synthesize relational operators like
2155 : * `<` and `>=` etc.
2156 : */
2157 : template<typename _Tp, typename _Alloc>
2158 : [[nodiscard]]
2159 : inline __detail::__synth3way_t<_Tp>
2160 : operator<=>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2161 : {
2162 : return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2163 : __y.begin(), __y.end(),
2164 : __detail::__synth3way);
2165 : }
2166 : #else
2167 : /**
2168 : * @brief List ordering relation.
2169 : * @param __x A %list.
2170 : * @param __y A %list of the same type as @a __x.
2171 : * @return True iff @a __x is lexicographically less than @a __y.
2172 : *
2173 : * This is a total ordering relation. It is linear in the size of the
2174 : * lists. The elements must be comparable with @c <.
2175 : *
2176 : * See std::lexicographical_compare() for how the determination is made.
2177 : */
2178 : template<typename _Tp, typename _Alloc>
2179 : _GLIBCXX_NODISCARD
2180 : inline bool
2181 : operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2182 : { return std::lexicographical_compare(__x.begin(), __x.end(),
2183 : __y.begin(), __y.end()); }
2184 :
2185 : /// Based on operator==
2186 : template<typename _Tp, typename _Alloc>
2187 : _GLIBCXX_NODISCARD
2188 : inline bool
2189 : operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2190 : { return !(__x == __y); }
2191 :
2192 : /// Based on operator<
2193 : template<typename _Tp, typename _Alloc>
2194 : _GLIBCXX_NODISCARD
2195 : inline bool
2196 : operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2197 : { return __y < __x; }
2198 :
2199 : /// Based on operator<
2200 : template<typename _Tp, typename _Alloc>
2201 : _GLIBCXX_NODISCARD
2202 : inline bool
2203 : operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2204 : { return !(__y < __x); }
2205 :
2206 : /// Based on operator<
2207 : template<typename _Tp, typename _Alloc>
2208 : _GLIBCXX_NODISCARD
2209 : inline bool
2210 : operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2211 : { return !(__x < __y); }
2212 : #endif // three-way comparison
2213 :
2214 : /// See std::list::swap().
2215 : template<typename _Tp, typename _Alloc>
2216 : inline void
2217 : swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2218 : _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2219 : { __x.swap(__y); }
2220 :
2221 : _GLIBCXX_END_NAMESPACE_CONTAINER
2222 :
2223 : #if _GLIBCXX_USE_CXX11_ABI
2224 :
2225 : // Detect when distance is used to compute the size of the whole list.
2226 : template<typename _Tp>
2227 : inline ptrdiff_t
2228 : __distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first,
2229 : _GLIBCXX_STD_C::_List_iterator<_Tp> __last,
2230 : input_iterator_tag __tag)
2231 : {
2232 : typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _CIter;
2233 : return std::__distance(_CIter(__first), _CIter(__last), __tag);
2234 : }
2235 :
2236 : template<typename _Tp>
2237 : inline ptrdiff_t
2238 116 : __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp> __first,
2239 : _GLIBCXX_STD_C::_List_const_iterator<_Tp> __last,
2240 : input_iterator_tag)
2241 : {
2242 : typedef __detail::_List_node_header _Sentinel;
2243 116 : _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last;
2244 116 : ++__beyond;
2245 116 : const bool __whole = __first == __beyond;
2246 116 : if (__builtin_constant_p (__whole) && __whole)
2247 0 : return static_cast<const _Sentinel*>(__last._M_node)->_M_size;
2248 :
2249 : ptrdiff_t __n = 0;
2250 1726 : while (__first != __last)
2251 : {
2252 1610 : ++__first;
2253 1610 : ++__n;
2254 : }
2255 : return __n;
2256 : }
2257 : #endif
2258 :
2259 : _GLIBCXX_END_NAMESPACE_VERSION
2260 : } // namespace std
2261 :
2262 : #endif /* _STL_LIST_H */
|
