网站维护工作内容有什么,做设计找素材的 网站有哪些,网站错误404,ink域名网站目录
文章目录
前言
一、list的简介
二、list的使用方法
三、list的模拟实现
1.基本框架#xff1a;
2.迭代器实现
3.常用接口实现
四、完整代码
总结 前言 本文主要介绍C【STL】容器中的 list#xff0c;包括接口说明和模拟实现。其中讲解了迭代器功能上的分类
2.迭代器实现
3.常用接口实现
四、完整代码
总结 前言 本文主要介绍C【STL】容器中的 list包括接口说明和模拟实现。其中讲解了迭代器功能上的分类让你了解为何 list 要实现这个接口。 一、list的简介 list就是链表对应我们在C语言数据结构中学的带头双向循环链表。既然是链表那么它在内存中就是不连续的数据由节点组成。 list为模版类创建时需要传数据类型类型。 我们接着前面 string 和 vector 继续讲解因为STL中容器的使用方法很相似因此我写的比较简洁 二、list的使用方法
1.list 的构造
常用构造
构造函数接口说明list (size_type n, const value_type val value_type())构造的list中包含n个值为val的 元素list()构造空的listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用迭代器[first, last)区间中的元素构造 listlist (initializer_listvalue_type il)用initializer_list构造
简单演示
#include iostream
#include list
#include vector
using namespace std;int main()
{//(1)listint l1(8, 6);for (auto e : l1){cout e ;}cout endl;//(2)vectorint v({ 1,2,3,4,5,6,7,8 });listintl2(v.begin(), v.end());for (auto e : l2){cout e ;}cout endl;//(3)listint l3({ 1,2,3,4,5,6 });for (auto e : l3){cout e ;}cout endl;return 0;
}
运行结果 2.list的迭代器、list遍历
迭代器 用法和 string、vector 一样不赘述。 遍历方式
1迭代器和范围for
#include iostream
#include list
using namespace std;int main()
{listint l1({ 9, 8, 7, 6, 5, 4, 12 });//迭代器遍历auto it l1.begin();while (it ! l1.end()){cout *it ;it;}cout endl;//范围for支持迭代器就支持范围forfor (auto e : l1){cout e ;}cout endl;return 0;
}运行结果 注意因为 [ ] 对于链式结构的数据来说效率不高因此 list 并没有重载 [ ] 3.常见方法
函数声明接口说明size()返回list中有效节点的个数empty()检测list是否为空是返回true否则返回falsefront()返回list的第一个节点中值的引用back()返回list的最后一个节点中值的引用push_front (const value_type val)在list首元素前插入值为val的元素pop_front()删除list中第一个元素 push_back (const value_type val) 在list尾部插入值为val的元素pop_back()删除list中最后一个元素emplace_back (Args... args)模版函数与push_back大致相同具体区别下面在讲insert在list position 位置中插入值为val的元素swap交换两个list中的元素clear清空list中的有效元素
简单演示
1size、empyt、front、back、push_front、pop_front、pop_back
#include iostream
#include list
using namespace std;int main()
{listint l1({ 1,2,3 });l1.push_front(88);for (auto e : l1){cout e ;}cout endl;cout size: l1.size() endl;cout empty: l1.empty() endl;cout front: l1.front() endl;cout back: l1.back() endl;l1.pop_back();l1.pop_front();for (auto e : l1){cout e ;}cout endl;return 0;
}
运行结果 因为list是链式结构所以头插头删是没有效率消耗的。 2push_back 和 emplace_back 的区别 首先 emplace_back 是一个模版函数 用法异同
#include iostream
#include list
using namespace std;struct Pos
{int _row;int _col;Pos(int row 0, int col 0):_row(row),_col(col){}
};int main()
{listPos l1;listPos l2;Pos p;//push_back支持l1.push_back(p);l1.push_back(Pos(1, 2));//匿名对象l1.push_back({ 1,2 });//大括号//emplace_back支持l2.emplace_back(p);l2.emplace_back(Pos(1, 2));l2.emplace_back(1, 2);//支持直接传参l2.emplace_back(1);//支持直接传参return 0;
} 简单说push_back 支持大括号传参emplace_back 支持直接传参 3insert、erase、迭代器失效问题
在 vector 中我们接触了迭代器失效的问题而在 list 中迭代器失效只会出现在 erase 中 list中insert 插入数据迭代器不失效的原因就是pos 指向的节点没有改变因为 list 是链式结构不存在扩容以及原空间销毁等问题。insert1的返回值是新节点的迭代器。而在 erase 中删除节点就等于将迭代器指定的空间销毁因此 erase 的返回值是被删除节点的下一个节点。 演示
#include iostream
#include list
using namespace std;int main()
{listint l1;//插入auto it l1.insert(l1.begin(), 22);cout *it endl;//迭代器没有失效l1.insert(l1.end(), 33);l1.insert(l1.end(), 44);l1.insert(l1.end(), 55);for (auto e : l1){cout e ;}cout endl;cout endl;//删除我们可以借助 find 函数来找到需要删除的节点auto del find(l1.begin(), l1.end(), 44);del l1.erase(del);//迭代器失效需要更新迭代器cout *del endl;for (auto e : l1){cout e ;}cout endl;return 0;
}
运行结果 4.特有方法
函数声明接口说明splice将另一个list对象中的元素拿出来插入到自己元素中。remove删除指定元素unique删除 list 中重复值需先排序merge合并两个链表被合并的链表会变为空合并前两个链表需先排序sort链表特供的排序reverse逆置
1sort排序 和 迭代器分类 通过前面 string 和 vector 的学习我们知道它们两个都没有提供 sort 接口而是直接使用算法库中的 sort。那么为什么 list 要提供 sort 接口这里就涉及迭代器分类的问题了。 首先我们可以发现算法库中的 sort 的参数列表迭代器的名字带有随机的字样。这里的命名其实就提示了使用者该函数需要的迭代器类型了。还有一个原因是 list 需要自己实现 sort 的我们在 sort 的定义中大致可以看出算法库中的 sort 为了计算排序元素的个数其实通过地址相减得到的这对于连续型存储空间的容器来说确实可以但是 list 是链式结构因此 list 不能使用算法库中的 sort 来进行排序。 1.1迭代器分类 按使用上分类 使用上分类就是我在 string 中讲到的 普通迭代器、const迭代器、反向迭代器等。这是我们按照使用上进行分类的。 按功能性分类 单向迭代器只支持比如 forward_list单链表双向迭代器支持、--比如 list双链表随机迭代器支持、--、、-比如 string,vector 从官方文档中也能看到每个容器的迭代器类型
例如vector随机迭代器 例如list双向迭代器 例如forward_list单向迭代器 所以算法库中 sort 的参数名其实就暗示了只有随机迭代器才能使用。当然这里还要注意一点就是如果一个函数只支持双向迭代器那么其实随机迭代器也可以使用我们记住 随机迭代器 双向迭代器 单向迭代器类似包含的关系如果一个接口支持单向迭代器那么双向和随机迭代器也可以使用但如果只支持随机那么单向和双向都不能使用 例如1算法库中的 reverse 逆置方法 算法库中的 reverse 显示支持双向迭代器那么 list 其实是可以直接使用算法库中的 reverse那么为什么还要自己实现一个 reverse关于这一点应该是效率问题。 例如2算法库中的 find 接口 这里显示的迭代器名称其实是可读迭代器这涉及另外一种分类但是其实 find 按功能是支持单向迭代器的也就是 单向、双向、随机迭代器都可以使用该接口进行查找元素的。 1.2对比sort排序效率
#include iostream
#include vector
#include list
#include algorithm
using namespace std;int main()
{srand((unsigned int)time(0));const int N 1000000;vectorint v1;listint l1;for (size_t i 0; i N; i){v1.push_back(rand());l1.push_back(v1[i]);}int begin1 clock();sort(v1.begin(), v1.end());int end1 clock();int begin2 clock();l1.sort();int end2 clock();cout vector_sort: end1 - begin1 endl;cout list_sort: end2 - begin2 endl;return 0;
}
运行结果 我们可以看到排一百万个数据时list 比 vector 多花了3倍多的时间。所以效率上list 的 sort 是比不上算法库的 sort 的 我们可以试着将 list 的数据拷贝到 vector 进行排序然后再拷回 list看看效率如何
#include iostream
#include vector
#include list
#include algorithm
using namespace std;int main()
{srand((unsigned int)time(0));const int N 1000000;vectorint v;listint l1;listint l2;for (size_t i 0; i N; i){l1.push_back(rand());}l2.assign(l1.begin(), l1.end());//assign用于重新赋值int begin1 clock();v.assign(l1.begin(), l1.end());sort(v.begin(), v.end());l1.assign(v.begin(), v.end());int end1 clock();int begin2 clock();l2.sort();int end2 clock();cout list_vector_sort_list: end1 - begin1 endl;cout list_sort: end2 - begin2 endl;return 0;
}
运行结果 我们可以很直观的发现list 的 sort 效率甚至比不上list 拷贝给vector排再拷回来的效率。所以我们一般不直接使用 list 的 sort 进行排序因为效率不高除非数据量少一般我们还是拷贝给 vector 进行排序毕竟连续型空间排序优势很大。 2splice、remove、unique、merge 和 reverse 演示
splice 1将 x 的全部数据插入到自己的 pos 位置x 中的数据将会清除2将 x 中 i 位置的数据插入到自己 pos 位置x 中该数据会删除3将 x 中的一段迭代器区间的内容插入到 pos 位置x 中这些数据会删除 简单演示
#include iostream
#include list
#include algorithm
using namespace std;int main()
{listint l1{ 1,2,3,4,5 };listint l2{ 6,7,8,9,10 };auto it find(l2.begin(), l2.end(), 8);l1.splice(l1.begin(), l2, it);for (auto e : l1){cout e ;}cout endl;for (auto e : l2){cout e ;}cout endl;return 0;
}
运行结果 uinque、merge: 这两个的第二个重载都涉及仿函数仿函数下篇再讲注意这两个接口使用前需要先将数据排成有序的。 简单演示
#include iostream
#include list
#include algorithm
using namespace std;int main()
{listint l1{ 5,8,3,3,1,2,2,8 };listint l2({ 4, 4, 9, 9, 9, 6, 6, 5 });l1.sort();l2.sort();l1.unique();//删除重复项for (auto e : l1){cout e ;}cout endl;l2.unique();//删除重复项for (auto e : l2){cout e ;}cout endl;l1.merge(l2);//合并for (auto e : l1){cout e ;}cout endl;for (auto e : l2){cout e ;}cout 没了 endl;return 0;
}运行结果 reverse、remove: remove 只要知道元素内容就能删除 演示
#include iostream
#include list
#include algorithm
using namespace std;int main()
{listint l1({ 1,2,3,4,5 });l1.remove(2);//删除for (auto e : l1){cout e ;}cout endl;l1.reverse();//逆置for (auto e : l1){cout e ;}cout endl;return 0;
}
运行结果 小结 list常用方法当然还有一些比如关系运算等这些比较简单就不一一演示了接下来我们就模拟实现 list。 三、list的模拟实现
我们不完全模拟主要实现出 list 常用的接口加强印象和使用。
1.基本框架
namespace txp
{//定义节点templateclass Tstruct list_node{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x),_next(nullptr),_prev(nullptr){}};//链表templateclass Tclass list{typedef list_nodeT Node;//节点public://初始化void empty_init(){_head new Node();_head-_next _head;_head-_prev _head;_size 0;}//默认构造list(){empty_init();}private:Node* _head;size_t _size;};
}
节点 首先依然需要命名空间来与库里的list区分然后定义节点我们之前学过链表链表是由一个个节点连接组成的既然是双向带头循环链表那么就有三个成员变量存储数据的_data存储下一个节点地址的_next存储上一个节点的地址_prev。节点 list_node 需要写成模版类模版参数即是存储数据的类型然后我们需要手动写一个默认构造将成员初始化。注意你可能想知道为啥 list_node 要用 struct 进行定义这里简单说一下。 使用 struct 定义节点的原因 在学习c类时我们知道 c 中 struct 和 class 的区别其实大致上没有区别c中 struct 也能定义类。唯一的区别就是如果不加访问限定符struct 的成员默认是公有的而 class 不加访问限定符则成员默认是私有的。然后行业内就有一个不成文的规定假如类中的每个成员都需要写成公有的那么就用 struct 进行定义反之则使用 class 进行定义。因为 list_node 的每个成员都需要被频繁的访问所以 list_node 成员全部为公有成员故而不加访问限定符直接使用 struct 进行定义。 链表 链表有两个成员变量一个是头结点 _head另一个是记录节点个数的 _size。头结点的类型由节点类决定因此对节点类进行重命名这里重命名到链表类中其实相当于将节点类设置为链表的内部类了并且重命名在 public 的上面这样节点就是私有的对外部来说无法访问。链表的初始化先写到一个函数 empty_init 中不直接写在构造函数中是因为构造有很多为了避免重复写就直接写成一个函数给构造函数调用。初始化因为是双向带头循环链表因此头结点是不储存数据的也就是哨兵位。然后_next 和 _prev 指针初始化时需要指向自己这样才算是循环链表。 2.迭代器实现 在 string 和 vector 的模拟实现中迭代器是直接对指针进行重命名的这样迭代器、--就能遍历数据了但是在 list 中这种方法行不通因为链表的存储结构是不连续的在这种情况下我们该怎么实现迭代器呢 其实之前我们就能发现迭代器很像指针但我们不能说它就是指针其实它是对指针的一种封装面向对象的三大特征之一就是封装为什么要封装就是为了通用性在STL中迭代器是通用的功能都叫一个名字但其实底层实现不一样。对于 list 来说想要实现迭代器就需要对指针进行封装封装成一个类在类中重载 、--等操作符对于迭代器来说就是走到下一个数据那么链表要实现这样的效果就是将指针指向下一个节点。按照这样的思路我们实现出 list 的迭代器 //定义迭代器
templateclass T, class Ref, class Ptr
struct list_iterator
{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _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;}//重载!bool operator!(const Self s){return _node ! s._node;}//重载bool operator(const Self s){return _node s._node;}
}; 首先迭代器的全部功能都需要公开因此直接写成 struct 类。迭代器只要一个成员变量 _node也就是节点指针。然后你会发现迭代器有3个模版参数这其实是一种巧妙的设计我们模拟迭代器时一般只模拟两个迭代器普通迭代器和const迭代器。这两个迭代器在解引用返回值上有差别const 迭代器解引用返回的是 const 修饰的数据不能修改。因此如果只有一个模版参数用来替换数据类型时那么对于这两个迭代器就需要手动写两个迭代器类了。为了避免再手动写一个高度相似的迭代器类因此另加两个参数 Ref 和 Ptr。 然后我们在链表中传递不同参数就能得到两种迭代器了
//链表
templateclass T
class list
{typedef list_nodeT Node;//节点
public:typedef list_iteratorT, T, T* iterator;//迭代器typedef list_iteratorT, const T, const T* const_iterator;//const迭代器注意迭代器重命名在 public 下方迭代器需要被外部访问 其实这样重命名后编译器会根据模版自动生成两份迭代器类只是减少了我们的代码量将本来应该我们写两份迭代器类的工作交给了编译器。 Ref 和 Ptr 只用于解引用操作符* 和 -中 *的重载函数就是返回对应节点的 _data 即可。-的重载函数就需要返回对应节点 _data 的地址了写法就是前面加个取地址符 关于其他的运算符重载 如前置、--其实就是将节点指针移动到下一个节点或者上一个节点即可后置同理只不过返回的是修改前的地址。另外需要重载的就是 ! 和 了! 就是为了支持我们迭代器遍历有时候需要用到。 3.常用接口实现
1迭代器
//链表templateclass Tclass list{typedef list_nodeT Node;//节点public:typedef list_iteratorT, T, T* iterator;//迭代器typedef list_iteratorT, const T, const T* const_iterator;//const迭代器iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);} begin() 就是头结点的下一个节点end() 就是头结点了 2insert
//insert
iterator insert(iterator pos, const T val)
{Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);cur-_prev newnode;newnode-_next cur;prev-_next newnode;newnode-_prev prev;_size;return iterator(newnode);
} 直接看示意图最后需要返回新节点的指针。 3push_back、push_front 我们先实现了insert那么这两个就可以直接复用insert了 //尾插
void push_back(const T x)
{//复用写法insert(end(), x);
}//头插
void push_front(const T val T())
{insert(begin(), val);
} 4erase
//erase
iterator erase(iterator pos)
{assert(pos ! end());Node* del pos._node;Node* next del-_next;Node* prev del-_prev;next-_prev prev;prev-_next next;delete del;del nullptr;--_size;return iterator(next);
} 先改变待删节点的前后节点指向最后删除。注意不能删除头结点使用assert进行断言最后需要返回被删节点的下一个节点的迭代器 5pop_backpop_front 同样当我们实现了erase后就可以直接复用 //尾删
void pop_back()
{erase(--end());
}//头删
void pop_front()
{erase(begin());
} 注意尾删需要--end()因为end()返回的是头结点。 6size、swapclear、析构和更多的构造
//size
size_t size()
{return _size;
}//交换
void swap(listT tmp)
{std::swap(_head, tmp._head);std::swap(_size, tmp._size);
}//赋值运算符重载
listT operator(listT lt)
{swap(lt);return *this;
}//clear
void clear()
{auto it begin();while (it ! end()){it erase(it);}
}//析构
~list()
{clear();delete _head;_head nullptr;
}//n个val构造
list(size_t n, const T val T())
{empty_init();for (size_t i 0; i n; i){push_back(val);}
}//initializer_list构造
list(std::initializer_listT il)
{empty_init();for (auto e : il){push_back(e);}
}//拷贝构造
list(const listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}这里面需要注意的就是 swap 的操作swap 本身是通过调用算法库中的swap交换两个list对象的指针和 _size 实现的。swap 配合赋值运算符重载能极大简化代码这里就是函数参数使用传值传参这样参数相当完成了拷贝将参数与自己调换就完成了赋值。clear 删除元素配合析构也能简化代码。其他的就很好理解了不再赘述 全局的 swap:
//全局的swap
templateclass T
void swap(listTl1, listTl2)
{l1.swap(l2);
} 全局的 swap 存在主要是怕调用到算法库中的 swap官方的文档中也有实现两个swap。这样一来当我们不用 对象. 去调用swap而是直接调用 swap 也能高效的调换两个list对象了 关于 list 模拟就实现这么多当然剩下的你如果有想法可以自己试着实现。 四、完整代码
#pragma once
#include assert.hnamespace txp
{//定义节点templateclass Tstruct list_node{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x),_next(nullptr),_prev(nullptr){}};//定义迭代器templateclass T, class Ref, class Ptrstruct list_iterator{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _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;}//重载!bool operator!(const Self s){return _node ! s._node;}//重载bool operator(const Self s){return _node s._node;}};//链表templateclass Tclass list{typedef list_nodeT Node;//节点public:typedef list_iteratorT, T, T* iterator;//迭代器typedef list_iteratorT, const T, const T* const_iterator;//const迭代器iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator begin() 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();}//n个val构造list(size_t n, const T val T()){empty_init();for (size_t i 0; i n; i){push_back(val);}}//initializer_list构造list(std::initializer_listT il){empty_init();for (auto e : il){push_back(e);}}//拷贝构造list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}//析构~list(){clear();delete _head;_head nullptr;}//sizesize_t size(){return _size;}//赋值运算符重载listT operator(listT lt){swap(lt);return *this;}//交换void swap(listT tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}//clearvoid clear(){auto it begin();while (it ! end()){it erase(it);}}//尾插void push_back(const T x){//原始写法/*Node* new_node new Node(x);Node* tail _head-_prev;tail-_next new_node;new_node-_prev tail;_head-_prev new_node;new_node-_next _head;*///复用写法insert(end(), x);}//头插void push_front(const T val T()){insert(begin(), val);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}//insertiterator insert(iterator pos, const T val){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);cur-_prev newnode;newnode-_next cur;prev-_next newnode;newnode-_prev prev;_size;return iterator(newnode);}//eraseiterator erase(iterator pos){assert(pos ! end());Node* del pos._node;Node* next del-_next;Node* prev del-_prev;next-_prev prev;prev-_next next;delete del;del nullptr;--_size;return iterator(next);}private:Node* _head;size_t _size;};//全局的swaptemplateclass Tvoid swap(listTl1, listTl2){l1.swap(l2);}
} 总结 以上就是本文的全部内容了感谢支持
