list的使用与迭代器的模拟实现

前面学习了string，vector类的使用及模拟，但是它们有一个统一的特点就是底层的内存是连续的，因此迭代器的实现也很简单。现在我们开始学习list类的使用，模拟实现，来看看这个底层内存不是连续的有什么特别之处！！

list的使用

简单的list类函数这里就不在提了，若那个不太清楚，可以自行查看，或许有意外收获哦~；

list类函数的的使用

底层结构影响了什么

我们知道list的底层是不连续的，就是链表的形式，

我们还知道，迭代器的功能分为

正向迭代器 反向迭代器 固定正向迭代器 和 固定反向迭代器 四种。而 

迭代器的性质也区分

• 单向迭代器：就能只能++ 或者 --；如：forward_list……
• 双向迭代器（BidirectionalIterator）：既能++ 又能--；如：list，map，set……
• 随机迭代器（RandomAccessIterator）：既能++，又能--，还能 + 或 - ；如：string，vector，deque……

 （+ ，- 指 iterator a + 1或- 1 ，还能指向数据，这些对于底层内存连续的是能够实现的，但是对于内存分散的却不能；++ a  就是只能通过 ++a 才能实现迭代器指向数据的转变，这种不通过 + 1也能实现）

这些是由底层结构实现的，而底层结构又决定了其算法

如：std库里的sort

这里可以解释一下，这个库函数用的快排  利用三数取中 要取随机值；只要随机迭代器能实现。

 std库里的reverse

std库里的generate

 

 

通过这张图我们也能看出，随机是特殊 的双向，双向是特殊的单向，单向是特殊的input output迭代器；这种关系类似于继承的关系，如双向是符，随机是子 

reverse的用途 

其实在list 的reverse是没有必要的；毕竟std库里的revserse都能一样，能完成其能完成的工作，把数据倒置；

emplace back  与 push back 

目前可以认为 emplace back  与 push back 一样，但其实  在一定情况下 emplace back 比 push back好；大多数情况下二者都是差距很小的；

最简单的区别就是他们的用法区别

	list<A> lt;A aa1(1, 1);lt.push_back(aa1);lt.push_back(A(2,2));//lt.push_back(3, 3);lt.emplace_back(aa1);lt.emplace_back(A(2,2));cout << endl;// 支持直接传构造A对象的参数emplace_backlt.emplace_back(3, 3);

 Operations

 这一部分的类函数与前面学习的类函数使用方法稍微有一些不一样；这一部分和二叉树中堆的使用与拓展十分像，底层应该也是用堆实现的；

splice的使用

splice的翻译为汉语是 剪切，粘贴。但其实用法和其是一个意思的，把一个list的某个位置的值剪切到另一个list。

void test1()
{list<int> l1(5, 1);list<int> l2(5, 2);l1.splice(++l1.begin(), l2);l1.splice(++l1.begin(), l2, l2.end()--);l1.splice(++l1.begin(), l2, ++l2.begin(), l2.end()--);
}

remove，remove_if 

nique 

注意一个前提条件，他的排序必须的有有序的，因此它的描述就有了这一段话

 

// a binary predicate implemented as a function:bool same_integral_part (double first, double second)
{ return ( int(first)==int(second) ); }// a binary predicate implemented as a class:struct is_near {bool operator() (double first, double second){ return (fabs(first-second)<5.0); }int main()
{
double mydoubles[]={ 12.15,  2.72, 73.0,  12.77,  3.14,12.77, 73.35, 72.25, 15.3,  72.25 };std::list<double> mylist (mydoubles,mydoubles+10);mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,// 15.3,  72.25, 72.25, 73.0,  73.35mylist.unique();           //  2.72,  3.14, 12.15, 12.77// 15.3,  72.25, 73.0,  73.35mylist.unique (same_integral_part);  //  2.72,  3.14, 12.15// 15.3,  72.25, 73.0mylist.unique (is_near());           //  2.72, 12.15, 72.25
}

merge 

 

它的前提条和nique一样，不同的一点是，list  和 参数list 都要是有序的 使用前 要记得，调用其sort。

