3 * Copyright (c) 1996,1997
4 * Silicon Graphics Computer Systems, Inc.
7 * Moscow Center for SPARC Technology
12 * This material is provided "as is", with absolutely no warranty expressed
13 * or implied. Any use is at your own risk.
15 * Permission to use or copy this software for any purpose is hereby granted
16 * without fee, provided the above notices are retained on all copies.
17 * Permission to modify the code and to distribute modified code is granted,
18 * provided the above notices are retained, and a notice that the code was
19 * modified is included with the above copyright notice.
23 /* NOTE: This is an internal header file, included by other STL headers.
24 * You should not attempt to use it directly.
27 #ifndef _STLP_INTERNAL_SLIST_H
28 #define _STLP_INTERNAL_SLIST_H
30 #ifndef _STLP_INTERNAL_ALGOBASE_H
31 # include <stl/_algobase.h>
34 #ifndef _STLP_INTERNAL_ALLOC_H
35 # include <stl/_alloc.h>
38 #ifndef _STLP_INTERNAL_ITERATOR_H
39 # include <stl/_iterator.h>
42 #ifndef _STLP_INTERNAL_CONSTRUCT_H
43 # include <stl/_construct.h>
46 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
47 # include <stl/_function_base.h>
50 #ifndef _STLP_INTERNAL_SLIST_BASE_H
51 # include <stl/_slist_base.h>
56 _STLP_MOVE_TO_PRIV_NAMESPACE
59 class _Slist_node
: public _Slist_node_base
{
62 __TRIVIAL_STUFF(_Slist_node
)
65 struct _Slist_iterator_base
{
66 typedef size_t size_type
;
67 typedef ptrdiff_t difference_type
;
68 typedef forward_iterator_tag iterator_category
;
70 _Slist_node_base
*_M_node
;
72 _Slist_iterator_base(_Slist_node_base
*__x
) : _M_node(__x
) {}
75 _M_node
= _M_node
->_M_next
;
79 template <class _Tp
, class _Traits
>
80 class _Slist_iterator
: public _Slist_iterator_base
{
82 typedef typename
_Traits::value_type value_type
;
83 typedef typename
_Traits::pointer pointer
;
84 typedef typename
_Traits::reference reference
;
85 typedef forward_iterator_tag iterator_category
;
86 typedef size_t size_type
;
87 typedef ptrdiff_t difference_type
;
89 typedef _Slist_iterator
<_Tp
, _Traits
> _Self
;
90 typedef typename
_Traits::_NonConstTraits _NonConstTraits
;
91 typedef _Slist_iterator
<_Tp
, _NonConstTraits
> iterator
;
92 typedef typename
_Traits::_ConstTraits _ConstTraits
;
93 typedef _Slist_iterator
<_Tp
, _ConstTraits
> const_iterator
;
95 typedef _Slist_node
<value_type
> _Node
;
97 explicit _Slist_iterator(_Slist_node_base
*__x
) : _Slist_iterator_base(__x
) {}
98 _Slist_iterator() : _Slist_iterator_base(0) {}
99 //copy constructor for iterator and constructor from iterator for const_iterator
100 _Slist_iterator(const iterator
& __x
) : _Slist_iterator_base(__x
._M_node
) {}
102 reference
operator*() const { return __STATIC_CAST(_Node
*, this->_M_node
)->_M_data
; }
104 _STLP_DEFINE_ARROW_OPERATOR
106 _Self
& operator++() {
110 _Self
operator++(int) {
116 bool operator==(const_iterator __y
) const {
117 return this->_M_node
== __y
._M_node
;
119 bool operator!=(const_iterator __y
) const {
120 return this->_M_node
!= __y
._M_node
;
124 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
125 _STLP_MOVE_TO_STD_NAMESPACE
126 template <class _Tp
, class _Traits
>
127 struct __type_traits
<_STLP_PRIV _Slist_iterator
<_Tp
, _Traits
> > {
128 typedef __false_type has_trivial_default_constructor
;
129 typedef __true_type has_trivial_copy_constructor
;
130 typedef __true_type has_trivial_assignment_operator
;
131 typedef __true_type has_trivial_destructor
;
132 typedef __false_type is_POD_type
;
134 _STLP_MOVE_TO_PRIV_NAMESPACE
135 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
137 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
138 _STLP_MOVE_TO_STD_NAMESPACE
139 template <class _Tp
, class _Traits
>
140 inline _Tp
* _STLP_CALL
value_type(const _STLP_PRIV _Slist_iterator
<_Tp
, _Traits
>&) { return __STATIC_CAST(_Tp
*, 0); }
141 inline ptrdiff_t* _STLP_CALL
distance_type(const _STLP_PRIV _Slist_iterator_base
&) { return 0; }
142 inline forward_iterator_tag _STLP_CALL
iterator_category(const _STLP_PRIV _Slist_iterator_base
&) { return forward_iterator_tag(); }
143 _STLP_MOVE_TO_PRIV_NAMESPACE
144 #endif /* OLD_QUERIES */
146 // Base class that encapsulates details of allocators and simplifies EH
147 template <class _Tp
, class _Alloc
>
150 typedef _Slist_node
<_Tp
> _Node
;
151 typedef typename _Alloc_traits
<_Node
,_Alloc
>::allocator_type _M_node_allocator_type
;
152 typedef _Slist_base
<_Tp
, _Alloc
> _Self
;
155 typedef _STLP_alloc_proxy
<_Slist_node_base
, _Node
, _M_node_allocator_type
> _AllocProxy
;
157 _STLP_FORCE_ALLOCATORS(_Tp
, _Alloc
)
158 typedef _Alloc allocator_type
;
160 _Slist_base(const allocator_type
& __a
) :
161 _M_head(_STLP_CONVERT_ALLOCATOR(__a
, _Node
), _Slist_node_base() )
162 { _M_head
._M_data
._M_next
= 0; }
164 #if !defined (_STLP_NO_MOVE_SEMANTIC)
165 _Slist_base(__move_source
<_Self
> src
) :
166 _M_head(__move_source
<_AllocProxy
>(src
.get()._M_head
))
167 { src
.get()._M_head
._M_data
._M_next
= 0; }
170 ~_Slist_base() { _M_erase_after(&_M_head
._M_data
, 0); }
173 _Slist_node_base
* _M_erase_after(_Slist_node_base
* __pos
) {
174 _Node
* __next
= __STATIC_CAST(_Node
*, __pos
->_M_next
);
175 _Slist_node_base
* __next_next
= __next
->_M_next
;
176 __pos
->_M_next
= __next_next
;
177 _STLP_STD::_Destroy(&__next
->_M_data
);
178 _M_head
.deallocate(__next
,1);
181 _Slist_node_base
* _M_erase_after(_Slist_node_base
*, _Slist_node_base
*);
184 allocator_type
get_allocator() const
185 { return _STLP_CONVERT_ALLOCATOR((const _M_node_allocator_type
&)_M_head
, _Tp
); }
189 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
190 # define slist _STLP_PTR_IMPL_NAME(slist)
191 #elif defined (_STLP_DEBUG)
192 # define slist _STLP_NON_DBG_NAME(slist)
194 _STLP_MOVE_TO_STD_NAMESPACE
197 template <class _Tp
, _STLP_DFL_TMPL_PARAM(_Alloc
, allocator
<_Tp
>) >
201 _STLP_MOVE_TO_PRIV_NAMESPACE
204 // helper functions to reduce code duplication
205 template <class _Tp
, class _Alloc
, class _BinaryPredicate
>
206 void _Slist_unique(slist
<_Tp
, _Alloc
>& __that
, _BinaryPredicate __binary_pred
);
208 template <class _Tp
, class _Alloc
, class _StrictWeakOrdering
>
209 void _Slist_merge(slist
<_Tp
, _Alloc
>& __that
, slist
<_Tp
, _Alloc
>& __x
,
210 _StrictWeakOrdering __comp
);
212 template <class _Tp
, class _Alloc
, class _StrictWeakOrdering
>
213 void _Slist_sort(slist
<_Tp
, _Alloc
>& __that
, _StrictWeakOrdering __comp
);
216 _STLP_MOVE_TO_STD_NAMESPACE
219 template <class _Tp
, class _Alloc
>
220 class slist
: protected _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>
221 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (slist)
222 , public __stlport_class
<slist
<_Tp
, _Alloc
> >
226 typedef _STLP_PRIV _Slist_base
<_Tp
,_Alloc
> _Base
;
227 typedef slist
<_Tp
,_Alloc
> _Self
;
229 typedef _Tp value_type
;
231 typedef value_type
* pointer
;
232 typedef const value_type
* const_pointer
;
233 typedef value_type
& reference
;
234 typedef const value_type
& const_reference
;
235 typedef size_t size_type
;
236 typedef ptrdiff_t difference_type
;
237 typedef forward_iterator_tag _Iterator_category
;
239 typedef _STLP_PRIV _Slist_iterator
<_Tp
, _Nonconst_traits
<_Tp
> > iterator
;
240 typedef _STLP_PRIV _Slist_iterator
<_Tp
, _Const_traits
<_Tp
> > const_iterator
;
242 _STLP_FORCE_ALLOCATORS(_Tp
, _Alloc
)
243 typedef typename
_Base::allocator_type allocator_type
;
246 typedef _STLP_PRIV _Slist_node
<_Tp
> _Node
;
247 typedef _STLP_PRIV _Slist_node_base _Node_base
;
249 #if !defined(_STLP_DONT_SUP_DFLT_PARAM)
250 _Node
* _M_create_node(const value_type
& __x
= _Tp()) {
252 _Node
* _M_create_node(const value_type
& __x
) {
253 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
254 _Node
* __node
= this->_M_head
.allocate(1);
256 _Copy_Construct(&__node
->_M_data
, __x
);
259 _STLP_UNWIND(this->_M_head
.deallocate(__node
, 1))
263 #if defined(_STLP_DONT_SUP_DFLT_PARAM)
264 _Node
* _M_create_node() {
265 _Node
* __node
= this->_M_head
.allocate(1);
267 _STLP_STD::_Construct(&__node
->_M_data
);
270 _STLP_UNWIND(this->_M_head
.deallocate(__node
, 1))
273 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
277 allocator_type
get_allocator() const { return _Base::get_allocator(); }
279 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
280 explicit slist(const allocator_type
& __a
= allocator_type())
283 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(allocator_type()) {}
284 slist(const allocator_type
& __a
)
286 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(__a
) {}
288 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
289 explicit slist(size_type __n
, const value_type
& __x
= _STLP_DEFAULT_CONSTRUCTED(_Tp
),
290 const allocator_type
& __a
= allocator_type())
292 explicit slist(size_type __n
)
293 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(allocator_type())
294 { _M_insert_after_fill(&this->_M_head
._M_data
, __n
, _STLP_DEFAULT_CONSTRUCTED(_Tp
)); }
295 slist(size_type __n
, const value_type
& __x
)
296 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(allocator_type())
297 { _M_insert_after_fill(&this->_M_head
._M_data
, __n
, __x
); }
298 slist(size_type __n
, const value_type
& __x
, const allocator_type
& __a
)
300 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(__a
)
301 { _M_insert_after_fill(&this->_M_head
._M_data
, __n
, __x
); }
303 #if defined (_STLP_MEMBER_TEMPLATES)
304 // We don't need any dispatching tricks here, because _M_insert_after_range
305 // already does them.
306 template <class _InputIterator
>
307 slist(_InputIterator __first
, _InputIterator __last
,
308 const allocator_type
& __a _STLP_ALLOCATOR_TYPE_DFL
)
309 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(__a
)
310 { _M_insert_after_range(&this->_M_head
._M_data
, __first
, __last
); }
311 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
312 // VC++ needs this crazyness
313 template <class _InputIterator
>
314 slist(_InputIterator __first
, _InputIterator __last
)
315 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(allocator_type())
316 { _M_insert_after_range(&this->_M_head
._M_data
, __first
, __last
); }
318 #else /* _STLP_MEMBER_TEMPLATES */
319 slist(const_iterator __first
, const_iterator __last
,
320 const allocator_type
& __a
= allocator_type() )
321 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(__a
)
322 { _M_insert_after_range(&this->_M_head
._M_data
, __first
, __last
); }
323 slist(const value_type
* __first
, const value_type
* __last
,
324 const allocator_type
& __a
= allocator_type())
325 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(__a
)
326 { _M_insert_after_range(&this->_M_head
._M_data
, __first
, __last
); }
327 #endif /* _STLP_MEMBER_TEMPLATES */
329 slist(const _Self
& __x
)
330 : _STLP_PRIV _Slist_base
<_Tp
,_Alloc
>(__x
.get_allocator())
331 { _M_insert_after_range(&this->_M_head
._M_data
, __x
.begin(), __x
.end()); }
333 #if !defined (_STLP_NO_MOVE_SEMANTIC)
334 slist(__move_source
<_Self
> src
)
335 : _STLP_PRIV _Slist_base
<_Tp
, _Alloc
>(__move_source
<_Base
>(src
.get())) {}
338 _Self
& operator= (const _Self
& __x
);
343 // assign(), a generalized assignment member function. Two
344 // versions: one that takes a count, and one that takes a range.
345 // The range version is a member template, so we dispatch on whether
346 // or not the type is an integer.
348 void assign(size_type __n
, const _Tp
& __val
) { _M_fill_assign(__n
, __val
); }
351 void _M_fill_assign(size_type __n
, const _Tp
& __val
);
353 #if defined (_STLP_MEMBER_TEMPLATES)
355 template <class _InputIterator
>
356 void assign(_InputIterator __first
, _InputIterator __last
) {
357 typedef typename _IsIntegral
<_InputIterator
>::_Ret _Integral
;
358 _M_assign_dispatch(__first
, __last
, _Integral());
362 template <class _Integer
>
363 void _M_assign_dispatch(_Integer __n
, _Integer __val
,
364 const __true_type
& /*_IsIntegral*/) {
365 _M_fill_assign((size_type
) __n
, (_Tp
) __val
);
368 template <class _InputIter
>
369 void _M_assign_dispatch(_InputIter __first
, _InputIter __last
,
370 const __false_type
& /*_IsIntegral*/) {
373 void assign(const_pointer __first
, const_pointer __last
) {
374 _Node_base
* __prev
= &this->_M_head
._M_data
;
375 _Node_base
* __node
= this->_M_head
._M_data
._M_next
;
376 while (__node
!= 0 && __first
!= __last
) {
377 __STATIC_CAST(_Node
*, __node
)->_M_data
= *__first
;
379 __node
= __node
->_M_next
;
382 if (__first
!= __last
)
383 _M_insert_after_range(__prev
, __first
, __last
);
385 this->_M_erase_after(__prev
, 0);
387 void assign(const_iterator __first
, const_iterator __last
) {
388 #endif /* _STLP_MEMBER_TEMPLATES */
389 _Node_base
* __prev
= &this->_M_head
._M_data
;
390 _Node_base
* __node
= this->_M_head
._M_data
._M_next
;
391 while (__node
!= 0 && __first
!= __last
) {
392 __STATIC_CAST(_Node
*, __node
)->_M_data
= *__first
;
394 __node
= __node
->_M_next
;
397 if (__first
!= __last
)
398 _M_insert_after_range(__prev
, __first
, __last
);
400 this->_M_erase_after(__prev
, 0);
405 // Experimental new feature: before_begin() returns a
406 // non-dereferenceable iterator that, when incremented, yields
407 // begin(). This iterator may be used as the argument to
408 // insert_after, erase_after, etc. Note that even for an empty
409 // slist, before_begin() is not the same iterator as end(). It
410 // is always necessary to increment before_begin() at least once to
412 iterator
before_begin() { return iterator(&this->_M_head
._M_data
); }
413 const_iterator
before_begin() const
414 { return const_iterator(__CONST_CAST(_Node_base
*, &this->_M_head
._M_data
)); }
416 iterator
begin() { return iterator(this->_M_head
._M_data
._M_next
); }
417 const_iterator
begin() const
418 { return const_iterator(this->_M_head
._M_data
._M_next
);}
420 iterator
end() { return iterator(); }
421 const_iterator
end() const { return const_iterator(); }
423 size_type
size() const
424 { return _STLP_PRIV
_Sl_global_inst::size(this->_M_head
._M_data
._M_next
); }
426 size_type
max_size() const { return size_type(-1); }
428 bool empty() const { return this->_M_head
._M_data
._M_next
== 0; }
430 void swap(_Self
& __x
)
431 { this->_M_head
.swap(__x
._M_head
); }
432 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
433 void _M_swap_workaround(_Self
& __x
) { swap(__x
); }
437 reference
front() { return *begin(); }
438 const_reference
front() const { return *begin(); }
439 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
440 void push_front(const value_type
& __x
= _Tp()) {
442 void push_front(const value_type
& __x
) {
443 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
444 _STLP_PRIV
__slist_make_link(&this->_M_head
._M_data
, _M_create_node(__x
));
447 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
448 void push_front() { _STLP_PRIV
__slist_make_link(&this->_M_head
._M_data
, _M_create_node());}
449 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
452 _Node
* __node
= __STATIC_CAST(_Node
*, this->_M_head
._M_data
._M_next
);
453 this->_M_head
._M_data
._M_next
= __node
->_M_next
;
454 _STLP_STD::_Destroy(&__node
->_M_data
);
455 this->_M_head
.deallocate(__node
, 1);
458 iterator
previous(const_iterator __pos
) {
459 return iterator(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
._M_node
));
461 const_iterator
previous(const_iterator __pos
) const {
462 return const_iterator(__CONST_CAST(_Node_base
*,
463 _STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
,
468 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
469 _Node
* _M_insert_after(_Node_base
* __pos
, const value_type
& __x
= _Tp()) {
471 _Node
* _M_insert_after(_Node_base
* __pos
, const value_type
& __x
) {
472 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
473 return __STATIC_CAST(_Node
*, _STLP_PRIV
__slist_make_link(__pos
, _M_create_node(__x
)));
476 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
477 _Node
* _M_insert_after(_Node_base
* __pos
) {
478 return __STATIC_CAST(_Node
*, _STLP_PRIV
__slist_make_link(__pos
, _M_create_node()));
480 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
482 void _M_insert_after_fill(_Node_base
* __pos
,
483 size_type __n
, const value_type
& __x
) {
484 for (size_type __i
= 0; __i
< __n
; ++__i
)
485 __pos
= _STLP_PRIV
__slist_make_link(__pos
, _M_create_node(__x
));
488 #if defined (_STLP_MEMBER_TEMPLATES)
489 // Check whether it's an integral type. If so, it's not an iterator.
490 template <class _InIter
>
491 void _M_insert_after_range(_Node_base
* __pos
,
492 _InIter __first
, _InIter __last
) {
493 typedef typename _IsIntegral
<_InIter
>::_Ret _Integral
;
494 _M_insert_after_range(__pos
, __first
, __last
, _Integral());
497 template <class _Integer
>
498 void _M_insert_after_range(_Node_base
* __pos
, _Integer __n
, _Integer __x
,
499 const __true_type
&) {
500 _M_insert_after_fill(__pos
, __n
, __x
);
503 template <class _InIter
>
504 void _M_insert_after_range(_Node_base
* __pos
,
505 _InIter __first
, _InIter __last
,
506 const __false_type
&) {
507 #else /* _STLP_MEMBER_TEMPLATES */
508 void _M_insert_after_range(_Node_base
* __pos
,
509 const value_type
* __first
,
510 const value_type
* __last
) {
511 while (__first
!= __last
) {
512 __pos
= _STLP_PRIV
__slist_make_link(__pos
, _M_create_node(*__first
));
516 void _M_insert_after_range(_Node_base
* __pos
,
517 const_iterator __first
, const_iterator __last
) {
518 #endif /* _STLP_MEMBER_TEMPLATES */
519 while (__first
!= __last
) {
520 __pos
= _STLP_PRIV
__slist_make_link(__pos
, _M_create_node(*__first
));
525 #if defined (_STLP_MEMBER_TEMPLATES)
526 // Check whether it's an integral type. If so, it's not an iterator.
527 template <class _InIter
>
528 void _M_splice_after_range(_Node_base
* __pos
,
529 _InIter __first
, _InIter __last
) {
530 typedef typename _IsIntegral
<_InIter
>::_Ret _Integral
;
531 _M_splice_after_range(__pos
, __first
, __last
, _Integral());
534 template <class _Integer
>
535 void _M_splice_after_range(_Node_base
* __pos
, _Integer __n
, _Integer __x
,
536 const __true_type
&) {
537 _M_insert_after_fill(__pos
, __n
, __x
);
540 template <class _InIter
>
541 void _M_splice_after_range(_Node_base
* __pos
,
542 _InIter __first
, _InIter __last
,
543 const __false_type
&) {
544 #else /* _STLP_MEMBER_TEMPLATES */
545 void _M_splice_after_range(_Node_base
* __pos
,
546 const value_type
* __first
,
547 const value_type
* __last
) {
548 while (__first
!= __last
) {
549 __pos
= _STLP_PRIV
__slist_make_link(__pos
, _M_create_node(*__first
));
553 void _M_splice_after_range(_Node_base
* __pos
,
554 const_iterator __first
, const_iterator __last
) {
555 #endif /* _STLP_MEMBER_TEMPLATES */
556 //We use a temporary slist to avoid the auto reference troubles (infinite loop)
557 _Self
__tmp(__first
, __last
, this->get_allocator());
558 splice_after(iterator(__pos
), __tmp
);
561 #if defined (_STLP_MEMBER_TEMPLATES)
562 // Check whether it's an integral type. If so, it's not an iterator.
563 template <class _InIter
>
564 void _M_splice_range(_Node_base
* __pos
,
565 _InIter __first
, _InIter __last
) {
566 typedef typename _IsIntegral
<_InIter
>::_Ret _Integral
;
567 _M_splice_range(__pos
, __first
, __last
, _Integral());
570 template <class _Integer
>
571 void _M_splice_range(_Node_base
* __pos
, _Integer __n
, _Integer __x
,
572 const __true_type
&) {
573 _M_insert_after_fill(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
),
577 template <class _InIter
>
578 void _M_splice_range(_Node_base
* __pos
,
579 _InIter __first
, _InIter __last
,
580 const __false_type
&) {
581 #else /* _STLP_MEMBER_TEMPLATES */
582 void _M_splice_range(_Node_base
* __pos
,
583 const value_type
* __first
,
584 const value_type
* __last
) {
585 while (__first
!= __last
) {
586 __pos
= _STLP_PRIV
__slist_make_link(__pos
, _M_create_node(*__first
));
590 void _M_splice_range(_Node_base
* __pos
,
591 const_iterator __first
, const_iterator __last
) {
592 #endif /* _STLP_MEMBER_TEMPLATES */
593 //We use a temporary slist to avoid the auto reference troubles (infinite loop)
594 _Self
__tmp(__first
, __last
, this->get_allocator());
595 splice(iterator(__pos
), __tmp
);
600 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
601 iterator
insert_after(iterator __pos
, const value_type
& __x
= _Tp()) {
603 iterator
insert_after(iterator __pos
, const value_type
& __x
) {
604 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
605 return iterator(_M_insert_after(__pos
._M_node
, __x
));
608 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
609 iterator
insert_after(iterator __pos
) {
610 return insert_after(__pos
, _STLP_DEFAULT_CONSTRUCTED(_Tp
));
612 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
614 void insert_after(iterator __pos
, size_type __n
, const value_type
& __x
) {
615 _M_insert_after_fill(__pos
._M_node
, __n
, __x
);
618 #if defined (_STLP_MEMBER_TEMPLATES)
619 // We don't need any dispatching tricks here, because _M_insert_after_range
620 // already does them.
621 template <class _InIter
>
622 void insert_after(iterator __pos
, _InIter __first
, _InIter __last
) {
623 #else /* _STLP_MEMBER_TEMPLATES */
624 void insert_after(iterator __pos
,
625 const value_type
* __first
, const value_type
* __last
) {
626 _M_insert_after_range(__pos
._M_node
, __first
, __last
);
628 void insert_after(iterator __pos
,
629 const_iterator __first
, const_iterator __last
) {
630 #endif /* _STLP_MEMBER_TEMPLATES */
631 _M_splice_after_range(__pos
._M_node
, __first
, __last
);
634 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
635 iterator
insert(iterator __pos
, const value_type
& __x
= _Tp()) {
637 iterator
insert(iterator __pos
, const value_type
& __x
) {
638 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
639 return iterator(_M_insert_after(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
._M_node
),
643 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
644 iterator
insert(iterator __pos
) {
645 return iterator(_M_insert_after(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
._M_node
),
646 _STLP_DEFAULT_CONSTRUCTED(_Tp
)));
648 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
650 void insert(iterator __pos
, size_type __n
, const value_type
& __x
) {
651 _M_insert_after_fill(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
._M_node
), __n
, __x
);
654 #if defined (_STLP_MEMBER_TEMPLATES)
655 // We don't need any dispatching tricks here, because _M_insert_after_range
656 // already does them.
657 template <class _InIter
>
658 void insert(iterator __pos
, _InIter __first
, _InIter __last
) {
659 #else /* _STLP_MEMBER_TEMPLATES */
660 void insert(iterator __pos
, const value_type
* __first
,
661 const value_type
* __last
) {
662 _M_insert_after_range(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
._M_node
),
665 void insert(iterator __pos
, const_iterator __first
, const_iterator __last
) {
666 #endif /* _STLP_MEMBER_TEMPLATES */
667 _M_splice_range(__pos
._M_node
, __first
, __last
);
671 iterator
erase_after(iterator __pos
)
672 { return iterator(this->_M_erase_after(__pos
._M_node
)); }
673 iterator
erase_after(iterator __before_first
, iterator __last
)
674 { return iterator(this->_M_erase_after(__before_first
._M_node
, __last
._M_node
)); }
676 iterator
erase(iterator __pos
)
677 { return iterator(this->_M_erase_after(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
._M_node
))); }
678 iterator
erase(iterator __first
, iterator __last
)
679 { return iterator(this->_M_erase_after(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __first
._M_node
), __last
._M_node
)); }
681 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
682 void resize(size_type new_size
, const value_type
& __x
= _Tp());
684 void resize(size_type new_size
, const value_type
& __x
);
685 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
687 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
688 void resize(size_type new_size
) { resize(new_size
, _STLP_DEFAULT_CONSTRUCTED(_Tp
)); }
689 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
692 { this->_M_erase_after(&this->_M_head
._M_data
, 0); }
695 // Moves the range [__before_first + 1, __before_last + 1) to *this,
696 // inserting it immediately after __pos. This is constant time.
697 void splice_after(iterator __pos
, _Self
& __x
,
698 iterator __before_first
, iterator __before_last
) {
699 if (__before_first
!= __before_last
) {
700 if (this->get_allocator() == __x
.get_allocator()) {
701 _STLP_PRIV
_Sl_global_inst::__splice_after(__pos
._M_node
,
702 __before_first
._M_node
, __before_last
._M_node
);
705 this->insert_after(__pos
, iterator(__before_first
._M_node
->_M_next
), iterator(__before_last
._M_node
->_M_next
));
706 __x
.erase_after(__before_first
, ++__before_last
);
711 // Moves the element that follows __prev to *this, inserting it immediately
712 // after __pos. This is constant time.
713 void splice_after(iterator __pos
, _Self
& __x
, iterator __prev
) {
714 if (this->get_allocator() == __x
.get_allocator()) {
715 _STLP_PRIV
_Sl_global_inst::__splice_after(__pos
._M_node
,
716 __prev
._M_node
, __prev
._M_node
->_M_next
);
719 this->insert_after(__pos
, __STATIC_CAST(_Node
*, __prev
._M_node
->_M_next
)->_M_data
);
720 __x
.erase_after(__prev
);
724 // Removes all of the elements from the list __x to *this, inserting
725 // them immediately after __pos. __x must not be *this. Complexity:
726 // linear in __x.size().
727 void splice_after(iterator __pos
, _Self
& __x
) {
728 if (this->get_allocator() == __x
.get_allocator())
729 _STLP_PRIV
_Sl_global_inst::__splice_after(__pos
._M_node
, &__x
._M_head
._M_data
);
731 this->insert_after(__pos
, __x
.begin(), __x
.end());
736 // Linear in distance(begin(), __pos), and linear in __x.size().
737 void splice(iterator __pos
, _Self
& __x
) {
738 if (__x
._M_head
._M_data
._M_next
) {
739 if (this->get_allocator() == __x
.get_allocator()) {
740 _STLP_PRIV
_Sl_global_inst::__splice_after(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
._M_node
),
741 &__x
._M_head
._M_data
,
742 _STLP_PRIV
_Sl_global_inst::__previous(&__x
._M_head
._M_data
, 0));
745 insert(__pos
, __x
.begin(), __x
.end());
751 // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
752 void splice(iterator __pos
, _Self
& __x
, iterator __i
) {
753 if (this->get_allocator() == __x
.get_allocator()) {
754 _STLP_PRIV
_Sl_global_inst::__splice_after(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
._M_node
),
755 _STLP_PRIV
_Sl_global_inst::__previous(&__x
._M_head
._M_data
, __i
._M_node
),
764 // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
765 // and in distance(__first, __last).
766 void splice(iterator __pos
, _Self
& __x
, iterator __first
, iterator __last
) {
767 if (__first
!= __last
) {
768 if (this->get_allocator() == __x
.get_allocator()) {
769 _STLP_PRIV
_Sl_global_inst::__splice_after(_STLP_PRIV
_Sl_global_inst::__previous(&this->_M_head
._M_data
, __pos
._M_node
),
770 _STLP_PRIV
_Sl_global_inst::__previous(&__x
._M_head
._M_data
, __first
._M_node
),
771 _STLP_PRIV
_Sl_global_inst::__previous(__first
._M_node
, __last
._M_node
));
774 insert(__pos
, __first
, __last
);
775 __x
.erase(__first
, __last
);
782 if (this->_M_head
._M_data
._M_next
)
783 this->_M_head
._M_data
._M_next
= _STLP_PRIV
_Sl_global_inst::__reverse(this->_M_head
._M_data
._M_next
);
786 void remove(const _Tp
& __val
);
788 void unique() { _STLP_PRIV
_Slist_unique(*this, equal_to
<value_type
>()); }
789 void merge(_Self
& __x
) { _STLP_PRIV
_Slist_merge(*this, __x
, less
<value_type
>()); }
790 void sort() { _STLP_PRIV
_Slist_sort(*this, less
<value_type
>()); }
792 #if defined (_STLP_MEMBER_TEMPLATES)
793 template <class _Predicate
>
794 void remove_if(_Predicate __pred
) {
795 _Node_base
* __cur
= &this->_M_head
._M_data
;
796 while (__cur
->_M_next
) {
797 if (__pred(__STATIC_CAST(_Node
*, __cur
->_M_next
)->_M_data
))
798 this->_M_erase_after(__cur
);
800 __cur
= __cur
->_M_next
;
804 template <class _BinaryPredicate
>
805 void unique(_BinaryPredicate __pred
)
806 { _STLP_PRIV
_Slist_unique(*this, __pred
); }
808 template <class _StrictWeakOrdering
>
809 void merge(_Self
& __x
, _StrictWeakOrdering __comp
)
810 { _STLP_PRIV
_Slist_merge(*this, __x
, __comp
); }
812 template <class _StrictWeakOrdering
>
813 void sort(_StrictWeakOrdering __comp
)
814 { _STLP_PRIV
_Slist_sort(*this, __comp
); }
815 #endif /* _STLP_MEMBER_TEMPLATES */
820 _STLP_MOVE_TO_STD_NAMESPACE
825 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
826 # include <stl/_slist.c>
829 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
830 # include <stl/pointers/_slist.h>
833 #if defined (_STLP_DEBUG)
834 # include <stl/debug/_slist.h>
837 _STLP_BEGIN_NAMESPACE
839 template <class _Tp
, class _Alloc
>
840 inline bool _STLP_CALL
841 operator == (const slist
<_Tp
,_Alloc
>& _SL1
, const slist
<_Tp
,_Alloc
>& _SL2
) {
842 typedef typename slist
<_Tp
,_Alloc
>::const_iterator const_iterator
;
843 const_iterator __end1
= _SL1
.end();
844 const_iterator __end2
= _SL2
.end();
846 const_iterator __i1
= _SL1
.begin();
847 const_iterator __i2
= _SL2
.begin();
848 while (__i1
!= __end1
&& __i2
!= __end2
&& *__i1
== *__i2
) {
852 return __i1
== __end1
&& __i2
== __end2
;
855 #define _STLP_EQUAL_OPERATOR_SPECIALIZED
856 #define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
857 #define _STLP_TEMPLATE_CONTAINER slist<_Tp, _Alloc>
858 #include <stl/_relops_cont.h>
859 #undef _STLP_TEMPLATE_CONTAINER
860 #undef _STLP_TEMPLATE_HEADER
861 #undef _STLP_EQUAL_OPERATOR_SPECIALIZED
863 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
864 # if !defined (_STLP_NO_MOVE_SEMANTIC)
865 template <class _Tp
, class _Alloc
>
866 struct __move_traits
<slist
<_Tp
, _Alloc
> > {
867 typedef __true_type implemented
;
868 typedef typename __move_traits
<_Alloc
>::complete complete
;
872 // Specialization of insert_iterator so that insertions will be constant
873 // time rather than linear time.
874 template <class _Tp
, class _Alloc
>
875 class insert_iterator
<slist
<_Tp
, _Alloc
> > {
877 typedef slist
<_Tp
, _Alloc
> _Container
;
878 _Container
* _M_container
;
879 typename
_Container::iterator _M_iter
;
881 typedef _Container container_type
;
882 typedef output_iterator_tag iterator_category
;
883 typedef void value_type
;
884 typedef void difference_type
;
885 typedef void pointer
;
886 typedef void reference
;
888 insert_iterator(_Container
& __x
, typename
_Container::iterator __i
)
889 : _M_container(&__x
) {
890 if (__i
== __x
.begin())
891 _M_iter
= __x
.before_begin();
893 _M_iter
= __x
.previous(__i
);
896 insert_iterator
<_Container
>&
897 operator = (const typename
_Container::value_type
& __val
) {
898 _M_iter
= _M_container
->insert_after(_M_iter
, __val
);
902 insert_iterator
<_Container
>& operator*() { return *this; }
903 insert_iterator
<_Container
>& operator++() { return *this; }
904 insert_iterator
<_Container
>& operator++(int) { return *this; }
906 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
910 #endif /* _STLP_INTERNAL_SLIST_H */