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