1/*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
8 *
9 * Copyright (c) 1997
10 * Moscow Center for SPARC Technology
11 *
12 * Copyright (c) 1999
13 * Boris Fomitchev
14 *
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
17 *
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
23 *
24 */
25
26/* NOTE: This is an internal header file, included by other STL headers.
27 *   You should not attempt to use it directly.
28 */
29
30#ifndef _STLP_INTERNAL_LIST_IMPL_H
31#define _STLP_INTERNAL_LIST_IMPL_H
32
33#ifndef _STLP_INTERNAL_ALGOBASE_H
34#  include <stl/_algobase.h>
35#endif
36
37#ifndef _STLP_INTERNAL_ALLOC_H
38#  include <stl/_alloc.h>
39#endif
40
41#ifndef _STLP_INTERNAL_ITERATOR_H
42#  include <stl/_iterator.h>
43#endif
44
45#ifndef _STLP_INTERNAL_CONSTRUCT_H
46#  include <stl/_construct.h>
47#endif
48
49#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
50#  include <stl/_function_base.h>
51#endif
52
53_STLP_BEGIN_NAMESPACE
54
55_STLP_MOVE_TO_PRIV_NAMESPACE
56
57struct _List_node_base {
58  _List_node_base* _M_next;
59  _List_node_base* _M_prev;
60};
61
62template <class _Dummy>
63class _List_global {
64public:
65  typedef _List_node_base _Node_base;
66  static void  _STLP_CALL _Transfer(_Node_base* __pos,
67                                    _Node_base* __first, _Node_base* __last);
68};
69
70#if defined (_STLP_USE_TEMPLATE_EXPORT)
71_STLP_EXPORT_TEMPLATE_CLASS _List_global<bool>;
72#endif
73typedef _List_global<bool> _List_global_inst;
74
75template <class _Tp>
76class _List_node : public _List_node_base {
77public:
78  _Tp _M_data;
79  __TRIVIAL_STUFF(_List_node)
80};
81
82struct _List_iterator_base {
83  typedef size_t                     size_type;
84  typedef ptrdiff_t                  difference_type;
85  typedef bidirectional_iterator_tag iterator_category;
86
87  _List_node_base* _M_node;
88
89  _List_iterator_base(_List_node_base* __x) : _M_node(__x) {}
90
91  void _M_incr() { _M_node = _M_node->_M_next; }
92  void _M_decr() { _M_node = _M_node->_M_prev; }
93};
94
95
96template<class _Tp, class _Traits>
97struct _List_iterator : public _List_iterator_base {
98  typedef _Tp value_type;
99  typedef typename _Traits::pointer    pointer;
100  typedef typename _Traits::reference  reference;
101
102  typedef _List_iterator<_Tp, _Traits>         _Self;
103  typedef typename _Traits::_NonConstTraits    _NonConstTraits;
104  typedef _List_iterator<_Tp, _NonConstTraits> iterator;
105  typedef typename _Traits::_ConstTraits       _ConstTraits;
106  typedef _List_iterator<_Tp, _ConstTraits>    const_iterator;
107
108  typedef bidirectional_iterator_tag iterator_category;
109  typedef _List_node<_Tp> _Node;
110  typedef size_t size_type;
111  typedef ptrdiff_t difference_type;
112
113  explicit _List_iterator(_List_node_base* __x) : _List_iterator_base(__x) {}
114  _List_iterator() : _List_iterator_base(0) {}
115  //copy constructor for iterator and constructor from iterator for const_iterator
116  _List_iterator(const iterator& __x) :  _List_iterator_base(__x._M_node) {}
117
118  reference operator*() const { return __STATIC_CAST(_Node*, this->_M_node)->_M_data; }
119
120  _STLP_DEFINE_ARROW_OPERATOR
121
122  _Self& operator++() {
123    this->_M_incr();
124    return *this;
125  }
126  _Self operator++(int) {
127    _Self __tmp = *this;
128    this->_M_incr();
129    return __tmp;
130  }
131  _Self& operator--() {
132    this->_M_decr();
133    return *this;
134  }
135  _Self operator--(int) {
136    _Self __tmp = *this;
137    this->_M_decr();
138    return __tmp;
139  }
140  bool operator==(const_iterator __y ) const {
141    return this->_M_node == __y._M_node;
142  }
143  bool operator!=(const_iterator __y ) const {
144    return this->_M_node != __y._M_node;
145  }
146};
147
148#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
149_STLP_MOVE_TO_STD_NAMESPACE
150template <class _Tp, class _Traits>
151struct __type_traits<_STLP_PRIV _List_iterator<_Tp, _Traits> > {
152  typedef __false_type   has_trivial_default_constructor;
153  typedef __true_type    has_trivial_copy_constructor;
154  typedef __true_type    has_trivial_assignment_operator;
155  typedef __true_type    has_trivial_destructor;
156  typedef __false_type   is_POD_type;
157};
158_STLP_MOVE_TO_PRIV_NAMESPACE
159#endif
160
161#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
162_STLP_MOVE_TO_STD_NAMESPACE
163template <class _Tp, class _Traits>
164inline _Tp* value_type(const _STLP_PRIV _List_iterator<_Tp, _Traits>&) { return 0; }
165inline bidirectional_iterator_tag iterator_category(const _STLP_PRIV _List_iterator_base&) { return bidirectional_iterator_tag();}
166inline ptrdiff_t* distance_type(const _STLP_PRIV _List_iterator_base&) { return 0; }
167_STLP_MOVE_TO_PRIV_NAMESPACE
168#endif
169
170// Base class that encapsulates details of allocators and helps
171// to simplify EH
172
173template <class _Tp, class _Alloc>
174class _List_base {
175protected:
176  _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
177  typedef _List_node_base _Node_base;
178  typedef _List_node<_Tp> _Node;
179  typedef _List_base<_Tp, _Alloc> _Self;
180  typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _Node_allocator_type;
181public:
182  typedef _STLP_alloc_proxy<_Node_base, _Node, _Node_allocator_type> _AllocProxy;
183  typedef _Alloc allocator_type;
184
185  allocator_type get_allocator() const
186  { return _STLP_CONVERT_ALLOCATOR((const _Node_allocator_type&)_M_node, _Tp); }
187
188  _List_base(const allocator_type& __a) : _M_node(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Node_base())
189  { _M_empty_initialize(); }
190
191#if !defined (_STLP_NO_MOVE_SEMANTIC)
192  _List_base(__move_source<_Self> src) :
193    _M_node(__move_source<_AllocProxy>(src.get()._M_node)) {
194    if (src.get().empty())
195      //We force this to empty.
196      _M_empty_initialize();
197    else {
198      src.get()._M_empty_initialize();
199      _M_node._M_data._M_prev->_M_next = _M_node._M_data._M_next->_M_prev = &_M_node._M_data;
200    }
201  }
202#endif
203
204  ~_List_base()
205  { clear(); }
206
207  void clear();
208  bool empty() const { return _M_node._M_data._M_next == &_M_node._M_data; }
209
210  void _M_empty_initialize() {
211    _M_node._M_data._M_next = &_M_node._M_data;
212    _M_node._M_data._M_prev = _M_node._M_data._M_next;
213  }
214
215public:
216  _AllocProxy _M_node;
217};
218
219#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
220#  define list _STLP_PTR_IMPL_NAME(list)
221#elif defined (_STLP_DEBUG)
222#  define list _STLP_NON_DBG_NAME(list)
223#else
224_STLP_MOVE_TO_STD_NAMESPACE
225#endif
226
227template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) >
228class list;
229
230#if !defined (list)
231_STLP_MOVE_TO_PRIV_NAMESPACE
232#endif
233
234// helper functions to reduce code duplication
235template <class _Tp, class _Alloc, class _Predicate>
236void _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred);
237
238template <class _Tp, class _Alloc, class _BinaryPredicate>
239void _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred);
240
241template <class _Tp, class _Alloc, class _StrictWeakOrdering>
242void _S_merge(list<_Tp, _Alloc>& __that, list<_Tp, _Alloc>& __x,
243              _StrictWeakOrdering __comp);
244
245template <class _Tp, class _Alloc, class _StrictWeakOrdering>
246void _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp);
247
248#if !defined (list)
249_STLP_MOVE_TO_STD_NAMESPACE
250#endif
251
252template <class _Tp, class _Alloc>
253class list : public _STLP_PRIV _List_base<_Tp, _Alloc>
254#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (list)
255           , public __stlport_class<list<_Tp, _Alloc> >
256#endif
257{
258  typedef _STLP_PRIV _List_base<_Tp, _Alloc> _Base;
259  typedef list<_Tp, _Alloc> _Self;
260  typedef _STLP_PRIV _List_node<_Tp> _Node;
261  typedef _STLP_PRIV _List_node_base _Node_base;
262public:
263  typedef _Tp value_type;
264  typedef value_type* pointer;
265  typedef const value_type* const_pointer;
266  typedef value_type& reference;
267  typedef const value_type& const_reference;
268  typedef size_t size_type;
269  typedef ptrdiff_t difference_type;
270  _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
271  typedef typename _Base::allocator_type allocator_type;
272  typedef bidirectional_iterator_tag _Iterator_category;
273
274public:
275  typedef _STLP_PRIV _List_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
276  typedef _STLP_PRIV _List_iterator<_Tp, _Const_traits<_Tp> >    const_iterator;
277  _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;
278
279protected:
280#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
281  _Node_base* _M_create_node(const_reference __x = value_type()) {
282#else
283  _Node_base* _M_create_node(const_reference __x) {
284#endif
285    _Node* __p = this->_M_node.allocate(1);
286    _STLP_TRY {
287      _Copy_Construct(&__p->_M_data, __x);
288    }
289    _STLP_UNWIND(this->_M_node.deallocate(__p, 1))
290    return __p;
291  }
292
293#if defined (_STLP_DONT_SUP_DFLT_PARAM)
294  _Node_base* _M_create_node() {
295    _Node* __p = this->_M_node.allocate(1);
296    _STLP_TRY {
297      _STLP_STD::_Construct(&__p->_M_data);
298    }
299    _STLP_UNWIND(this->_M_node.deallocate(__p, 1))
300    return __p;
301  }
302#endif
303
304public:
305#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
306  explicit list(size_type __n, const_reference __val = _STLP_DEFAULT_CONSTRUCTED(value_type),
307                const allocator_type& __a = allocator_type())
308#else
309  explicit list(size_type __n)
310    : _STLP_PRIV _List_base<_Tp, _Alloc>(allocator_type())
311    { this->insert(begin(), __n, _STLP_DEFAULT_CONSTRUCTED(value_type)); }
312  list(size_type __n, const_reference __val)
313    : _STLP_PRIV _List_base<_Tp, _Alloc>(allocator_type())
314    { this->insert(begin(), __n, __val); }
315  list(size_type __n, const_reference __val, const allocator_type& __a)
316#endif /*_STLP_DONT_SUP_DFLT_PARAM*/
317    : _STLP_PRIV _List_base<_Tp, _Alloc>(__a)
318    { this->insert(begin(), __n, __val); }
319
320#if defined (_STLP_MEMBER_TEMPLATES)
321  // We don't need any dispatching tricks here, because insert does all of
322  // that anyway.
323  template <class _InputIterator>
324  list(_InputIterator __first, _InputIterator __last,
325       const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
326    : _STLP_PRIV _List_base<_Tp, _Alloc>(__a)
327  { _M_insert(begin(), __first, __last); }
328
329#  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
330  template <class _InputIterator>
331  list(_InputIterator __first, _InputIterator __last)
332    : _STLP_PRIV _List_base<_Tp, _Alloc>(allocator_type())
333  { _M_insert(begin(), __first, __last); }
334#  endif
335#else /* _STLP_MEMBER_TEMPLATES */
336  list(const value_type* __first, const value_type* __last,
337       const allocator_type& __a = allocator_type())
338    : _STLP_PRIV _List_base<_Tp, _Alloc>(__a)
339    { _M_insert(begin(), __first, __last); }
340  list(const_iterator __first, const_iterator __last,
341       const allocator_type& __a = allocator_type())
342    : _STLP_PRIV _List_base<_Tp, _Alloc>(__a)
343    { _M_insert(begin(), __first, __last); }
344#endif /* _STLP_MEMBER_TEMPLATES */
345
346#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
347  explicit list(const allocator_type& __a = allocator_type())
348#else
349  list()
350    : _STLP_PRIV _List_base<_Tp, _Alloc>(allocator_type()) {}
351  list(const allocator_type& __a)
352#endif
353    : _STLP_PRIV _List_base<_Tp, _Alloc>(__a) {}
354
355  list(const _Self& __x) : _STLP_PRIV _List_base<_Tp, _Alloc>(__x.get_allocator())
356  { _M_insert(begin(), __x.begin(), __x.end()); }
357
358#if !defined (_STLP_NO_MOVE_SEMANTIC)
359  list(__move_source<_Self> src)
360    : _STLP_PRIV _List_base<_Tp, _Alloc>(__move_source<_Base>(src.get())) {}
361#endif
362
363  ~list() {}
364
365  _Self& operator = (const _Self& __x);
366
367  iterator begin()                      { return iterator(this->_M_node._M_data._M_next); }
368  const_iterator begin() const          { return const_iterator(this->_M_node._M_data._M_next); }
369
370  iterator end()                        { return iterator(&this->_M_node._M_data); }
371  const_iterator end() const            { return const_iterator(__CONST_CAST(_Node_base*, &this->_M_node._M_data)); }
372
373  reverse_iterator rbegin()             { return reverse_iterator(end()); }
374  const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
375
376  reverse_iterator rend()               { return reverse_iterator(begin()); }
377  const_reverse_iterator rend() const   { return const_reverse_iterator(begin()); }
378
379  size_type size() const {
380    size_type __result = _STLP_STD::distance(begin(), end());
381    return __result;
382  }
383  size_type max_size() const { return size_type(-1); }
384
385  reference front()             { return *begin(); }
386  const_reference front() const { return *begin(); }
387  reference back()              { return *(--end()); }
388  const_reference back() const  { return *(--end()); }
389
390private:
391  void _M_swap_aux(_Self& __x) {
392    __x._M_node._M_swap_alloc(this->_M_node);
393    __x._M_node._M_data._M_next = this->_M_node._M_data._M_next;
394    __x._M_node._M_data._M_next->_M_prev = &__x._M_node._M_data;
395    __x._M_node._M_data._M_prev = this->_M_node._M_data._M_prev;
396    __x._M_node._M_data._M_prev->_M_next = &__x._M_node._M_data;
397    this->_M_empty_initialize();
398  }
399
400public:
401  void swap(_Self& __x) {
402    if (__x.empty()) {
403      if (this->empty()) {
404        return;
405      }
406      this->_M_swap_aux(__x);
407    } else if (this->empty()) {
408      __x._M_swap_aux(*this);
409    } else {
410      this->_M_node.swap(__x._M_node);
411      _STLP_STD::swap(this->_M_node._M_data._M_prev->_M_next, __x._M_node._M_data._M_prev->_M_next);
412      _STLP_STD::swap(this->_M_node._M_data._M_next->_M_prev, __x._M_node._M_data._M_next->_M_prev);
413    }
414  }
415#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
416  void _M_swap_workaround(_Self& __x) { swap(__x); }
417#endif
418
419#if !defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
420  iterator insert(iterator __pos, const_reference __x = value_type())
421#else
422  iterator insert(iterator __pos, const_reference __x)
423#endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
424  {
425    _Node_base* __tmp = _M_create_node(__x);
426    _Node_base* __n = __pos._M_node;
427    _Node_base* __p = __n->_M_prev;
428    __tmp->_M_next = __n;
429    __tmp->_M_prev = __p;
430    __p->_M_next = __tmp;
431    __n->_M_prev = __tmp;
432    return iterator(__tmp);
433  }
434
435private:
436#if defined (_STLP_MEMBER_TEMPLATES)
437  template <class _InputIterator>
438  void _M_insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
439    typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
440    _M_insert_dispatch(__pos, __first, __last, _Integral());
441  }
442
443  // Check whether it's an integral type.  If so, it's not an iterator.
444  template<class _Integer>
445  void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
446                          const __true_type& /*_IsIntegral*/) {
447    _M_fill_insert(__pos, __n, __x);
448  }
449  template <class _InputIter>
450  void _M_insert_dispatch(iterator __pos,
451                          _InputIter __first, _InputIter __last,
452                          const __false_type& /*_IsIntegral*/) {
453#else /* _STLP_MEMBER_TEMPLATES */
454  void _M_insert(iterator __pos, const value_type* __first, const value_type* __last) {
455    for (; __first != __last; ++__first)
456      insert(__pos, *__first);
457  }
458  void _M_insert(iterator __pos, const_iterator __first, const_iterator __last) {
459#endif /* _STLP_MEMBER_TEMPLATES */
460    //We use a temporary list to avoid the auto reference troubles (infinite loop)
461    for (; __first != __last; ++__first)
462      insert(__pos, *__first);
463  }
464
465public:
466#if defined (_STLP_MEMBER_TEMPLATES)
467  template <class _InputIterator>
468  void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
469    typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
470    _M_splice_insert_dispatch(__pos, __first, __last, _Integral());
471  }
472
473private:
474  // Check whether it's an integral type.  If so, it's not an iterator.
475  template<class _Integer>
476  void _M_splice_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
477                          const __true_type& /*_IsIntegral*/) {
478    _M_fill_insert(__pos, __n, __x);
479  }
480  template <class _InputIter>
481  void _M_splice_insert_dispatch(iterator __pos,
482                          _InputIter __first, _InputIter __last,
483                          const __false_type& /*_IsIntegral*/) {
484#else /* _STLP_MEMBER_TEMPLATES */
485  void insert(iterator __pos, const value_type* __first, const value_type* __last) {
486    _Self __tmp(__first, __last, this->get_allocator());
487    _STLP_ASSERT(__tmp.get_allocator() == this->get_allocator())
488    splice(__pos, __tmp);
489  }
490  void insert(iterator __pos, const_iterator __first, const_iterator __last) {
491#endif /* _STLP_MEMBER_TEMPLATES */
492    //We use a temporary list to avoid the auto reference troubles (infinite loop)
493    _Self __tmp(__first, __last, this->get_allocator());
494    splice(__pos, __tmp);
495  }
496
497public:
498  void insert(iterator __pos, size_type __n, const_reference __x)
499  { _M_fill_insert(__pos, __n, __x); }
500
501private:
502  void _M_fill_insert(iterator __pos, size_type __n, const_reference __x) {
503    for ( ; __n > 0; --__n)
504      insert(__pos, __x);
505  }
506
507public:
508  void push_front(const_reference __x) { insert(begin(), __x); }
509  void push_back (const_reference __x) { insert(end(), __x); }
510
511#if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
512  iterator insert(iterator __pos)
513  { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(value_type)); }
514  void push_front() {insert(begin());}
515  void push_back() {insert(end());}
516# endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
517
518  iterator erase(iterator __pos) {
519    _Node_base* __next_node = __pos._M_node->_M_next;
520    _Node_base* __prev_node = __pos._M_node->_M_prev;
521    _Node* __n = __STATIC_CAST(_Node*, __pos._M_node);
522    __prev_node->_M_next = __next_node;
523    __next_node->_M_prev = __prev_node;
524    _STLP_STD::_Destroy(&__n->_M_data);
525    this->_M_node.deallocate(__n, 1);
526    return iterator(__next_node);
527  }
528
529  iterator erase(iterator __first, iterator __last) {
530    while (__first != __last)
531      erase(__first++);
532    return __last;
533  }
534
535#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
536  void resize(size_type __new_size, const_reference __x = value_type());
537#else
538  void resize(size_type __new_size, const_reference __x);
539  void resize(size_type __new_size)
540  { this->resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(value_type)); }
541#endif /*!_STLP_DONT_SUP_DFLT_PARAM*/
542
543  void pop_front() { erase(begin()); }
544  void pop_back() {
545    iterator __tmp = end();
546    erase(--__tmp);
547  }
548
549public:
550  // assign(), a generalized assignment member function.  Two
551  // versions: one that takes a count, and one that takes a range.
552  // The range version is a member template, so we dispatch on whether
553  // or not the type is an integer.
554
555  void assign(size_type __n, const_reference __val) { _M_fill_assign(__n, __val); }
556
557  void _M_fill_assign(size_type __n, const_reference __val);
558
559#if defined (_STLP_MEMBER_TEMPLATES)
560  template <class _InputIterator>
561  void assign(_InputIterator __first, _InputIterator __last) {
562    typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
563    _M_assign_dispatch(__first, __last, _Integral());
564  }
565
566  template <class _Integer>
567  void _M_assign_dispatch(_Integer __n, _Integer __val,
568                          const __true_type& /*_IsIntegral*/) {
569    _M_fill_assign(__n, __val);
570  }
571
572  template <class _InputIterator>
573  void _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
574                          const __false_type& /*_IsIntegral*/) {
575#else
576  void assign(const value_type *__first2, const value_type *__last2) {
577    iterator __first1 = begin();
578    iterator __last1 = end();
579    for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
580      *__first1 = *__first2;
581    if (__first2 == __last2)
582      erase(__first1, __last1);
583    else
584      insert(__last1, __first2, __last2);
585  }
586  void assign(const_iterator __first2, const_iterator __last2) {
587#endif /* _STLP_MEMBER_TEMPLATES */
588    iterator __first1 = begin();
589    iterator __last1 = end();
590    for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
591      *__first1 = *__first2;
592    if (__first2 == __last2)
593      erase(__first1, __last1);
594    else
595      insert(__last1, __first2, __last2);
596  }
597
598public:
599  void splice(iterator __pos, _Self& __x) {
600    if (!__x.empty()) {
601      if (this->get_allocator() == __x.get_allocator()) {
602        _STLP_PRIV _List_global_inst::_Transfer(__pos._M_node, __x.begin()._M_node, __x.end()._M_node);
603      }
604      else {
605        insert(__pos, __x.begin(), __x.end());
606        __x.clear();
607      }
608    }
609  }
610  void splice(iterator __pos, _Self& __x, iterator __i) {
611    iterator __j = __i;
612    ++__j;
613    if (__pos == __i || __pos == __j) return;
614    if (this->get_allocator() == __x.get_allocator()) {
615      _STLP_PRIV _List_global_inst::_Transfer(__pos._M_node, __i._M_node, __j._M_node);
616    }
617    else {
618      insert(__pos, *__i);
619      __x.erase(__i);
620    }
621  }
622  void splice(iterator __pos, _Self& __x, iterator __first, iterator __last) {
623    if (__first != __last) {
624      if (this->get_allocator() == __x.get_allocator()) {
625        _STLP_PRIV _List_global_inst::_Transfer(__pos._M_node, __first._M_node, __last._M_node);
626      }
627      else {
628        insert(__pos, __first, __last);
629        __x.erase(__first, __last);
630      }
631    }
632  }
633
634  void remove(const_reference __val) {
635    iterator __first = begin();
636    iterator __last = end();
637    while (__first != __last) {
638      iterator __next = __first;
639      ++__next;
640      if (__val == *__first) erase(__first);
641      __first = __next;
642    }
643  }
644
645  void unique()
646  { _STLP_PRIV _S_unique(*this, equal_to<value_type>()); }
647
648  void merge(_Self& __x)
649  { _STLP_PRIV _S_merge(*this, __x, less<value_type>()); }
650
651  void reverse() {
652    _Node_base* __p = &this->_M_node._M_data;
653    _Node_base* __tmp = __p;
654    do {
655      _STLP_STD::swap(__tmp->_M_next, __tmp->_M_prev);
656      __tmp = __tmp->_M_prev;     // Old next node is now prev.
657    } while (__tmp != __p);
658  }
659
660  void sort()
661  { _STLP_PRIV _S_sort(*this, less<value_type>()); }
662
663#if defined (_STLP_MEMBER_TEMPLATES)
664  template <class _Predicate>
665  void remove_if(_Predicate __pred)
666  { _STLP_PRIV _S_remove_if(*this, __pred); }
667  template <class _BinaryPredicate>
668  void unique(_BinaryPredicate __binary_pred)
669  { _STLP_PRIV _S_unique(*this, __binary_pred); }
670
671  template <class _StrictWeakOrdering>
672  void merge(_Self& __x,
673             _StrictWeakOrdering __comp) {
674    _STLP_PRIV _S_merge(*this, __x, __comp);
675  }
676
677  template <class _StrictWeakOrdering>
678  void sort(_StrictWeakOrdering __comp)
679  { _STLP_PRIV _S_sort(*this, __comp); }
680#endif /* _STLP_MEMBER_TEMPLATES */
681};
682
683#if defined (list)
684#  undef list
685_STLP_MOVE_TO_STD_NAMESPACE
686#endif
687
688_STLP_END_NAMESPACE
689
690#if !defined (_STLP_LINK_TIME_INSTANTIATION)
691#  include <stl/_list.c>
692#endif
693
694#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
695#  include <stl/pointers/_list.h>
696#endif
697
698#if defined (_STLP_DEBUG)
699#  include <stl/debug/_list.h>
700#endif
701
702_STLP_BEGIN_NAMESPACE
703
704template <class _Tp, class _Alloc>
705_STLP_INLINE_LOOP bool  _STLP_CALL
706operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) {
707  typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
708  const_iterator __end1 = __x.end();
709  const_iterator __end2 = __y.end();
710
711  const_iterator __i1 = __x.begin();
712  const_iterator __i2 = __y.begin();
713  while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
714    ++__i1;
715    ++__i2;
716  }
717  return __i1 == __end1 && __i2 == __end2;
718}
719
720#define _STLP_EQUAL_OPERATOR_SPECIALIZED
721#define _STLP_TEMPLATE_HEADER    template <class _Tp, class _Alloc>
722#define _STLP_TEMPLATE_CONTAINER list<_Tp, _Alloc>
723#include <stl/_relops_cont.h>
724#undef _STLP_TEMPLATE_CONTAINER
725#undef _STLP_TEMPLATE_HEADER
726#undef _STLP_EQUAL_OPERATOR_SPECIALIZED
727
728#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
729template <class _Tp, class _Alloc>
730struct __move_traits<list<_Tp, _Alloc> > {
731  typedef __true_type implemented;
732  typedef typename __move_traits<_Alloc>::complete complete;
733};
734#endif
735
736_STLP_END_NAMESPACE
737
738#endif /* _STLP_INTERNAL_LIST_IMPL_H */
739
740// Local Variables:
741// mode:C++
742// End:
743