Line data Source code
1 : // List implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2013 Free Software Foundation, Inc.
4 : //
5 : // This file is part of the GNU ISO C++ Library. This library is free
6 : // software; you can redistribute it and/or modify it under the
7 : // terms of the GNU General Public License as published by the
8 : // Free Software Foundation; either version 3, or (at your option)
9 : // any later version.
10 :
11 : // This library is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 :
16 : // Under Section 7 of GPL version 3, you are granted additional
17 : // permissions described in the GCC Runtime Library Exception, version
18 : // 3.1, as published by the Free Software Foundation.
19 :
20 : // You should have received a copy of the GNU General Public License and
21 : // a copy of the GCC Runtime Library Exception along with this program;
22 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : // <http://www.gnu.org/licenses/>.
24 :
25 : /*
26 : *
27 : * Copyright (c) 1994
28 : * Hewlett-Packard Company
29 : *
30 : * Permission to use, copy, modify, distribute and sell this software
31 : * and its documentation for any purpose is hereby granted without fee,
32 : * provided that the above copyright notice appear in all copies and
33 : * that both that copyright notice and this permission notice appear
34 : * in supporting documentation. Hewlett-Packard Company makes no
35 : * representations about the suitability of this software for any
36 : * purpose. It is provided "as is" without express or implied warranty.
37 : *
38 : *
39 : * Copyright (c) 1996,1997
40 : * Silicon Graphics Computer Systems, Inc.
41 : *
42 : * Permission to use, copy, modify, distribute and sell this software
43 : * and its documentation for any purpose is hereby granted without fee,
44 : * provided that the above copyright notice appear in all copies and
45 : * that both that copyright notice and this permission notice appear
46 : * in supporting documentation. Silicon Graphics makes no
47 : * representations about the suitability of this software for any
48 : * purpose. It is provided "as is" without express or implied warranty.
49 : */
50 :
51 : /** @file bits/stl_list.h
52 : * This is an internal header file, included by other library headers.
53 : * Do not attempt to use it directly. @headername{list}
54 : */
55 :
56 : #ifndef _STL_LIST_H
57 : #define _STL_LIST_H 1
58 :
59 : #include <bits/concept_check.h>
60 : #if __cplusplus >= 201103L
61 : #include <initializer_list>
62 : #endif
63 :
64 : namespace std _GLIBCXX_VISIBILITY(default)
65 : {
66 : namespace __detail
67 : {
68 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
69 :
70 : // Supporting structures are split into common and templated
71 : // types; the latter publicly inherits from the former in an
72 : // effort to reduce code duplication. This results in some
73 : // "needless" static_cast'ing later on, but it's all safe
74 : // downcasting.
75 :
76 : /// Common part of a node in the %list.
77 : struct _List_node_base
78 : {
79 : _List_node_base* _M_next;
80 : _List_node_base* _M_prev;
81 :
82 : static void
83 : swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
84 :
85 : void
86 : _M_transfer(_List_node_base* const __first,
87 : _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
88 :
89 : void
90 : _M_reverse() _GLIBCXX_USE_NOEXCEPT;
91 :
92 : void
93 : _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
94 :
95 : void
96 : _M_unhook() _GLIBCXX_USE_NOEXCEPT;
97 : };
98 :
99 : _GLIBCXX_END_NAMESPACE_VERSION
100 : } // namespace detail
101 :
102 : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
103 :
104 : /// An actual node in the %list.
105 : template<typename _Tp>
106 2092 : struct _List_node : public __detail::_List_node_base
107 : {
108 : ///< User's data.
109 : _Tp _M_data;
110 :
111 : #if __cplusplus >= 201103L
112 : template<typename... _Args>
113 281079 : _List_node(_Args&&... __args)
114 281079 : : __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...)
115 281074 : { }
116 : #endif
117 : };
118 :
119 : /**
120 : * @brief A list::iterator.
121 : *
122 : * All the functions are op overloads.
123 : */
124 : template<typename _Tp>
125 : struct _List_iterator
126 : {
127 : typedef _List_iterator<_Tp> _Self;
128 : typedef _List_node<_Tp> _Node;
129 :
130 : typedef ptrdiff_t difference_type;
131 : typedef std::bidirectional_iterator_tag iterator_category;
132 : typedef _Tp value_type;
133 : typedef _Tp* pointer;
134 : typedef _Tp& reference;
135 :
136 1139330 : _List_iterator()
137 1139330 : : _M_node() { }
138 :
139 : explicit
140 3306065 : _List_iterator(__detail::_List_node_base* __x)
141 3306065 : : _M_node(__x) { }
142 :
143 : // Must downcast from _List_node_base to _List_node to get to _M_data.
144 : reference
145 2527503 : operator*() const
146 2527503 : { return static_cast<_Node*>(_M_node)->_M_data; }
147 :
148 : pointer
149 2658 : operator->() const
150 2658 : { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }
151 :
152 : _Self&
153 254 : operator++()
154 : {
155 254 : _M_node = _M_node->_M_next;
156 254 : return *this;
157 : }
158 :
159 : _Self
160 1202 : operator++(int)
161 : {
162 1202 : _Self __tmp = *this;
163 1202 : _M_node = _M_node->_M_next;
164 1202 : return __tmp;
165 : }
166 :
167 : _Self&
168 255293 : operator--()
169 : {
170 255293 : _M_node = _M_node->_M_prev;
171 255293 : return *this;
172 : }
173 :
174 : _Self
175 : operator--(int)
176 : {
177 : _Self __tmp = *this;
178 : _M_node = _M_node->_M_prev;
179 : return __tmp;
180 : }
181 :
182 : bool
183 : operator==(const _Self& __x) const
184 : { return _M_node == __x._M_node; }
185 :
186 : bool
187 27302 : operator!=(const _Self& __x) const
188 27302 : { return _M_node != __x._M_node; }
189 :
190 : // The only member points to the %list element.
191 : __detail::_List_node_base* _M_node;
192 : };
193 :
194 : /**
195 : * @brief A list::const_iterator.
196 : *
197 : * All the functions are op overloads.
198 : */
199 : template<typename _Tp>
200 : struct _List_const_iterator
201 : {
202 : typedef _List_const_iterator<_Tp> _Self;
203 : typedef const _List_node<_Tp> _Node;
204 : typedef _List_iterator<_Tp> iterator;
205 :
206 : typedef ptrdiff_t difference_type;
207 : typedef std::bidirectional_iterator_tag iterator_category;
208 : typedef _Tp value_type;
209 : typedef const _Tp* pointer;
210 : typedef const _Tp& reference;
211 :
212 : _List_const_iterator()
213 : : _M_node() { }
214 :
215 : explicit
216 546 : _List_const_iterator(const __detail::_List_node_base* __x)
217 546 : : _M_node(__x) { }
218 :
219 : _List_const_iterator(const iterator& __x)
220 : : _M_node(__x._M_node) { }
221 :
222 : // Must downcast from List_node_base to _List_node to get to
223 : // _M_data.
224 : reference
225 254 : operator*() const
226 254 : { return static_cast<_Node*>(_M_node)->_M_data; }
227 :
228 : pointer
229 254 : operator->() const
230 254 : { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }
231 :
232 : _Self&
233 508 : operator++()
234 : {
235 508 : _M_node = _M_node->_M_next;
236 508 : return *this;
237 : }
238 :
239 : _Self
240 : operator++(int)
241 : {
242 : _Self __tmp = *this;
243 : _M_node = _M_node->_M_next;
244 : return __tmp;
245 : }
246 :
247 : _Self&
248 : operator--()
249 : {
250 : _M_node = _M_node->_M_prev;
251 : return *this;
252 : }
253 :
254 : _Self
255 : operator--(int)
256 : {
257 : _Self __tmp = *this;
258 : _M_node = _M_node->_M_prev;
259 : return __tmp;
260 : }
261 :
262 : bool
263 : operator==(const _Self& __x) const
264 : { return _M_node == __x._M_node; }
265 :
266 : bool
267 436 : operator!=(const _Self& __x) const
268 436 : { return _M_node != __x._M_node; }
269 :
270 : // The only member points to the %list element.
271 : const __detail::_List_node_base* _M_node;
272 : };
273 :
274 : template<typename _Val>
275 : inline bool
276 : operator==(const _List_iterator<_Val>& __x,
277 : const _List_const_iterator<_Val>& __y)
278 : { return __x._M_node == __y._M_node; }
279 :
280 : template<typename _Val>
281 : inline bool
282 : operator!=(const _List_iterator<_Val>& __x,
283 : const _List_const_iterator<_Val>& __y)
284 : { return __x._M_node != __y._M_node; }
285 :
286 :
287 : /// See bits/stl_deque.h's _Deque_base for an explanation.
288 : template<typename _Tp, typename _Alloc>
289 : class _List_base
290 : {
291 : protected:
292 : // NOTA BENE
293 : // The stored instance is not actually of "allocator_type"'s
294 : // type. Instead we rebind the type to
295 : // Allocator<List_node<Tp>>, which according to [20.1.5]/4
296 : // should probably be the same. List_node<Tp> is not the same
297 : // size as Tp (it's two pointers larger), and specializations on
298 : // Tp may go unused because List_node<Tp> is being bound
299 : // instead.
300 : //
301 : // We put this to the test in the constructors and in
302 : // get_allocator, where we use conversions between
303 : // allocator_type and _Node_alloc_type. The conversion is
304 : // required by table 32 in [20.1.5].
305 : typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
306 : _Node_alloc_type;
307 :
308 : typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
309 :
310 748 : struct _List_impl
311 : : public _Node_alloc_type
312 : {
313 : __detail::_List_node_base _M_node;
314 :
315 559 : _List_impl()
316 559 : : _Node_alloc_type(), _M_node()
317 559 : { }
318 :
319 182 : _List_impl(const _Node_alloc_type& __a)
320 182 : : _Node_alloc_type(__a), _M_node()
321 182 : { }
322 :
323 : #if __cplusplus >= 201103L
324 7 : _List_impl(_Node_alloc_type&& __a)
325 7 : : _Node_alloc_type(std::move(__a)), _M_node()
326 7 : { }
327 : #endif
328 : };
329 :
330 : _List_impl _M_impl;
331 :
332 : _List_node<_Tp>*
333 281078 : _M_get_node()
334 281078 : { return _M_impl._Node_alloc_type::allocate(1); }
335 :
336 : void
337 281089 : _M_put_node(_List_node<_Tp>* __p)
338 281089 : { _M_impl._Node_alloc_type::deallocate(__p, 1); }
339 :
340 : public:
341 : typedef _Alloc allocator_type;
342 :
343 : _Node_alloc_type&
344 561850 : _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
345 561850 : { return *static_cast<_Node_alloc_type*>(&_M_impl); }
346 :
347 : const _Node_alloc_type&
348 182 : _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
349 182 : { return *static_cast<const _Node_alloc_type*>(&_M_impl); }
350 :
351 : _Tp_alloc_type
352 : _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
353 : { return _Tp_alloc_type(_M_get_Node_allocator()); }
354 :
355 : allocator_type
356 : get_allocator() const _GLIBCXX_NOEXCEPT
357 : { return allocator_type(_M_get_Node_allocator()); }
358 :
359 559 : _List_base()
360 559 : : _M_impl()
361 559 : { _M_init(); }
362 :
363 182 : _List_base(const _Node_alloc_type& __a)
364 182 : : _M_impl(__a)
365 182 : { _M_init(); }
366 :
367 : #if __cplusplus >= 201103L
368 7 : _List_base(_List_base&& __x)
369 7 : : _M_impl(std::move(__x._M_get_Node_allocator()))
370 : {
371 7 : _M_init();
372 7 : __detail::_List_node_base::swap(_M_impl._M_node, __x._M_impl._M_node);
373 7 : }
374 : #endif
375 :
376 : // This is what actually destroys the list.
377 748 : ~_List_base() _GLIBCXX_NOEXCEPT
378 748 : { _M_clear(); }
379 :
380 : void
381 : _M_clear();
382 :
383 : void
384 748 : _M_init()
385 : {
386 748 : this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
387 748 : this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
388 748 : }
389 : };
390 :
391 : /**
392 : * @brief A standard container with linear time access to elements,
393 : * and fixed time insertion/deletion at any point in the sequence.
394 : *
395 : * @ingroup sequences
396 : *
397 : * @tparam _Tp Type of element.
398 : * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
399 : *
400 : * Meets the requirements of a <a href="tables.html#65">container</a>, a
401 : * <a href="tables.html#66">reversible container</a>, and a
402 : * <a href="tables.html#67">sequence</a>, including the
403 : * <a href="tables.html#68">optional sequence requirements</a> with the
404 : * %exception of @c at and @c operator[].
405 : *
406 : * This is a @e doubly @e linked %list. Traversal up and down the
407 : * %list requires linear time, but adding and removing elements (or
408 : * @e nodes) is done in constant time, regardless of where the
409 : * change takes place. Unlike std::vector and std::deque,
410 : * random-access iterators are not provided, so subscripting ( @c
411 : * [] ) access is not allowed. For algorithms which only need
412 : * sequential access, this lack makes no difference.
413 : *
414 : * Also unlike the other standard containers, std::list provides
415 : * specialized algorithms %unique to linked lists, such as
416 : * splicing, sorting, and in-place reversal.
417 : *
418 : * A couple points on memory allocation for list<Tp>:
419 : *
420 : * First, we never actually allocate a Tp, we allocate
421 : * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure
422 : * that after elements from %list<X,Alloc1> are spliced into
423 : * %list<X,Alloc2>, destroying the memory of the second %list is a
424 : * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
425 : *
426 : * Second, a %list conceptually represented as
427 : * @code
428 : * A <---> B <---> C <---> D
429 : * @endcode
430 : * is actually circular; a link exists between A and D. The %list
431 : * class holds (as its only data member) a private list::iterator
432 : * pointing to @e D, not to @e A! To get to the head of the %list,
433 : * we start at the tail and move forward by one. When this member
434 : * iterator's next/previous pointers refer to itself, the %list is
435 : * %empty.
436 : */
437 : template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
438 748 : class list : protected _List_base<_Tp, _Alloc>
439 : {
440 : // concept requirements
441 : typedef typename _Alloc::value_type _Alloc_value_type;
442 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
443 : __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
444 :
445 : typedef _List_base<_Tp, _Alloc> _Base;
446 : typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
447 : typedef typename _Base::_Node_alloc_type _Node_alloc_type;
448 :
449 : public:
450 : typedef _Tp value_type;
451 : typedef typename _Tp_alloc_type::pointer pointer;
452 : typedef typename _Tp_alloc_type::const_pointer const_pointer;
453 : typedef typename _Tp_alloc_type::reference reference;
454 : typedef typename _Tp_alloc_type::const_reference const_reference;
455 : typedef _List_iterator<_Tp> iterator;
456 : typedef _List_const_iterator<_Tp> const_iterator;
457 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
458 : typedef std::reverse_iterator<iterator> reverse_iterator;
459 : typedef size_t size_type;
460 : typedef ptrdiff_t difference_type;
461 : typedef _Alloc allocator_type;
462 :
463 : protected:
464 : // Note that pointers-to-_Node's can be ctor-converted to
465 : // iterator types.
466 : typedef _List_node<_Tp> _Node;
467 :
468 : using _Base::_M_impl;
469 : using _Base::_M_put_node;
470 : using _Base::_M_get_node;
471 : using _Base::_M_get_Tp_allocator;
472 : using _Base::_M_get_Node_allocator;
473 :
474 : /**
475 : * @param __args An instance of user data.
476 : *
477 : * Allocates space for a new node and constructs a copy of
478 : * @a __args in it.
479 : */
480 : #if __cplusplus < 201103L
481 : _Node*
482 : _M_create_node(const value_type& __x)
483 : {
484 : _Node* __p = this->_M_get_node();
485 : __try
486 : {
487 : _M_get_Tp_allocator().construct
488 : (std::__addressof(__p->_M_data), __x);
489 : }
490 : __catch(...)
491 : {
492 : _M_put_node(__p);
493 : __throw_exception_again;
494 : }
495 : return __p;
496 : }
497 : #else
498 : template<typename... _Args>
499 : _Node*
500 280710 : _M_create_node(_Args&&... __args)
501 : {
502 280710 : _Node* __p = this->_M_get_node();
503 : __try
504 : {
505 281090 : _M_get_Node_allocator().construct(__p,
506 281078 : std::forward<_Args>(__args)...);
507 : }
508 : __catch(...)
509 : {
510 : _M_put_node(__p);
511 : __throw_exception_again;
512 : }
513 281074 : return __p;
514 : }
515 : #endif
516 :
517 : public:
518 : // [23.2.2.1] construct/copy/destroy
519 : // (assign() and get_allocator() are also listed in this section)
520 : /**
521 : * @brief Default constructor creates no elements.
522 : */
523 559 : list()
524 559 : : _Base() { }
525 :
526 : /**
527 : * @brief Creates a %list with no elements.
528 : * @param __a An allocator object.
529 : */
530 : explicit
531 : list(const allocator_type& __a)
532 : : _Base(_Node_alloc_type(__a)) { }
533 :
534 : #if __cplusplus >= 201103L
535 : /**
536 : * @brief Creates a %list with default constructed elements.
537 : * @param __n The number of elements to initially create.
538 : *
539 : * This constructor fills the %list with @a __n default
540 : * constructed elements.
541 : */
542 : explicit
543 : list(size_type __n)
544 : : _Base()
545 : { _M_default_initialize(__n); }
546 :
547 : /**
548 : * @brief Creates a %list with copies of an exemplar element.
549 : * @param __n The number of elements to initially create.
550 : * @param __value An element to copy.
551 : * @param __a An allocator object.
552 : *
553 : * This constructor fills the %list with @a __n copies of @a __value.
554 : */
555 : list(size_type __n, const value_type& __value,
556 : const allocator_type& __a = allocator_type())
557 : : _Base(_Node_alloc_type(__a))
558 : { _M_fill_initialize(__n, __value); }
559 : #else
560 : /**
561 : * @brief Creates a %list with copies of an exemplar element.
562 : * @param __n The number of elements to initially create.
563 : * @param __value An element to copy.
564 : * @param __a An allocator object.
565 : *
566 : * This constructor fills the %list with @a __n copies of @a __value.
567 : */
568 : explicit
569 : list(size_type __n, const value_type& __value = value_type(),
570 : const allocator_type& __a = allocator_type())
571 : : _Base(_Node_alloc_type(__a))
572 : { _M_fill_initialize(__n, __value); }
573 : #endif
574 :
575 : /**
576 : * @brief %List copy constructor.
577 : * @param __x A %list of identical element and allocator types.
578 : *
579 : * The newly-created %list uses a copy of the allocation object used
580 : * by @a __x.
581 : */
582 182 : list(const list& __x)
583 182 : : _Base(__x._M_get_Node_allocator())
584 182 : { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
585 :
586 : #if __cplusplus >= 201103L
587 : /**
588 : * @brief %List move constructor.
589 : * @param __x A %list of identical element and allocator types.
590 : *
591 : * The newly-created %list contains the exact contents of @a __x.
592 : * The contents of @a __x are a valid, but unspecified %list.
593 : */
594 7 : list(list&& __x) noexcept
595 7 : : _Base(std::move(__x)) { }
596 :
597 : /**
598 : * @brief Builds a %list from an initializer_list
599 : * @param __l An initializer_list of value_type.
600 : * @param __a An allocator object.
601 : *
602 : * Create a %list consisting of copies of the elements in the
603 : * initializer_list @a __l. This is linear in __l.size().
604 : */
605 : list(initializer_list<value_type> __l,
606 : const allocator_type& __a = allocator_type())
607 : : _Base(_Node_alloc_type(__a))
608 : { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
609 : #endif
610 :
611 : /**
612 : * @brief Builds a %list from a range.
613 : * @param __first An input iterator.
614 : * @param __last An input iterator.
615 : * @param __a An allocator object.
616 : *
617 : * Create a %list consisting of copies of the elements from
618 : * [@a __first,@a __last). This is linear in N (where N is
619 : * distance(@a __first,@a __last)).
620 : */
621 : #if __cplusplus >= 201103L
622 : template<typename _InputIterator,
623 : typename = std::_RequireInputIter<_InputIterator>>
624 : list(_InputIterator __first, _InputIterator __last,
625 : const allocator_type& __a = allocator_type())
626 : : _Base(_Node_alloc_type(__a))
627 : { _M_initialize_dispatch(__first, __last, __false_type()); }
628 : #else
629 : template<typename _InputIterator>
630 : list(_InputIterator __first, _InputIterator __last,
631 : const allocator_type& __a = allocator_type())
632 : : _Base(_Node_alloc_type(__a))
633 : {
634 : // Check whether it's an integral type. If so, it's not an iterator.
635 : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
636 : _M_initialize_dispatch(__first, __last, _Integral());
637 : }
638 : #endif
639 :
640 : /**
641 : * No explicit dtor needed as the _Base dtor takes care of
642 : * things. The _Base dtor only erases the elements, and note
643 : * that if the elements themselves are pointers, the pointed-to
644 : * memory is not touched in any way. Managing the pointer is
645 : * the user's responsibility.
646 : */
647 :
648 : /**
649 : * @brief %List assignment operator.
650 : * @param __x A %list of identical element and allocator types.
651 : *
652 : * All the elements of @a __x are copied, but unlike the copy
653 : * constructor, the allocator object is not copied.
654 : */
655 : list&
656 : operator=(const list& __x);
657 :
658 : #if __cplusplus >= 201103L
659 : /**
660 : * @brief %List move assignment operator.
661 : * @param __x A %list of identical element and allocator types.
662 : *
663 : * The contents of @a __x are moved into this %list (without copying).
664 : * @a __x is a valid, but unspecified %list
665 : */
666 : list&
667 : operator=(list&& __x)
668 : {
669 : // NB: DR 1204.
670 : // NB: DR 675.
671 : this->clear();
672 : this->swap(__x);
673 : return *this;
674 : }
675 :
676 : /**
677 : * @brief %List initializer list assignment operator.
678 : * @param __l An initializer_list of value_type.
679 : *
680 : * Replace the contents of the %list with copies of the elements
681 : * in the initializer_list @a __l. This is linear in l.size().
682 : */
683 : list&
684 : operator=(initializer_list<value_type> __l)
685 : {
686 : this->assign(__l.begin(), __l.end());
687 : return *this;
688 : }
689 : #endif
690 :
691 : /**
692 : * @brief Assigns a given value to a %list.
693 : * @param __n Number of elements to be assigned.
694 : * @param __val Value to be assigned.
695 : *
696 : * This function fills a %list with @a __n copies of the given
697 : * value. Note that the assignment completely changes the %list
698 : * and that the resulting %list's size is the same as the number
699 : * of elements assigned. Old data may be lost.
700 : */
701 : void
702 : assign(size_type __n, const value_type& __val)
703 : { _M_fill_assign(__n, __val); }
704 :
705 : /**
706 : * @brief Assigns a range to a %list.
707 : * @param __first An input iterator.
708 : * @param __last An input iterator.
709 : *
710 : * This function fills a %list with copies of the elements in the
711 : * range [@a __first,@a __last).
712 : *
713 : * Note that the assignment completely changes the %list and
714 : * that the resulting %list's size is the same as the number of
715 : * elements assigned. Old data may be lost.
716 : */
717 : #if __cplusplus >= 201103L
718 : template<typename _InputIterator,
719 : typename = std::_RequireInputIter<_InputIterator>>
720 : void
721 : assign(_InputIterator __first, _InputIterator __last)
722 : { _M_assign_dispatch(__first, __last, __false_type()); }
723 : #else
724 : template<typename _InputIterator>
725 : void
726 : assign(_InputIterator __first, _InputIterator __last)
727 : {
728 : // Check whether it's an integral type. If so, it's not an iterator.
729 : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
730 : _M_assign_dispatch(__first, __last, _Integral());
731 : }
732 : #endif
733 :
734 : #if __cplusplus >= 201103L
735 : /**
736 : * @brief Assigns an initializer_list to a %list.
737 : * @param __l An initializer_list of value_type.
738 : *
739 : * Replace the contents of the %list with copies of the elements
740 : * in the initializer_list @a __l. This is linear in __l.size().
741 : */
742 : void
743 : assign(initializer_list<value_type> __l)
744 : { this->assign(__l.begin(), __l.end()); }
745 : #endif
746 :
747 : /// Get a copy of the memory allocation object.
748 : allocator_type
749 : get_allocator() const _GLIBCXX_NOEXCEPT
750 : { return _Base::get_allocator(); }
751 :
752 : // iterators
753 : /**
754 : * Returns a read/write iterator that points to the first element in the
755 : * %list. Iteration is done in ordinary element order.
756 : */
757 : iterator
758 2507066 : begin() _GLIBCXX_NOEXCEPT
759 2507066 : { return iterator(this->_M_impl._M_node._M_next); }
760 :
761 : /**
762 : * Returns a read-only (constant) iterator that points to the
763 : * first element in the %list. Iteration is done in ordinary
764 : * element order.
765 : */
766 : const_iterator
767 364 : begin() const _GLIBCXX_NOEXCEPT
768 364 : { return const_iterator(this->_M_impl._M_node._M_next); }
769 :
770 : /**
771 : * Returns a read/write iterator that points one past the last
772 : * element in the %list. Iteration is done in ordinary element
773 : * order.
774 : */
775 : iterator
776 562538 : end() _GLIBCXX_NOEXCEPT
777 562538 : { return iterator(&this->_M_impl._M_node); }
778 :
779 : /**
780 : * Returns a read-only (constant) iterator that points one past
781 : * the last element in the %list. Iteration is done in ordinary
782 : * element order.
783 : */
784 : const_iterator
785 182 : end() const _GLIBCXX_NOEXCEPT
786 182 : { return const_iterator(&this->_M_impl._M_node); }
787 :
788 : /**
789 : * Returns a read/write reverse iterator that points to the last
790 : * element in the %list. Iteration is done in reverse element
791 : * order.
792 : */
793 : reverse_iterator
794 : rbegin() _GLIBCXX_NOEXCEPT
795 : { return reverse_iterator(end()); }
796 :
797 : /**
798 : * Returns a read-only (constant) reverse iterator that points to
799 : * the last element in the %list. Iteration is done in reverse
800 : * element order.
801 : */
802 : const_reverse_iterator
803 : rbegin() const _GLIBCXX_NOEXCEPT
804 : { return const_reverse_iterator(end()); }
805 :
806 : /**
807 : * Returns a read/write reverse iterator that points to one
808 : * before the first element in the %list. Iteration is done in
809 : * reverse element order.
810 : */
811 : reverse_iterator
812 : rend() _GLIBCXX_NOEXCEPT
813 : { return reverse_iterator(begin()); }
814 :
815 : /**
816 : * Returns a read-only (constant) reverse iterator that points to one
817 : * before the first element in the %list. Iteration is done in reverse
818 : * element order.
819 : */
820 : const_reverse_iterator
821 : rend() const _GLIBCXX_NOEXCEPT
822 : { return const_reverse_iterator(begin()); }
823 :
824 : #if __cplusplus >= 201103L
825 : /**
826 : * Returns a read-only (constant) iterator that points to the
827 : * first element in the %list. Iteration is done in ordinary
828 : * element order.
829 : */
830 : const_iterator
831 : cbegin() const noexcept
832 : { return const_iterator(this->_M_impl._M_node._M_next); }
833 :
834 : /**
835 : * Returns a read-only (constant) iterator that points one past
836 : * the last element in the %list. Iteration is done in ordinary
837 : * element order.
838 : */
839 : const_iterator
840 : cend() const noexcept
841 : { return const_iterator(&this->_M_impl._M_node); }
842 :
843 : /**
844 : * Returns a read-only (constant) reverse iterator that points to
845 : * the last element in the %list. Iteration is done in reverse
846 : * element order.
847 : */
848 : const_reverse_iterator
849 : crbegin() const noexcept
850 : { return const_reverse_iterator(end()); }
851 :
852 : /**
853 : * Returns a read-only (constant) reverse iterator that points to one
854 : * before the first element in the %list. Iteration is done in reverse
855 : * element order.
856 : */
857 : const_reverse_iterator
858 : crend() const noexcept
859 : { return const_reverse_iterator(begin()); }
860 : #endif
861 :
862 : // [23.2.2.2] capacity
863 : /**
864 : * Returns true if the %list is empty. (Thus begin() would equal
865 : * end().)
866 : */
867 : bool
868 2665015 : empty() const _GLIBCXX_NOEXCEPT
869 2665015 : { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
870 :
871 : /** Returns the number of elements in the %list. */
872 : size_type
873 : size() const _GLIBCXX_NOEXCEPT
874 : { return std::distance(begin(), end()); }
875 :
876 : /** Returns the size() of the largest possible %list. */
877 : size_type
878 : max_size() const _GLIBCXX_NOEXCEPT
879 : { return _M_get_Node_allocator().max_size(); }
880 :
881 : #if __cplusplus >= 201103L
882 : /**
883 : * @brief Resizes the %list to the specified number of elements.
884 : * @param __new_size Number of elements the %list should contain.
885 : *
886 : * This function will %resize the %list to the specified number
887 : * of elements. If the number is smaller than the %list's
888 : * current size the %list is truncated, otherwise default
889 : * constructed elements are appended.
890 : */
891 : void
892 : resize(size_type __new_size);
893 :
894 : /**
895 : * @brief Resizes the %list to the specified number of elements.
896 : * @param __new_size Number of elements the %list should contain.
897 : * @param __x Data with which new elements should be populated.
898 : *
899 : * This function will %resize the %list to the specified number
900 : * of elements. If the number is smaller than the %list's
901 : * current size the %list is truncated, otherwise the %list is
902 : * extended and new elements are populated with given data.
903 : */
904 : void
905 : resize(size_type __new_size, const value_type& __x);
906 : #else
907 : /**
908 : * @brief Resizes the %list to the specified number of elements.
909 : * @param __new_size Number of elements the %list should contain.
910 : * @param __x Data with which new elements should be populated.
911 : *
912 : * This function will %resize the %list to the specified number
913 : * of elements. If the number is smaller than the %list's
914 : * current size the %list is truncated, otherwise the %list is
915 : * extended and new elements are populated with given data.
916 : */
917 : void
918 : resize(size_type __new_size, value_type __x = value_type());
919 : #endif
920 :
921 : // element access
922 : /**
923 : * Returns a read/write reference to the data at the first
924 : * element of the %list.
925 : */
926 : reference
927 : front()
928 : { return *begin(); }
929 :
930 : /**
931 : * Returns a read-only (constant) reference to the data at the first
932 : * element of the %list.
933 : */
934 : const_reference
935 : front() const
936 : { return *begin(); }
937 :
938 : /**
939 : * Returns a read/write reference to the data at the last element
940 : * of the %list.
941 : */
942 : reference
943 636 : back()
944 : {
945 636 : iterator __tmp = end();
946 636 : --__tmp;
947 636 : return *__tmp;
948 : }
949 :
950 : /**
951 : * Returns a read-only (constant) reference to the data at the last
952 : * element of the %list.
953 : */
954 : const_reference
955 : back() const
956 : {
957 : const_iterator __tmp = end();
958 : --__tmp;
959 : return *__tmp;
960 : }
961 :
962 : // [23.2.2.3] modifiers
963 : /**
964 : * @brief Add data to the front of the %list.
965 : * @param __x Data to be added.
966 : *
967 : * This is a typical stack operation. The function creates an
968 : * element at the front of the %list and assigns the given data
969 : * to it. Due to the nature of a %list this operation can be
970 : * done in constant time, and does not invalidate iterators and
971 : * references.
972 : */
973 : void
974 : push_front(const value_type& __x)
975 : { this->_M_insert(begin(), __x); }
976 :
977 : #if __cplusplus >= 201103L
978 : void
979 : push_front(value_type&& __x)
980 : { this->_M_insert(begin(), std::move(__x)); }
981 :
982 : template<typename... _Args>
983 : void
984 : emplace_front(_Args&&... __args)
985 : { this->_M_insert(begin(), std::forward<_Args>(__args)...); }
986 : #endif
987 :
988 : /**
989 : * @brief Removes first element.
990 : *
991 : * This is a typical stack operation. It shrinks the %list by
992 : * one. Due to the nature of a %list this operation can be done
993 : * in constant time, and only invalidates iterators/references to
994 : * the element being removed.
995 : *
996 : * Note that no data is returned, and if the first element's data
997 : * is needed, it should be retrieved before pop_front() is
998 : * called.
999 : */
1000 : void
1001 : pop_front()
1002 : { this->_M_erase(begin()); }
1003 :
1004 : /**
1005 : * @brief Add data to the end of the %list.
1006 : * @param __x Data to be added.
1007 : *
1008 : * This is a typical stack operation. The function creates an
1009 : * element at the end of the %list and assigns the given data to
1010 : * it. Due to the nature of a %list this operation can be done
1011 : * in constant time, and does not invalidate iterators and
1012 : * references.
1013 : */
1014 : void
1015 24948 : push_back(const value_type& __x)
1016 24948 : { this->_M_insert(end(), __x); }
1017 :
1018 : #if __cplusplus >= 201103L
1019 : void
1020 126 : push_back(value_type&& __x)
1021 126 : { this->_M_insert(end(), std::move(__x)); }
1022 :
1023 : template<typename... _Args>
1024 : void
1025 256008 : emplace_back(_Args&&... __args)
1026 256008 : { this->_M_insert(end(), std::forward<_Args>(__args)...); }
1027 : #endif
1028 :
1029 : /**
1030 : * @brief Removes last element.
1031 : *
1032 : * This is a typical stack operation. It shrinks the %list by
1033 : * one. Due to the nature of a %list this operation can be done
1034 : * in constant time, and only invalidates iterators/references to
1035 : * the element being removed.
1036 : *
1037 : * Note that no data is returned, and if the last element's data
1038 : * is needed, it should be retrieved before pop_back() is called.
1039 : */
1040 : void
1041 : pop_back()
1042 : { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
1043 :
1044 : #if __cplusplus >= 201103L
1045 : /**
1046 : * @brief Constructs object in %list before specified iterator.
1047 : * @param __position A const_iterator into the %list.
1048 : * @param __args Arguments.
1049 : * @return An iterator that points to the inserted data.
1050 : *
1051 : * This function will insert an object of type T constructed
1052 : * with T(std::forward<Args>(args)...) before the specified
1053 : * location. Due to the nature of a %list this operation can
1054 : * be done in constant time, and does not invalidate iterators
1055 : * and references.
1056 : */
1057 : template<typename... _Args>
1058 : iterator
1059 : emplace(iterator __position, _Args&&... __args);
1060 : #endif
1061 :
1062 : /**
1063 : * @brief Inserts given value into %list before specified iterator.
1064 : * @param __position An iterator into the %list.
1065 : * @param __x Data to be inserted.
1066 : * @return An iterator that points to the inserted data.
1067 : *
1068 : * This function will insert a copy of the given value before
1069 : * the specified location. Due to the nature of a %list this
1070 : * operation can be done in constant time, and does not
1071 : * invalidate iterators and references.
1072 : */
1073 : iterator
1074 : insert(iterator __position, const value_type& __x);
1075 :
1076 : #if __cplusplus >= 201103L
1077 : /**
1078 : * @brief Inserts given rvalue into %list before specified iterator.
1079 : * @param __position An iterator into the %list.
1080 : * @param __x Data to be inserted.
1081 : * @return An iterator that points to the inserted data.
1082 : *
1083 : * This function will insert a copy of the given rvalue before
1084 : * the specified location. Due to the nature of a %list this
1085 : * operation can be done in constant time, and does not
1086 : * invalidate iterators and references.
1087 : */
1088 : iterator
1089 : insert(iterator __position, value_type&& __x)
1090 : { return emplace(__position, std::move(__x)); }
1091 :
1092 : /**
1093 : * @brief Inserts the contents of an initializer_list into %list
1094 : * before specified iterator.
1095 : * @param __p An iterator into the %list.
1096 : * @param __l An initializer_list of value_type.
1097 : *
1098 : * This function will insert copies of the data in the
1099 : * initializer_list @a l into the %list before the location
1100 : * specified by @a p.
1101 : *
1102 : * This operation is linear in the number of elements inserted and
1103 : * does not invalidate iterators and references.
1104 : */
1105 : void
1106 : insert(iterator __p, initializer_list<value_type> __l)
1107 : { this->insert(__p, __l.begin(), __l.end()); }
1108 : #endif
1109 :
1110 : /**
1111 : * @brief Inserts a number of copies of given data into the %list.
1112 : * @param __position An iterator into the %list.
1113 : * @param __n Number of elements to be inserted.
1114 : * @param __x Data to be inserted.
1115 : *
1116 : * This function will insert a specified number of copies of the
1117 : * given data before the location specified by @a position.
1118 : *
1119 : * This operation is linear in the number of elements inserted and
1120 : * does not invalidate iterators and references.
1121 : */
1122 : void
1123 : insert(iterator __position, size_type __n, const value_type& __x)
1124 : {
1125 : list __tmp(__n, __x, get_allocator());
1126 : splice(__position, __tmp);
1127 : }
1128 :
1129 : /**
1130 : * @brief Inserts a range into the %list.
1131 : * @param __position An iterator into the %list.
1132 : * @param __first An input iterator.
1133 : * @param __last An input iterator.
1134 : *
1135 : * This function will insert copies of the data in the range [@a
1136 : * first,@a last) into the %list before the location specified by
1137 : * @a position.
1138 : *
1139 : * This operation is linear in the number of elements inserted and
1140 : * does not invalidate iterators and references.
1141 : */
1142 : #if __cplusplus >= 201103L
1143 : template<typename _InputIterator,
1144 : typename = std::_RequireInputIter<_InputIterator>>
1145 : #else
1146 : template<typename _InputIterator>
1147 : #endif
1148 : void
1149 : insert(iterator __position, _InputIterator __first,
1150 : _InputIterator __last)
1151 : {
1152 : list __tmp(__first, __last, get_allocator());
1153 : splice(__position, __tmp);
1154 : }
1155 :
1156 : /**
1157 : * @brief Remove element at given position.
1158 : * @param __position Iterator pointing to element to be erased.
1159 : * @return An iterator pointing to the next element (or end()).
1160 : *
1161 : * This function will erase the element at the given position and thus
1162 : * shorten the %list by one.
1163 : *
1164 : * Due to the nature of a %list this operation can be done in
1165 : * constant time, and only invalidates iterators/references to
1166 : * the element being removed. The user is also cautioned that
1167 : * this function only erases the element, and that if the element
1168 : * is itself a pointer, the pointed-to memory is not touched in
1169 : * any way. Managing the pointer is the user's responsibility.
1170 : */
1171 : iterator
1172 : erase(iterator __position);
1173 :
1174 : /**
1175 : * @brief Remove a range of elements.
1176 : * @param __first Iterator pointing to the first element to be erased.
1177 : * @param __last Iterator pointing to one past the last element to be
1178 : * erased.
1179 : * @return An iterator pointing to the element pointed to by @a last
1180 : * prior to erasing (or end()).
1181 : *
1182 : * This function will erase the elements in the range @a
1183 : * [first,last) and shorten the %list accordingly.
1184 : *
1185 : * This operation is linear time in the size of the range and only
1186 : * invalidates iterators/references to the element being removed.
1187 : * The user is also cautioned that this function only erases the
1188 : * elements, and that if the elements themselves are pointers, the
1189 : * pointed-to memory is not touched in any way. Managing the pointer
1190 : * is the user's responsibility.
1191 : */
1192 : iterator
1193 : erase(iterator __first, iterator __last)
1194 : {
1195 : while (__first != __last)
1196 : __first = erase(__first);
1197 : return __last;
1198 : }
1199 :
1200 : /**
1201 : * @brief Swaps data with another %list.
1202 : * @param __x A %list of the same element and allocator types.
1203 : *
1204 : * This exchanges the elements between two lists in constant
1205 : * time. Note that the global std::swap() function is
1206 : * specialized such that std::swap(l1,l2) will feed to this
1207 : * function.
1208 : */
1209 : void
1210 0 : swap(list& __x)
1211 : {
1212 0 : __detail::_List_node_base::swap(this->_M_impl._M_node,
1213 0 : __x._M_impl._M_node);
1214 :
1215 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1216 : // 431. Swapping containers with unequal allocators.
1217 0 : std::__alloc_swap<typename _Base::_Node_alloc_type>::
1218 0 : _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator());
1219 0 : }
1220 :
1221 : /**
1222 : * Erases all the elements. Note that this function only erases
1223 : * the elements, and that if the elements themselves are
1224 : * pointers, the pointed-to memory is not touched in any way.
1225 : * Managing the pointer is the user's responsibility.
1226 : */
1227 : void
1228 : clear() _GLIBCXX_NOEXCEPT
1229 : {
1230 : _Base::_M_clear();
1231 : _Base::_M_init();
1232 : }
1233 :
1234 : // [23.2.2.4] list operations
1235 : /**
1236 : * @brief Insert contents of another %list.
1237 : * @param __position Iterator referencing the element to insert before.
1238 : * @param __x Source list.
1239 : *
1240 : * The elements of @a __x are inserted in constant time in front of
1241 : * the element referenced by @a __position. @a __x becomes an empty
1242 : * list.
1243 : *
1244 : * Requires this != @a __x.
1245 : */
1246 : void
1247 : #if __cplusplus >= 201103L
1248 : splice(iterator __position, list&& __x)
1249 : #else
1250 : splice(iterator __position, list& __x)
1251 : #endif
1252 : {
1253 : if (!__x.empty())
1254 : {
1255 : _M_check_equal_allocators(__x);
1256 :
1257 : this->_M_transfer(__position, __x.begin(), __x.end());
1258 : }
1259 : }
1260 :
1261 : #if __cplusplus >= 201103L
1262 : void
1263 : splice(iterator __position, list& __x)
1264 : { splice(__position, std::move(__x)); }
1265 : #endif
1266 :
1267 : /**
1268 : * @brief Insert element from another %list.
1269 : * @param __position Iterator referencing the element to insert before.
1270 : * @param __x Source list.
1271 : * @param __i Iterator referencing the element to move.
1272 : *
1273 : * Removes the element in list @a __x referenced by @a __i and
1274 : * inserts it into the current list before @a __position.
1275 : */
1276 : void
1277 : #if __cplusplus >= 201103L
1278 : splice(iterator __position, list&& __x, iterator __i)
1279 : #else
1280 : splice(iterator __position, list& __x, iterator __i)
1281 : #endif
1282 : {
1283 : iterator __j = __i;
1284 : ++__j;
1285 : if (__position == __i || __position == __j)
1286 : return;
1287 :
1288 : if (this != &__x)
1289 : _M_check_equal_allocators(__x);
1290 :
1291 : this->_M_transfer(__position, __i, __j);
1292 : }
1293 :
1294 : #if __cplusplus >= 201103L
1295 : void
1296 : splice(iterator __position, list& __x, iterator __i)
1297 : { splice(__position, std::move(__x), __i); }
1298 : #endif
1299 :
1300 : /**
1301 : * @brief Insert range from another %list.
1302 : * @param __position Iterator referencing the element to insert before.
1303 : * @param __x Source list.
1304 : * @param __first Iterator referencing the start of range in x.
1305 : * @param __last Iterator referencing the end of range in x.
1306 : *
1307 : * Removes elements in the range [__first,__last) and inserts them
1308 : * before @a __position in constant time.
1309 : *
1310 : * Undefined if @a __position is in [__first,__last).
1311 : */
1312 : void
1313 : #if __cplusplus >= 201103L
1314 : splice(iterator __position, list&& __x, iterator __first,
1315 : iterator __last)
1316 : #else
1317 : splice(iterator __position, list& __x, iterator __first,
1318 : iterator __last)
1319 : #endif
1320 : {
1321 : if (__first != __last)
1322 : {
1323 : if (this != &__x)
1324 : _M_check_equal_allocators(__x);
1325 :
1326 : this->_M_transfer(__position, __first, __last);
1327 : }
1328 : }
1329 :
1330 : #if __cplusplus >= 201103L
1331 : void
1332 : splice(iterator __position, list& __x, iterator __first, iterator __last)
1333 : { splice(__position, std::move(__x), __first, __last); }
1334 : #endif
1335 :
1336 : /**
1337 : * @brief Remove all elements equal to value.
1338 : * @param __value The value to remove.
1339 : *
1340 : * Removes every element in the list equal to @a value.
1341 : * Remaining elements stay in list order. Note that this
1342 : * function only erases the elements, and that if the elements
1343 : * themselves are pointers, the pointed-to memory is not
1344 : * touched in any way. Managing the pointer is the user's
1345 : * responsibility.
1346 : */
1347 : void
1348 : remove(const _Tp& __value);
1349 :
1350 : /**
1351 : * @brief Remove all elements satisfying a predicate.
1352 : * @tparam _Predicate Unary predicate function or object.
1353 : *
1354 : * Removes every element in the list for which the predicate
1355 : * returns true. Remaining elements stay in list order. Note
1356 : * that this function only erases the elements, and that if the
1357 : * elements themselves are pointers, the pointed-to memory is
1358 : * not touched in any way. Managing the pointer is the user's
1359 : * responsibility.
1360 : */
1361 : template<typename _Predicate>
1362 : void
1363 : remove_if(_Predicate);
1364 :
1365 : /**
1366 : * @brief Remove consecutive duplicate elements.
1367 : *
1368 : * For each consecutive set of elements with the same value,
1369 : * remove all but the first one. Remaining elements stay in
1370 : * list order. Note that this function only erases the
1371 : * elements, and that if the elements themselves are pointers,
1372 : * the pointed-to memory is not touched in any way. Managing
1373 : * the pointer is the user's responsibility.
1374 : */
1375 : void
1376 : unique();
1377 :
1378 : /**
1379 : * @brief Remove consecutive elements satisfying a predicate.
1380 : * @tparam _BinaryPredicate Binary predicate function or object.
1381 : *
1382 : * For each consecutive set of elements [first,last) that
1383 : * satisfy predicate(first,i) where i is an iterator in
1384 : * [first,last), remove all but the first one. Remaining
1385 : * elements stay in list order. Note that this function only
1386 : * erases the elements, and that if the elements themselves are
1387 : * pointers, the pointed-to memory is not touched in any way.
1388 : * Managing the pointer is the user's responsibility.
1389 : */
1390 : template<typename _BinaryPredicate>
1391 : void
1392 : unique(_BinaryPredicate);
1393 :
1394 : /**
1395 : * @brief Merge sorted lists.
1396 : * @param __x Sorted list to merge.
1397 : *
1398 : * Assumes that both @a __x and this list are sorted according to
1399 : * operator<(). Merges elements of @a __x into this list in
1400 : * sorted order, leaving @a __x empty when complete. Elements in
1401 : * this list precede elements in @a __x that are equal.
1402 : */
1403 : #if __cplusplus >= 201103L
1404 : void
1405 : merge(list&& __x);
1406 :
1407 : void
1408 : merge(list& __x)
1409 : { merge(std::move(__x)); }
1410 : #else
1411 : void
1412 : merge(list& __x);
1413 : #endif
1414 :
1415 : /**
1416 : * @brief Merge sorted lists according to comparison function.
1417 : * @tparam _StrictWeakOrdering Comparison function defining
1418 : * sort order.
1419 : * @param __x Sorted list to merge.
1420 : * @param __comp Comparison functor.
1421 : *
1422 : * Assumes that both @a __x and this list are sorted according to
1423 : * StrictWeakOrdering. Merges elements of @a __x into this list
1424 : * in sorted order, leaving @a __x empty when complete. Elements
1425 : * in this list precede elements in @a __x that are equivalent
1426 : * according to StrictWeakOrdering().
1427 : */
1428 : #if __cplusplus >= 201103L
1429 : template<typename _StrictWeakOrdering>
1430 : void
1431 : merge(list&& __x, _StrictWeakOrdering __comp);
1432 :
1433 : template<typename _StrictWeakOrdering>
1434 : void
1435 : merge(list& __x, _StrictWeakOrdering __comp)
1436 : { merge(std::move(__x), __comp); }
1437 : #else
1438 : template<typename _StrictWeakOrdering>
1439 : void
1440 : merge(list& __x, _StrictWeakOrdering __comp);
1441 : #endif
1442 :
1443 : /**
1444 : * @brief Reverse the elements in list.
1445 : *
1446 : * Reverse the order of elements in the list in linear time.
1447 : */
1448 : void
1449 : reverse() _GLIBCXX_NOEXCEPT
1450 : { this->_M_impl._M_node._M_reverse(); }
1451 :
1452 : /**
1453 : * @brief Sort the elements.
1454 : *
1455 : * Sorts the elements of this list in NlogN time. Equivalent
1456 : * elements remain in list order.
1457 : */
1458 : void
1459 : sort();
1460 :
1461 : /**
1462 : * @brief Sort the elements according to comparison function.
1463 : *
1464 : * Sorts the elements of this list in NlogN time. Equivalent
1465 : * elements remain in list order.
1466 : */
1467 : template<typename _StrictWeakOrdering>
1468 : void
1469 : sort(_StrictWeakOrdering);
1470 :
1471 : protected:
1472 : // Internal constructor functions follow.
1473 :
1474 : // Called by the range constructor to implement [23.1.1]/9
1475 :
1476 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1477 : // 438. Ambiguity in the "do the right thing" clause
1478 : template<typename _Integer>
1479 : void
1480 : _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1481 : { _M_fill_initialize(static_cast<size_type>(__n), __x); }
1482 :
1483 : // Called by the range constructor to implement [23.1.1]/9
1484 : template<typename _InputIterator>
1485 : void
1486 182 : _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1487 : __false_type)
1488 : {
1489 436 : for (; __first != __last; ++__first)
1490 : #if __cplusplus >= 201103L
1491 254 : emplace_back(*__first);
1492 : #else
1493 : push_back(*__first);
1494 : #endif
1495 182 : }
1496 :
1497 : // Called by list(n,v,a), and the range constructor when it turns out
1498 : // to be the same thing.
1499 : void
1500 : _M_fill_initialize(size_type __n, const value_type& __x)
1501 : {
1502 : for (; __n; --__n)
1503 : push_back(__x);
1504 : }
1505 :
1506 : #if __cplusplus >= 201103L
1507 : // Called by list(n).
1508 : void
1509 : _M_default_initialize(size_type __n)
1510 : {
1511 : for (; __n; --__n)
1512 : emplace_back();
1513 : }
1514 :
1515 : // Called by resize(sz).
1516 : void
1517 : _M_default_append(size_type __n);
1518 : #endif
1519 :
1520 : // Internal assign functions follow.
1521 :
1522 : // Called by the range assign to implement [23.1.1]/9
1523 :
1524 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1525 : // 438. Ambiguity in the "do the right thing" clause
1526 : template<typename _Integer>
1527 : void
1528 : _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1529 : { _M_fill_assign(__n, __val); }
1530 :
1531 : // Called by the range assign to implement [23.1.1]/9
1532 : template<typename _InputIterator>
1533 : void
1534 : _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1535 : __false_type);
1536 :
1537 : // Called by assign(n,t), and the range assign when it turns out
1538 : // to be the same thing.
1539 : void
1540 : _M_fill_assign(size_type __n, const value_type& __val);
1541 :
1542 :
1543 : // Moves the elements from [first,last) before position.
1544 : void
1545 : _M_transfer(iterator __position, iterator __first, iterator __last)
1546 : { __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
1547 :
1548 : // Inserts new element at position given and with value given.
1549 : #if __cplusplus < 201103L
1550 : void
1551 : _M_insert(iterator __position, const value_type& __x)
1552 : {
1553 : _Node* __tmp = _M_create_node(__x);
1554 : __tmp->_M_hook(__position._M_node);
1555 : }
1556 : #else
1557 : template<typename... _Args>
1558 : void
1559 281022 : _M_insert(iterator __position, _Args&&... __args)
1560 : {
1561 281022 : _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
1562 281074 : __tmp->_M_hook(__position._M_node);
1563 281064 : }
1564 : #endif
1565 :
1566 : // Erases element at position given.
1567 : void
1568 270990 : _M_erase(iterator __position)
1569 : {
1570 270990 : __position._M_node->_M_unhook();
1571 270989 : _Node* __n = static_cast<_Node*>(__position._M_node);
1572 : #if __cplusplus >= 201103L
1573 270989 : _M_get_Node_allocator().destroy(__n);
1574 : #else
1575 : _M_get_Tp_allocator().destroy(std::__addressof(__n->_M_data));
1576 : #endif
1577 270995 : _M_put_node(__n);
1578 270999 : }
1579 :
1580 : // To implement the splice (and merge) bits of N1599.
1581 : void
1582 : _M_check_equal_allocators(list& __x)
1583 : {
1584 : if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
1585 : _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
1586 : __throw_runtime_error(__N("list::_M_check_equal_allocators"));
1587 : }
1588 : };
1589 :
1590 : /**
1591 : * @brief List equality comparison.
1592 : * @param __x A %list.
1593 : * @param __y A %list of the same type as @a __x.
1594 : * @return True iff the size and elements of the lists are equal.
1595 : *
1596 : * This is an equivalence relation. It is linear in the size of
1597 : * the lists. Lists are considered equivalent if their sizes are
1598 : * equal, and if corresponding elements compare equal.
1599 : */
1600 : template<typename _Tp, typename _Alloc>
1601 : inline bool
1602 : operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1603 : {
1604 : typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
1605 : const_iterator __end1 = __x.end();
1606 : const_iterator __end2 = __y.end();
1607 :
1608 : const_iterator __i1 = __x.begin();
1609 : const_iterator __i2 = __y.begin();
1610 : while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
1611 : {
1612 : ++__i1;
1613 : ++__i2;
1614 : }
1615 : return __i1 == __end1 && __i2 == __end2;
1616 : }
1617 :
1618 : /**
1619 : * @brief List ordering relation.
1620 : * @param __x A %list.
1621 : * @param __y A %list of the same type as @a __x.
1622 : * @return True iff @a __x is lexicographically less than @a __y.
1623 : *
1624 : * This is a total ordering relation. It is linear in the size of the
1625 : * lists. The elements must be comparable with @c <.
1626 : *
1627 : * See std::lexicographical_compare() for how the determination is made.
1628 : */
1629 : template<typename _Tp, typename _Alloc>
1630 : inline bool
1631 : operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1632 : { return std::lexicographical_compare(__x.begin(), __x.end(),
1633 : __y.begin(), __y.end()); }
1634 :
1635 : /// Based on operator==
1636 : template<typename _Tp, typename _Alloc>
1637 : inline bool
1638 : operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1639 : { return !(__x == __y); }
1640 :
1641 : /// Based on operator<
1642 : template<typename _Tp, typename _Alloc>
1643 : inline bool
1644 : operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1645 : { return __y < __x; }
1646 :
1647 : /// Based on operator<
1648 : template<typename _Tp, typename _Alloc>
1649 : inline bool
1650 : operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1651 : { return !(__y < __x); }
1652 :
1653 : /// Based on operator<
1654 : template<typename _Tp, typename _Alloc>
1655 : inline bool
1656 : operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1657 : { return !(__x < __y); }
1658 :
1659 : /// See std::list::swap().
1660 : template<typename _Tp, typename _Alloc>
1661 : inline void
1662 : swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
1663 : { __x.swap(__y); }
1664 :
1665 : _GLIBCXX_END_NAMESPACE_CONTAINER
1666 : } // namespace std
1667 :
1668 : #endif /* _STL_LIST_H */
|
