1 /*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
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.
13 *
14 *
15 * Copyright (c) 1996,1997
16 * Silicon Graphics Computer Systems, Inc.
17 *
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.
25 */
26
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
29 */
30
31 #ifndef __SGI_STL_INTERNAL_LIST_H
32 #define __SGI_STL_INTERNAL_LIST_H
33
34 __STL_BEGIN_NAMESPACE
35
36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
37 #pragma set woff 1174
38 #pragma set woff 1375
39 #endif
40
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;
47 };
48
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;
54
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;
62
63 _Node* _M_node;
64
_List_iterator_List_iterator65 _List_iterator(_Node* __x) : _M_node(__x) {}
_List_iterator_List_iterator66 _List_iterator() {}
_List_iterator_List_iterator67 _List_iterator(const iterator& __x) : _M_node(__x._M_node) {}
68
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; }
72
73 #ifndef __SGI_STL_NO_ARROW_OPERATOR
74 pointer operator->() const { return &(operator*()); }
75 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
76
77 _Self& operator++() {
78 _M_node = (_Node*)(_M_node->_M_next);
79 return *this;
80 }
81 _Self operator++(int) {
82 _Self __tmp = *this;
83 ++*this;
84 return __tmp;
85 }
86 _Self& operator--() {
87 _M_node = (_Node*)(_M_node->_M_prev);
88 return *this;
89 }
90 _Self operator--(int) {
91 _Self __tmp = *this;
92 --*this;
93 return __tmp;
94 }
95 };
96
97 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
98
99 template <class _Tp, class _Ref, class _Ptr>
100 inline bidirectional_iterator_tag
iterator_category(const _List_iterator<_Tp,_Ref,_Ptr> &)101 iterator_category(const _List_iterator<_Tp, _Ref, _Ptr>&)
102 {
103 return bidirectional_iterator_tag();
104 }
105
106 template <class _Tp, class _Ref, class _Ptr>
107 inline _Tp*
value_type(const _List_iterator<_Tp,_Ref,_Ptr> &)108 value_type(const _List_iterator<_Tp, _Ref, _Ptr>&)
109 {
110 return 0;
111 }
112
113 template <class _Tp, class _Ref, class _Ptr>
114 inline ptrdiff_t*
distance_type(const _List_iterator<_Tp,_Ref,_Ptr> &)115 distance_type(const _List_iterator<_Tp, _Ref, _Ptr>&)
116 {
117 return 0;
118 }
119
120 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
121
122
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.
129
130 #ifdef __STL_USE_STD_ALLOCATORS
131
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;
get_allocator()138 allocator_type get_allocator() const { return _Node_allocator; }
139
_List_alloc_base(const allocator_type & __a)140 _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
141
142 protected:
_M_get_node()143 _List_node<_Tp>* _M_get_node()
144 { return _Node_allocator.allocate(1); }
_M_put_node(_List_node<_Tp> * __p)145 void _M_put_node(_List_node<_Tp>* __p)
146 { _Node_allocator.deallocate(__p, 1); }
147
148 protected:
149 typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
150 _Node_allocator;
151 _List_node<_Tp>* _M_node;
152 };
153
154 // Specialization for instanceless allocators.
155
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;
get_allocator()161 allocator_type get_allocator() const { return allocator_type(); }
162
_List_alloc_base(const allocator_type &)163 _List_alloc_base(const allocator_type&) {}
164
165 protected:
166 typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
167 _Alloc_type;
_M_get_node()168 _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
_M_put_node(_List_node<_Tp> * __p)169 void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
170
171 protected:
172 _List_node<_Tp>* _M_node;
173 };
174
175 template <class _Tp, class _Alloc>
176 class _List_base
177 : public _List_alloc_base<_Tp, _Alloc,
178 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
179 {
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;
185
_List_base(const allocator_type & __a)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;
190 }
~_List_base()191 ~_List_base() {
192 clear();
193 _M_put_node(_M_node);
194 }
195
196 void clear();
197 };
198
199 #else /* __STL_USE_STD_ALLOCATORS */
200
201 template <class _Tp, class _Alloc>
202 class _List_base
203 {
204 public:
205 typedef _Alloc allocator_type;
get_allocator()206 allocator_type get_allocator() const { return allocator_type(); }
207
_List_base(const 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;
212 }
~_List_base()213 ~_List_base() {
214 clear();
215 _M_put_node(_M_node);
216 }
217
218 void clear();
219
220 protected:
221 typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type;
_M_get_node()222 _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
_M_put_node(_List_node<_Tp> * __p)223 void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
224
225 protected:
226 _List_node<_Tp>* _M_node;
227 };
228
229 #endif /* __STL_USE_STD_ALLOCATORS */
230
231 template <class _Tp, class _Alloc>
232 void
clear()233 _List_base<_Tp,_Alloc>::clear()
234 {
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);
241 }
242 _M_node->_M_next = _M_node;
243 _M_node->_M_prev = _M_node;
244 }
245
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;
251
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;
261
262 typedef typename _Base::allocator_type allocator_type;
get_allocator()263 allocator_type get_allocator() const { return _Base::get_allocator(); }
264
265 public:
266 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
267 typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
268
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 */
280
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 */
287
288 protected:
_M_create_node(const _Tp & __x)289 _Node* _M_create_node(const _Tp& __x)
290 {
291 _Node* __p = _M_get_node();
292 __STL_TRY {
293 construct(&__p->_M_data, __x);
294 }
295 __STL_UNWIND(_M_put_node(__p));
296 return __p;
297 }
298
_M_create_node()299 _Node* _M_create_node()
300 {
301 _Node* __p = _M_get_node();
302 __STL_TRY {
303 construct(&__p->_M_data);
304 }
305 __STL_UNWIND(_M_put_node(__p));
306 return __p;
307 }
308
309 public:
_Base(__a)310 explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
311
begin()312 iterator begin() { return (_Node*)(_M_node->_M_next); }
begin()313 const_iterator begin() const { return (_Node*)(_M_node->_M_next); }
314
end()315 iterator end() { return _M_node; }
end()316 const_iterator end() const { return _M_node; }
317
rbegin()318 reverse_iterator rbegin()
319 { return reverse_iterator(end()); }
rbegin()320 const_reverse_iterator rbegin() const
321 { return const_reverse_iterator(end()); }
322
rend()323 reverse_iterator rend()
324 { return reverse_iterator(begin()); }
rend()325 const_reverse_iterator rend() const
326 { return const_reverse_iterator(begin()); }
327
empty()328 bool empty() const { return _M_node->_M_next == _M_node; }
size()329 size_type size() const {
330 size_type __result = 0;
331 distance(begin(), end(), __result);
332 return __result;
333 }
max_size()334 size_type max_size() const { return size_type(-1); }
335
front()336 reference front() { return *begin(); }
front()337 const_reference front() const { return *begin(); }
back()338 reference back() { return *(--end()); }
back()339 const_reference back() const { return *(--end()); }
340
swap(list<_Tp,_Alloc> & __x)341 void swap(list<_Tp, _Alloc>& __x) { __STD::swap(_M_node, __x._M_node); }
342
insert(iterator __position,const _Tp & __x)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;
350 }
insert(iterator __position)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.
354
355 template<class _Integer>
_M_insert_dispatch(iterator __pos,_Integer __n,_Integer __x,__true_type)356 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
357 __true_type) {
358 insert(__pos, (size_type) __n, (_Tp) __x);
359 }
360
361 template <class _InputIterator>
362 void _M_insert_dispatch(iterator __pos,
363 _InputIterator __first, _InputIterator __last,
364 __false_type);
365
366 template <class _InputIterator>
insert(iterator __pos,_InputIterator __first,_InputIterator __last)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());
370 }
371
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);
378
push_front(const _Tp & __x)379 void push_front(const _Tp& __x) { insert(begin(), __x); }
push_front()380 void push_front() {insert(begin());}
push_back(const _Tp & __x)381 void push_back(const _Tp& __x) { insert(end(), __x); }
push_back()382 void push_back() {insert(end());}
383
erase(iterator __position)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);
392 }
393 iterator erase(iterator __first, iterator __last);
clear()394 void clear() { _Base::clear(); }
395
396 void resize(size_type __new_size, const _Tp& __x);
resize(size_type __new_size)397 void resize(size_type __new_size) { resize(__new_size, _Tp()); }
398
pop_front()399 void pop_front() { erase(begin()); }
pop_back()400 void pop_back() {
401 iterator __tmp = end();
402 erase(--__tmp);
403 }
404 list(size_type __n, const _Tp& __value,
405 const allocator_type& __a = allocator_type())
_Base(__a)406 : _Base(__a)
407 { insert(begin(), __n, __value); }
list(size_type __n)408 explicit list(size_type __n)
409 : _Base(allocator_type())
410 { insert(begin(), __n, _Tp()); }
411
412 #ifdef __STL_MEMBER_TEMPLATES
413
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())
_Base(__a)419 : _Base(__a)
420 { insert(begin(), __first, __last); }
421
422 #else /* __STL_MEMBER_TEMPLATES */
423
424 list(const _Tp* __first, const _Tp* __last,
425 const allocator_type& __a = allocator_type())
_Base(__a)426 : _Base(__a)
427 { insert(begin(), __first, __last); }
428 list(const_iterator __first, const_iterator __last,
429 const allocator_type& __a = allocator_type())
_Base(__a)430 : _Base(__a)
431 { insert(begin(), __first, __last); }
432
433 #endif /* __STL_MEMBER_TEMPLATES */
list(const list<_Tp,_Alloc> & __x)434 list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())
435 { insert(begin(), __x.begin(), __x.end()); }
436
~list()437 ~list() { }
438
439 list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x);
440
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.
446
447 void assign(size_type __n, const _Tp& __val);
448
449 #ifdef __STL_MEMBER_TEMPLATES
450
451 template <class _InputIterator>
assign(_InputIterator __first,_InputIterator __last)452 void assign(_InputIterator __first, _InputIterator __last) {
453 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
454 _M_assign_dispatch(__first, __last, _Integral());
455 }
456
457 template <class _Integer>
_M_assign_dispatch(_Integer __n,_Integer __val,__true_type)458 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
459 { assign((size_type) __n, (_Tp) __val); }
460
461 template <class _InputIterator>
462 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
463 __false_type);
464
465 #endif /* __STL_MEMBER_TEMPLATES */
466
467 protected:
transfer(iterator __position,iterator __first,iterator __last)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;
474
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;
480 }
481 }
482
483 public:
splice(iterator __position,list & __x)484 void splice(iterator __position, list& __x) {
485 if (!__x.empty())
486 transfer(__position, __x.begin(), __x.end());
487 }
splice(iterator __position,list &,iterator __i)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);
493 }
splice(iterator __position,list &,iterator __first,iterator __last)494 void splice(iterator __position, list&, iterator __first, iterator __last) {
495 if (__first != __last)
496 transfer(__position, __first, __last);
497 }
498 void remove(const _Tp& __value);
499 void unique();
500 void merge(list& __x);
501 void reverse();
502 void sort();
503
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 */
510
511 friend bool operator== __STL_NULL_TMPL_ARGS (
512 const list& __x, const list& __y);
513 };
514
515 template <class _Tp, class _Alloc>
516 inline bool operator==(const list<_Tp,_Alloc>& __x,
517 const list<_Tp,_Alloc>& __y)
518 {
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;
529 }
530
531 template <class _Tp, class _Alloc>
532 inline bool operator<(const list<_Tp,_Alloc>& __x,
533 const list<_Tp,_Alloc>& __y)
534 {
535 return lexicographical_compare(__x.begin(), __x.end(),
536 __y.begin(), __y.end());
537 }
538
539 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
540
541 template <class _Tp, class _Alloc>
542 inline void
swap(list<_Tp,_Alloc> & __x,list<_Tp,_Alloc> & __y)543 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
544 {
545 __x.swap(__y);
546 }
547
548 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
549
550 #ifdef __STL_MEMBER_TEMPLATES
551
552 template <class _Tp, class _Alloc> template <class _InputIter>
553 void
_M_insert_dispatch(iterator __position,_InputIter __first,_InputIter __last,__false_type)554 list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position,
555 _InputIter __first, _InputIter __last,
556 __false_type)
557 {
558 for ( ; __first != __last; ++__first)
559 insert(__position, *__first);
560 }
561
562 #else /* __STL_MEMBER_TEMPLATES */
563
564 template <class _Tp, class _Alloc>
565 void
insert(iterator __position,const _Tp * __first,const _Tp * __last)566 list<_Tp, _Alloc>::insert(iterator __position,
567 const _Tp* __first, const _Tp* __last)
568 {
569 for ( ; __first != __last; ++__first)
570 insert(__position, *__first);
571 }
572
573 template <class _Tp, class _Alloc>
574 void
insert(iterator __position,const_iterator __first,const_iterator __last)575 list<_Tp, _Alloc>::insert(iterator __position,
576 const_iterator __first, const_iterator __last)
577 {
578 for ( ; __first != __last; ++__first)
579 insert(__position, *__first);
580 }
581
582 #endif /* __STL_MEMBER_TEMPLATES */
583
584 template <class _Tp, class _Alloc>
585 void
insert(iterator __position,size_type __n,const _Tp & __x)586 list<_Tp, _Alloc>::insert(iterator __position, size_type __n, const _Tp& __x)
587 {
588 for ( ; __n > 0; --__n)
589 insert(__position, __x);
590 }
591
592 template <class _Tp, class _Alloc>
erase(iterator __first,iterator __last)593 list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first,
594 iterator __last)
595 {
596 while (__first != __last)
597 erase(__first++);
598 return __last;
599 }
600
601 template <class _Tp, class _Alloc>
resize(size_type __new_size,const _Tp & __x)602 void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
603 {
604 iterator __i = begin();
605 size_type __len = 0;
606 for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
607 ;
608 if (__len == __new_size)
609 erase(__i, end());
610 else // __i == end()
611 insert(end(), __new_size - __len, __x);
612 }
613
614 template <class _Tp, class _Alloc>
615 list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
616 {
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);
628 }
629 return *this;
630 }
631
632 template <class _Tp, class _Alloc>
assign(size_type __n,const _Tp & __val)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());
641 }
642
643 #ifdef __STL_MEMBER_TEMPLATES
644
645 template <class _Tp, class _Alloc> template <class _InputIter>
646 void
_M_assign_dispatch(_InputIter __first2,_InputIter __last2,__false_type)647 list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2,
648 __false_type)
649 {
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);
658 }
659
660 #endif /* __STL_MEMBER_TEMPLATES */
661
662 template <class _Tp, class _Alloc>
remove(const _Tp & __value)663 void list<_Tp, _Alloc>::remove(const _Tp& __value)
664 {
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;
672 }
673 }
674
675 template <class _Tp, class _Alloc>
unique()676 void list<_Tp, _Alloc>::unique()
677 {
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;
688 }
689 }
690
691 template <class _Tp, class _Alloc>
merge(list<_Tp,_Alloc> & __x)692 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
693 {
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;
703 }
704 else
705 ++__first1;
706 if (__first2 != __last2) transfer(__last1, __first2, __last2);
707 }
708
709 template <class _Tp, class _Alloc>
reverse()710 void list<_Tp, _Alloc>::reverse()
711 {
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);
721 }
722 }
723 }
724
725 template <class _Tp, class _Alloc>
sort()726 void list<_Tp, _Alloc>::sort()
727 {
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++]);
740 }
741 __carry.swap(__counter[__i]);
742 if (__i == __fill) ++__fill;
743 }
744
745 for (int __i = 1; __i < __fill; ++__i)
746 __counter[__i].merge(__counter[__i-1]);
747 swap(__counter[__fill-1]);
748 }
749 }
750
751 #ifdef __STL_MEMBER_TEMPLATES
752
753 template <class _Tp, class _Alloc> template <class _Predicate>
remove_if(_Predicate __pred)754 void list<_Tp, _Alloc>::remove_if(_Predicate __pred)
755 {
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;
763 }
764 }
765
766 template <class _Tp, class _Alloc> template <class _BinaryPredicate>
unique(_BinaryPredicate __binary_pred)767 void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
768 {
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;
779 }
780 }
781
782 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
merge(list<_Tp,_Alloc> & __x,_StrictWeakOrdering __comp)783 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x,
784 _StrictWeakOrdering __comp)
785 {
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;
795 }
796 else
797 ++__first1;
798 if (__first2 != __last2) transfer(__last1, __first2, __last2);
799 }
800
801 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
sort(_StrictWeakOrdering __comp)802 void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
803 {
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++]);
816 }
817 __carry.swap(__counter[__i]);
818 if (__i == __fill) ++__fill;
819 }
820
821 for (int __i = 1; __i < __fill; ++__i)
822 __counter[__i].merge(__counter[__i-1], __comp);
823 swap(__counter[__fill-1]);
824 }
825 }
826
827 #endif /* __STL_MEMBER_TEMPLATES */
828
829 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
830 #pragma reset woff 1174
831 #pragma reset woff 1375
832 #endif
833
834 __STL_END_NAMESPACE
835
836 #endif /* __SGI_STL_INTERNAL_LIST_H */
837
838 // Local Variables:
839 // mode:C++
840 // End:
841