This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[v3] stl_list.h reformat to C++STYLE
- From: Stephen M. Webb <stephen at bregmasoft dot com>
- To: libstdc++ at gcc dot gnu dot org
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Thu, 22 Nov 2001 13:31:33 -0500
- Subject: [v3] stl_list.h reformat to C++STYLE
- Organization: CRYPTOCard Corporation
- Reply-to: stephen at bregmasoft dot com
Here's a (rather large but mostly harmless) patch that reformats
bits/stl_list.h in the C++STYLE. Also fixes a couple of non-standard
names (which started me down the path of reformatting).
Bootstraps on i686-pc-linux-gnu ok, passes testsuite.
2001-11-22 Stephen M. Webb <stephen@bregmasoft.com>
* include/bits/stl_list.h: Reformatted according to C++STYLE rules.
(size): Replaced nonstandard distance() call with the standard one.
(transfer): Uglified to _M_transfer.
Index: stl_list.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_list.h,v
retrieving revision 1.10
diff -c -3 -p -r1.10 stl_list.h
*** stl_list.h 2001/11/02 17:38:11 1.10
--- stl_list.h 2001/11/22 17:23:13
***************
*** 66,783 ****
namespace std
{
! struct _List_node_base {
! _List_node_base* _M_next;
! _List_node_base* _M_prev;
! };
!
! template <class _Tp>
! struct _List_node : public _List_node_base {
! _Tp _M_data;
! };
!
! struct _List_iterator_base {
! typedef size_t size_type;
! typedef ptrdiff_t difference_type;
! typedef bidirectional_iterator_tag iterator_category;
!
! _List_node_base* _M_node;
! _List_iterator_base(_List_node_base* __x) : _M_node(__x) {}
! _List_iterator_base() {}
! void _M_incr() { _M_node = _M_node->_M_next; }
! void _M_decr() { _M_node = _M_node->_M_prev; }
! bool operator==(const _List_iterator_base& __x) const {
! return _M_node == __x._M_node;
! }
! bool operator!=(const _List_iterator_base& __x) const {
! return _M_node != __x._M_node;
! }
! };
! template<class _Tp, class _Ref, class _Ptr>
! struct _List_iterator : public _List_iterator_base {
! typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
! typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
! typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;
!
! typedef _Tp value_type;
! typedef _Ptr pointer;
! typedef _Ref reference;
! typedef _List_node<_Tp> _Node;
!
! _List_iterator(_Node* __x) : _List_iterator_base(__x) {}
! _List_iterator() {}
! _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {}
!
! reference operator*() const { return ((_Node*) _M_node)->_M_data; }
! pointer operator->() const { return &(operator*()); }
!
! _Self& operator++() {
! this->_M_incr();
! return *this;
! }
! _Self operator++(int) {
! _Self __tmp = *this;
! this->_M_incr();
! return __tmp;
! }
! _Self& operator--() {
! this->_M_decr();
! return *this;
! }
! _Self operator--(int) {
! _Self __tmp = *this;
! this->_M_decr();
! return __tmp;
! }
! };
- // Base class that encapsulates details of allocators. Three cases:
- // an ordinary standard-conforming allocator, a standard-conforming
- // allocator with no non-static data, and an SGI-style allocator.
- // This complexity is necessary only because we're worrying about backward
- // compatibility and because we want to avoid wasting storage on an
- // allocator instance if it isn't necessary.
-
-
- // Base for general standard-conforming allocators.
- template <class _Tp, class _Allocator, bool _IsStatic>
- class _List_alloc_base {
- public:
- typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
- allocator_type;
- allocator_type get_allocator() const { return _Node_allocator; }
-
- _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
-
- protected:
- _List_node<_Tp>* _M_get_node()
- { return _Node_allocator.allocate(1); }
- void _M_put_node(_List_node<_Tp>* __p)
- { _Node_allocator.deallocate(__p, 1); }
-
- protected:
- typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
- _Node_allocator;
- _List_node<_Tp>* _M_node;
- };
-
- // Specialization for instanceless allocators.
-
- template <class _Tp, class _Allocator>
- class _List_alloc_base<_Tp, _Allocator, true> {
- public:
- typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
- allocator_type;
- allocator_type get_allocator() const { return allocator_type(); }
-
- _List_alloc_base(const allocator_type&) {}
-
- protected:
- typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
- _Alloc_type;
- _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
- void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
-
- protected:
- _List_node<_Tp>* _M_node;
- };
-
- template <class _Tp, class _Alloc>
- class _List_base
- : public _List_alloc_base<_Tp, _Alloc,
- _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
- {
- public:
- typedef _List_alloc_base<_Tp, _Alloc,
- _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
- _Base;
- typedef typename _Base::allocator_type allocator_type;
-
- _List_base(const allocator_type& __a) : _Base(__a) {
- _M_node = _M_get_node();
- _M_node->_M_next = _M_node;
- _M_node->_M_prev = _M_node;
- }
- ~_List_base() {
- clear();
- _M_put_node(_M_node);
- }
! void clear();
! };
! template <class _Tp, class _Alloc>
! void
! _List_base<_Tp,_Alloc>::clear()
! {
! _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next;
! while (__cur != _M_node) {
! _List_node<_Tp>* __tmp = __cur;
! __cur = (_List_node<_Tp>*) __cur->_M_next;
! _Destroy(&__tmp->_M_data);
! _M_put_node(__tmp);
! }
! _M_node->_M_next = _M_node;
! _M_node->_M_prev = _M_node;
! }
!
! template <class _Tp, class _Alloc = allocator<_Tp> >
! class list : protected _List_base<_Tp, _Alloc>
! {
! // concept requirements
! __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
!
! typedef _List_base<_Tp, _Alloc> _Base;
! protected:
! typedef void* _Void_pointer;
!
! public:
! typedef _Tp value_type;
! typedef value_type* pointer;
! typedef const value_type* const_pointer;
! typedef value_type& reference;
! typedef const value_type& const_reference;
! typedef _List_node<_Tp> _Node;
! typedef size_t size_type;
! typedef ptrdiff_t difference_type;
!
! typedef typename _Base::allocator_type allocator_type;
! allocator_type get_allocator() const { return _Base::get_allocator(); }
!
! public:
! typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
! typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
!
! typedef reverse_iterator<const_iterator> const_reverse_iterator;
! typedef reverse_iterator<iterator> reverse_iterator;
!
! protected:
! using _Base::_M_node;
! using _Base::_M_put_node;
! using _Base::_M_get_node;
! protected:
! _Node* _M_create_node(const _Tp& __x)
! {
! _Node* __p = _M_get_node();
! try {
! _Construct(&__p->_M_data, __x);
! }
! catch(...)
! {
! _M_put_node(__p);
! __throw_exception_again;
}
- return __p;
- }
! _Node* _M_create_node()
! {
! _Node* __p = _M_get_node();
! try {
! _Construct(&__p->_M_data);
! }
! catch(...)
{
! _M_put_node(__p);
! __throw_exception_again;
}
- return __p;
- }
! public:
! explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
! iterator begin() { return (_Node*)(_M_node->_M_next); }
! const_iterator begin() const { return (_Node*)(_M_node->_M_next); }
! iterator end() { return _M_node; }
! const_iterator end() const { return _M_node; }
! reverse_iterator rbegin()
! { return reverse_iterator(end()); }
! const_reverse_iterator rbegin() const
! { return const_reverse_iterator(end()); }
!
! reverse_iterator rend()
! { return reverse_iterator(begin()); }
! const_reverse_iterator rend() const
! { return const_reverse_iterator(begin()); }
!
! bool empty() const { return _M_node->_M_next == _M_node; }
! size_type size() const {
! size_type __result = 0;
! distance(begin(), end(), __result);
! return __result;
! }
! size_type max_size() const { return size_type(-1); }
! reference front() { return *begin(); }
! const_reference front() const { return *begin(); }
! reference back() { return *(--end()); }
! const_reference back() const { return *(--end()); }
!
! void swap(list<_Tp, _Alloc>& __x) { std::swap(_M_node, __x._M_node); }
!
! iterator insert(iterator __position, const _Tp& __x) {
! _Node* __tmp = _M_create_node(__x);
! __tmp->_M_next = __position._M_node;
! __tmp->_M_prev = __position._M_node->_M_prev;
! __position._M_node->_M_prev->_M_next = __tmp;
! __position._M_node->_M_prev = __tmp;
! return __tmp;
! }
! iterator insert(iterator __position) { return insert(__position, _Tp()); }
! // Check whether it's an integral type. If so, it's not an iterator.
! template<class _Integer>
! void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
! __true_type) {
! _M_fill_insert(__pos, (size_type) __n, (_Tp) __x);
! }
! template <class _InputIterator>
! void _M_insert_dispatch(iterator __pos,
! _InputIterator __first, _InputIterator __last,
! __false_type);
!
! template <class _InputIterator>
! void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
! typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
! _M_insert_dispatch(__pos, __first, __last, _Integral());
! }
! void insert(iterator __pos, size_type __n, const _Tp& __x)
! { _M_fill_insert(__pos, __n, __x); }
! void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x);
!
! void push_front(const _Tp& __x) { insert(begin(), __x); }
! void push_front() {insert(begin());}
! void push_back(const _Tp& __x) { insert(end(), __x); }
! void push_back() {insert(end());}
!
! iterator erase(iterator __position) {
! _List_node_base* __next_node = __position._M_node->_M_next;
! _List_node_base* __prev_node = __position._M_node->_M_prev;
! _Node* __n = (_Node*) __position._M_node;
! __prev_node->_M_next = __next_node;
! __next_node->_M_prev = __prev_node;
! _Destroy(&__n->_M_data);
! _M_put_node(__n);
! return iterator((_Node*) __next_node);
! }
! iterator erase(iterator __first, iterator __last);
! void clear() { _Base::clear(); }
! void resize(size_type __new_size, const _Tp& __x);
! void resize(size_type __new_size) { this->resize(__new_size, _Tp()); }
! void pop_front() { erase(begin()); }
! void pop_back() {
! iterator __tmp = end();
! erase(--__tmp);
! }
! list(size_type __n, const _Tp& __value,
! const allocator_type& __a = allocator_type())
! : _Base(__a)
! { insert(begin(), __n, __value); }
! explicit list(size_type __n)
! : _Base(allocator_type())
! { insert(begin(), __n, _Tp()); }
!
! // We don't need any dispatching tricks here, because insert does all of
! // that anyway.
! template <class _InputIterator>
! list(_InputIterator __first, _InputIterator __last,
! const allocator_type& __a = allocator_type())
! : _Base(__a)
! { insert(begin(), __first, __last); }
!
! list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())
! { insert(begin(), __x.begin(), __x.end()); }
!
! ~list() { }
!
! list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x);
!
! public:
! // assign(), a generalized assignment member function. Two
! // versions: one that takes a count, and one that takes a range.
! // The range version is a member template, so we dispatch on whether
! // or not the type is an integer.
!
! void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
!
! void _M_fill_assign(size_type __n, const _Tp& __val);
!
! template <class _InputIterator>
! void assign(_InputIterator __first, _InputIterator __last) {
! typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
! _M_assign_dispatch(__first, __last, _Integral());
! }
! template <class _Integer>
! void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
! { _M_fill_assign((size_type) __n, (_Tp) __val); }
!
! template <class _InputIterator>
! void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
! __false_type);
!
! protected:
! void transfer(iterator __position, iterator __first, iterator __last) {
! if (__position != __last) {
! // Remove [first, last) from its old position.
! __last._M_node->_M_prev->_M_next = __position._M_node;
! __first._M_node->_M_prev->_M_next = __last._M_node;
! __position._M_node->_M_prev->_M_next = __first._M_node;
!
! // Splice [first, last) into its new position.
! _List_node_base* __tmp = __position._M_node->_M_prev;
! __position._M_node->_M_prev = __last._M_node->_M_prev;
! __last._M_node->_M_prev = __first._M_node->_M_prev;
! __first._M_node->_M_prev = __tmp;
}
- }
! public:
! void splice(iterator __position, list& __x) {
! if (!__x.empty())
! this->transfer(__position, __x.begin(), __x.end());
! }
! void splice(iterator __position, list&, iterator __i) {
! iterator __j = __i;
! ++__j;
! if (__position == __i || __position == __j) return;
! this->transfer(__position, __i, __j);
! }
! void splice(iterator __position, list&, iterator __first, iterator __last) {
! if (__first != __last)
! this->transfer(__position, __first, __last);
! }
! void remove(const _Tp& __value);
! void unique();
! void merge(list& __x);
! void reverse();
! void sort();
!
! template <class _Predicate> void remove_if(_Predicate);
! template <class _BinaryPredicate> void unique(_BinaryPredicate);
! template <class _StrictWeakOrdering> void merge(list&, _StrictWeakOrdering);
! template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering);
! };
!
! template <class _Tp, class _Alloc>
! inline bool
! operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
! {
! typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
! const_iterator __end1 = __x.end();
! const_iterator __end2 = __y.end();
!
! const_iterator __i1 = __x.begin();
! const_iterator __i2 = __y.begin();
! while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
! ++__i1;
! ++__i2;
! }
! return __i1 == __end1 && __i2 == __end2;
! }
! template <class _Tp, class _Alloc>
! inline bool operator<(const list<_Tp,_Alloc>& __x,
! const list<_Tp,_Alloc>& __y)
! {
! return lexicographical_compare(__x.begin(), __x.end(),
! __y.begin(), __y.end());
! }
!
! template <class _Tp, class _Alloc>
! inline bool operator!=(const list<_Tp,_Alloc>& __x,
! const list<_Tp,_Alloc>& __y) {
! return !(__x == __y);
! }
!
! template <class _Tp, class _Alloc>
! inline bool operator>(const list<_Tp,_Alloc>& __x,
! const list<_Tp,_Alloc>& __y) {
! return __y < __x;
! }
!
! template <class _Tp, class _Alloc>
! inline bool operator<=(const list<_Tp,_Alloc>& __x,
! const list<_Tp,_Alloc>& __y) {
! return !(__y < __x);
! }
!
! template <class _Tp, class _Alloc>
! inline bool operator>=(const list<_Tp,_Alloc>& __x,
! const list<_Tp,_Alloc>& __y) {
! return !(__x < __y);
! }
!
! template <class _Tp, class _Alloc>
! inline void
! swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
! {
! __x.swap(__y);
! }
!
! template <class _Tp, class _Alloc> template <class _InputIter>
! void
! list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position,
! _InputIter __first, _InputIter __last,
! __false_type)
! {
! for ( ; __first != __last; ++__first)
! insert(__position, *__first);
! }
!
! template <class _Tp, class _Alloc>
! void
! list<_Tp, _Alloc>::_M_fill_insert(iterator __position,
! size_type __n, const _Tp& __x)
! {
! for ( ; __n > 0; --__n)
! insert(__position, __x);
! }
!
! template <class _Tp, class _Alloc>
! typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first,
! iterator __last)
! {
! while (__first != __last)
! erase(__first++);
! return __last;
! }
!
! template <class _Tp, class _Alloc>
! void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
! {
! iterator __i = begin();
! size_type __len = 0;
! for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
! ;
! if (__len == __new_size)
! erase(__i, end());
! else // __i == end()
! insert(end(), __new_size - __len, __x);
! }
!
! template <class _Tp, class _Alloc>
! list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
! {
! if (this != &__x) {
! iterator __first1 = begin();
! iterator __last1 = end();
! const_iterator __first2 = __x.begin();
! const_iterator __last2 = __x.end();
! while (__first1 != __last1 && __first2 != __last2)
! *__first1++ = *__first2++;
! if (__first2 == __last2)
! erase(__first1, __last1);
! else
! insert(__last1, __first2, __last2);
! }
! return *this;
! }
! template <class _Tp, class _Alloc>
! void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
! iterator __i = begin();
! for ( ; __i != end() && __n > 0; ++__i, --__n)
! *__i = __val;
! if (__n > 0)
! insert(end(), __n, __val);
! else
! erase(__i, end());
! }
!
! template <class _Tp, class _Alloc> template <class _InputIter>
! void
! list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2,
! __false_type)
! {
! iterator __first1 = begin();
! iterator __last1 = end();
! for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
! *__first1 = *__first2;
! if (__first2 == __last2)
! erase(__first1, __last1);
! else
! insert(__last1, __first2, __last2);
! }
!
! template <class _Tp, class _Alloc>
! void list<_Tp, _Alloc>::remove(const _Tp& __value)
! {
! iterator __first = begin();
! iterator __last = end();
! while (__first != __last) {
! iterator __next = __first;
! ++__next;
! if (*__first == __value) erase(__first);
! __first = __next;
! }
! }
! template <class _Tp, class _Alloc>
! void list<_Tp, _Alloc>::unique()
! {
! iterator __first = begin();
! iterator __last = end();
! if (__first == __last) return;
! iterator __next = __first;
! while (++__next != __last) {
! if (*__first == *__next)
! erase(__next);
! else
! __first = __next;
! __next = __first;
! }
! }
! template <class _Tp, class _Alloc>
! void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
! {
! iterator __first1 = begin();
! iterator __last1 = end();
! iterator __first2 = __x.begin();
! iterator __last2 = __x.end();
! while (__first1 != __last1 && __first2 != __last2)
! if (*__first2 < *__first1) {
! iterator __next = __first2;
! transfer(__first1, __first2, ++__next);
! __first2 = __next;
! }
! else
! ++__first1;
! if (__first2 != __last2) transfer(__last1, __first2, __last2);
! }
!
! inline void __List_base_reverse(_List_node_base* __p)
! {
! _List_node_base* __tmp = __p;
! do {
! std::swap(__tmp->_M_next, __tmp->_M_prev);
! __tmp = __tmp->_M_prev; // Old next node is now prev.
! } while (__tmp != __p);
! }
!
! template <class _Tp, class _Alloc>
! inline void list<_Tp, _Alloc>::reverse()
! {
! __List_base_reverse(this->_M_node);
! }
!
! template <class _Tp, class _Alloc>
! void list<_Tp, _Alloc>::sort()
! {
! // Do nothing if the list has length 0 or 1.
! if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
! list<_Tp, _Alloc> __carry;
! list<_Tp, _Alloc> __counter[64];
! int __fill = 0;
! while (!empty()) {
! __carry.splice(__carry.begin(), *this, begin());
! int __i = 0;
! while(__i < __fill && !__counter[__i].empty()) {
! __counter[__i].merge(__carry);
! __carry.swap(__counter[__i++]);
! }
! __carry.swap(__counter[__i]);
! if (__i == __fill) ++__fill;
! }
!
! for (int __i = 1; __i < __fill; ++__i)
! __counter[__i].merge(__counter[__i-1]);
! swap(__counter[__fill-1]);
! }
! }
! template <class _Tp, class _Alloc> template <class _Predicate>
! void list<_Tp, _Alloc>::remove_if(_Predicate __pred)
! {
! iterator __first = begin();
! iterator __last = end();
! while (__first != __last) {
! iterator __next = __first;
! ++__next;
! if (__pred(*__first)) erase(__first);
! __first = __next;
! }
! }
! template <class _Tp, class _Alloc> template <class _BinaryPredicate>
! void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
! {
! iterator __first = begin();
! iterator __last = end();
! if (__first == __last) return;
! iterator __next = __first;
! while (++__next != __last) {
! if (__binary_pred(*__first, *__next))
! erase(__next);
! else
! __first = __next;
! __next = __first;
! }
! }
! template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
! void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x,
! _StrictWeakOrdering __comp)
! {
! iterator __first1 = begin();
! iterator __last1 = end();
! iterator __first2 = __x.begin();
! iterator __last2 = __x.end();
! while (__first1 != __last1 && __first2 != __last2)
! if (__comp(*__first2, *__first1)) {
! iterator __next = __first2;
! transfer(__first1, __first2, ++__next);
! __first2 = __next;
! }
! else
! ++__first1;
! if (__first2 != __last2) transfer(__last1, __first2, __last2);
! }
!
! template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
! void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
! {
! // Do nothing if the list has length 0 or 1.
! if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
! list<_Tp, _Alloc> __carry;
! list<_Tp, _Alloc> __counter[64];
! int __fill = 0;
! while (!empty()) {
! __carry.splice(__carry.begin(), *this, begin());
! int __i = 0;
! while(__i < __fill && !__counter[__i].empty()) {
! __counter[__i].merge(__carry, __comp);
! __carry.swap(__counter[__i++]);
! }
! __carry.swap(__counter[__i]);
! if (__i == __fill) ++__fill;
! }
!
! for (int __i = 1; __i < __fill; ++__i)
! __counter[__i].merge(__counter[__i-1], __comp);
! swap(__counter[__fill-1]);
! }
! }
} // namespace std
#endif /* __SGI_STL_INTERNAL_LIST_H */
// Local Variables:
// mode:C++
// End:
--- 66,977 ----
namespace std
{
! struct _List_node_base
! {
! _List_node_base* _M_next;
! _List_node_base* _M_prev;
! };
!
! template<typename _Tp>
! struct _List_node : public _List_node_base
! {
! _Tp _M_data;
! };
! struct _List_iterator_base
! {
! typedef size_t size_type;
! typedef ptrdiff_t difference_type;
! typedef bidirectional_iterator_tag iterator_category;
!
! _List_node_base* _M_node;
!
! _List_iterator_base(_List_node_base* __x)
! : _M_node(__x)
! { }
!
! _List_iterator_base()
! { }
!
! void
! _M_incr()
! { _M_node = _M_node->_M_next; }
!
! void
! _M_decr()
! { _M_node = _M_node->_M_prev; }
!
! bool
! operator==(const _List_iterator_base& __x) const
! { return _M_node == __x._M_node; }
!
! bool
! operator!=(const _List_iterator_base& __x) const
! { return _M_node != __x._M_node; }
! };
!
! template<typename _Tp, typename _Ref, typename _Ptr>
! struct _List_iterator : public _List_iterator_base
! {
! typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
! typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
! typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;
!
! typedef _Tp value_type;
! typedef _Ptr pointer;
! typedef _Ref reference;
! typedef _List_node<_Tp> _Node;
!
! _List_iterator(_Node* __x)
! : _List_iterator_base(__x)
! { }
!
! _List_iterator()
! { }
!
! _List_iterator(const iterator& __x)
! : _List_iterator_base(__x._M_node)
! { }
!
! reference
! operator*() const
! { return ((_Node*) _M_node)->_M_data; }
!
! pointer
! operator->() const
! { return &(operator*()); }
! _Self&
! operator++()
! {
! this->_M_incr();
! return *this;
! }
! _Self
! operator++(int)
! {
! _Self __tmp = *this;
! this->_M_incr();
! return __tmp;
! }
! _Self&
! operator--()
! {
! this->_M_decr();
! return *this;
! }
+ _Self
+ operator--(int)
+ {
+ _Self __tmp = *this;
+ this->_M_decr();
+ return __tmp;
+ }
+ };
! // Base class that encapsulates details of allocators. Three cases:
! // an ordinary standard-conforming allocator, a standard-conforming
! // allocator with no non-static data, and an SGI-style allocator.
! // This complexity is necessary only because we're worrying about backward
! // compatibility and because we want to avoid wasting storage on an
! // allocator instance if it isn't necessary.
!
!
! // Base for general standard-conforming allocators.
! template<typename _Tp, typename _Allocator, bool _IsStatic>
! class _List_alloc_base
! {
! public:
! typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
! allocator_type;
!
! allocator_type
! get_allocator() const
! { return _Node_allocator; }
!
! _List_alloc_base(const allocator_type& __a)
! : _Node_allocator(__a)
! { }
!
! protected:
! _List_node<_Tp>*
! _M_get_node()
! { return _Node_allocator.allocate(1); }
!
! void
! _M_put_node(_List_node<_Tp>* __p)
! { _Node_allocator.deallocate(__p, 1); }
!
! protected:
! typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
! _Node_allocator;
!
! _List_node<_Tp>* _M_node;
! };
!
! // Specialization for instanceless allocators.
!
! template<typename _Tp, typename _Allocator>
! class _List_alloc_base<_Tp, _Allocator, true>
! {
! public:
! typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
! allocator_type;
!
! allocator_type
! get_allocator() const
! { return allocator_type(); }
!
! _List_alloc_base(const allocator_type&)
! { }
!
! protected:
! typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
! _Alloc_type;
!
! _List_node<_Tp>*
! _M_get_node()
! { return _Alloc_type::allocate(1); }
!
! void
! _M_put_node(_List_node<_Tp>* __p)
! { _Alloc_type::deallocate(__p, 1); }
!
! protected:
! _List_node<_Tp>* _M_node;
! };
!
! template<typename _Tp, typename _Alloc>
! class _List_base
! : public _List_alloc_base<_Tp, _Alloc,
! _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
! {
! public:
! typedef _List_alloc_base<_Tp, _Alloc,
! _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
! _Base;
! typedef typename _Base::allocator_type allocator_type;
!
! _List_base(const allocator_type& __a)
! : _Base(__a)
! {
! _M_node = _M_get_node();
! _M_node->_M_next = _M_node;
! _M_node->_M_prev = _M_node;
! }
+ ~_List_base()
+ {
+ clear();
+ _M_put_node(_M_node);
+ }
! void clear();
! };
!
! template<typename _Tp, typename _Alloc = allocator<_Tp> >
! class list : protected _List_base<_Tp, _Alloc>
! {
! // concept requirements
! __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
!
! typedef _List_base<_Tp, _Alloc> _Base;
! protected:
! typedef void* _Void_pointer;
!
! public:
! typedef _Tp value_type;
! typedef value_type* pointer;
! typedef const value_type* const_pointer;
! typedef value_type& reference;
! typedef const value_type& const_reference;
! typedef _List_node<_Tp> _Node;
! typedef size_t size_type;
! typedef ptrdiff_t difference_type;
!
! typedef typename _Base::allocator_type allocator_type;
!
! typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
! typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
!
! typedef reverse_iterator<const_iterator> const_reverse_iterator;
! typedef reverse_iterator<iterator> reverse_iterator;
!
! protected:
! using _Base::_M_node;
! using _Base::_M_put_node;
! using _Base::_M_get_node;
!
! protected:
! _Node*
! _M_create_node(const _Tp& __x)
! {
! _Node* __p = _M_get_node();
! try {
! _Construct(&__p->_M_data, __x);
! }
! catch(...)
! {
! _M_put_node(__p);
! __throw_exception_again;
! }
! return __p;
}
! _Node*
! _M_create_node()
! {
! _Node* __p = _M_get_node();
! try {
! _Construct(&__p->_M_data);
! }
! catch(...)
! {
! _M_put_node(__p);
! __throw_exception_again;
! }
! return __p;
! }
!
! public:
! allocator_type
! get_allocator() const
! { return _Base::get_allocator(); }
!
! explicit
! list(const allocator_type& __a = allocator_type())
! : _Base(__a)
! { }
!
! iterator
! begin()
! { return static_cast<_Node*>(_M_node->_M_next); }
!
! const_iterator
! begin() const
! { return static_cast<_Node*>(_M_node->_M_next); }
!
! iterator
! end()
! { return _M_node; }
!
! const_iterator
! end() const
! { return _M_node; }
!
! reverse_iterator
! rbegin()
! { return reverse_iterator(end()); }
!
! const_reverse_iterator
! rbegin() const
! { return const_reverse_iterator(end()); }
!
! reverse_iterator
! rend()
! { return reverse_iterator(begin()); }
!
! const_reverse_iterator
! rend() const
! { return const_reverse_iterator(begin()); }
!
! bool
! empty() const
! { return _M_node->_M_next == _M_node; }
!
! size_type
! size() const
! { return distance(begin(), end()); }
!
! size_type
! max_size() const
! { return size_type(-1); }
!
! reference
! front()
! { return *begin(); }
!
! const_reference
! front() const
! { return *begin(); }
!
! reference
! back()
! { return *(--end()); }
!
! const_reference
! back() const
! { return *(--end()); }
!
! void
! swap(list<_Tp, _Alloc>& __x)
! { std::swap(_M_node, __x._M_node); }
!
! iterator
! insert(iterator __position, const _Tp& __x)
! {
! _Node* __tmp = _M_create_node(__x);
! __tmp->_M_next = __position._M_node;
! __tmp->_M_prev = __position._M_node->_M_prev;
! __position._M_node->_M_prev->_M_next = __tmp;
! __position._M_node->_M_prev = __tmp;
! return __tmp;
! }
!
! iterator
! insert(iterator __position)
! { return insert(__position, _Tp()); }
!
! // Check whether it's an integral type. If so, it's not an iterator.
! template<typename _Integer>
! void
! _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
! { _M_fill_insert(__pos, (size_type) __n, (_Tp) __x); }
!
! template<typename _InputIterator>
! void
! _M_insert_dispatch(iterator __pos,
! _InputIterator __first, _InputIterator __last,
! __false_type);
!
! template<typename _InputIterator>
! void
! insert(iterator __pos, _InputIterator __first, _InputIterator __last)
! {
! typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
! _M_insert_dispatch(__pos, __first, __last, _Integral());
! }
!
! void
! insert(iterator __pos, size_type __n, const _Tp& __x)
! { _M_fill_insert(__pos, __n, __x); }
!
! void
! _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x);
!
! void
! push_front(const _Tp& __x)
! { insert(begin(), __x); }
!
! void
! push_front()
! { insert(begin()); }
!
! void
! push_back(const _Tp& __x)
! { insert(end(), __x); }
!
! void
! push_back()
! { insert(end()); }
!
! iterator
! erase(iterator __position)
! {
! _List_node_base* __next_node = __position._M_node->_M_next;
! _List_node_base* __prev_node = __position._M_node->_M_prev;
! _Node* __n = static_cast<_Node*>(__position._M_node);
! __prev_node->_M_next = __next_node;
! __next_node->_M_prev = __prev_node;
! _Destroy(&__n->_M_data);
! _M_put_node(__n);
! return iterator(static_cast<_Node*>(__next_node));
! }
!
! iterator
! erase(iterator __first, iterator __last);
!
! void
! clear()
! { _Base::clear(); }
!
! void
! resize(size_type __new_size, const _Tp& __x);
!
! void
! resize(size_type __new_size)
! { this->resize(__new_size, _Tp()); }
!
! void
! pop_front()
! { erase(begin()); }
!
! void
! pop_back()
{
! iterator __tmp = end();
! erase(--__tmp);
}
! list(size_type __n, const _Tp& __value,
! const allocator_type& __a = allocator_type())
! : _Base(__a)
! { insert(begin(), __n, __value); }
!
! explicit
! list(size_type __n)
! : _Base(allocator_type())
! { insert(begin(), __n, _Tp()); }
!
! // We don't need any dispatching tricks here, because insert does all of
! // that anyway.
! template<typename _InputIterator>
! list(_InputIterator __first, _InputIterator __last,
! const allocator_type& __a = allocator_type())
! : _Base(__a)
! { insert(begin(), __first, __last); }
!
! list(const list<_Tp, _Alloc>& __x)
! : _Base(__x.get_allocator())
! { insert(begin(), __x.begin(), __x.end()); }
!
! ~list()
! { }
!
! list<_Tp, _Alloc>&
! operator=(const list<_Tp, _Alloc>& __x);
!
! public:
! // assign(), a generalized assignment member function. Two
! // versions: one that takes a count, and one that takes a range.
! // The range version is a member template, so we dispatch on whether
! // or not the type is an integer.
!
! void
! assign(size_type __n, const _Tp& __val)
! { _M_fill_assign(__n, __val); }
!
! void
! _M_fill_assign(size_type __n, const _Tp& __val);
!
! template<typename _InputIterator>
! void
! assign(_InputIterator __first, _InputIterator __last)
! {
! typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
! _M_assign_dispatch(__first, __last, _Integral());
! }
!
! template<typename _Integer>
! void
! _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
! { _M_fill_assign((size_type) __n, (_Tp) __val); }
!
! template<typename _InputIterator>
! void
! _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
! __false_type);
!
! protected:
! void
! _M_transfer(iterator __position, iterator __first, iterator __last)
! {
! if (__position != __last) {
! // Remove [first, last) from its old position.
! __last._M_node->_M_prev->_M_next = __position._M_node;
! __first._M_node->_M_prev->_M_next = __last._M_node;
! __position._M_node->_M_prev->_M_next = __first._M_node;
!
! // Splice [first, last) into its new position.
! _List_node_base* __tmp = __position._M_node->_M_prev;
! __position._M_node->_M_prev = __last._M_node->_M_prev;
! __last._M_node->_M_prev = __first._M_node->_M_prev;
! __first._M_node->_M_prev = __tmp;
! }
! }
! public:
! void
! splice(iterator __position, list& __x)
! {
! if (!__x.empty())
! this->_M_transfer(__position, __x.begin(), __x.end());
! }
! void
! splice(iterator __position, list&, iterator __i)
! {
! iterator __j = __i;
! ++__j;
! if (__position == __i || __position == __j) return;
! this->_M_transfer(__position, __i, __j);
! }
! void
! splice(iterator __position, list&, iterator __first, iterator __last)
! {
! if (__first != __last)
! this->_M_transfer(__position, __first, __last);
! }
! void
! remove(const _Tp& __value);
! void
! unique();
! void
! merge(list& __x);
! void
! reverse();
!
! void
! sort();
!
! template<typename _Predicate>
! void
! remove_if(_Predicate);
!
! template<typename _BinaryPredicate>
! void
! unique(_BinaryPredicate);
!
! template<typename _StrictWeakOrdering>
! void
! merge(list&, _StrictWeakOrdering);
!
! template<typename _StrictWeakOrdering>
! void
! sort(_StrictWeakOrdering);
! };
!
! template<typename _Tp, typename _Alloc>
! inline bool
! operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
! {
! typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
! const_iterator __end1 = __x.end();
! const_iterator __end2 = __y.end();
!
! const_iterator __i1 = __x.begin();
! const_iterator __i2 = __y.begin();
! while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
! ++__i1;
! ++__i2;
! }
! return __i1 == __end1 && __i2 == __end2;
! }
! template<typename _Tp, typename _Alloc>
! inline bool
! operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
! {
! return lexicographical_compare(__x.begin(), __x.end(),
! __y.begin(), __y.end());
! }
! template<typename _Tp, typename _Alloc>
! inline bool
! operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
! { return !(__x == __y); }
!
! template<typename _Tp, typename _Alloc>
! inline bool
! operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
! { return __y < __x; }
!
! template<typename _Tp, typename _Alloc>
! inline bool
! operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
! { return !(__y < __x); }
!
! template<typename _Tp, typename _Alloc>
! inline bool
! operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
! { return !(__x < __y); }
!
! template<typename _Tp, typename _Alloc>
! inline void
! swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
! { __x.swap(__y); }
!
! // move these to stl_list.tcc
!
! template<typename _Tp, typename _Alloc>
! void _List_base<_Tp,_Alloc>::
! clear()
! {
! _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next);
! while (__cur != _M_node) {
! _List_node<_Tp>* __tmp = __cur;
! __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
! _Destroy(&__tmp->_M_data);
! _M_put_node(__tmp);
! }
! _M_node->_M_next = _M_node;
! _M_node->_M_prev = _M_node;
! }
!
! template<typename _Tp, typename _Alloc>
! template <typename _InputIter>
! void list<_Tp, _Alloc>::
! _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
! __false_type)
! {
! for ( ; __first != __last; ++__first)
! insert(__position, *__first);
!
! }
! template<typename _Tp, typename _Alloc>
! void list<_Tp, _Alloc>::
! _M_fill_insert(iterator __position, size_type __n, const _Tp& __x)
! {
! for ( ; __n > 0; --__n)
! insert(__position, __x);
}
! template<typename _Tp, typename _Alloc>
! typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::
! erase(iterator __first, iterator __last)
! {
! while (__first != __last)
! erase(__first++);
! return __last;
! }
! template<typename _Tp, typename _Alloc>
! void list<_Tp, _Alloc>::
! resize(size_type __new_size, const _Tp& __x)
! {
! iterator __i = begin();
! size_type __len = 0;
! for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
! ;
! if (__len == __new_size)
! erase(__i, end());
! else // __i == end()
! insert(end(), __new_size - __len, __x);
! }
! template<typename _Tp, typename _Alloc>
! list<_Tp, _Alloc>& list<_Tp, _Alloc>::
! operator=(const list<_Tp, _Alloc>& __x)
! {
! if (this != &__x) {
! iterator __first1 = begin();
! iterator __last1 = end();
! const_iterator __first2 = __x.begin();
! const_iterator __last2 = __x.end();
! while (__first1 != __last1 && __first2 != __last2)
! *__first1++ = *__first2++;
! if (__first2 == __last2)
! erase(__first1, __last1);
! else
! insert(__last1, __first2, __last2);
! }
! return *this;
! }
! template<typename _Tp, typename _Alloc>
! void list<_Tp, _Alloc>::
! _M_fill_assign(size_type __n, const _Tp& __val) {
! iterator __i = begin();
! for ( ; __i != end() && __n > 0; ++__i, --__n)
! *__i = __val;
! if (__n > 0)
! insert(end(), __n, __val);
! else
! erase(__i, end());
! }
! template<typename _Tp, typename _Alloc>
! template <typename _InputIter>
! void list<_Tp, _Alloc>::
! _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type)
! {
! iterator __first1 = begin();
! iterator __last1 = end();
! for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
! *__first1 = *__first2;
! if (__first2 == __last2)
! erase(__first1, __last1);
! else
! insert(__last1, __first2, __last2);
! }
! template<typename _Tp, typename _Alloc>
! void list<_Tp, _Alloc>::
! remove(const _Tp& __value)
! {
! iterator __first = begin();
! iterator __last = end();
! while (__first != __last) {
! iterator __next = __first;
! ++__next;
! if (*__first == __value) erase(__first);
! __first = __next;
! }
! }
! template<typename _Tp, typename _Alloc>
! void list<_Tp, _Alloc>::
! unique()
! {
! iterator __first = begin();
! iterator __last = end();
! if (__first == __last) return;
! iterator __next = __first;
! while (++__next != __last) {
! if (*__first == *__next)
! erase(__next);
! else
! __first = __next;
! __next = __first;
! }
! }
! template<typename _Tp, typename _Alloc>
! void list<_Tp, _Alloc>::
! merge(list<_Tp, _Alloc>& __x)
! {
! iterator __first1 = begin();
! iterator __last1 = end();
! iterator __first2 = __x.begin();
! iterator __last2 = __x.end();
! while (__first1 != __last1 && __first2 != __last2)
! if (*__first2 < *__first1) {
! iterator __next = __first2;
! _M_transfer(__first1, __first2, ++__next);
! __first2 = __next;
! }
! else
! ++__first1;
! if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
! }
!
! inline void
! __List_base_reverse(_List_node_base* __p)
! {
! _List_node_base* __tmp = __p;
! do {
! std::swap(__tmp->_M_next, __tmp->_M_prev);
! __tmp = __tmp->_M_prev; // Old next node is now prev.
! } while (__tmp != __p);
! }
!
! template<typename _Tp, typename _Alloc>
! inline void list<_Tp, _Alloc>::
! reverse()
! { __List_base_reverse(this->_M_node); }
!
! template<typename _Tp, typename _Alloc>
! void list<_Tp, _Alloc>::
! sort()
! {
! // Do nothing if the list has length 0 or 1.
! if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
! list<_Tp, _Alloc> __carry;
! list<_Tp, _Alloc> __counter[64];
! int __fill = 0;
! while (!empty()) {
! __carry.splice(__carry.begin(), *this, begin());
! int __i = 0;
! while(__i < __fill && !__counter[__i].empty()) {
! __counter[__i].merge(__carry);
! __carry.swap(__counter[__i++]);
! }
! __carry.swap(__counter[__i]);
! if (__i == __fill) ++__fill;
! }
!
! for (int __i = 1; __i < __fill; ++__i)
! __counter[__i].merge(__counter[__i-1]);
! swap(__counter[__fill-1]);
! }
! }
!
! template<typename _Tp, typename _Alloc>
! template <typename _Predicate>
! void list<_Tp, _Alloc>::
! remove_if(_Predicate __pred)
! {
! iterator __first = begin();
! iterator __last = end();
! while (__first != __last) {
! iterator __next = __first;
! ++__next;
! if (__pred(*__first)) erase(__first);
! __first = __next;
! }
! }
!
! template<typename _Tp, typename _Alloc>
! template <typename _BinaryPredicate>
! void list<_Tp, _Alloc>::
! unique(_BinaryPredicate __binary_pred)
! {
! iterator __first = begin();
! iterator __last = end();
! if (__first == __last) return;
! iterator __next = __first;
! while (++__next != __last) {
! if (__binary_pred(*__first, *__next))
! erase(__next);
! else
! __first = __next;
! __next = __first;
! }
! }
!
! template<typename _Tp, typename _Alloc>
! template <typename _StrictWeakOrdering>
! void list<_Tp, _Alloc>::
! merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp)
! {
! iterator __first1 = begin();
! iterator __last1 = end();
! iterator __first2 = __x.begin();
! iterator __last2 = __x.end();
! while (__first1 != __last1 && __first2 != __last2)
! if (__comp(*__first2, *__first1)) {
! iterator __next = __first2;
! _M_transfer(__first1, __first2, ++__next);
! __first2 = __next;
! }
! else
! ++__first1;
! if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
! }
!
! template<typename _Tp, typename _Alloc>
! template <typename _StrictWeakOrdering>
! void list<_Tp, _Alloc>::
! sort(_StrictWeakOrdering __comp)
! {
! // Do nothing if the list has length 0 or 1.
! if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
! list<_Tp, _Alloc> __carry;
! list<_Tp, _Alloc> __counter[64];
! int __fill = 0;
! while (!empty()) {
! __carry.splice(__carry.begin(), *this, begin());
! int __i = 0;
! while(__i < __fill && !__counter[__i].empty()) {
! __counter[__i].merge(__carry, __comp);
! __carry.swap(__counter[__i++]);
! }
! __carry.swap(__counter[__i]);
! if (__i == __fill) ++__fill;
! }
!
! for (int __i = 1; __i < __fill; ++__i)
! __counter[__i].merge(__counter[__i-1], __comp);
! swap(__counter[__fill-1]);
! }
! }
} // namespace std
#endif /* __SGI_STL_INTERNAL_LIST_H */
+ // vi:set ts=2 sw=2:
// Local Variables:
// mode:C++
// End:
__
Stephen M. Webb