首页 > 代码库 > (C++ STL)list的实现
(C++ STL)list的实现
#include <iostream>
using namespace std;
//採用迭代器和空间配置器所实现的双向链表的基本功能
template<class _Ty,class _A = allocator<_Ty> >
//定义模板类
class list
//list类
{
public:
typedef size_t size_type;
//类型重定义
protected:
struct _Node;
//结构体_Node
friend struct _Node;
//友元
typedef _Node* _Nodeptr;
//类型重定义
struct _Node
//结构体定义
{
_Nodeptr _Next,_Prev;
_Ty _Value;
};
protected:
_A allocator;
_Nodeptr _Head;
size_type _Size;
public:
typedef list<_Ty,_A> _Myt;
typedef _A allocator_type;
//该类型是模板參数A的同义词
typedef size_t size_type;
//正整数类型
typedef ptrdiff_t difference_type;
//整数类型
typedef _Ty* pointer;
//指向_Ty的指针
typedef const _Ty* const_pointer;
//指向_Ty的常量指针
typedef _Ty& reference;
//_Ty的引用
typedef const _Ty& const_reference;
//_Ty的常量引用
typedef _Ty value_type;
//对象类型_Ty
class iterator;
//訪问list的迭代器
class const_iterator;
//訪问list的常量迭代器
friend class const_iterator;
//友元
class const_iterator : public _Bidit<_Ty, difference_type>
//继承
{
public:
//共同拥有成员
_Nodeptr _Mynode() const
//指向当前结点
{
return (_Ptr);
}
const_iterator()
//默认构造函数
{}
const_iterator(_Nodeptr _P):_Ptr(_P)
//參数为指针的构造函数
{}
const_iterator(const iterator& _X):_Ptr(_X._Ptr)
//參数为訪问list的常量迭代器的构造函数
{}
const_reference operator*() const
//获取当前_Ty的常量的值
{
return _Ptr->_Value;
}
const_pointer operator->() const
//?
{
return (&**this);
}
const_iterator& operator++()
//前置++的引用
{
_Ptr = _Ptr->_Next;
return (*this);
}
const_iterator operator++(int)
//后置++的引用
{
const_iterator _Tmp = *this;
++*this;
return (_Tmp);
}
const_iterator& operator--()
//前置--的引用
{
_Ptr = _Ptr->_Prev;
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));
}
protected:
//保护成员
_Nodeptr _Ptr;
};
friend class iterator;
//友元
class iterator : public const_iterator
//继承
{
public:
iterator()
//默认构造函数
{}
iterator(_Nodeptr _P): const_iterator(_P)
//參数为指针的构造函数
{}
reference operator*() const
//获取当前_Ty的值
{
return _Ptr->_Value;
}
_Ty* operator->() const
//?
{
return (&**this);
}
iterator& operator++()
//前置++的引用
{
_Ptr = _Ptr->_Next;
return (*this);
}
iterator operator++(int)
//后置++的引用
{
iterator _Tmp = *this;
++*this;
return (_Tmp);
}
iterator& operator--()
//前置--的引用
{
_Ptr = _Ptr->_Prev;
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));
}
};
public:
_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
//购买结点
{
_Nodeptr _S = (_Nodeptr)allocator._Charalloc( //开辟空间
1 * sizeof (_Node));
_S->_Next = _Narg != 0 ? _Narg : _S;;
_S->_Prev = _Parg != 0 ? _Parg : _S;
return (_S);
}
void _Freenode(_Nodeptr _S)
//释放空间
{
allocator.deallocate(_S, 1);
}
void _Splice(iterator _P, _Myt& _X, iterator _F, iterator _L)
//拼接
{
if (allocator == _X.allocator) //将两个拼接到一起，_X清空
{
(_L._Mynode())->_Prev->_Next = _P._Mynode();
(_F._Mynode())->_Prev->_Next = _L._Mynode();
(_P._Mynode())->_Prev->_Next = _F._Mynode();
_Nodeptr _S = (_P._Mynode())->_Prev;
(_P._Mynode())->_Prev =(_L._Mynode())->_Prev;
(_L._Mynode())->_Prev =(_F._Mynode())->_Prev;
(_F._Mynode())->_Prev = _S;
}
else //将_X中的链表数值加入到_P中，_X清空
{
insert(_P, _F, _L);
_X.erase(_F, _L);
}
}
void _Xran() const
//抛出异常
{
_THROW(out_of_range, "invalid list<T> subscript");
}
public:
size_type size() const
//长度
{
return (_Size);
}
bool empty() const
//判空
{
return (size() == 0);
}
_A get_allocator() const
//返回空间配置器
{
return (allocator);
}
void resize(size_type _N, _Ty _X = _Ty())
//又一次定义链表长度
{
if (size() < _N)
{
insert(end(), _N - size(), _X);
}
else
{
while (_N < size())
{
pop_back();
}
}
}
size_type max_size() const
//返回链表最大可能长度
{
return (allocator.max_size());
}
reference front()
//返回第一个元素的引用
{
return (*begin());
}
const_reference front() const
//返回第一个元素的常量引用
{
return (*begin());
}
reference back()
//返回最后一元素的引用
{
return (*(--end()));
}
const_reference back() const
//返回最后一元素的常量引用
{
return (*(--end()));
}
_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);
}
public:
explicit list():_Head(_Buynode()), _Size(0)
//空链表
{}
explicit list(const _Ty& _V):_Head(_Buynode()), _Size(0)
//建一个含_V个默认值是0的元素的链表
{
insert(begin(),_V,0);
}
explicit list(size_type _N, const _Ty& _V):_Head(_Buynode()), _Size(0)
//建一个含_V个元素的链表。值都是_N
{
insert(begin(),_N, _V);
}
list(const _Myt& _X): _Head(_Buynode()), _Size(0)
//建一个_X的copy链表
{
insert(begin(), _X.begin(), _X.end());
}
list(const _Ty *_F, const _Ty *_L): _Head(_Buynode()), _Size(0)
//一个区域的元素[_First, _Last)。
{
insert(begin(), _F, _L);
}
typedef const_iterator _It;
list(_It _F, _It _L):_Head(_Buynode()), _Size(0)
//常量迭代器
{
insert(begin(), _F, _L);
}
iterator begin()
//迭代器第一个节点
{
return iterator(_Head->_Next);
}
const_iterator begin() const
//常量迭代器第一个节点
{
return (const_iterator(_Head->_Next));
}
iterator end()
//返回最后一个元素的下一位置的指针
{
return iterator(_Head);
}
const_iterator end() const
//返回最后一个元素的下一位置的指针
{
return (const_iterator(_Head));
}
iterator insert(iterator _P,const _Ty& _X)
//在_P之前插入结点
{
_Nodeptr _S = _P._Mynode();
_S->_Prev = _Buynode(_S,_S->_Prev);
_S = _S->_Prev;
_S->_Prev->_Next = _S;
_S->_Value = http://www.mamicode.com/_X; >
(C++ STL)list的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。