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