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