【C++】list链表容器功能模拟实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++】list链表容器功能模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

介绍

一，容器的结构设计

二，构造函数与赋值运算符

三，析构函数

四，list容器接口

1，begin和end

2，insert和erase

3，其它常用接口函数

介绍

上一次介绍了list双向链表容器的迭代器模拟，这次模拟实现list的简单功能，尤其要注意构造函数、析构函数、以及赋值运算符重载的实现。这里需要进行深拷贝和确定“ 哨兵结点 ”。

我们先回顾list迭代器的模拟结构，如下：

//结点

template<class T> //模板
struct ListNode
{
ListNode<T>* _next; //指向前结点的指针
ListNode<T>* _last; //指向后结点的指针
T _data;
ListNode(const T& x = T())
:_next(nullptr)
, _last(nullptr)
, _data(x)
{ }
}

//迭代器

template<class T, class Ref, class Ptr> //T表示数据类型，Ref表示T& 或 const T&，Ptr表示T* 或 const T*
struct ListIterator
{
typedef ListNode<T>* PNode; //结点
typedef ListIterator<T, Ref, Ptr> Self; //迭代器
PNode _pNode; //结点成员
ListIterator(PNode pNode = nullptr); //传入结点的构造函数

ListIterator(const Self& l); //传入迭代器的构造函数

Ref operator*(); //*操作符重载，相当与指针的解引用，直接返回具体数据

Ptr operator->(); //->操作符重载，这里我们实现"->"指向T类型数据

Self& operator++(); //后置++，要返回迭代器本身

Self operator++(int); //前置++

Self& operator--(); //后置--

Self operator--(int); //前置--

bool operator!=(const Self& l); //"!="操作符重载

bool operator==(const Self& l); //"=="操作符重载

};

一，容器的结构设计

list容器在建立初就先要确定“ 哨兵结点 ”，因此，这里需在构造函数中确定哨兵结点，而在设计功能函数时，要思考运用什么类型。这里，我们的结构设计如下：

template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* PNode;
public:
typedef ListIterator<T, T&, T*> iterator; //list迭代器
typedef ListIterator<T, const T&, const T*> const_iterator; //const型迭代器，指向const型

list(); //无参构造

list(int n, const T& value = T()); //n个T类型数据的构造

template <class Iterator>
list(Iterator first, Iterator last); //迭代器方式的构造

list(const list<T>& l); //list的拷贝构造

list<T>& operator=(const list<T> l); //赋值运算符重载

~list(); //析构函数的使用

iterator begin(); //返回头结点的迭代器

iterator end(); //返回指向尾结点下一个结点的迭代器

const_iterator begin() const; //const_iterator型begin的情况，运用const修饰this指针表示begin函数重载

const_iterator end() const;

size_t size()const; //容器大小

bool empty()const; //判断容器是否为空

T& front(); //返回首元素

const T& front()const; //const_iterator型front的情况，const修饰表示重载

T& back(); //返回尾元素

const T& back()const; //const_iterator型back()情况

void push_back(const T& val); //尾插

void pop_back(); //尾删

void push_front(const T& val); //头插

void pop_front(); //头删

iterator insert(iterator pos, const T& val); //在pos迭代器指向的位置插入数据val，返回此刻位置的迭代器

iterator erase(iterator pos);// 删除pos位置的节点，返回该节点的下一个位置

void clear(); //清空所有结点

void swap(list<T>& l); //实现队列的交换

private:
void CreateHead(); //运用此函数确定" 哨兵结点 "以及哨兵结点内部的结构
PNode _pHead; //哨兵结点
};

二，构造函数与赋值运算符

构造函数

构造函数需确定“ 哨兵结点 ”，因为这里使用链式结构存储，需在开始阶段确定哨兵结点，这样方便后面数据的插入与执行。要注意的是这里设计到动态内存的管理，因此需要进行深拷贝。

void CreateHead()
{
_pHead = new Node;
_pHead->_pNext = _pHead;
_pHead->_pPre = _pHead;
}

//无参构造，直接确定哨兵结点即可
list()
{
CreateHead();
}

//实现插入n个数据的构造，这里运用了内部的功能函数

list(int n, const T& value = T())
{
CreateHead();
for (int i = 0; i < n; i++)
{
push_back(value); //直接未插即可
}
}

//迭代器方式构造

template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
Iterator it = first;
while (it != last)
{
push_back((it._pNode)->_val);
it++;
}
}

//拷贝构造

list(const list<T>& l)
{
CreateHead();
*this = l; //这里直接运用赋值运算符
}

赋值运算符

这里唯一要注意的是赋值运算符要实现深拷贝。

list<T>& operator=(const list<T> l)
{
iterator it = l.begin();
for (size_t i = 0; i < l.size(); i++)
{
push_back((it._pNode)->_val);
it++;
}
return *this;
}

三，析构函数

析构函数的设计只需诼渐释放所有结点即可，注意，释放结点时要将“ 哨兵结点 ”一并释放，代码如下：

~list()
{
clear(); //先清空所有数据结点
delete _pHead; //释放哨兵结点
_pHead = nullptr;
}

四，list容器接口

1，begin和end

这里的begin()与end()返回的分别是第一个结点的迭代器与最后一个结点的迭代器，因此，这里分为const迭代器型与非const迭代器型，在设计时为了实现函数重载，这里我们可使用const来修饰this指针进行区分。还有就是注意隐式类型的转换.。

//非const迭代器的使用

iterator begin()
{
return _pHead->_pNext; //这里返回的结点，用迭代器接收，迭代器内部有结点类型的构造函数，可以进行隐式类型的转换
}
iterator end()
{
return _pHead;
}

//const迭代器的使用

const_iterator begin() const
{
return _pHead->_pNext; //这里直接返回即可，相当于不管传入的数据，我们直接返回一个const成员
}
const_iterator end() const
{
return _pHead;
}

2，insert和erase

insert和erase返回的都是迭代器，由于迭代器内部我们实现了结点的构造函数，因此可以直接返回结点进行隐式类型转换。

// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
PNode tem = new Node(val);
tem->_pNext = pos._pNode;
tem->_pPre = (pos._pNode)->_pPre;
(pos._pNode)->_pPre->_pNext = tem;
(pos._pNode)->_pPre = tem;
return tem; //因为iterator封装中存在tem类型的构造函数，因此这里可以进行隐式类型转换
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
assert(_pHead->_pNext != _pHead);
iterator it = pos;
PNode next = (pos._pNode)->_pNext;
delete pos._pNode;
return next;
}

3，其它常用接口函数

在list内部，其它常用接口有size()、empty()、front()、back()、push_back()、 pop_back()、push_front()、pop_front()、clear()、swap() 等，接口在实现时较为简单，我们直接实现，如下：

size_t size()const
{
size_t count = 0;
iterator tem = begin();
while (tem != end())
{
count++;
tem++;
}
return count;
}
bool empty()const
{
return _pHead->_pNext == _pHead;
}
T& front()
{
return _pHead->_pNext->_val;
}
const T& front()const //const迭代器返回
{
//注意:这里不能使用return const _pHead->_pNext->_val;因为这里的错误相当于T a = front()即T a = const _pHead->_pNext->_val;
//const是用来修饰类型的，不是直接修饰数据的
return _pHead->_pNext->_val;
}
T& back()
{
return _pHead->_pPre->_val;
}
const T& back()const //const迭代器返回
{
return _pHead->_pPre->_val;
}
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
void clear()
{
iterator it(begin());
while (it != end())
{
it = erase(it);
}
}
void swap(list<T>& l)
{
std::swap(_pHead, l._pHead);
}