c++之List容器的模拟实现

注：最终代码以汇总的为准

1.前言

在之前的数据结构中，我们曾模拟实现过链表的数据结构，但是十分麻烦，全篇都暴露了链表的底层结构-----指针，但是从使用的角度，使用者并不关心你用的底层结构是啥，而且编写者也不愿意将所有的底层结构暴露出来，为此，在此文章中，我们将充分发挥c++的优势，将指针包装一下，变为迭代器

2.基本框架的实现

基本结构包括链表的创建，包括链表结点的创建，结点的初始化，以及对底层结构----指针的封装,还有一些基本操作，例如++，==，！=，还有解引用操作等。

我们将造链表的文件放在List.h文件中，等下在test.cpp文件中进行测试。

如下代码是基本的结构代码：（具体功能没实现）

#include <assert.h>
namespace rens
{template<class T>struct list_node              //定义结点结构{list_node* <T> _next;list_node* <T> _prev;T _data;list_node(const T& x=T()):_next(nullptr),_prev(nullptr),_data(x){}};
}
template <class T>
struct list_iterator
{typedef list_node<T> Node;Node* _node;list_iterator(Node* node):_node(node){}T& operator*()                  //模拟指针的解引用{return _node->_data;        //返回的是数据，类型为T}T* operator->()                 //解引用的->,这个较为特殊{return &_node->_data;}list_iterator<T>& operator++(){_node = _node->_next;return *this;              //++操作返回的是下一个结点}bool operator!=(const list_iterator<T>& it){return this->_node != it._node;}bool operator==(const list_node<T>& it){return this->_node == it._node;}
};template <class T>
class list
{typedef list_node<T> Node;
public:typedef list_iterator<T> iterator;
private:Node* _head;size_t _size;
};

但是，上述代码如果要是想遍历const对象是，由于我们的迭代器不是const迭代器，不能满足我们的需求，为此我们还要将上述代码cv一份，并改为const迭代器。

const迭代器代码如下：

template <class T>
struct const_list_iterator
{typedef list_node<T> Node;Node* _node;const_list_iterator(Node* node):_node(node){}const T& operator*()                  //模拟指针的解引用{return _node->_data;        //返回的是数据，类型为T}const T* operator->()                 //解引用的->,这个较为特殊{return &_node->_data;}const_list_iterator<T>& operator++(){_node = _node->_next;return *this;              //++操作返回的是下一个结点}bool operator!=(const const_list_iterator<T>& it){return this->_node != it._node;}bool operator==(const const_list_iterator<T>& it){return this->_node == it._node;}
};

但是，通过对比（对比图如下），我们发现这两段代码重复度太大了，仅仅是返回类型的区别，这样写未免太浪费，所以我们将其改造一下！

改造想法：既然我们的类型就是有无const的区别，那我们不妨利用模板，对其进行改造，添加一个Ref,即reference,引用&以及Ptr,即pointer,指针

为了方便改造，我们将原来的list_iterator<T>给typedef一下，省的总改！

改造代码：

template <class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*()                  //模拟指针的解引用{return _node->_data;        //返回的是数据，类型为T}Ptr operator->()                 //解引用的->,这个较为特殊{return &_node->_data;}self& operator++()           //前置++,返回的是引用， this指向的对象不销毁。{_node = _node->_next;return *this;              //++操作返回的是下一个对象}self operator++(int)          //后置++,返回的是一个临时对象，tmp出函数就销毁了{self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it){return this->_node != it._node;}bool operator==(const self& it){return this->_node == it._node;}
};

其余功能的实现：

	template <class T>class list{typedef list_node<T> Node;public://typedef list_iterator<T> iterator;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){iterator it(_head->_next);      //我们的链表是双向循环链表，_head可以理解为哨兵结点return it;}iterator end(){return iterator(_head);}const_iterator begin()const        //加上const关键字表示该函数不会修改类的任何成员变量，即它是一个常量成员函数{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(std::initializer_list<T> lt){empty_init();for (auto& e : lt){push_back(e);}}//lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//lt1=lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}size_t size()const{return _size;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* nextnode = cur->_next;Node* prevnode = cur->_prev;prevnode->_next = nextnode;nextnode->_prev = prevnode;delete cur;--_size;return iterator(nextnode);}private:Node* _head;size_t _size;};
}

3.代码的汇总及实现

这是List.h文件