merge就是有两个排序好的list，把一个list内的数据 有序的插入到另一个list中，（默认是升序）

可以参考代码，自行更深的理解 

bool mycomparison(double first, double second)
{return (int(first) < int(second));
}int main()
{std::list<double> first, second;first.push_back(3.1);first.push_back(2.2);first.push_back(2.9);second.push_back(3.7);second.push_back(7.1);second.push_back(1.4);first.sort();second.sort();first.merge(second);// (second is now empty)second.push_back(2.1);    1.4 2.2 2.9 2.1 3.1 3.7 7.1
}

 sort

默认是升序用的是底层 归并的排序思想。

 可以用放仿函数来改变为降序

list<int> lt;lt.push_back(1);lt.push_back(20);lt.push_back(3);lt.push_back(5);lt.push_back(4);lt.push_back(5);lt.push_back(6);//less<int> ls;//greater<int> gt;//lt.sort(gt);//方便点直接用匿名函数lt.sort(greater<int>());for (auto e : lt){cout << e << " ";}cout << endl;

list的模拟实现 

基础成员函数

 

我们知道，链表的组成肯定要有节点，哨兵位。

节点要有一个类list_node，struct默认是public：，因此节点的组成用struct

然后就是list的成员函数的实现要有一个类

迭代器的模拟list_iterator实现要有一个类；

VS编译器底层实现list，也是类似这样的

构造函数的组成

 由于list的构造函数的参数很多，因此可以多设几个重载函数来满足这个需求；

 其中empty_init 的目的是增加可读性，简化步骤，毕竟很多构造函数都需要使用一样的写法；

initializer_list<T> 是要初始化 的类型为 initializer_list 的参数而出现的；注意其使用，不要不会用就行；

void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//初始化列表 的初始化list(initializer_list<T> il){empty_init();for (auto& e : il){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;}list(size_t n, const T& x = T()){for (size_t i = 0; i < n; i++){push_back(x);}}

迭代器的实现

 由于list 底层内存不是连续的，其迭代器没变办法像 string vector 一样简单的实现，因此我们要自主实现迭代器；

需要注意的点是，要明白其构造函数是什么，成员函数是什么；

主要内容就是重载 *  ->  ==  != 的符号，让其满足与其他迭代器相同的作用；这里也体现了c++的封装，就算麻烦，也要把它们使用的方法尽量一样;

这里给迭代器类 多个模板参数的原因是 简化其内容，不如写一个 iterator 类 和 const_iterator 类很麻烦。

如何理解？

模板参数就是编译器自主识别是什么类型，然后在list_iterator中 实现；

比如 编译器识别 其类型是 iterator 还是 const iterator，然后有对应的模板和模板参数，然后对于的模板类中，再有就是模板参数代替了原本的 T& T* ，其余都一样。

可以对应这没写多个模板参数的代码在深度理解一下；

 

	template<class T>struct list_iterator {typedef list_node<T> Node;typedef list_iterator<T> self;Node* node;list_iterator(Node* n):node(n){}T& operator*(){return node->_date;}T* operator->(){return &node->_date;}self& operator++(){node = node->_next;return *this;}self& operator--(){node = node->_prev;return *this;}bool operator==(const self& i){return  node == i.node;}bool operator!=(const self& i){return  node != i.node;}};template<class T>struct list_const_iterator {typedef list_node<T> Node;typedef list_const_iterator<T> self;Node* node;list_const_iterator(Node* n):node(n){}const T& operator*() const{return node->_date;}const T* operator->() const{return &node->_date}self& operator++(){node = node->_nextreturn *this;}self& operator--(){node = node->_prev;return *this;}bool operator==(const self& i){return  node == i.node;}bool operator!=(const self& i){return  node != i.node;}};

 

参考代码 

list.h 

