目录

构造函数

析构函数

结点：

创建结点

_ACC找结点的三个域

插入

插入的三种方式

删除结点

其他基于插入删除的函数

运算符重载

与size有关的函数

开头定义一个模板

allocator:空间配置器，负责开辟空间

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

构造函数

构造函数一共三个

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);
//大小置0_Head = 0, _Size = 0;}

结点：

        双向链表，包含指向下一个结点的指针、指向当前结点的指针，和当前结点的值。

struct _Node 
{_Nodeptr _Next, _Prev;//后，前指针_Ty _Value;//值
};

_Nodeptr是指向node的指针类型

typedef _POINTER_X(_Node, _A) _Nodeptr;

创建结点

在此假设当前结点为p，传入p和p->prev。

创建一个结点S，目标是把S插入到p前面（头插）（如果p是空说明S作为头节点）。

//传当前结点(p,p->prev)
_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
{//开空间_S_Nodeptr _S = (_Nodeptr)allocator._Charalloc(1 * sizeof (_Node));//p若不等于空，_S->next = p，否则，_S->next指向_S_Acc::_Next(_S) = _Narg != 0 ? _Narg : _S;//p->prev若不等于空，_S->prev= p->prev，否则，指向_S。_Acc::_Prev(_S) = _Parg != 0 ? _Parg : _S;return (_S);}

_ACC找结点的三个域

使用static静态可以不用使用对象直接用成员函数，如： _Acc::_Next(_P) == _P->next

struct _Acc 
{
//node结点p指针ref引用，结点指针的引用typedef _REFERENCE_X(_Nodeptr, _A) _Nodepref;
//值类型的引用typedef _A::reference _Vref;
//返回指向的下一个结点的指针static _Nodepref _Next(_Nodeptr _P){return ((_Nodepref)(*_P)._Next); }
//返回指向的（_P）前一个结点（_P->prev）的指针static _Nodepref _Prev(_Nodeptr _P){return ((_Nodepref)(*_P)._Prev);}
//返回_P指向的值static _Vref _Value(_Nodeptr _P){return ((_Vref)(*_P)._Value); }
};

插入

//迭代器_P，值_X
iterator insert(iterator _P, const _Ty& _X = _Ty())
{
//把迭代器转成指针指向当前结点_Nodeptr _S = _P._Mynode();
//_S的前驱指向新创建的一个结点（在Buynode中这个新创建的结点）_Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));
//_S指向刚才创建的结点_S = _Acc::_Prev(_S);
//_S->prev->next = _S_Acc::_Next(_Acc::_Prev(_S)) = _S;allocator.construct(&_Acc::_Value(_S), _X);++_Size;//个数++return (iterator(_S)); 
}

插入的三种方式

在p位置插入M个x

在p位置插入_F到_L的数据（指针、值传递）

void insert(iterator _P, size_type _M, const _Ty& _X)
{for (; 0 < _M; --_M)insert(_P, _X);//每次都是在_P的位置插（头插）
}
void insert(iterator _P, const _Ty *_F, const _Ty *_L)//指针传递
{for (; _F != _L; ++_F)insert(_P, *_F);}
void insert(iterator _P, _It _F, _It _L)//值传递
{for (; _F != _L; ++_F)insert(_P, *_F);}

删除结点

iterator erase(iterator _P)
{_Nodeptr _S = (_P++)._Mynode();
//_S->prev->next = _S->next_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
//_S->next->prev = _S->prev_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);allocator.destroy(&_Acc::_Value(_S));//销毁_S结点_Freenode(_S);//释放--_Size;//结点个数减一return (_P);
}
//删除多个结点F到L
iterator erase(iterator _F, iterator _L)
{while (_F != _L)erase(_F++);return (_F);
}

其他基于插入删除的函数

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

运算符重载

		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;

与size有关的函数

//重新赋大小
void resize(size_type _N, _Ty _X = _Ty())
{if (size() < _N)//原本的小，给结尾插 _N - size()个_Xinsert(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); }

未完待续