#include <assert.h>
#include <initializer_list>
#include<iostream>
#include<algorithm>
namespace rens
{template<class T>struct list_node              //定义结点结构{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};template <class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*()                  //模拟指针的解引用{return _node->_data;        //返回的是数据，类型为T}Ptr operator->()                 //解引用的->,这个较为特殊{return &_node->_data;}self& operator++()           //前置++,返回的是引用， this指向的对象不销毁。{_node = _node->_next;return *this;              //++操作返回的是下一个对象}self operator++(int)          //后置++,返回的是一个临时对象，tmp出函数就销毁了{self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it){return this->_node != it._node;}bool operator==(const self& it){return this->_node == it._node;}};//template <class T>//struct list_iterator//{//	typedef list_node<T> Node;//	Node* _node;//	list_iterator(Node* node)//		:_node(node)//	{}////	T& operator*()                  //模拟指针的解引用//	{//		return _node->_data;        //返回的是数据，类型为T//	}////	T* operator->()                 //解引用的->,这个较为特殊//	{//		return &_node->_data;//	}////	list_iterator<T>& operator++()//	{//		_node = _node->_next;//		return *this;              //++操作返回的是下一个结点//	}////	bool operator!=(const list_iterator<T>& it)//	{//		return this->_node != it._node;//	}////	bool operator==(const list_node<T>& it)//	{//		return this->_node == it._node;//	}//};//template <class T>//struct const_list_iterator//{//	typedef list_node<T> Node;//	Node* _node;//	const_list_iterator(Node* node)//		:_node(node)//	{}////	const T& operator*()                  //模拟指针的解引用//	{//		return _node->_data;        //返回的是数据，类型为T//	}////	const T* operator->()                 //解引用的->,这个较为特殊//	{//		return &_node->_data;//	}////	const_list_iterator<T>& operator++()//	{//		_node = _node->_next;//		return *this;              //++操作返回的是下一个结点//	}////	bool operator!=(const const_list_iterator<T>& it)//	{//		return this->_node != it._node;//	}////	bool operator==(const const_list_iterator<T>& it)//	{//		return this->_node == it._node;//	}//};template <class T>class list{typedef list_node<T> Node;public://typedef list_iterator<T> iterator;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){iterator it(_head->_next);      //我们的链表是双向循环链表，_head可以理解为哨兵结点return it;}iterator end(){return iterator(_head);}const_iterator begin()const        //加上const关键字表示该函数不会修改类的任何成员变量，即它是一个常量成员函数{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(std::initializer_list<T> lt){empty_init();for (auto& e : lt){push_back(e);}}//lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//lt1=lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}size_t size()const{return _size;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* nextnode = cur->_next;Node* prevnode = cur->_prev;prevnode->_next = nextnode;nextnode->_prev = prevnode;delete cur;--_size;return iterator(nextnode);}private:Node* _head;size_t _size;};
}

这是test.cpp文件

#include"list.h"using namespace std;void test1()
{rens::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);rens::list<int>::iterator it1 = lt1.begin();while (it1 != lt1.end()){*it1 += 1;cout << *it1 << " ";++it1;}cout << endl;
}
void print(const rens::list<int>& lt)
{// const迭代器本身可以修改，指向内容不能修改rens::list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}
struct A
{A(int a1=1,int a2=1):_a1(a1),_a2(a2){}int _a1;int _a2;
};
void test2()
{rens::list<A> lt2;lt2.push_back({ 1,1 });lt2.push_back({ 2,2 });lt2.push_back({ 3,3 });lt2.push_back({ 4,4 });rens::list<A>::iterator it = lt2.begin();while (it != lt2.end()){cout << it->_a1 << "," << it->_a2 << endl;++it;}cout << endl;rens::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);print(lt1);
}
void test3()
{rens::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);for (auto e : lt1){cout << e << " ";}cout << endl;lt1.push_front(5);lt1.push_front(6);for (auto e : lt1){cout << e << " ";}cout << endl;lt1.pop_back();lt1.pop_back();lt1.pop_front();lt1.pop_front();for (auto e : lt1){cout << e << " ";}cout << endl;lt1.pop_back();lt1.pop_back();for (auto e : lt1){cout << e << " ";}cout << endl;
}
void test4()
{rens::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);for (auto e : lt1){cout << e << " ";}cout << endl;rens::list<int> lt2(lt1);lt1.clear();for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;rens::list<int> lt3 = { 10,20,30,40 };lt1 = lt3;for (auto e : lt1){cout << e << " ";}cout << endl;
}
int main()
{//test1();//test2();//test3();test4();return 0;
}