libstdc++
slist
Go to the documentation of this file.
1 // Singly-linked list implementation -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2004, 2005, 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  * Copyright (c) 1997
28  * Silicon Graphics Computer Systems, Inc.
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. Silicon Graphics 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 
40 /** @file ext/slist
41  * This file is a GNU extension to the Standard C++ Library (possibly
42  * containing extensions from the HP/SGI STL subset).
43  */
44 
45 #ifndef _SLIST
46 #define _SLIST 1
47 
48 #include <algorithm>
49 #include <bits/allocator.h>
50 #include <bits/stl_construct.h>
51 #include <bits/stl_uninitialized.h>
52 #include <bits/concept_check.h>
53 
54 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
55 {
56 _GLIBCXX_BEGIN_NAMESPACE_VERSION
57 
58  using std::size_t;
59  using std::ptrdiff_t;
60  using std::_Construct;
61  using std::_Destroy;
62  using std::allocator;
63  using std::__true_type;
64  using std::__false_type;
65 
66  struct _Slist_node_base
67  {
68  _Slist_node_base* _M_next;
69  };
70 
71  inline _Slist_node_base*
72  __slist_make_link(_Slist_node_base* __prev_node,
73  _Slist_node_base* __new_node)
74  {
75  __new_node->_M_next = __prev_node->_M_next;
76  __prev_node->_M_next = __new_node;
77  return __new_node;
78  }
79 
80  inline _Slist_node_base*
81  __slist_previous(_Slist_node_base* __head,
82  const _Slist_node_base* __node)
83  {
84  while (__head && __head->_M_next != __node)
85  __head = __head->_M_next;
86  return __head;
87  }
88 
89  inline const _Slist_node_base*
90  __slist_previous(const _Slist_node_base* __head,
91  const _Slist_node_base* __node)
92  {
93  while (__head && __head->_M_next != __node)
94  __head = __head->_M_next;
95  return __head;
96  }
97 
98  inline void
99  __slist_splice_after(_Slist_node_base* __pos,
100  _Slist_node_base* __before_first,
101  _Slist_node_base* __before_last)
102  {
103  if (__pos != __before_first && __pos != __before_last)
104  {
105  _Slist_node_base* __first = __before_first->_M_next;
106  _Slist_node_base* __after = __pos->_M_next;
107  __before_first->_M_next = __before_last->_M_next;
108  __pos->_M_next = __first;
109  __before_last->_M_next = __after;
110  }
111  }
112 
113  inline void
114  __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head)
115  {
116  _Slist_node_base* __before_last = __slist_previous(__head, 0);
117  if (__before_last != __head)
118  {
119  _Slist_node_base* __after = __pos->_M_next;
120  __pos->_M_next = __head->_M_next;
121  __head->_M_next = 0;
122  __before_last->_M_next = __after;
123  }
124  }
125 
126  inline _Slist_node_base*
127  __slist_reverse(_Slist_node_base* __node)
128  {
129  _Slist_node_base* __result = __node;
130  __node = __node->_M_next;
131  __result->_M_next = 0;
132  while(__node)
133  {
134  _Slist_node_base* __next = __node->_M_next;
135  __node->_M_next = __result;
136  __result = __node;
137  __node = __next;
138  }
139  return __result;
140  }
141 
142  inline size_t
143  __slist_size(_Slist_node_base* __node)
144  {
145  size_t __result = 0;
146  for (; __node != 0; __node = __node->_M_next)
147  ++__result;
148  return __result;
149  }
150 
151  template <class _Tp>
152  struct _Slist_node : public _Slist_node_base
153  {
154  _Tp _M_data;
155  };
156 
157  struct _Slist_iterator_base
158  {
159  typedef size_t size_type;
160  typedef ptrdiff_t difference_type;
161  typedef std::forward_iterator_tag iterator_category;
162 
163  _Slist_node_base* _M_node;
164 
165  _Slist_iterator_base(_Slist_node_base* __x)
166  : _M_node(__x) {}
167 
168  void
169  _M_incr()
170  { _M_node = _M_node->_M_next; }
171 
172  bool
173  operator==(const _Slist_iterator_base& __x) const
174  { return _M_node == __x._M_node; }
175 
176  bool
177  operator!=(const _Slist_iterator_base& __x) const
178  { return _M_node != __x._M_node; }
179  };
180 
181  template <class _Tp, class _Ref, class _Ptr>
182  struct _Slist_iterator : public _Slist_iterator_base
183  {
184  typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator;
185  typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
186  typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self;
187 
188  typedef _Tp value_type;
189  typedef _Ptr pointer;
190  typedef _Ref reference;
191  typedef _Slist_node<_Tp> _Node;
192 
193  explicit
194  _Slist_iterator(_Node* __x)
195  : _Slist_iterator_base(__x) {}
196 
197  _Slist_iterator()
198  : _Slist_iterator_base(0) {}
199 
200  _Slist_iterator(const iterator& __x)
201  : _Slist_iterator_base(__x._M_node) {}
202 
203  reference
204  operator*() const
205  { return ((_Node*) _M_node)->_M_data; }
206 
207  pointer
208  operator->() const
209  { return &(operator*()); }
210 
211  _Self&
212  operator++()
213  {
214  _M_incr();
215  return *this;
216  }
217 
218  _Self
219  operator++(int)
220  {
221  _Self __tmp = *this;
222  _M_incr();
223  return __tmp;
224  }
225  };
226 
227  template <class _Tp, class _Alloc>
228  struct _Slist_base
229  : public _Alloc::template rebind<_Slist_node<_Tp> >::other
230  {
231  typedef typename _Alloc::template rebind<_Slist_node<_Tp> >::other
232  _Node_alloc;
233  typedef _Alloc allocator_type;
234 
235  allocator_type
236  get_allocator() const
237  { return *static_cast<const _Node_alloc*>(this); }
238 
239  _Slist_base(const allocator_type& __a)
240  : _Node_alloc(__a)
241  { this->_M_head._M_next = 0; }
242 
243  ~_Slist_base()
244  { _M_erase_after(&this->_M_head, 0); }
245 
246  protected:
247  _Slist_node_base _M_head;
248 
249  _Slist_node<_Tp>*
250  _M_get_node()
251  { return _Node_alloc::allocate(1); }
252 
253  void
254  _M_put_node(_Slist_node<_Tp>* __p)
255  { _Node_alloc::deallocate(__p, 1); }
256 
257  protected:
258  _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
259  {
260  _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
261  _Slist_node_base* __next_next = __next->_M_next;
262  __pos->_M_next = __next_next;
263  get_allocator().destroy(&__next->_M_data);
264  _M_put_node(__next);
265  return __next_next;
266  }
267  _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
268  };
269 
270  template <class _Tp, class _Alloc>
271  _Slist_node_base*
272  _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
273  _Slist_node_base* __last_node)
274  {
275  _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
276  while (__cur != __last_node)
277  {
278  _Slist_node<_Tp>* __tmp = __cur;
279  __cur = (_Slist_node<_Tp>*) __cur->_M_next;
280  get_allocator().destroy(&__tmp->_M_data);
281  _M_put_node(__tmp);
282  }
283  __before_first->_M_next = __last_node;
284  return __last_node;
285  }
286 
287  /**
288  * This is an SGI extension.
289  * @ingroup SGIextensions
290  * @doctodo
291  */
292  template <class _Tp, class _Alloc = allocator<_Tp> >
293  class slist : private _Slist_base<_Tp,_Alloc>
294  {
295  // concept requirements
296  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
297 
298  private:
299  typedef _Slist_base<_Tp,_Alloc> _Base;
300 
301  public:
302  typedef _Tp value_type;
303  typedef value_type* pointer;
304  typedef const value_type* const_pointer;
305  typedef value_type& reference;
306  typedef const value_type& const_reference;
307  typedef size_t size_type;
308  typedef ptrdiff_t difference_type;
309 
310  typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator;
311  typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
312 
313  typedef typename _Base::allocator_type allocator_type;
314 
315  allocator_type
316  get_allocator() const
317  { return _Base::get_allocator(); }
318 
319  private:
320  typedef _Slist_node<_Tp> _Node;
321  typedef _Slist_node_base _Node_base;
322  typedef _Slist_iterator_base _Iterator_base;
323 
324  _Node*
325  _M_create_node(const value_type& __x)
326  {
327  _Node* __node = this->_M_get_node();
328  __try
329  {
330  get_allocator().construct(&__node->_M_data, __x);
331  __node->_M_next = 0;
332  }
333  __catch(...)
334  {
335  this->_M_put_node(__node);
336  __throw_exception_again;
337  }
338  return __node;
339  }
340 
341  _Node*
342  _M_create_node()
343  {
344  _Node* __node = this->_M_get_node();
345  __try
346  {
347  get_allocator().construct(&__node->_M_data, value_type());
348  __node->_M_next = 0;
349  }
350  __catch(...)
351  {
352  this->_M_put_node(__node);
353  __throw_exception_again;
354  }
355  return __node;
356  }
357 
358  public:
359  explicit
360  slist(const allocator_type& __a = allocator_type())
361  : _Base(__a) {}
362 
363  slist(size_type __n, const value_type& __x,
364  const allocator_type& __a = allocator_type())
365  : _Base(__a)
366  { _M_insert_after_fill(&this->_M_head, __n, __x); }
367 
368  explicit
369  slist(size_type __n)
370  : _Base(allocator_type())
371  { _M_insert_after_fill(&this->_M_head, __n, value_type()); }
372 
373  // We don't need any dispatching tricks here, because
374  // _M_insert_after_range already does them.
375  template <class _InputIterator>
376  slist(_InputIterator __first, _InputIterator __last,
377  const allocator_type& __a = allocator_type())
378  : _Base(__a)
379  { _M_insert_after_range(&this->_M_head, __first, __last); }
380 
381  slist(const slist& __x)
382  : _Base(__x.get_allocator())
383  { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }
384 
385  slist&
386  operator= (const slist& __x);
387 
388  ~slist() {}
389 
390  public:
391  // assign(), a generalized assignment member function. Two
392  // versions: one that takes a count, and one that takes a range.
393  // The range version is a member template, so we dispatch on whether
394  // or not the type is an integer.
395 
396  void
397  assign(size_type __n, const _Tp& __val)
398  { _M_fill_assign(__n, __val); }
399 
400  void
401  _M_fill_assign(size_type __n, const _Tp& __val);
402 
403  template <class _InputIterator>
404  void
405  assign(_InputIterator __first, _InputIterator __last)
406  {
407  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
408  _M_assign_dispatch(__first, __last, _Integral());
409  }
410 
411  template <class _Integer>
412  void
413  _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
414  { _M_fill_assign((size_type) __n, (_Tp) __val); }
415 
416  template <class _InputIterator>
417  void
418  _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
419  __false_type);
420 
421  public:
422 
423  iterator
424  begin()
425  { return iterator((_Node*)this->_M_head._M_next); }
426 
427  const_iterator
428  begin() const
429  { return const_iterator((_Node*)this->_M_head._M_next);}
430 
431  iterator
432  end()
433  { return iterator(0); }
434 
435  const_iterator
436  end() const
437  { return const_iterator(0); }
438 
439  // Experimental new feature: before_begin() returns a
440  // non-dereferenceable iterator that, when incremented, yields
441  // begin(). This iterator may be used as the argument to
442  // insert_after, erase_after, etc. Note that even for an empty
443  // slist, before_begin() is not the same iterator as end(). It
444  // is always necessary to increment before_begin() at least once to
445  // obtain end().
446  iterator
447  before_begin()
448  { return iterator((_Node*) &this->_M_head); }
449 
450  const_iterator
451  before_begin() const
452  { return const_iterator((_Node*) &this->_M_head); }
453 
454  size_type
455  size() const
456  { return __slist_size(this->_M_head._M_next); }
457 
458  size_type
459  max_size() const
460  { return size_type(-1); }
461 
462  bool
463  empty() const
464  { return this->_M_head._M_next == 0; }
465 
466  void
467  swap(slist& __x)
468  { std::swap(this->_M_head._M_next, __x._M_head._M_next); }
469 
470  public:
471 
472  reference
473  front()
474  { return ((_Node*) this->_M_head._M_next)->_M_data; }
475 
476  const_reference
477  front() const
478  { return ((_Node*) this->_M_head._M_next)->_M_data; }
479 
480  void
481  push_front(const value_type& __x)
482  { __slist_make_link(&this->_M_head, _M_create_node(__x)); }
483 
484  void
485  push_front()
486  { __slist_make_link(&this->_M_head, _M_create_node()); }
487 
488  void
489  pop_front()
490  {
491  _Node* __node = (_Node*) this->_M_head._M_next;
492  this->_M_head._M_next = __node->_M_next;
493  get_allocator().destroy(&__node->_M_data);
494  this->_M_put_node(__node);
495  }
496 
497  iterator
498  previous(const_iterator __pos)
499  { return iterator((_Node*) __slist_previous(&this->_M_head,
500  __pos._M_node)); }
501 
502  const_iterator
503  previous(const_iterator __pos) const
504  { return const_iterator((_Node*) __slist_previous(&this->_M_head,
505  __pos._M_node)); }
506 
507  private:
508  _Node*
509  _M_insert_after(_Node_base* __pos, const value_type& __x)
510  { return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); }
511 
512  _Node*
513  _M_insert_after(_Node_base* __pos)
514  { return (_Node*) (__slist_make_link(__pos, _M_create_node())); }
515 
516  void
517  _M_insert_after_fill(_Node_base* __pos,
518  size_type __n, const value_type& __x)
519  {
520  for (size_type __i = 0; __i < __n; ++__i)
521  __pos = __slist_make_link(__pos, _M_create_node(__x));
522  }
523 
524  // Check whether it's an integral type. If so, it's not an iterator.
525  template <class _InIterator>
526  void
527  _M_insert_after_range(_Node_base* __pos,
528  _InIterator __first, _InIterator __last)
529  {
530  typedef typename std::__is_integer<_InIterator>::__type _Integral;
531  _M_insert_after_range(__pos, __first, __last, _Integral());
532  }
533 
534  template <class _Integer>
535  void
536  _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
537  __true_type)
538  { _M_insert_after_fill(__pos, __n, __x); }
539 
540  template <class _InIterator>
541  void
542  _M_insert_after_range(_Node_base* __pos,
543  _InIterator __first, _InIterator __last,
544  __false_type)
545  {
546  while (__first != __last)
547  {
548  __pos = __slist_make_link(__pos, _M_create_node(*__first));
549  ++__first;
550  }
551  }
552 
553  public:
554  iterator
555  insert_after(iterator __pos, const value_type& __x)
556  { return iterator(_M_insert_after(__pos._M_node, __x)); }
557 
558  iterator
559  insert_after(iterator __pos)
560  { return insert_after(__pos, value_type()); }
561 
562  void
563  insert_after(iterator __pos, size_type __n, const value_type& __x)
564  { _M_insert_after_fill(__pos._M_node, __n, __x); }
565 
566  // We don't need any dispatching tricks here, because
567  // _M_insert_after_range already does them.
568  template <class _InIterator>
569  void
570  insert_after(iterator __pos, _InIterator __first, _InIterator __last)
571  { _M_insert_after_range(__pos._M_node, __first, __last); }
572 
573  iterator
574  insert(iterator __pos, const value_type& __x)
575  { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
576  __pos._M_node),
577  __x)); }
578 
579  iterator
580  insert(iterator __pos)
581  { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
582  __pos._M_node),
583  value_type())); }
584 
585  void
586  insert(iterator __pos, size_type __n, const value_type& __x)
587  { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),
588  __n, __x); }
589 
590  // We don't need any dispatching tricks here, because
591  // _M_insert_after_range already does them.
592  template <class _InIterator>
593  void
594  insert(iterator __pos, _InIterator __first, _InIterator __last)
595  { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node),
596  __first, __last); }
597 
598  public:
599  iterator
600  erase_after(iterator __pos)
601  { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); }
602 
603  iterator
604  erase_after(iterator __before_first, iterator __last)
605  {
606  return iterator((_Node*) this->_M_erase_after(__before_first._M_node,
607  __last._M_node));
608  }
609 
610  iterator
611  erase(iterator __pos)
612  {
613  return iterator((_Node*) this->_M_erase_after
614  (__slist_previous(&this->_M_head, __pos._M_node)));
615  }
616 
617  iterator
618  erase(iterator __first, iterator __last)
619  {
620  return iterator((_Node*) this->_M_erase_after
621  (__slist_previous(&this->_M_head, __first._M_node),
622  __last._M_node));
623  }
624 
625  void
626  resize(size_type new_size, const _Tp& __x);
627 
628  void
629  resize(size_type new_size)
630  { resize(new_size, _Tp()); }
631 
632  void
633  clear()
634  { this->_M_erase_after(&this->_M_head, 0); }
635 
636  public:
637  // Moves the range [__before_first + 1, __before_last + 1) to *this,
638  // inserting it immediately after __pos. This is constant time.
639  void
640  splice_after(iterator __pos,
641  iterator __before_first, iterator __before_last)
642  {
643  if (__before_first != __before_last)
644  __slist_splice_after(__pos._M_node, __before_first._M_node,
645  __before_last._M_node);
646  }
647 
648  // Moves the element that follows __prev to *this, inserting it
649  // immediately after __pos. This is constant time.
650  void
651  splice_after(iterator __pos, iterator __prev)
652  { __slist_splice_after(__pos._M_node,
653  __prev._M_node, __prev._M_node->_M_next); }
654 
655  // Removes all of the elements from the list __x to *this, inserting
656  // them immediately after __pos. __x must not be *this. Complexity:
657  // linear in __x.size().
658  void
659  splice_after(iterator __pos, slist& __x)
660  { __slist_splice_after(__pos._M_node, &__x._M_head); }
661 
662  // Linear in distance(begin(), __pos), and linear in __x.size().
663  void
664  splice(iterator __pos, slist& __x)
665  {
666  if (__x._M_head._M_next)
667  __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
668  &__x._M_head,
669  __slist_previous(&__x._M_head, 0)); }
670 
671  // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
672  void
673  splice(iterator __pos, slist& __x, iterator __i)
674  { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
675  __slist_previous(&__x._M_head, __i._M_node),
676  __i._M_node); }
677 
678  // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
679  // and in distance(__first, __last).
680  void
681  splice(iterator __pos, slist& __x, iterator __first, iterator __last)
682  {
683  if (__first != __last)
684  __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
685  __slist_previous(&__x._M_head, __first._M_node),
686  __slist_previous(__first._M_node,
687  __last._M_node));
688  }
689 
690  public:
691  void
692  reverse()
693  {
694  if (this->_M_head._M_next)
695  this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);
696  }
697 
698  void
699  remove(const _Tp& __val);
700 
701  void
702  unique();
703 
704  void
705  merge(slist& __x);
706 
707  void
708  sort();
709 
710  template <class _Predicate>
711  void
712  remove_if(_Predicate __pred);
713 
714  template <class _BinaryPredicate>
715  void
716  unique(_BinaryPredicate __pred);
717 
718  template <class _StrictWeakOrdering>
719  void
720  merge(slist&, _StrictWeakOrdering);
721 
722  template <class _StrictWeakOrdering>
723  void
724  sort(_StrictWeakOrdering __comp);
725  };
726 
727  template <class _Tp, class _Alloc>
730  {
731  if (&__x != this)
732  {
733  _Node_base* __p1 = &this->_M_head;
734  _Node* __n1 = (_Node*) this->_M_head._M_next;
735  const _Node* __n2 = (const _Node*) __x._M_head._M_next;
736  while (__n1 && __n2)
737  {
738  __n1->_M_data = __n2->_M_data;
739  __p1 = __n1;
740  __n1 = (_Node*) __n1->_M_next;
741  __n2 = (const _Node*) __n2->_M_next;
742  }
743  if (__n2 == 0)
744  this->_M_erase_after(__p1, 0);
745  else
746  _M_insert_after_range(__p1, const_iterator((_Node*)__n2),
747  const_iterator(0));
748  }
749  return *this;
750  }
751 
752  template <class _Tp, class _Alloc>
753  void
754  slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val)
755  {
756  _Node_base* __prev = &this->_M_head;
757  _Node* __node = (_Node*) this->_M_head._M_next;
758  for (; __node != 0 && __n > 0; --__n)
759  {
760  __node->_M_data = __val;
761  __prev = __node;
762  __node = (_Node*) __node->_M_next;
763  }
764  if (__n > 0)
765  _M_insert_after_fill(__prev, __n, __val);
766  else
767  this->_M_erase_after(__prev, 0);
768  }
769 
770  template <class _Tp, class _Alloc>
771  template <class _InputIterator>
772  void
773  slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first,
774  _InputIterator __last,
775  __false_type)
776  {
777  _Node_base* __prev = &this->_M_head;
778  _Node* __node = (_Node*) this->_M_head._M_next;
779  while (__node != 0 && __first != __last)
780  {
781  __node->_M_data = *__first;
782  __prev = __node;
783  __node = (_Node*) __node->_M_next;
784  ++__first;
785  }
786  if (__first != __last)
787  _M_insert_after_range(__prev, __first, __last);
788  else
789  this->_M_erase_after(__prev, 0);
790  }
791 
792  template <class _Tp, class _Alloc>
793  inline bool
794  operator==(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
795  {
796  typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
797  const_iterator __end1 = _SL1.end();
798  const_iterator __end2 = _SL2.end();
799 
800  const_iterator __i1 = _SL1.begin();
801  const_iterator __i2 = _SL2.begin();
802  while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
803  {
804  ++__i1;
805  ++__i2;
806  }
807  return __i1 == __end1 && __i2 == __end2;
808  }
809 
810 
811  template <class _Tp, class _Alloc>
812  inline bool
813  operator<(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
814  { return std::lexicographical_compare(_SL1.begin(), _SL1.end(),
815  _SL2.begin(), _SL2.end()); }
816 
817  template <class _Tp, class _Alloc>
818  inline bool
819  operator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
820  { return !(_SL1 == _SL2); }
821 
822  template <class _Tp, class _Alloc>
823  inline bool
824  operator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
825  { return _SL2 < _SL1; }
826 
827  template <class _Tp, class _Alloc>
828  inline bool
829  operator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
830  { return !(_SL2 < _SL1); }
831 
832  template <class _Tp, class _Alloc>
833  inline bool
834  operator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
835  { return !(_SL1 < _SL2); }
836 
837  template <class _Tp, class _Alloc>
838  inline void
839  swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y)
840  { __x.swap(__y); }
841 
842  template <class _Tp, class _Alloc>
843  void
844  slist<_Tp, _Alloc>::resize(size_type __len, const _Tp& __x)
845  {
846  _Node_base* __cur = &this->_M_head;
847  while (__cur->_M_next != 0 && __len > 0)
848  {
849  --__len;
850  __cur = __cur->_M_next;
851  }
852  if (__cur->_M_next)
853  this->_M_erase_after(__cur, 0);
854  else
855  _M_insert_after_fill(__cur, __len, __x);
856  }
857 
858  template <class _Tp, class _Alloc>
859  void
860  slist<_Tp, _Alloc>::remove(const _Tp& __val)
861  {
862  _Node_base* __cur = &this->_M_head;
863  while (__cur && __cur->_M_next)
864  {
865  if (((_Node*) __cur->_M_next)->_M_data == __val)
866  this->_M_erase_after(__cur);
867  else
868  __cur = __cur->_M_next;
869  }
870  }
871 
872  template <class _Tp, class _Alloc>
873  void
874  slist<_Tp, _Alloc>::unique()
875  {
876  _Node_base* __cur = this->_M_head._M_next;
877  if (__cur)
878  {
879  while (__cur->_M_next)
880  {
881  if (((_Node*)__cur)->_M_data
882  == ((_Node*)(__cur->_M_next))->_M_data)
883  this->_M_erase_after(__cur);
884  else
885  __cur = __cur->_M_next;
886  }
887  }
888  }
889 
890  template <class _Tp, class _Alloc>
891  void
892  slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x)
893  {
894  _Node_base* __n1 = &this->_M_head;
895  while (__n1->_M_next && __x._M_head._M_next)
896  {
897  if (((_Node*) __x._M_head._M_next)->_M_data
898  < ((_Node*) __n1->_M_next)->_M_data)
899  __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
900  __n1 = __n1->_M_next;
901  }
902  if (__x._M_head._M_next)
903  {
904  __n1->_M_next = __x._M_head._M_next;
905  __x._M_head._M_next = 0;
906  }
907  }
908 
909  template <class _Tp, class _Alloc>
910  void
911  slist<_Tp, _Alloc>::sort()
912  {
913  if (this->_M_head._M_next && this->_M_head._M_next->_M_next)
914  {
915  slist __carry;
916  slist __counter[64];
917  int __fill = 0;
918  while (!empty())
919  {
920  __slist_splice_after(&__carry._M_head,
921  &this->_M_head, this->_M_head._M_next);
922  int __i = 0;
923  while (__i < __fill && !__counter[__i].empty())
924  {
925  __counter[__i].merge(__carry);
926  __carry.swap(__counter[__i]);
927  ++__i;
928  }
929  __carry.swap(__counter[__i]);
930  if (__i == __fill)
931  ++__fill;
932  }
933 
934  for (int __i = 1; __i < __fill; ++__i)
935  __counter[__i].merge(__counter[__i-1]);
936  this->swap(__counter[__fill-1]);
937  }
938  }
939 
940  template <class _Tp, class _Alloc>
941  template <class _Predicate>
942  void slist<_Tp, _Alloc>::remove_if(_Predicate __pred)
943  {
944  _Node_base* __cur = &this->_M_head;
945  while (__cur->_M_next)
946  {
947  if (__pred(((_Node*) __cur->_M_next)->_M_data))
948  this->_M_erase_after(__cur);
949  else
950  __cur = __cur->_M_next;
951  }
952  }
953 
954  template <class _Tp, class _Alloc>
955  template <class _BinaryPredicate>
956  void
957  slist<_Tp, _Alloc>::unique(_BinaryPredicate __pred)
958  {
959  _Node* __cur = (_Node*) this->_M_head._M_next;
960  if (__cur)
961  {
962  while (__cur->_M_next)
963  {
964  if (__pred(((_Node*)__cur)->_M_data,
965  ((_Node*)(__cur->_M_next))->_M_data))
966  this->_M_erase_after(__cur);
967  else
968  __cur = (_Node*) __cur->_M_next;
969  }
970  }
971  }
972 
973  template <class _Tp, class _Alloc>
974  template <class _StrictWeakOrdering>
975  void
976  slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x,
977  _StrictWeakOrdering __comp)
978  {
979  _Node_base* __n1 = &this->_M_head;
980  while (__n1->_M_next && __x._M_head._M_next)
981  {
982  if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
983  ((_Node*) __n1->_M_next)->_M_data))
984  __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
985  __n1 = __n1->_M_next;
986  }
987  if (__x._M_head._M_next)
988  {
989  __n1->_M_next = __x._M_head._M_next;
990  __x._M_head._M_next = 0;
991  }
992  }
993 
994  template <class _Tp, class _Alloc>
995  template <class _StrictWeakOrdering>
996  void
997  slist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
998  {
999  if (this->_M_head._M_next && this->_M_head._M_next->_M_next)
1000  {
1001  slist __carry;
1002  slist __counter[64];
1003  int __fill = 0;
1004  while (!empty())
1005  {
1006  __slist_splice_after(&__carry._M_head,
1007  &this->_M_head, this->_M_head._M_next);
1008  int __i = 0;
1009  while (__i < __fill && !__counter[__i].empty())
1010  {
1011  __counter[__i].merge(__carry, __comp);
1012  __carry.swap(__counter[__i]);
1013  ++__i;
1014  }
1015  __carry.swap(__counter[__i]);
1016  if (__i == __fill)
1017  ++__fill;
1018  }
1019 
1020  for (int __i = 1; __i < __fill; ++__i)
1021  __counter[__i].merge(__counter[__i-1], __comp);
1022  this->swap(__counter[__fill-1]);
1023  }
1024  }
1025 
1026 _GLIBCXX_END_NAMESPACE_VERSION
1027 } // namespace
1028 
1029 namespace std _GLIBCXX_VISIBILITY(default)
1030 {
1031 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1032 
1033  // Specialization of insert_iterator so that insertions will be constant
1034  // time rather than linear time.
1035  template <class _Tp, class _Alloc>
1036  class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> >
1037  {
1038  protected:
1039  typedef __gnu_cxx::slist<_Tp, _Alloc> _Container;
1040  _Container* container;
1041  typename _Container::iterator iter;
1042 
1043  public:
1044  typedef _Container container_type;
1045  typedef output_iterator_tag iterator_category;
1046  typedef void value_type;
1047  typedef void difference_type;
1048  typedef void pointer;
1049  typedef void reference;
1050 
1051  insert_iterator(_Container& __x, typename _Container::iterator __i)
1052  : container(&__x)
1053  {
1054  if (__i == __x.begin())
1055  iter = __x.before_begin();
1056  else
1057  iter = __x.previous(__i);
1058  }
1059 
1060  insert_iterator<_Container>&
1061  operator=(const typename _Container::value_type& __value)
1062  {
1063  iter = container->insert_after(iter, __value);
1064  return *this;
1065  }
1066 
1067  insert_iterator<_Container>&
1068  operator*()
1069  { return *this; }
1070 
1071  insert_iterator<_Container>&
1072  operator++()
1073  { return *this; }
1074 
1075  insert_iterator<_Container>&
1076  operator++(int)
1077  { return *this; }
1078  };
1079 
1080 _GLIBCXX_END_NAMESPACE_VERSION
1081 } // namespace
1082 
1083 #endif
void _Destroy(_Tp *__pointer)
Definition: stl_construct.h:93
insert_iterator & operator*()
Simply returns *this.
Definition: stl_iterator.h:650
insert_iterator(_Container &__x, typename _Container::iterator __i)
Definition: stl_iterator.h:596
insert_iterator & operator=(const typename _Container::value_type &__value)
Definition: stl_iterator.h:632
Forward iterators support a superset of input iterator operations.
void difference_type
Distance between iterators is represented as this type.
void pointer
This type represents a pointer-to-value_type.
_Container container_type
A nested typedef for the type of whatever container you used.
Definition: stl_iterator.h:590
insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
Definition: stl_iterator.h:655
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
void _Construct(_T1 *__p, _Args &&...__args)
Definition: stl_construct.h:75
void reference
This type represents a reference-to-value_type.
The standard allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manual...
Definition: allocator.h:66