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