C++ list容器的实现及讲解

所需要的基础知识

对C++类的基本了解 默认构造函数 操作符重载 this指针 引用 模板等知识具有一定的了解，阅读该文章会很轻松。

链表节点

	template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr)//只需要将链表的节点初始化为空 在链表对象中重新进行节点的设置, _prev(nullptr){}};

template<class T> 是类模板 取决于链表存的数据类型 因为链表可以存许多类型的数据类型 那么只要显示传类型 就可以反复去复用 类模板 但是该写的代码编译器会帮你写 就是每个类型都会有一份代码  

默认构造函数 对链表成员进行初始化 运用了初始化列表 在花括号中只能进行赋值 不是初始化

链表list中的成员及函数 

插入 

从插入函数的实现就可以看出 该链表是双向循环链表

		iterator insert(iterator pos, const T& x){node* cur = pos.node;node* newnode = new node(x);newnode->_next = cur->_next;newnode->_prev = cur;cur->_next->_prev = newnode;cur->_next = newnode;++_size;return newnode;}

插入和C语言中链表的插入没有区别 创建一个新节点 先对新结点进行操作 再对要插入的位置进行操作一面将插入的位置丢失 无法将双向循环链表连接上

返回值是新节点的位置 防止你再再此处插入 方便插入

下面的头插尾插都是对插入接口的赋用  

		void push_back(const T& x){insert(--end(), x);}void push_front(const T& x){insert(begin(), x);}

链表的遍历靠的就是迭代器 所以传迭代器就知道了链表的节点位置 依次可以插入 如果你要任意位置插入 那就要计算 迭代器的位置 进行传入  

删除

		iterator earse(iterator pos){node* cur = pos.node;node* next = cur->_next;node* prev = cur->_prev;delete cur;next->_prev = prev;prev->_next = next;--_size;return iterator(next);}

删除也是和之前讲过的C语言部分链表一样 删除操作要返回下一个位置的迭代器 

返回值这样设计 就可以自动向后遍历删除

头删尾删 就是对删除链表的复用

		void pop_back(){earse(--end());}void pop_front(){earse(begin());}

链表中的迭代器调用接口

		iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}  const_reverse_iterator rend()const{return const_reverse_iterator(begin());}

 迭代器再外面就是这样调用的 只需调用list函数中的正向和反向迭代器接口 就可以进行正反向遍历

