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