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 typename _Alloc_traits<_Tp,_Alloc>::allocator_type 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 _Slist_base(__move_source<_Self> src) :
165 _M_head(__move_source<_AllocProxy>(src.get()._M_head)) {
166 src.get()._M_head._M_data._M_next = 0;
168 ~_Slist_base() { _M_erase_after(&_M_head._M_data, 0); }
171 _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) {
172 _Node* __next = __STATIC_CAST(_Node*, __pos->_M_next);
173 _Slist_node_base* __next_next = __next->_M_next;
174 __pos->_M_next = __next_next;
175 _STLP_STD::_Destroy(&__next->_M_data);
176 _M_head.deallocate(__next,1);
179 _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
182 allocator_type get_allocator() const
183 { return _STLP_CONVERT_ALLOCATOR((const _M_node_allocator_type&)_M_head, _Tp); }
187 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
188 # define slist _STLP_PTR_IMPL_NAME(slist)
189 #elif defined (_STLP_DEBUG)
190 # define slist _STLP_NON_DBG_NAME(slist)
192 _STLP_MOVE_TO_STD_NAMESPACE
195 template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
199 _STLP_MOVE_TO_PRIV_NAMESPACE
202 // helper functions to reduce code duplication
203 template <class _Tp, class _Alloc, class _BinaryPredicate>
204 void _Slist_unique(slist<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred);
206 template <class _Tp, class _Alloc, class _StrictWeakOrdering>
207 void _Slist_merge(slist<_Tp, _Alloc>& __that, slist<_Tp, _Alloc>& __x,
208 _StrictWeakOrdering __comp);
210 template <class _Tp, class _Alloc, class _StrictWeakOrdering>
211 void _Slist_sort(slist<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp);
214 _STLP_MOVE_TO_STD_NAMESPACE
217 template <class _Tp, class _Alloc>
218 class slist : protected _STLP_PRIV _Slist_base<_Tp,_Alloc>
219 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (slist)
220 , public __stlport_class<slist<_Tp, _Alloc> >
224 typedef _STLP_PRIV _Slist_base<_Tp,_Alloc> _Base;
225 typedef slist<_Tp,_Alloc> _Self;
227 typedef _Tp value_type;
229 typedef value_type* pointer;
230 typedef const value_type* const_pointer;
231 typedef value_type& reference;
232 typedef const value_type& const_reference;
233 typedef size_t size_type;
234 typedef ptrdiff_t difference_type;
235 typedef forward_iterator_tag _Iterator_category;
237 typedef _STLP_PRIV _Slist_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
238 typedef _STLP_PRIV _Slist_iterator<_Tp, _Const_traits<_Tp> > const_iterator;
240 _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
241 typedef typename _Base::allocator_type allocator_type;
244 typedef _STLP_PRIV _Slist_node<_Tp> _Node;
245 typedef _STLP_PRIV _Slist_node_base _Node_base;
247 #if !defined(_STLP_DONT_SUP_DFLT_PARAM)
248 _Node* _M_create_node(const value_type& __x = _Tp()) {
250 _Node* _M_create_node(const value_type& __x) {
251 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
252 _Node* __node = this->_M_head.allocate(1);
254 _Copy_Construct(&__node->_M_data, __x);
257 _STLP_UNWIND(this->_M_head.deallocate(__node, 1))
261 #if defined(_STLP_DONT_SUP_DFLT_PARAM)
262 _Node* _M_create_node() {
263 _Node* __node = this->_M_head.allocate(1);
265 _STLP_STD::_Construct(&__node->_M_data);
268 _STLP_UNWIND(this->_M_head.deallocate(__node, 1))
271 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
275 allocator_type get_allocator() const { return _Base::get_allocator(); }
277 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
278 explicit slist(const allocator_type& __a = allocator_type())
281 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(allocator_type()) {}
282 slist(const allocator_type& __a)
284 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a) {}
286 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
287 explicit slist(size_type __n, const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp),
288 const allocator_type& __a = allocator_type())
290 explicit slist(size_type __n)
291 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(allocator_type())
292 { _M_insert_after_fill(&this->_M_head._M_data, __n, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
293 slist(size_type __n, const value_type& __x)
294 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(allocator_type())
295 { _M_insert_after_fill(&this->_M_head._M_data, __n, __x); }
296 slist(size_type __n, const value_type& __x, const allocator_type& __a)
298 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a)
299 { _M_insert_after_fill(&this->_M_head._M_data, __n, __x); }
301 #if defined (_STLP_MEMBER_TEMPLATES)
302 // We don't need any dispatching tricks here, because _M_insert_after_range
303 // already does them.
304 template <class _InputIterator>
305 slist(_InputIterator __first, _InputIterator __last,
306 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
307 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a)
308 { _M_insert_after_range(&this->_M_head._M_data, __first, __last); }
309 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
310 // VC++ needs this crazyness
311 template <class _InputIterator>
312 slist(_InputIterator __first, _InputIterator __last)
313 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(allocator_type())
314 { _M_insert_after_range(&this->_M_head._M_data, __first, __last); }
316 #else /* _STLP_MEMBER_TEMPLATES */
317 slist(const_iterator __first, const_iterator __last,
318 const allocator_type& __a = allocator_type() )
319 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a)
320 { _M_insert_after_range(&this->_M_head._M_data, __first, __last); }
321 slist(const value_type* __first, const value_type* __last,
322 const allocator_type& __a = allocator_type())
323 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a)
324 { _M_insert_after_range(&this->_M_head._M_data, __first, __last); }
325 #endif /* _STLP_MEMBER_TEMPLATES */
327 slist(const _Self& __x)
328 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__x.get_allocator())
329 { _M_insert_after_range(&this->_M_head._M_data, __x.begin(), __x.end()); }
331 slist(__move_source<_Self> src)
332 : _STLP_PRIV _Slist_base<_Tp, _Alloc>(__move_source<_Base>(src.get())) {}
334 _Self& operator= (const _Self& __x);
339 // assign(), a generalized assignment member function. Two
340 // versions: one that takes a count, and one that takes a range.
341 // The range version is a member template, so we dispatch on whether
342 // or not the type is an integer.
344 void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
347 void _M_fill_assign(size_type __n, const _Tp& __val);
349 #if defined (_STLP_MEMBER_TEMPLATES)
351 template <class _InputIterator>
352 void assign(_InputIterator __first, _InputIterator __last) {
353 typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
354 _M_assign_dispatch(__first, __last, _Integral());
358 template <class _Integer>
359 void _M_assign_dispatch(_Integer __n, _Integer __val,
360 const __true_type& /*_IsIntegral*/) {
361 _M_fill_assign((size_type) __n, (_Tp) __val);
364 template <class _InputIter>
365 void _M_assign_dispatch(_InputIter __first, _InputIter __last,
366 const __false_type& /*_IsIntegral*/) {
369 void assign(const_pointer __first, const_pointer __last) {
370 _Node_base* __prev = &this->_M_head._M_data;
371 _Node_base* __node = this->_M_head._M_data._M_next;
372 while (__node != 0 && __first != __last) {
373 __STATIC_CAST(_Node*, __node)->_M_data = *__first;
375 __node = __node->_M_next;
378 if (__first != __last)
379 _M_insert_after_range(__prev, __first, __last);
381 this->_M_erase_after(__prev, 0);
383 void assign(const_iterator __first, const_iterator __last) {
384 #endif /* _STLP_MEMBER_TEMPLATES */
385 _Node_base* __prev = &this->_M_head._M_data;
386 _Node_base* __node = this->_M_head._M_data._M_next;
387 while (__node != 0 && __first != __last) {
388 __STATIC_CAST(_Node*, __node)->_M_data = *__first;
390 __node = __node->_M_next;
393 if (__first != __last)
394 _M_insert_after_range(__prev, __first, __last);
396 this->_M_erase_after(__prev, 0);
401 // Experimental new feature: before_begin() returns a
402 // non-dereferenceable iterator that, when incremented, yields
403 // begin(). This iterator may be used as the argument to
404 // insert_after, erase_after, etc. Note that even for an empty
405 // slist, before_begin() is not the same iterator as end(). It
406 // is always necessary to increment before_begin() at least once to
408 iterator before_begin() { return iterator(&this->_M_head._M_data); }
409 const_iterator before_begin() const
410 { return const_iterator(__CONST_CAST(_Node_base*, &this->_M_head._M_data)); }
412 iterator begin() { return iterator(this->_M_head._M_data._M_next); }
413 const_iterator begin() const
414 { return const_iterator(this->_M_head._M_data._M_next);}
416 iterator end() { return iterator(); }
417 const_iterator end() const { return const_iterator(); }
419 size_type size() const
420 { return _STLP_PRIV _Sl_global_inst::size(this->_M_head._M_data._M_next); }
422 size_type max_size() const { return size_type(-1); }
424 bool empty() const { return this->_M_head._M_data._M_next == 0; }
426 void swap(_Self& __x) {
427 this->_M_head.swap(__x._M_head);
431 reference front() { return *begin(); }
432 const_reference front() const { return *begin(); }
433 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
434 void push_front(const value_type& __x = _Tp()) {
436 void push_front(const value_type& __x) {
437 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
438 _STLP_PRIV __slist_make_link(&this->_M_head._M_data, _M_create_node(__x));
441 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
442 void push_front() { _STLP_PRIV __slist_make_link(&this->_M_head._M_data, _M_create_node());}
443 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
446 _Node* __node = __STATIC_CAST(_Node*, this->_M_head._M_data._M_next);
447 this->_M_head._M_data._M_next = __node->_M_next;
448 _STLP_STD::_Destroy(&__node->_M_data);
449 this->_M_head.deallocate(__node, 1);
452 iterator previous(const_iterator __pos) {
453 return iterator(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node));
455 const_iterator previous(const_iterator __pos) const {
456 return const_iterator(__CONST_CAST(_Node_base*,
457 _STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data,
462 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
463 _Node* _M_insert_after(_Node_base* __pos, const value_type& __x = _Tp()) {
465 _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
466 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
467 return __STATIC_CAST(_Node*, _STLP_PRIV __slist_make_link(__pos, _M_create_node(__x)));
470 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
471 _Node* _M_insert_after(_Node_base* __pos) {
472 return __STATIC_CAST(_Node*, _STLP_PRIV __slist_make_link(__pos, _M_create_node()));
474 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
476 void _M_insert_after_fill(_Node_base* __pos,
477 size_type __n, const value_type& __x) {
478 for (size_type __i = 0; __i < __n; ++__i)
479 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(__x));
482 #if defined (_STLP_MEMBER_TEMPLATES)
483 // Check whether it's an integral type. If so, it's not an iterator.
484 template <class _InIter>
485 void _M_insert_after_range(_Node_base* __pos,
486 _InIter __first, _InIter __last) {
487 typedef typename _IsIntegral<_InIter>::_Ret _Integral;
488 _M_insert_after_range(__pos, __first, __last, _Integral());
491 template <class _Integer>
492 void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
493 const __true_type&) {
494 _M_insert_after_fill(__pos, __n, __x);
497 template <class _InIter>
498 void _M_insert_after_range(_Node_base* __pos,
499 _InIter __first, _InIter __last,
500 const __false_type&) {
501 #else /* _STLP_MEMBER_TEMPLATES */
502 void _M_insert_after_range(_Node_base* __pos,
503 const value_type* __first,
504 const value_type* __last) {
505 while (__first != __last) {
506 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(*__first));
510 void _M_insert_after_range(_Node_base* __pos,
511 const_iterator __first, const_iterator __last) {
512 #endif /* _STLP_MEMBER_TEMPLATES */
513 while (__first != __last) {
514 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(*__first));
519 #if defined (_STLP_MEMBER_TEMPLATES)
520 // Check whether it's an integral type. If so, it's not an iterator.
521 template <class _InIter>
522 void _M_splice_after_range(_Node_base* __pos,
523 _InIter __first, _InIter __last) {
524 typedef typename _IsIntegral<_InIter>::_Ret _Integral;
525 _M_splice_after_range(__pos, __first, __last, _Integral());
528 template <class _Integer>
529 void _M_splice_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
530 const __true_type&) {
531 _M_insert_after_fill(__pos, __n, __x);
534 template <class _InIter>
535 void _M_splice_after_range(_Node_base* __pos,
536 _InIter __first, _InIter __last,
537 const __false_type&) {
538 #else /* _STLP_MEMBER_TEMPLATES */
539 void _M_splice_after_range(_Node_base* __pos,
540 const value_type* __first,
541 const value_type* __last) {
542 while (__first != __last) {
543 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(*__first));
547 void _M_splice_after_range(_Node_base* __pos,
548 const_iterator __first, const_iterator __last) {
549 #endif /* _STLP_MEMBER_TEMPLATES */
550 //We use a temporary slist to avoid the auto reference troubles (infinite loop)
551 _Self __tmp(__first, __last, this->get_allocator());
552 splice_after(iterator(__pos), __tmp);
555 #if defined (_STLP_MEMBER_TEMPLATES)
556 // Check whether it's an integral type. If so, it's not an iterator.
557 template <class _InIter>
558 void _M_splice_range(_Node_base* __pos,
559 _InIter __first, _InIter __last) {
560 typedef typename _IsIntegral<_InIter>::_Ret _Integral;
561 _M_splice_range(__pos, __first, __last, _Integral());
564 template <class _Integer>
565 void _M_splice_range(_Node_base* __pos, _Integer __n, _Integer __x,
566 const __true_type&) {
567 _M_insert_after_fill(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos),
571 template <class _InIter>
572 void _M_splice_range(_Node_base* __pos,
573 _InIter __first, _InIter __last,
574 const __false_type&) {
575 #else /* _STLP_MEMBER_TEMPLATES */
576 void _M_splice_range(_Node_base* __pos,
577 const value_type* __first,
578 const value_type* __last) {
579 while (__first != __last) {
580 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(*__first));
584 void _M_splice_range(_Node_base* __pos,
585 const_iterator __first, const_iterator __last) {
586 #endif /* _STLP_MEMBER_TEMPLATES */
587 //We use a temporary slist to avoid the auto reference troubles (infinite loop)
588 _Self __tmp(__first, __last, this->get_allocator());
589 splice(iterator(__pos), __tmp);
594 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
595 iterator insert_after(iterator __pos, const value_type& __x = _Tp()) {
597 iterator insert_after(iterator __pos, const value_type& __x) {
598 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
599 return iterator(_M_insert_after(__pos._M_node, __x));
602 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
603 iterator insert_after(iterator __pos) {
604 return insert_after(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp));
606 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
608 void insert_after(iterator __pos, size_type __n, const value_type& __x) {
609 _M_insert_after_fill(__pos._M_node, __n, __x);
612 #if defined (_STLP_MEMBER_TEMPLATES)
613 // We don't need any dispatching tricks here, because _M_insert_after_range
614 // already does them.
615 template <class _InIter>
616 void insert_after(iterator __pos, _InIter __first, _InIter __last) {
617 #else /* _STLP_MEMBER_TEMPLATES */
618 void insert_after(iterator __pos,
619 const value_type* __first, const value_type* __last) {
620 _M_insert_after_range(__pos._M_node, __first, __last);
622 void insert_after(iterator __pos,
623 const_iterator __first, const_iterator __last) {
624 #endif /* _STLP_MEMBER_TEMPLATES */
625 _M_splice_after_range(__pos._M_node, __first, __last);
628 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
629 iterator insert(iterator __pos, const value_type& __x = _Tp()) {
631 iterator insert(iterator __pos, const value_type& __x) {
632 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
633 return iterator(_M_insert_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
637 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
638 iterator insert(iterator __pos) {
639 return iterator(_M_insert_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
640 _STLP_DEFAULT_CONSTRUCTED(_Tp)));
642 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
644 void insert(iterator __pos, size_type __n, const value_type& __x) {
645 _M_insert_after_fill(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), __n, __x);
648 #if defined (_STLP_MEMBER_TEMPLATES)
649 // We don't need any dispatching tricks here, because _M_insert_after_range
650 // already does them.
651 template <class _InIter>
652 void insert(iterator __pos, _InIter __first, _InIter __last) {
653 #else /* _STLP_MEMBER_TEMPLATES */
654 void insert(iterator __pos, const value_type* __first,
655 const value_type* __last) {
656 _M_insert_after_range(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
659 void insert(iterator __pos, const_iterator __first, const_iterator __last) {
660 #endif /* _STLP_MEMBER_TEMPLATES */
661 _M_splice_range(__pos._M_node, __first, __last);
665 iterator erase_after(iterator __pos)
666 { return iterator(this->_M_erase_after(__pos._M_node)); }
667 iterator erase_after(iterator __before_first, iterator __last)
668 { return iterator(this->_M_erase_after(__before_first._M_node, __last._M_node)); }
670 iterator erase(iterator __pos)
671 { return iterator(this->_M_erase_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node))); }
672 iterator erase(iterator __first, iterator __last)
673 { return iterator(this->_M_erase_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __first._M_node), __last._M_node)); }
675 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
676 void resize(size_type new_size, const value_type& __x = _Tp());
678 void resize(size_type new_size, const value_type& __x);
679 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
681 #if defined (_STLP_DONT_SUP_DFLT_PARAM)
682 void resize(size_type new_size) { resize(new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
683 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
686 { this->_M_erase_after(&this->_M_head._M_data, 0); }
689 // Moves the range [__before_first + 1, __before_last + 1) to *this,
690 // inserting it immediately after __pos. This is constant time.
691 void splice_after(iterator __pos, _Self& __x,
692 iterator __before_first, iterator __before_last) {
693 if (__before_first != __before_last) {
694 if (this->get_allocator() == __x.get_allocator()) {
695 _STLP_PRIV _Sl_global_inst::__splice_after(__pos._M_node,
696 __before_first._M_node, __before_last._M_node);
699 this->insert_after(__pos, iterator(__before_first._M_node->_M_next), iterator(__before_last._M_node->_M_next));
700 __x.erase_after(__before_first, ++__before_last);
705 // Moves the element that follows __prev to *this, inserting it immediately
706 // after __pos. This is constant time.
707 void splice_after(iterator __pos, _Self& __x, iterator __prev) {
708 if (this->get_allocator() == __x.get_allocator()) {
709 _STLP_PRIV _Sl_global_inst::__splice_after(__pos._M_node,
710 __prev._M_node, __prev._M_node->_M_next);
713 this->insert_after(__pos, __STATIC_CAST(_Node*, __prev._M_node->_M_next)->_M_data);
714 __x.erase_after(__prev);
718 // Removes all of the elements from the list __x to *this, inserting
719 // them immediately after __pos. __x must not be *this. Complexity:
720 // linear in __x.size().
721 void splice_after(iterator __pos, _Self& __x) {
722 if (this->get_allocator() == __x.get_allocator())
723 _STLP_PRIV _Sl_global_inst::__splice_after(__pos._M_node, &__x._M_head._M_data);
725 this->insert_after(__pos, __x.begin(), __x.end());
730 // Linear in distance(begin(), __pos), and linear in __x.size().
731 void splice(iterator __pos, _Self& __x) {
732 if (__x._M_head._M_data._M_next) {
733 if (this->get_allocator() == __x.get_allocator()) {
734 _STLP_PRIV _Sl_global_inst::__splice_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
735 &__x._M_head._M_data,
736 _STLP_PRIV _Sl_global_inst::__previous(&__x._M_head._M_data, 0));
739 insert(__pos, __x.begin(), __x.end());
745 // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
746 void splice(iterator __pos, _Self& __x, iterator __i) {
747 if (this->get_allocator() == __x.get_allocator()) {
748 _STLP_PRIV _Sl_global_inst::__splice_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
749 _STLP_PRIV _Sl_global_inst::__previous(&__x._M_head._M_data, __i._M_node),
758 // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
759 // and in distance(__first, __last).
760 void splice(iterator __pos, _Self& __x, iterator __first, iterator __last) {
761 if (__first != __last) {
762 if (this->get_allocator() == __x.get_allocator()) {
763 _STLP_PRIV _Sl_global_inst::__splice_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
764 _STLP_PRIV _Sl_global_inst::__previous(&__x._M_head._M_data, __first._M_node),
765 _STLP_PRIV _Sl_global_inst::__previous(__first._M_node, __last._M_node));
768 insert(__pos, __first, __last);
769 __x.erase(__first, __last);
776 if (this->_M_head._M_data._M_next)
777 this->_M_head._M_data._M_next = _STLP_PRIV _Sl_global_inst::__reverse(this->_M_head._M_data._M_next);
780 void remove(const _Tp& __val);
782 void unique() { _STLP_PRIV _Slist_unique(*this, equal_to<value_type>()); }
783 void merge(_Self& __x) { _STLP_PRIV _Slist_merge(*this, __x, less<value_type>()); }
784 void sort() { _STLP_PRIV _Slist_sort(*this, less<value_type>()); }
786 #if defined (_STLP_MEMBER_TEMPLATES)
787 template <class _Predicate>
788 void remove_if(_Predicate __pred) {
789 _Node_base* __cur = &this->_M_head._M_data;
790 while (__cur->_M_next) {
791 if (__pred(__STATIC_CAST(_Node*, __cur->_M_next)->_M_data))
792 this->_M_erase_after(__cur);
794 __cur = __cur->_M_next;
798 template <class _BinaryPredicate>
799 void unique(_BinaryPredicate __pred)
800 { _STLP_PRIV _Slist_unique(*this, __pred); }
802 template <class _StrictWeakOrdering>
803 void merge(_Self& __x, _StrictWeakOrdering __comp)
804 { _STLP_PRIV _Slist_merge(*this, __x, __comp); }
806 template <class _StrictWeakOrdering>
807 void sort(_StrictWeakOrdering __comp)
808 { _STLP_PRIV _Slist_sort(*this, __comp); }
809 #endif /* _STLP_MEMBER_TEMPLATES */
814 _STLP_MOVE_TO_STD_NAMESPACE
819 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
820 # include <stl/_slist.c>
823 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
824 # include <stl/pointers/_slist.h>
827 #if defined (_STLP_DEBUG)
828 # include <stl/debug/_slist.h>
831 _STLP_BEGIN_NAMESPACE
833 template <class _Tp, class _Alloc>
834 inline bool _STLP_CALL
835 operator == (const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
836 typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
837 const_iterator __end1 = _SL1.end();
838 const_iterator __end2 = _SL2.end();
840 const_iterator __i1 = _SL1.begin();
841 const_iterator __i2 = _SL2.begin();
842 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
846 return __i1 == __end1 && __i2 == __end2;
849 #define _STLP_EQUAL_OPERATOR_SPECIALIZED
850 #define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
851 #define _STLP_TEMPLATE_CONTAINER slist<_Tp, _Alloc>
852 #include <stl/_relops_cont.h>
853 #undef _STLP_TEMPLATE_CONTAINER
854 #undef _STLP_TEMPLATE_HEADER
855 #undef _STLP_EQUAL_OPERATOR_SPECIALIZED
857 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
858 template <class _Tp, class _Alloc>
859 struct __move_traits<slist<_Tp, _Alloc> > {
860 typedef __stlp_movable implemented;
861 typedef typename __move_traits<_Alloc>::complete complete;
864 // Specialization of insert_iterator so that insertions will be constant
865 // time rather than linear time.
866 template <class _Tp, class _Alloc>
867 class insert_iterator<slist<_Tp, _Alloc> > {
869 typedef slist<_Tp, _Alloc> _Container;
870 _Container* _M_container;
871 typename _Container::iterator _M_iter;
873 typedef _Container container_type;
874 typedef output_iterator_tag iterator_category;
875 typedef void value_type;
876 typedef void difference_type;
877 typedef void pointer;
878 typedef void reference;
880 insert_iterator(_Container& __x, typename _Container::iterator __i)
881 : _M_container(&__x) {
882 if (__i == __x.begin())
883 _M_iter = __x.before_begin();
885 _M_iter = __x.previous(__i);
888 insert_iterator<_Container>&
889 operator = (const typename _Container::value_type& __val) {
890 _M_iter = _M_container->insert_after(_M_iter, __val);
894 insert_iterator<_Container>& operator*() { return *this; }
895 insert_iterator<_Container>& operator++() { return *this; }
896 insert_iterator<_Container>& operator++(int) { return *this; }
898 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
902 #endif /* _STLP_INTERNAL_SLIST_H */