清除函数clear()

		void clear(){iterator it = begin();while (it != end()){it = earse(it);//it++;//因为earse()返回的是该节点下一个节点 所以不用在进行++}}

 clear()就是复用earse()函数 只保留头节点_head

析构函数

		~list(){clear();_size = 0;delete _head;_head = nullptr;}

 编译器自己写的析构函数对自定义类型不进行析构 链表节点就是自定义类型 所以需要自己写析构函数 进行数据的释放 

赋值操作符重载“=”

		void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> x){swap(x);return *this;}

 operator=(参数) 参数是进行传值传参 传值传参就是原数据的拷贝 出了该函数这个拷贝参数x会自行销毁 会调用自己的构造函数 既然x和原数据类型值是一样的 所以就可以进行交换

swap(x)->this->swap(x) 在list函数内部除了static修饰的函数没有this指针其他函数都有this指针 你可以在函数内部进行显示调用 但是函数参数不能出现

如：A=B A的地址就是this B就是x; 

链表中的类型及函数讲解

     

• 正向迭代器

    typedef的类型简化

        typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;

        由于原始类型过于繁杂 所以进行类型简化 

迭代器函数介绍：

        默认构造函数

        list_iterator(Node* x):node(x){}

        因为迭代器中存的是 链表的节点 是自定义类型 需要调用对应的默认初始化函数 

        正向迭代器的功能就是将链表正向遍历一遍 

        既然是遍历肯定要将链表中的数据打印出来那就需要对应的函数去获取

        操作符重载：

        “*”->operator*()

		Ref operator*(){return node->_data;}

        "->"operator->()

        Ptr operator->(){return &node->_data;}

     

迭代器中存的是链表的节点 然而用迭代器是这么用的

        list<T>::iterator it = begin()获取迭代器的首 it就是指针 所以你想获取链表节点中的数据就需要重载“*和->" *it的功能就是获取该节点的数据 只是迭代器中对其进行了重载实现 所以你可以这样使用 ”->"道理也是一样 都是迭代器进行了重载实现 功能就是通过指针进行迭代器中共有函数和成员的直接获取 淡然*it也是可以就需要叫“.”操作符进行公有成员和函数的获取

        这两个返回值的类型是不一样的 “*”既然是数据 那么就可以引用返回 只要你不销毁程序不结束没有出作用域 就可以进行传引用返回 “->"返回的就是指针类型就是T* 他的返回值前面有个&取地址符 然而”*“和”->"两者遇到一起就抵消了 就剩下node->_data也就是你想要的节点数据 我就是这样理解操作符“->"的重载实现原理的

          "前置++，--，后置++，--"

		self& operator++(){node = node->_next;return *this;}self& operator--(){node = node->_prev;return *this;}self operator++(int){self tmp(*this);node = node->_next;return tmp;}self operator--(int){self tmp(*this);node = node->_prev;return tmp;}

        前置与后置操作的区别就是前置不需要数据类型进行占位 构成操作符重载

        那么返回值类型就是迭代器的类型 返回值根据前置和后置的功能有所不同

        前置：先++/--在用 也就迭代器要返回下一个位置 由于下一个位置是存在的你不销毁或者程序不结束 那么该位置始终是有效的 所以可以返回引用 &

        后置：先用再++/-- 也就是要返回当前的值还要进行++/-- 那就要储存当前的值 不然进行完++/--找起来有点麻烦 可以找因为list的结构是双向循环链表可以向前查找 返回++/--的前一个节点就行

拷贝当前数据出了作用域该数据会销毁 那么就不能进行引用& 返回 只能传值拷贝返回

        “比较操作符!=,==”因为不需要大于或小于 比较对象是指针

		bool operator==(const self& x){return node == x.node;}bool operator!=(const self& x){return node != x.node;}

既然是地址的比较就应该返回 bool类型的值 （true/false） 

反向迭代器

由上图可以看出 反向迭代器是对正向迭代器的赋用 而且反向迭代器中成员存的是正向迭代器_it

反向迭代器的默认构造函数

		reverse_iterator(iterator it):_it(it){}

 用正向迭代器对其进行初始化

操作符重载——>"*和->"

		Ref operator*(){iterator tmp = _it;return *(--tmp);}Ptr operator->(){iterator tmp = _it;return &(operator*());}

观察上图的反向迭代器的首部 再要获取节点的前一个位置 所以要先保存当前节点 再对当前进行前移 依次达到目的 

“->"返回的就是指针类型就是T* 他的返回值前面有个&取地址符 然而”*“和”->"两者遇到一起就抵消了 就剩下node->_data也就是你想要的节点数据 我就是这样理解操作符“->"的重载实现原理的

所以返回的既然是数据 那么就可以复用 之前实现的“operator*()”, 

Ref -> T& Ptr -> T* T就是模板参数 取决于外面链表中存的是什么类型的参数

操作符->前置“++/--”和后置"++/--"

		self& operator++(){--_it;return *this;}self& operator--(){++_it;return *this;}self operator++(int){self tmp(*this);--_it;return *this;}self operator--(int){self tmp(*this);++_it;return *this;}

 前置++/-- 和后置++/-- 都是对链表节点进行操作 然而迭代器中存的是链表节点 在外界对迭代器进行操作 为了使类型可以对上 所以返回self 就是反向迭代器的简化类型

反向迭代器的运用

前置++/-- 和后置++/--原理是一样的 先++再用 先用再++ 在正向迭代器中讲过 所以不再重复

迭代器判断是否相等

		bool operator!=(const self& s){return _it != s._it;}

 

链表list对象的实现

#pragma once#include<iostream>
#include<string>
#include<vector>
using namespace std;namespace DZ
{template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr)//只需要将链表的节点初始化为空 在链表对象中重新进行节点的设置, _prev(nullptr){}};template<class T, class Ref, class Ptr>class list_iterator{public:typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;list_iterator(Node* x):node(x){}self& operator++(){node = node->_next;return *this;}self& operator--(){node = node->_prev;return *this;}self operator++(int){self tmp(*this);node = node->_next;return tmp;}self operator--(int){self tmp(*this);node = node->_prev;return tmp;}bool operator==(const self& x){return node == x.node;}bool operator!=(const self& x){return node != x.node;}Ref operator*(){return node->_data;}Ptr operator->(){return &node->_data;}Node* node;};template<class iterator,class Ref,class Ptr>class reverse_iterator{public:iterator _it;typedef reverse_iterator<iterator, Ref, Ptr> self;reverse_iterator(iterator it):_it(it){}Ref operator*(){iterator tmp = _it;return *(--tmp);}Ptr operator->(){iterator tmp = _it;return &(operator*());}self& operator++(){--_it;return *this;}self& operator--(){++_it;return *this;}self operator++(int){self tmp(*this);--_it;return *this;}self operator--(int){self tmp(*this);++_it;return *this;}bool operator!=(const self& s){return _it != s._it;}};template<class T>class list{public:typedef list_node<T> node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;typedef reverse_iterator<iterator, T&, T*> reverse_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}const_reverse_iterator rend()const{return const_reverse_iterator(begin());}void empty_inti(){_head = new node;_head->_next = _head;_head->_prev = _head;}//it1(it2)list(const list<T>& x){empty_inti();for (auto& e : x){push_back(e);}}list(){empty_inti();_size = 0;}void push_back(const T& x){insert(--end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){earse(--end());}void pop_front(){earse(begin());}//list<T>& operator=(const list<T>& x)//{//	if (this != &x)//	{//		clear();//		for (auto& e : x)//		{//			push_back(e);//		}//	}//	return *this;//}//void swap(list<T>& x)//{//	std::swap(_size, x._size);//	std::swap(_head, x._head);//}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> x){swap(x);return *this;}~list(){clear();_size = 0;delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = earse(it);//it++;//因为earse()返回的是该节点下一个节点 所以不用在进行++}}iterator insert(iterator pos, const T& x){node* cur = pos.node;node* newnode = new node(x);newnode->_next = cur->_next;newnode->_prev = cur;cur->_next->_prev = newnode;cur->_next = newnode;++_size;return newnode;}iterator earse(iterator pos){node* cur = pos.node;node* next = cur->_next;node* prev = cur->_prev;delete cur;next->_prev = prev;prev->_next = next;--_size;return iterator(next);}size_t size(){return _size;}private:size_t _size;node* _head;};void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);// 封装屏蔽底层差异和实现细节// 提供统一的访问修改遍历方式list<int>::iterator it = lt.begin();while (it != lt.end()){*it += 20;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;/*set<int> s;s.insert(1);s.insert(3);s.insert(2);s.insert(4);set<int>::iterator sit = s.begin();while (sit != s.end()){cout << *sit << " ";++sit;}cout << endl;*/}void test_list2(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int> lt1(lt);for (auto e : lt){cout << e << " ";}cout << endl;for (auto e : lt1){cout << e << " ";}cout << endl;list<int> lt2;lt2.push_back(10);lt2.push_back(200);lt2.push_back(30);lt2.push_back(40);lt2.push_back(50);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}struct AA{AA(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;};void test_list3(){list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));list<AA>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1<<" "<<(*it)._a2 << endl;cout << it->_a1 << " " << it->_a2 << endl;cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << endl;++it;}cout << endl;int* p = new int;*p = 1;AA* ptr = new AA;ptr->_a1 = 1;}template<typename Container>void print_container(const Container& con){typename Container::const_iterator it = con.begin();while (it != con.end()){cout << *it << " ";++it;}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);//print_list(lt);print_container(lt);list<string> lt1;lt1.push_back("1111111111111");lt1.push_back("1111111111111");lt1.push_back("1111111111111");lt1.push_back("1111111111111");lt1.push_back("1111111111111");//print_list(lt1);print_container(lt1);vector<string> v;v.push_back("222222222222222222222");v.push_back("222222222222222222222");v.push_back("222222222222222222222");v.push_back("222222222222222222222");//print_list(v);print_container(v);}void test_list5(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::reverse_iterator it = lt.rbegin();while (it != lt.rend()){cout << *it << " ";++it;}}
}