docs/ikteam: Delete most files.
[haiku.git] / headers / cpp / stl_list.h
blob5d95d641e52d16d206e372369f115eb55a3458fc
1 /*
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation. Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
15 * Copyright (c) 1996,1997
16 * Silicon Graphics Computer Systems, Inc.
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation. Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose. It is provided "as is" without express or implied warranty.
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
31 #ifndef __SGI_STL_INTERNAL_LIST_H
32 #define __SGI_STL_INTERNAL_LIST_H
34 __STL_BEGIN_NAMESPACE
36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
37 #pragma set woff 1174
38 #pragma set woff 1375
39 #endif
41 template <class _Tp>
42 struct _List_node {
43 typedef void* _Void_pointer;
44 _Void_pointer _M_next;
45 _Void_pointer _M_prev;
46 _Tp _M_data;
49 template<class _Tp, class _Ref, class _Ptr>
50 struct _List_iterator {
51 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
52 typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
53 typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;
55 typedef bidirectional_iterator_tag iterator_category;
56 typedef _Tp value_type;
57 typedef _Ptr pointer;
58 typedef _Ref reference;
59 typedef _List_node<_Tp> _Node;
60 typedef size_t size_type;
61 typedef ptrdiff_t difference_type;
63 _Node* _M_node;
65 _List_iterator(_Node* __x) : _M_node(__x) {}
66 _List_iterator() {}
67 _List_iterator(const iterator& __x) : _M_node(__x._M_node) {}
69 bool operator==(const _Self& __x) const { return _M_node == __x._M_node; }
70 bool operator!=(const _Self& __x) const { return _M_node != __x._M_node; }
71 reference operator*() const { return (*_M_node)._M_data; }
73 #ifndef __SGI_STL_NO_ARROW_OPERATOR
74 pointer operator->() const { return &(operator*()); }
75 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
77 _Self& operator++() {
78 _M_node = (_Node*)(_M_node->_M_next);
79 return *this;
81 _Self operator++(int) {
82 _Self __tmp = *this;
83 ++*this;
84 return __tmp;
86 _Self& operator--() {
87 _M_node = (_Node*)(_M_node->_M_prev);
88 return *this;
90 _Self operator--(int) {
91 _Self __tmp = *this;
92 --*this;
93 return __tmp;
97 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
99 template <class _Tp, class _Ref, class _Ptr>
100 inline bidirectional_iterator_tag
101 iterator_category(const _List_iterator<_Tp, _Ref, _Ptr>&)
103 return bidirectional_iterator_tag();
106 template <class _Tp, class _Ref, class _Ptr>
107 inline _Tp*
108 value_type(const _List_iterator<_Tp, _Ref, _Ptr>&)
110 return 0;
113 template <class _Tp, class _Ref, class _Ptr>
114 inline ptrdiff_t*
115 distance_type(const _List_iterator<_Tp, _Ref, _Ptr>&)
117 return 0;
120 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
123 // Base class that encapsulates details of allocators. Three cases:
124 // an ordinary standard-conforming allocator, a standard-conforming
125 // allocator with no non-static data, and an SGI-style allocator.
126 // This complexity is necessary only because we're worrying about backward
127 // compatibility and because we want to avoid wasting storage on an
128 // allocator instance if it isn't necessary.
130 #ifdef __STL_USE_STD_ALLOCATORS
132 // Base for general standard-conforming allocators.
133 template <class _Tp, class _Allocator, bool _IsStatic>
134 class _List_alloc_base {
135 public:
136 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
137 allocator_type;
138 allocator_type get_allocator() const { return _Node_allocator; }
140 _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
142 protected:
143 _List_node<_Tp>* _M_get_node()
144 { return _Node_allocator.allocate(1); }
145 void _M_put_node(_List_node<_Tp>* __p)
146 { _Node_allocator.deallocate(__p, 1); }
148 protected:
149 typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
150 _Node_allocator;
151 _List_node<_Tp>* _M_node;
154 // Specialization for instanceless allocators.
156 template <class _Tp, class _Allocator>
157 class _List_alloc_base<_Tp, _Allocator, true> {
158 public:
159 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
160 allocator_type;
161 allocator_type get_allocator() const { return allocator_type(); }
163 _List_alloc_base(const allocator_type&) {}
165 protected:
166 typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
167 _Alloc_type;
168 _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
169 void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
171 protected:
172 _List_node<_Tp>* _M_node;
175 template <class _Tp, class _Alloc>
176 class _List_base
177 : public _List_alloc_base<_Tp, _Alloc,
178 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
180 public:
181 typedef _List_alloc_base<_Tp, _Alloc,
182 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
183 _Base;
184 typedef typename _Base::allocator_type allocator_type;
186 _List_base(const allocator_type& __a) : _Base(__a) {
187 _M_node = _M_get_node();
188 _M_node->_M_next = _M_node;
189 _M_node->_M_prev = _M_node;
191 ~_List_base() {
192 clear();
193 _M_put_node(_M_node);
196 void clear();
199 #else /* __STL_USE_STD_ALLOCATORS */
201 template <class _Tp, class _Alloc>
202 class _List_base
204 public:
205 typedef _Alloc allocator_type;
206 allocator_type get_allocator() const { return allocator_type(); }
208 _List_base(const allocator_type&) {
209 _M_node = _M_get_node();
210 _M_node->_M_next = _M_node;
211 _M_node->_M_prev = _M_node;
213 ~_List_base() {
214 clear();
215 _M_put_node(_M_node);
218 void clear();
220 protected:
221 typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type;
222 _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
223 void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
225 protected:
226 _List_node<_Tp>* _M_node;
229 #endif /* __STL_USE_STD_ALLOCATORS */
231 template <class _Tp, class _Alloc>
232 void
233 _List_base<_Tp,_Alloc>::clear()
235 _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next;
236 while (__cur != _M_node) {
237 _List_node<_Tp>* __tmp = __cur;
238 __cur = (_List_node<_Tp>*) __cur->_M_next;
239 destroy(&__tmp->_M_data);
240 _M_put_node(__tmp);
242 _M_node->_M_next = _M_node;
243 _M_node->_M_prev = _M_node;
246 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
247 class list : protected _List_base<_Tp, _Alloc> {
248 typedef _List_base<_Tp, _Alloc> _Base;
249 protected:
250 typedef void* _Void_pointer;
252 public:
253 typedef _Tp value_type;
254 typedef value_type* pointer;
255 typedef const value_type* const_pointer;
256 typedef value_type& reference;
257 typedef const value_type& const_reference;
258 typedef _List_node<_Tp> _Node;
259 typedef size_t size_type;
260 typedef ptrdiff_t difference_type;
262 typedef typename _Base::allocator_type allocator_type;
263 allocator_type get_allocator() const { return _Base::get_allocator(); }
265 public:
266 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
267 typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
269 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
270 typedef reverse_iterator<const_iterator> const_reverse_iterator;
271 typedef reverse_iterator<iterator> reverse_iterator;
272 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
273 typedef reverse_bidirectional_iterator<const_iterator,value_type,
274 const_reference,difference_type>
275 const_reverse_iterator;
276 typedef reverse_bidirectional_iterator<iterator,value_type,reference,
277 difference_type>
278 reverse_iterator;
279 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
281 protected:
282 #ifdef __STL_HAS_NAMESPACES
283 using _Base::_M_node;
284 using _Base::_M_put_node;
285 using _Base::_M_get_node;
286 #endif /* __STL_HAS_NAMESPACES */
288 protected:
289 _Node* _M_create_node(const _Tp& __x)
291 _Node* __p = _M_get_node();
292 __STL_TRY {
293 construct(&__p->_M_data, __x);
295 __STL_UNWIND(_M_put_node(__p));
296 return __p;
299 _Node* _M_create_node()
301 _Node* __p = _M_get_node();
302 __STL_TRY {
303 construct(&__p->_M_data);
305 __STL_UNWIND(_M_put_node(__p));
306 return __p;
309 public:
310 explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
312 iterator begin() { return (_Node*)(_M_node->_M_next); }
313 const_iterator begin() const { return (_Node*)(_M_node->_M_next); }
315 iterator end() { return _M_node; }
316 const_iterator end() const { return _M_node; }
318 reverse_iterator rbegin()
319 { return reverse_iterator(end()); }
320 const_reverse_iterator rbegin() const
321 { return const_reverse_iterator(end()); }
323 reverse_iterator rend()
324 { return reverse_iterator(begin()); }
325 const_reverse_iterator rend() const
326 { return const_reverse_iterator(begin()); }
328 bool empty() const { return _M_node->_M_next == _M_node; }
329 size_type size() const {
330 size_type __result = 0;
331 distance(begin(), end(), __result);
332 return __result;
334 size_type max_size() const { return size_type(-1); }
336 reference front() { return *begin(); }
337 const_reference front() const { return *begin(); }
338 reference back() { return *(--end()); }
339 const_reference back() const { return *(--end()); }
341 void swap(list<_Tp, _Alloc>& __x) { __STD::swap(_M_node, __x._M_node); }
343 iterator insert(iterator __position, const _Tp& __x) {
344 _Node* __tmp = _M_create_node(__x);
345 __tmp->_M_next = __position._M_node;
346 __tmp->_M_prev = __position._M_node->_M_prev;
347 ((_Node*) (__position._M_node->_M_prev))->_M_next = __tmp;
348 __position._M_node->_M_prev = __tmp;
349 return __tmp;
351 iterator insert(iterator __position) { return insert(__position, _Tp()); }
352 #ifdef __STL_MEMBER_TEMPLATES
353 // Check whether it's an integral type. If so, it's not an iterator.
355 template<class _Integer>
356 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
357 __true_type) {
358 insert(__pos, (size_type) __n, (_Tp) __x);
361 template <class _InputIterator>
362 void _M_insert_dispatch(iterator __pos,
363 _InputIterator __first, _InputIterator __last,
364 __false_type);
366 template <class _InputIterator>
367 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
368 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
369 _M_insert_dispatch(__pos, __first, __last, _Integral());
372 #else /* __STL_MEMBER_TEMPLATES */
373 void insert(iterator __position, const _Tp* __first, const _Tp* __last);
374 void insert(iterator __position,
375 const_iterator __first, const_iterator __last);
376 #endif /* __STL_MEMBER_TEMPLATES */
377 void insert(iterator __pos, size_type __n, const _Tp& __x);
379 void push_front(const _Tp& __x) { insert(begin(), __x); }
380 void push_front() {insert(begin());}
381 void push_back(const _Tp& __x) { insert(end(), __x); }
382 void push_back() {insert(end());}
384 iterator erase(iterator __position) {
385 _Node* __next_node = (_Node*) (__position._M_node->_M_next);
386 _Node* __prev_node = (_Node*) (__position._M_node->_M_prev);
387 __prev_node->_M_next = __next_node;
388 __next_node->_M_prev = __prev_node;
389 destroy(&__position._M_node->_M_data);
390 _M_put_node(__position._M_node);
391 return iterator(__next_node);
393 iterator erase(iterator __first, iterator __last);
394 void clear() { _Base::clear(); }
396 void resize(size_type __new_size, const _Tp& __x);
397 void resize(size_type __new_size) { resize(__new_size, _Tp()); }
399 void pop_front() { erase(begin()); }
400 void pop_back() {
401 iterator __tmp = end();
402 erase(--__tmp);
404 list(size_type __n, const _Tp& __value,
405 const allocator_type& __a = allocator_type())
406 : _Base(__a)
407 { insert(begin(), __n, __value); }
408 explicit list(size_type __n)
409 : _Base(allocator_type())
410 { insert(begin(), __n, _Tp()); }
412 #ifdef __STL_MEMBER_TEMPLATES
414 // We don't need any dispatching tricks here, because insert does all of
415 // that anyway.
416 template <class _InputIterator>
417 list(_InputIterator __first, _InputIterator __last,
418 const allocator_type& __a = allocator_type())
419 : _Base(__a)
420 { insert(begin(), __first, __last); }
422 #else /* __STL_MEMBER_TEMPLATES */
424 list(const _Tp* __first, const _Tp* __last,
425 const allocator_type& __a = allocator_type())
426 : _Base(__a)
427 { insert(begin(), __first, __last); }
428 list(const_iterator __first, const_iterator __last,
429 const allocator_type& __a = allocator_type())
430 : _Base(__a)
431 { insert(begin(), __first, __last); }
433 #endif /* __STL_MEMBER_TEMPLATES */
434 list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())
435 { insert(begin(), __x.begin(), __x.end()); }
437 ~list() { }
439 list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x);
441 public:
442 // assign(), a generalized assignment member function. Two
443 // versions: one that takes a count, and one that takes a range.
444 // The range version is a member template, so we dispatch on whether
445 // or not the type is an integer.
447 void assign(size_type __n, const _Tp& __val);
449 #ifdef __STL_MEMBER_TEMPLATES
451 template <class _InputIterator>
452 void assign(_InputIterator __first, _InputIterator __last) {
453 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
454 _M_assign_dispatch(__first, __last, _Integral());
457 template <class _Integer>
458 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
459 { assign((size_type) __n, (_Tp) __val); }
461 template <class _InputIterator>
462 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
463 __false_type);
465 #endif /* __STL_MEMBER_TEMPLATES */
467 protected:
468 void transfer(iterator __position, iterator __first, iterator __last) {
469 if (__position != __last) {
470 // Remove [first, last) from its old position.
471 ((_Node*) (__last._M_node->_M_prev))->_M_next = __position._M_node;
472 ((_Node*) (__first._M_node->_M_prev))->_M_next = __last._M_node;
473 ((_Node*) (__position._M_node->_M_prev))->_M_next = __first._M_node;
475 // Splice [first, last) into its new position.
476 _Node* __tmp = (_Node*) (__position._M_node->_M_prev);
477 __position._M_node->_M_prev = __last._M_node->_M_prev;
478 __last._M_node->_M_prev = __first._M_node->_M_prev;
479 __first._M_node->_M_prev = __tmp;
483 public:
484 void splice(iterator __position, list& __x) {
485 if (!__x.empty())
486 transfer(__position, __x.begin(), __x.end());
488 void splice(iterator __position, list&, iterator __i) {
489 iterator __j = __i;
490 ++__j;
491 if (__position == __i || __position == __j) return;
492 transfer(__position, __i, __j);
494 void splice(iterator __position, list&, iterator __first, iterator __last) {
495 if (__first != __last)
496 transfer(__position, __first, __last);
498 void remove(const _Tp& __value);
499 void unique();
500 void merge(list& __x);
501 void reverse();
502 void sort();
504 #ifdef __STL_MEMBER_TEMPLATES
505 template <class _Predicate> void remove_if(_Predicate);
506 template <class _BinaryPredicate> void unique(_BinaryPredicate);
507 template <class _StrictWeakOrdering> void merge(list&, _StrictWeakOrdering);
508 template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering);
509 #endif /* __STL_MEMBER_TEMPLATES */
511 friend bool operator== __STL_NULL_TMPL_ARGS (
512 const list& __x, const list& __y);
515 template <class _Tp, class _Alloc>
516 inline bool operator==(const list<_Tp,_Alloc>& __x,
517 const list<_Tp,_Alloc>& __y)
519 typedef typename list<_Tp,_Alloc>::_Node _Node;
520 _Node* __e1 = __x._M_node;
521 _Node* __e2 = __y._M_node;
522 _Node* __n1 = (_Node*) __e1->_M_next;
523 _Node* __n2 = (_Node*) __e2->_M_next;
524 for ( ; __n1 != __e1 && __n2 != __e2 ;
525 __n1 = (_Node*) __n1->_M_next, __n2 = (_Node*) __n2->_M_next)
526 if (__n1->_M_data != __n2->_M_data)
527 return false;
528 return __n1 == __e1 && __n2 == __e2;
531 template <class _Tp, class _Alloc>
532 inline bool operator<(const list<_Tp,_Alloc>& __x,
533 const list<_Tp,_Alloc>& __y)
535 return lexicographical_compare(__x.begin(), __x.end(),
536 __y.begin(), __y.end());
539 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
541 template <class _Tp, class _Alloc>
542 inline void
543 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
545 __x.swap(__y);
548 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
550 #ifdef __STL_MEMBER_TEMPLATES
552 template <class _Tp, class _Alloc> template <class _InputIter>
553 void
554 list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position,
555 _InputIter __first, _InputIter __last,
556 __false_type)
558 for ( ; __first != __last; ++__first)
559 insert(__position, *__first);
562 #else /* __STL_MEMBER_TEMPLATES */
564 template <class _Tp, class _Alloc>
565 void
566 list<_Tp, _Alloc>::insert(iterator __position,
567 const _Tp* __first, const _Tp* __last)
569 for ( ; __first != __last; ++__first)
570 insert(__position, *__first);
573 template <class _Tp, class _Alloc>
574 void
575 list<_Tp, _Alloc>::insert(iterator __position,
576 const_iterator __first, const_iterator __last)
578 for ( ; __first != __last; ++__first)
579 insert(__position, *__first);
582 #endif /* __STL_MEMBER_TEMPLATES */
584 template <class _Tp, class _Alloc>
585 void
586 list<_Tp, _Alloc>::insert(iterator __position, size_type __n, const _Tp& __x)
588 for ( ; __n > 0; --__n)
589 insert(__position, __x);
592 template <class _Tp, class _Alloc>
593 list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first,
594 iterator __last)
596 while (__first != __last)
597 erase(__first++);
598 return __last;
601 template <class _Tp, class _Alloc>
602 void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
604 iterator __i = begin();
605 size_type __len = 0;
606 for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
608 if (__len == __new_size)
609 erase(__i, end());
610 else // __i == end()
611 insert(end(), __new_size - __len, __x);
614 template <class _Tp, class _Alloc>
615 list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
617 if (this != &__x) {
618 iterator __first1 = begin();
619 iterator __last1 = end();
620 const_iterator __first2 = __x.begin();
621 const_iterator __last2 = __x.end();
622 while (__first1 != __last1 && __first2 != __last2)
623 *__first1++ = *__first2++;
624 if (__first2 == __last2)
625 erase(__first1, __last1);
626 else
627 insert(__last1, __first2, __last2);
629 return *this;
632 template <class _Tp, class _Alloc>
633 void list<_Tp, _Alloc>::assign(size_type __n, const _Tp& __val) {
634 iterator __i = begin();
635 for ( ; __i != end() && __n > 0; ++__i, --__n)
636 *__i = __val;
637 if (__n > 0)
638 insert(end(), __n, __val);
639 else
640 erase(__i, end());
643 #ifdef __STL_MEMBER_TEMPLATES
645 template <class _Tp, class _Alloc> template <class _InputIter>
646 void
647 list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2,
648 __false_type)
650 iterator __first1 = begin();
651 iterator __last1 = end();
652 for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
653 *__first1 = *__first2;
654 if (__first2 == __last2)
655 erase(__first1, __last1);
656 else
657 insert(__last1, __first2, __last2);
660 #endif /* __STL_MEMBER_TEMPLATES */
662 template <class _Tp, class _Alloc>
663 void list<_Tp, _Alloc>::remove(const _Tp& __value)
665 iterator __first = begin();
666 iterator __last = end();
667 while (__first != __last) {
668 iterator __next = __first;
669 ++__next;
670 if (*__first == __value) erase(__first);
671 __first = __next;
675 template <class _Tp, class _Alloc>
676 void list<_Tp, _Alloc>::unique()
678 iterator __first = begin();
679 iterator __last = end();
680 if (__first == __last) return;
681 iterator __next = __first;
682 while (++__next != __last) {
683 if (*__first == *__next)
684 erase(__next);
685 else
686 __first = __next;
687 __next = __first;
691 template <class _Tp, class _Alloc>
692 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
694 iterator __first1 = begin();
695 iterator __last1 = end();
696 iterator __first2 = __x.begin();
697 iterator __last2 = __x.end();
698 while (__first1 != __last1 && __first2 != __last2)
699 if (*__first2 < *__first1) {
700 iterator __next = __first2;
701 transfer(__first1, __first2, ++__next);
702 __first2 = __next;
704 else
705 ++__first1;
706 if (__first2 != __last2) transfer(__last1, __first2, __last2);
709 template <class _Tp, class _Alloc>
710 void list<_Tp, _Alloc>::reverse()
712 // Do nothing if the list has length 0 or 1.
713 if (_M_node->_M_next != _M_node &&
714 ((_Node*) (_M_node->_M_next))->_M_next != _M_node) {
715 iterator __first = begin();
716 ++__first;
717 while (__first != end()) {
718 iterator __old = __first;
719 ++__first;
720 transfer(begin(), __old, __first);
725 template <class _Tp, class _Alloc>
726 void list<_Tp, _Alloc>::sort()
728 // Do nothing if the list has length 0 or 1.
729 if (_M_node->_M_next != _M_node &&
730 ((_Node*) (_M_node->_M_next))->_M_next != _M_node) {
731 list<_Tp, _Alloc> __carry;
732 list<_Tp, _Alloc> __counter[64];
733 int __fill = 0;
734 while (!empty()) {
735 __carry.splice(__carry.begin(), *this, begin());
736 int __i = 0;
737 while(__i < __fill && !__counter[__i].empty()) {
738 __counter[__i].merge(__carry);
739 __carry.swap(__counter[__i++]);
741 __carry.swap(__counter[__i]);
742 if (__i == __fill) ++__fill;
745 for (int __i = 1; __i < __fill; ++__i)
746 __counter[__i].merge(__counter[__i-1]);
747 swap(__counter[__fill-1]);
751 #ifdef __STL_MEMBER_TEMPLATES
753 template <class _Tp, class _Alloc> template <class _Predicate>
754 void list<_Tp, _Alloc>::remove_if(_Predicate __pred)
756 iterator __first = begin();
757 iterator __last = end();
758 while (__first != __last) {
759 iterator __next = __first;
760 ++__next;
761 if (__pred(*__first)) erase(__first);
762 __first = __next;
766 template <class _Tp, class _Alloc> template <class _BinaryPredicate>
767 void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
769 iterator __first = begin();
770 iterator __last = end();
771 if (__first == __last) return;
772 iterator __next = __first;
773 while (++__next != __last) {
774 if (__binary_pred(*__first, *__next))
775 erase(__next);
776 else
777 __first = __next;
778 __next = __first;
782 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
783 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x,
784 _StrictWeakOrdering __comp)
786 iterator __first1 = begin();
787 iterator __last1 = end();
788 iterator __first2 = __x.begin();
789 iterator __last2 = __x.end();
790 while (__first1 != __last1 && __first2 != __last2)
791 if (__comp(*__first2, *__first1)) {
792 iterator __next = __first2;
793 transfer(__first1, __first2, ++__next);
794 __first2 = __next;
796 else
797 ++__first1;
798 if (__first2 != __last2) transfer(__last1, __first2, __last2);
801 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
802 void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
804 // Do nothing if the list has length 0 or 1.
805 if (_M_node->_M_next != _M_node &&
806 ((_Node*) (_M_node->_M_next))->_M_next != _M_node) {
807 list<_Tp, _Alloc> __carry;
808 list<_Tp, _Alloc> __counter[64];
809 int __fill = 0;
810 while (!empty()) {
811 __carry.splice(__carry.begin(), *this, begin());
812 int __i = 0;
813 while(__i < __fill && !__counter[__i].empty()) {
814 __counter[__i].merge(__carry, __comp);
815 __carry.swap(__counter[__i++]);
817 __carry.swap(__counter[__i]);
818 if (__i == __fill) ++__fill;
821 for (int __i = 1; __i < __fill; ++__i)
822 __counter[__i].merge(__counter[__i-1], __comp);
823 swap(__counter[__fill-1]);
827 #endif /* __STL_MEMBER_TEMPLATES */
829 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
830 #pragma reset woff 1174
831 #pragma reset woff 1375
832 #endif
834 __STL_END_NAMESPACE
836 #endif /* __SGI_STL_INTERNAL_LIST_H */
838 // Local Variables:
839 // mode:C++
840 // End: