VC STL的list iterator P.J实现

VC++ P.J STL list的实现

<<programmer-13-memory-pool>>

侯捷觀點 - 池內春秋— Memory Pool 的設計哲學和無痛運用

在文章中提到VC STL PJ实现这个版本的的allocator. (内存池与内存分配器).同时自己为了需要写一个在数据库的大量数据缓冲池,类似内存池管理的东西和它的叠加器iterator.刚好借鉴VC list中的iterator的实现代码,而是将list的代码看了一下,证实了一些”侯捷觀點 - 池內春秋— Memory Pool 的設計哲學和無痛運用”,另外有一点是PJ的代码可读性差是差点,也不见的非常差,看多了也不觉得这可能与习惯有关,感觉PJ的代码实现简洁很多, 代码没有GCC的实现的STL多,所以看和理解没有这么曲折.

主要看看它的iterator的实现.其他list的函数很多书籍都有介绍,或者直接看list的代码实现,这样理解比较深刻. 清楚iterator实现,以后直接copy过来改改就行

STL中为了类型的安全会使用到众多的typedef,别看得类型眼花缭乱.J

VC的list模板声明,它使用到了缺省的allocator内存分配器.下面有它的实现的代码

文件:stddef.h

#ifndef _PTRDIFF_T_DEFINED

typedef int ptrdiff_t;

#define _PTRDIFF_T_DEFINED

#endif

文件:utility

空tag类,主要目的是作iterator trains用

struct input_iterator_tag {};

struct output_iterator_tag {};

struct forward_iterator_tag

: public input_iterator_tag {};

struct bidirectional_iterator_tag

: public forward_iterator_tag {};

struct random_access_iterator_tag

: public bidirectional_iterator_tag {};

//最基层的iterator声明,实质是一个空类,提供类型定义

template<class _C, class _Ty, class _D = ptrdiff_t>

struct iterator {

typedef _C iterator_category;

typedef _Ty value_type;

typedef _D distance_type;

};

//最基层的_Bidit声明,实质是一个空类

template<class _Ty, class _D>

struct _Bidit : public iterator<bidirectional_iterator_tag,

_Ty, _D> {};

文件:list

例如:iterator常使用的方式.

X::iterator it;

for(it = x.begin();it!=x.end();++it)

? = *it;

这里涉及了list函数begin(),end(),iterator的!=操作符,*操作符,++操作符.

const_iterator在list的中的声明,其实不必理会这个_Bidit基层类,可以看作没有.

const_iterator有一个成员变量_Nodeptr _Ptr;保存当前的链表节点指针.指针的移动变换通过_Acc这个中间类来实现,在list中定义

class const_iterator : public _Bidit<_Ty, difference_type> {

public:

const_iterator()

{}

const_iterator(_Nodeptr _P)

: _Ptr(_P) {}

const_iterator(const iterator& _X)

: _Ptr(_X._Ptr) {}

const_reference operator*() const

{return (_Acc::_Value(_Ptr)); }

_Ctptr operator->() const

{return (&**this); }

const_iterator& operator++()

{_Ptr = _Acc::_Next(_Ptr);

return (*this); }

const_iterator operator++(int)

{const_iterator _Tmp = *this;

++*this;

return (_Tmp); }

const_iterator& operator--()

{_Ptr = _Acc::_Prev(_Ptr);

return (*this); }

const_iterator operator--(int)

{const_iterator _Tmp = *this;

--*this;

return (_Tmp); }

bool operator==(const const_iterator& _X) const

{return (_Ptr == _X._Ptr); }

bool operator!=(const const_iterator& _X) const

{return (!(*this == _X)); }

_Nodeptr _Mynode() const

{return (_Ptr); }

protected:

_Nodeptr _Ptr;

};

//iterator在list的中的声明,它继承了const_iterator

friend class iterator;

class iterator : public const_iterator {

public:

iterator()

{}

iterator(_Nodeptr _P)

: const_iterator(_P) {}

reference operator*() const

{return (_Acc::_Value(_Ptr)); }

_Tptr operator->() const

{return (&**this); }

iterator& operator++()

{_Ptr = _Acc::_Next(_Ptr);

return (*this); }

iterator operator++(int)

{iterator _Tmp = *this;

++*this;

return (_Tmp); }

iterator& operator--()

{_Ptr = _Acc::_Prev(_Ptr);

return (*this); }

iterator operator--(int)

{iterator _Tmp = *this;

--*this;

return (_Tmp); }

bool operator==(const iterator& _X) const

{return (_Ptr == _X._Ptr); }

bool operator!=(const iterator& _X) const

{return (!(*this == _X)); }

};

template<class _Ty, class _A = allocator<_Ty> >

class list {

protected:

struct _Node;

friend struct _Node;

typedef _POINTER_X(_Node, _A) _Nodeptr;

//链表的数据结构J

struct _Node {

_Nodeptr _Next, _Prev;

_Ty _Value;

};

struct _Acc;

friend struct _Acc;

//这个结构只有是用在iterator,设计它的目的是将iterator和指针的移动实现分离.这样使得//iterator的代码非常的简洁和干净,注意到他们都是static函数

struct _Acc {

typedef _REFERENCE_X(_Nodeptr, _A) _Nodepref;

typedef _A::reference _Vref;

static _Nodepref _Next(_Nodeptr _P)

{return ((_Nodepref)(*_P)._Next); }

static _Nodepref _Prev(_Nodeptr _P)

{return ((_Nodepref)(*_P)._Prev); }

static _Vref _Value(_Nodeptr _P)

{return ((_Vref)(*_P)._Value); }

};

public:

// 类型安全的typedef定义

typedef list<_Ty, _A> _Myt;

typedef _A allocator_type;

typedef _A::size_type size_type;

typedef _A::difference_type difference_type;

typedef _A::pointer _Tptr;

typedef _A::const_pointer _Ctptr;

typedef _A::reference reference;

typedef _A::const_reference const_reference;

typedef _A::value_type value_type;

// iterator的向前声明

class iterator;

class const_iterator;

friend class const_iterator;

//构造函数

explicit list(const _A& _Al = _A())

: allocator(_Al),

_Head(_Buynode()), _Size(0) {}

explicit list(size_type _N, const _Ty& _V = _Ty(),

const _A& _Al = _A())

: allocator(_Al),

_Head(_Buynode()), _Size(0)

{insert(begin(), _N, _V); }

list(const _Myt& _X)

: allocator(_X.allocator),

_Head(_Buynode()), _Size(0)

{insert(begin(), _X.begin(), _X.end()); }

list(const _Ty *_F, const _Ty *_L, const _A& _Al = _A())

: allocator(_Al),

_Head(_Buynode()), _Size(0)

{insert(begin(), _F, _L); }

typedef const_iterator _It;

list(_It _F, _It _L, const _A& _Al = _A())

: allocator(_Al),

_Head(_Buynode()), _Size(0)

{insert(begin(), _F, _L); }

~list()

{erase(begin(), end());

_Freenode(_Head);

_Head = 0, _Size = 0; }

_Myt& operator=(const _Myt& _X)

{if (this != &_X)

{iterator _F1 = begin();

iterator _L1 = end();

const_iterator _F2 = _X.begin();

const_iterator _L2 = _X.end();

for (; _F1 != _L1 && _F2 != _L2; ++_F1, ++_F2)

*_F1 = *_F2;

erase(_F1, _L1);

insert(_L1, _F2, _L2); }

return (*this); }

// 下面是一些常用到涉及iterator的方法

// begin(),end()都是返回一个iterator对象,其他类似

iterator begin()

{return (iterator(_Acc::_Next(_Head))); }

const_iterator begin() const

{return (const_iterator(_Acc::_Next(_Head))); }

iterator end()

{return (iterator(_Head)); }

const_iterator end() const

{return (const_iterator(_Head)); }

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())); }

// 下面是一些常用方法

void resize(size_type _N, _Ty _X = _Ty())

{if (size() < _N)

insert(end(), _N - size(), _X);

else

while (_N < size())

pop_back(); }

size_type size() const

{return (_Size); }

size_type max_size() const

{return (allocator.max_size()); }

bool empty() const

{return (size() == 0); }

_A get_allocator() const

{return (allocator); }

reference front()

{return (*begin()); }

const_reference front() const

{return (*begin()); }

reference back()

{return (*(--end())); }

const_reference back() const

{return (*(--end())); }

void push_front(const _Ty& _X)

{insert(begin(), _X); }

void pop_front()

{erase(begin()); }

void push_back(const _Ty& _X)

{insert(end(), _X); }

void pop_back()

{erase(--end()); }

void assign(_It _F, _It _L)

{erase(begin(), end());

insert(begin(), _F, _L); }

void assign(size_type _N, const _Ty& _X = _Ty())

{erase(begin(), end());

insert(begin(), _N, _X); }

…………..

};

内存分配器实现

很明显allocate调用_Allocate 模板函数使用了operator new实现,deallocate使用到了delete实现,所以allocate是C++new和delete的浅层包装类.

文件:xmemory

#define _FARQ

#define _PDFT ptrdiff_t

#define _SIZT size_t

template<class _Ty> inline

_Ty _FARQ *_Allocate(_PDFT _N, _Ty _FARQ *)

{if (_N < 0)

_N = 0;

return ((_Ty _FARQ *)operator new(

(_SIZT)_N * sizeof (_Ty))); }

template<class _Ty>

class allocator {

public:

typedef _SIZT size_type;

typedef _PDFT difference_type;

typedef _Ty _FARQ *pointer;

typedef const _Ty _FARQ *const_pointer;

typedef _Ty _FARQ& reference;

typedef const _Ty _FARQ& const_reference;

typedef _Ty value_type;

pointer address(reference _X) const

{return (&_X); }

const_pointer address(const_reference _X) const

{return (&_X); }

pointer allocate(size_type _N, const void *)

{return (_Allocate((difference_type)_N, (pointer)0)); }

char _FARQ *_Charalloc(size_type _N)

{return (_Allocate((difference_type)_N,

(char _FARQ *)0)); }

void deallocate(void _FARQ *_P, size_type)

{operator delete(_P); }

void construct(pointer _P, const _Ty& _V)

{_Construct(_P, _V); }

void destroy(pointer _P)

{_Destroy(_P); }

_SIZT max_size() const

{_SIZT _N = (_SIZT)(-1) / sizeof (_Ty);

return (0 < _N ? _N : 1); }

};

附录:

SGI的STL 实现

list头文件

#ifndef __SGI_STL_LIST

#define __SGI_STL_LIST

#include <stl_algobase.h>

#include <stl_alloc.h>

#include <stl_construct.h>

#include <stl_uninitialized.h>

#include <stl_list.h>

#endif /* __SGI_STL_LIST */

stl_list.h

#ifndef __SGI_STL_INTERNAL_LIST_H

#define __SGI_STL_INTERNAL_LIST_H

#include <concept_checks.h>

__STL_BEGIN_NAMESPACE

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)

#pragma set woff 1174

#pragma set woff 1375

#endif

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; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR

pointer operator->() const { return &(operator*()); }

#endif /* __SGI_STL_NO_ARROW_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;

}

};

#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION

inline bidirectional_iterator_tag

iterator_category(const _List_iterator_base&)

{

return bidirectional_iterator_tag();

}

template <class _Tp, class _Ref, class _Ptr>

inline _Tp*

value_type(const _List_iterator<_Tp, _Ref, _Ptr>&)

{

return 0;

}

inline ptrdiff_t*

distance_type(const _List_iterator_base&)

{

return 0;

}

#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */

// 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.

#ifdef __STL_USE_STD_ALLOCATORS

// 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();

};

#else /* __STL_USE_STD_ALLOCATORS */

template <class _Tp, class _Alloc>

class _List_base

{

public:

typedef _Alloc allocator_type;

allocator_type get_allocator() const { return allocator_type(); }

_List_base(const allocator_type&) {

_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();

protected:

typedef simple_alloc<_List_node<_Tp>, _Alloc> _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;

};

#endif /* __STL_USE_STD_ALLOCATORS */

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 = __STL_DEFAULT_ALLOCATOR(_Tp) >

class list : protected _List_base<_Tp, _Alloc> {

// requirements:

__STL_CLASS_REQUIRES(_Tp, _Assignable);

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;

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION

typedef reverse_iterator<const_iterator> const_reverse_iterator;

typedef reverse_iterator<iterator> reverse_iterator;

#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */

typedef reverse_bidirectional_iterator<const_iterator,value_type,

const_reference,difference_type>

const_reverse_iterator;

typedef reverse_bidirectional_iterator<iterator,value_type,reference,

difference_type>

reverse_iterator;

#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */

protected:

#ifdef __STL_HAS_NAMESPACES

using _Base::_M_node;

using _Base::_M_put_node;

using _Base::_M_get_node;

#endif /* __STL_HAS_NAMESPACES */

protected:

_Node* _M_create_node(const _Tp& __x)

{

_Node* __p = _M_get_node();

__STL_TRY {

_Construct(&__p->_M_data, __x);

}

__STL_UNWIND(_M_put_node(__p));

return __p;

}

_Node* _M_create_node()

{

_Node* __p = _M_get_node();

__STL_TRY {

_Construct(&__p->_M_data);

}

__STL_UNWIND(_M_put_node(__p));

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()); }

#ifdef __STL_MEMBER_TEMPLATES

// 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());

}

#else /* __STL_MEMBER_TEMPLATES */

void insert(iterator __position, const _Tp* __first, const _Tp* __last);

void insert(iterator __position,

const_iterator __first, const_iterator __last);

#endif /* __STL_MEMBER_TEMPLATES */

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()); }

#ifdef __STL_MEMBER_TEMPLATES

// 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); }

#else /* __STL_MEMBER_TEMPLATES */

list(const _Tp* __first, const _Tp* __last,

const allocator_type& __a = allocator_type())

: _Base(__a)

{ this->insert(begin(), __first, __last); }

list(const_iterator __first, const_iterator __last,

const allocator_type& __a = allocator_type())

: _Base(__a)

{ this->insert(begin(), __first, __last); }

#endif /* __STL_MEMBER_TEMPLATES */

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);

#ifdef __STL_MEMBER_TEMPLATES

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);

#endif /* __STL_MEMBER_TEMPLATES */

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();

#ifdef __STL_MEMBER_TEMPLATES

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);

#endif /* __STL_MEMBER_TEMPLATES */

};

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());

}

#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER

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);

}

#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */

#ifdef __STL_MEMBER_TEMPLATES

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);

}

#else /* __STL_MEMBER_TEMPLATES */

template <class _Tp, class _Alloc>

void

list<_Tp, _Alloc>::insert(iterator __position,

const _Tp* __first, const _Tp* __last)

{

for ( ; __first != __last; ++__first)

insert(__position, *__first);

}

template <class _Tp, class _Alloc>

void

list<_Tp, _Alloc>::insert(iterator __position,

const_iterator __first, const_iterator __last)

{

for ( ; __first != __last; ++__first)

insert(__position, *__first);

}

#endif /* __STL_MEMBER_TEMPLATES */

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());

}

#ifdef __STL_MEMBER_TEMPLATES

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);

}

#endif /* __STL_MEMBER_TEMPLATES */

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]);

}

}

#ifdef __STL_MEMBER_TEMPLATES

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]);

}

}

#endif /* __STL_MEMBER_TEMPLATES */

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)

#pragma reset woff 1174

#pragma reset woff 1375

#endif

__STL_END_NAMESPACE

#endif /* __SGI_STL_INTERNAL_LIST_H */

• ·HTML超强编辑器网站
• ·Windows Media Format SD
• ·C#中Base64之编码,解码方法
• ·“四色定理”证明
• ·RedHat9.0下安装Oracle8i
• ·Vistual studio 中在设计时显示控
• ·Shell FAQ 以后累加
• ·操作系统——动态优先级调度算法源代码
• ·用OpenGL实现射线拣取对象
• ·使用MiddleGen 产生hibernate