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