#pragma once#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;namespace xryq {template <class T>struct list_node {typedef list_node<T> Node;Node* _next;Node* _prev;T _date;//list_node(Node* n)//{//	_date = n->_date;//	_next = n->_next;//	_prev = n->_prev;//}list_node(const T& date = T()):_date(date), _next(nullptr), _prev(nullptr){}};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* n):node(n){}ref operator*(){return node->_date;}ptr operator->(){return &node->_date;}self& operator++(){node = node->_next;return *this;}self& operator--(){node = node->_prev;return *this;}bool operator==(const self& i){return  node == i.node;}bool operator!=(const self& i){return  node != i.node;}};//template<class T>//struct list_const_iterator {//	typedef list_node<T> Node;//	typedef list_const_iterator<T> self;//	Node* node;//	list_const_iterator(Node* n)//		:node(n)//	{}//	const T& operator*() //	{//		return node->_date;//	}//	const T* operator->()//	{//		return &node->_date//	}//	self& operator++()//	{//		node = node->_next//			return *this;//	}//	self& operator--()//	{//		node = node->_prev;//		return *this;//	}//	bool operator==(const self& i)//	{//		return  node == i.node;//	}//	bool operator!=(const self& i)//	{//		return  node != i.node;//	}//};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;iterator begin(){//return iterator(_head->_next);return _head->_next;}iterator end(){//return iterator(_head);return _head;}//如果不加 const  就会造成重定义const_iterator begin() const{//iterator it(_head->_next);//return it;//return iterator(_head->_next);return _head->_next;}const_iterator end() const{return _head;}iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* pre = pos.node->_prev;Node* cur = pos.node;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = pre;pre->_next = newnode;++_size;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* prev = pos.node->_prev;Node* next = pos.node->_next;prev->_next = next;next->_prev = prev;delete pos.node;--_size;return next;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//初始化列表 的初始化list(initializer_list<T> il){empty_init();for (auto& e : il){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;}list(size_t n, const T& x = T()){for (size_t i = 0; i < n; i++){push_back(x);}}void clear(){//auto i = begin();auto i = begin();while (i != end()){i = erase(i);}}~list(){clear();delete _head;_head = nullptr;}void push_back(const T& x){//Node* tmp = new Node(x);//Node* tail = _head->_prev;//tmp->_prev = tail;//tail->_next = tmp;//tmp->_next = _head;//_head->_prev = tmp;//++_size;insert(end(), x);}void pop_back(){//assert(!empty());//Node* tail = _head->_prev;//_head->_prev = tail->_prev;//tail->_prev->_next = _head;//--_size;//delete tail;//tail = nullptr;erase(--end());}void pop_front(){erase(begin());}void push_front(const T& x){insert(begin(), x);}void size(){return _size;}bool empty(){return _size == 0;}private:Node* _head = new Node;size_t _size = 0;};template<class Container>void print_container(const Container& con){// const iterator -> 迭代器本身不能修改// const_iterator -> 指向内容不能修改 // typename Container::const iterator it = con.begin();   错误的 迭代器无法++//typename Container::const_iterator it = con.begin();auto it = con.begin();while (it != con.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;//for (auto e : con)//{//	cout << e << " ";//}//cout << endl;}struct AA{int _a1 = 1;int _a2 = 1;};void test_list1(){list<AA> lta;lta.push_back(AA());lta.push_back(AA());lta.push_back(AA());lta.push_back(AA());list<AA>::iterator ita = lta.begin();while (ita != lta.end()){//cout << (*ita)._a1 << endl; 这样方位也行，但是为了方便 地址 直接用  -> 访问可读性更好；// vector<T>  也有这种设计// 特殊处理，本来应该是两个->才合理，为了可读性，省略了一个->cout << ita->_a1 << ":" << ita->_a2 << endl;cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;++ita;}cout << endl;//	list<int> lta;//lta.push_back(1);//lta.push_back(1);//lta.push_back(1);//lta.push_back(1);}void func(const list<int>& lt){print_container(lt);}void test_list2(){// 直接构造list<int> lt0({ 1,2,3,4,5,6 });// 隐式类型转换list<int> lt1 = { 1,2,3,4,5,6,7,8 };const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };func(lt0);func({ 1,2,3,4,5,6 });print_container(lt1);//auto il = { 10, 20, 30 };/*	initializer_list<int> il = { 10, 20, 30 };cout << typeid(il).name() << endl;cout << sizeof(il) << endl;*/}}