深圳建设局网站深业中城绿化项目,网站建设整体方案,济宁网站建设 企诺,企业网站做百度小程序文章目录 前言一、list的介绍及使用1.1 list的介绍1.2 list的使用1.2.1 list的构造1.2.2 list iterator的使用1.2.3 list capacity1.2.4 list element access1.2.5 list modifiers1.2.6 list operations1.2.7 list的迭代器失效 二、list的模拟实现2.1 定义一个结构体实现list的… 文章目录 前言一、list的介绍及使用1.1 list的介绍1.2 list的使用1.2.1 list的构造1.2.2 list iterator的使用1.2.3 list capacity1.2.4 list element access1.2.5 list modifiers1.2.6 list operations1.2.7 list的迭代器失效 二、list的模拟实现2.1 定义一个结构体实现list的节点2.2 list的成员变量2.3 list迭代器的封装实现2.3.1 普通迭代器2.3.2 const迭代器 2.4 list成员函数2.4.1 构造函数2.4.2 拷贝构造函数2.4.3 赋值运算符重载2.4.4 迭代器相关2.4.5 insert2.4.6 erase2.4.7 push_back()2.4.8 push_front()2.4.9 pop_back()2.4.10 pop_front()2.4.11 size()2.4.12 clear()2.4.13 析构函数 三、list与vector的对比 前言 个人主页小沈YO. 小编介绍欢迎来到我的乱七八糟小星球 专栏C 心愿便利店 本章内容list 记得 评论 点赞 收藏 关注哦~ 提示以下是本篇文章正文内容下面案例可供参考
一、list的介绍及使用
list的文档介绍
1.1 list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
1.2 list的使用
list中的接口比较多此处类似只需要掌握如何正确的使用然后再去深入研究背后的原理已达到可扩展 的能力。以下为list中一些常见的重要接口
1.2.1 list的构造
构造函数 (constructor)接口说明list()构造空的listlist (size_type n, const value_type val value_type())构造的list中包含n个值为val的元素list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造listlist (const list x)拷贝构造函数
void test_list1()
{listint l1;//构造空的listlistintl2(6, 6);//构造的list中包含n个值为val的元素listintl3(l2.begin(), l2.end());//用[first, last)区间中的元素构造listlistintl4(l3);//拷贝构造函数listint::iterator it l2.begin();while (it ! l2.end()){cout *it ;it;}cout endl;for (auto e : l3){cout e ;}cout endl;for (auto e : l4){cout e ;}cout endl;
}1.2.2 list iterator的使用
此处大家可暂时将迭代器理解成一个指针该指针指向list中的某个节点。
函数声明接口说明begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的reverse_iterator,即begin位置
void test_list2()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);// 使用正向迭代器遍历打印lt中的元素// listint::iterator it l.begin(); //两种写法都对auto it lt.begin(); while (it ! lt.end()){cout *it ;it;}cout endl;// 使用反向迭代器遍历打印lt中的元素// listint::reverse_iterator rit l.rbegin();auto rit lt.rbegin();while (rit ! lt.rend()){cout *rit ;rit;}cout endl;
}【注意】
begin与end为正向迭代器对迭代器执行操作迭代器向后移动rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动遍历链表只能使用迭代器和范围 for。
1.2.3 list capacity
函数声明接口说明empty检测list是否为空是返回true否则返回falsesize返回list中有效节点的个数
1.2.4 list element access
函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用
1.2.5 list modifiers
函数声明接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在list position 位置中插入值为val的元素erase删除list position位置的元素swap交换两个list中的元素clear清空list中的有效元素
1.2.6 list operations
函数声明接口说明splice实现list拼接的功能将源list的内容部分或全部元素删除拼插入到目的list。remove删除特定值节点unique对链表中的元素去重要求必须有序merge对两个有序的链表进行归并得到一个有序的链表sort对链表中的元素进行排序reverse逆置
注意链表排序只能使用 list 自身的 sort() 接口其底层是利用归并排序原理不能使用算法库的 sort因为算法库中的 sort 底层是通过快排来实现的快排涉及到三数取中需要迭代器 - 迭代器链表不能很好的支持。
void test_list3()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt){cout e ;}cout endl;lt.reverse();链表逆置可以使用 list 自身的接口也可以使用算法库中的 reversefor (auto e : lt){cout e ;}cout endl;//sort(lt.begin(), lt.end());lt.sort();//默认升序 less//降序 greater//greaterint gt;lt.sort(gt);lt.sort(greaterint());//上面的两种写法都可以for (auto e : lt){cout e ;}cout endl;
}
————————————————————————————————————————————————————————————————————————————————
unique --- 去重一定要记得有序
void test_list4()
{listint lt;lt.push_back(1);lt.push_back(3);lt.push_back(2);lt.push_back(3);lt.push_back(3);lt.push_back(2);lt.push_back(5);lt.push_back(5);for (auto e : lt){cout e ;}cout endl;lt.unique();for (auto e : lt){cout e ;}cout endl;
}#mermaid-svg-Ezw4yadMYSxMVwJp {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-Ezw4yadMYSxMVwJp .error-icon{fill:#552222;}#mermaid-svg-Ezw4yadMYSxMVwJp .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-Ezw4yadMYSxMVwJp .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-Ezw4yadMYSxMVwJp .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-Ezw4yadMYSxMVwJp .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-Ezw4yadMYSxMVwJp .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-Ezw4yadMYSxMVwJp .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-Ezw4yadMYSxMVwJp .marker{fill:#333333;stroke:#333333;}#mermaid-svg-Ezw4yadMYSxMVwJp .marker.cross{stroke:#333333;}#mermaid-svg-Ezw4yadMYSxMVwJp svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-Ezw4yadMYSxMVwJp .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-Ezw4yadMYSxMVwJp .cluster-label text{fill:#333;}#mermaid-svg-Ezw4yadMYSxMVwJp .cluster-label span{color:#333;}#mermaid-svg-Ezw4yadMYSxMVwJp .label text,#mermaid-svg-Ezw4yadMYSxMVwJp span{fill:#333;color:#333;}#mermaid-svg-Ezw4yadMYSxMVwJp .node rect,#mermaid-svg-Ezw4yadMYSxMVwJp .node circle,#mermaid-svg-Ezw4yadMYSxMVwJp .node ellipse,#mermaid-svg-Ezw4yadMYSxMVwJp .node polygon,#mermaid-svg-Ezw4yadMYSxMVwJp .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-Ezw4yadMYSxMVwJp .node .label{text-align:center;}#mermaid-svg-Ezw4yadMYSxMVwJp .node.clickable{cursor:pointer;}#mermaid-svg-Ezw4yadMYSxMVwJp .arrowheadPath{fill:#333333;}#mermaid-svg-Ezw4yadMYSxMVwJp .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-Ezw4yadMYSxMVwJp .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-Ezw4yadMYSxMVwJp .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-Ezw4yadMYSxMVwJp .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-Ezw4yadMYSxMVwJp .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-Ezw4yadMYSxMVwJp .cluster text{fill:#333;}#mermaid-svg-Ezw4yadMYSxMVwJp .cluster span{color:#333;}#mermaid-svg-Ezw4yadMYSxMVwJp div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-Ezw4yadMYSxMVwJp :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} vector和list的效率比对: 虽然链表提供了排序接口但是用链表对数据排序意义不大当数据比较大时效率太低了更希望用 vector 来对数据进行排序 — 如下具体可以通过对两者进行效率比对但是数据较小时sort还是很有用的
//将li中的数据拷贝到vector
vectorint v(lt.begin(),lt.end());
for (auto e : v)
{cout e ;
}
cout endl;
//排序
sort(v.begin(), v.end());
for (auto e : v)
{cout e ;
}
cout endl;
//拷贝回lt
lt.assign(v.begin(), v.end());
for (auto e : lt)
{cout e ;
}
cout endl;——————————————————————————————————————————————————————————————————————————————————————————
//对两者进行效率比对
void TestSort()
{srand(time(0));const int N 5000000;vectorint v;listint lt;v.reserve(N);//提前开好空间for (int i 0; i N; i){auto e rand();v.push_back(e);lt.push_back(e);}比较vector 和 list 的排序int begin1 clock();sort(v.begin(), v.end());int end1 clock();int begin2 clock();lt.sort();int end2 clock();printf(vector sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2);
}#mermaid-svg-8ckfpFdpHSIQn57u {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-8ckfpFdpHSIQn57u .error-icon{fill:#552222;}#mermaid-svg-8ckfpFdpHSIQn57u .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-8ckfpFdpHSIQn57u .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-8ckfpFdpHSIQn57u .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-8ckfpFdpHSIQn57u .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-8ckfpFdpHSIQn57u .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-8ckfpFdpHSIQn57u .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-8ckfpFdpHSIQn57u .marker{fill:#333333;stroke:#333333;}#mermaid-svg-8ckfpFdpHSIQn57u .marker.cross{stroke:#333333;}#mermaid-svg-8ckfpFdpHSIQn57u svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-8ckfpFdpHSIQn57u .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-8ckfpFdpHSIQn57u .cluster-label text{fill:#333;}#mermaid-svg-8ckfpFdpHSIQn57u .cluster-label span{color:#333;}#mermaid-svg-8ckfpFdpHSIQn57u .label text,#mermaid-svg-8ckfpFdpHSIQn57u span{fill:#333;color:#333;}#mermaid-svg-8ckfpFdpHSIQn57u .node rect,#mermaid-svg-8ckfpFdpHSIQn57u .node circle,#mermaid-svg-8ckfpFdpHSIQn57u .node ellipse,#mermaid-svg-8ckfpFdpHSIQn57u .node polygon,#mermaid-svg-8ckfpFdpHSIQn57u .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-8ckfpFdpHSIQn57u .node .label{text-align:center;}#mermaid-svg-8ckfpFdpHSIQn57u .node.clickable{cursor:pointer;}#mermaid-svg-8ckfpFdpHSIQn57u .arrowheadPath{fill:#333333;}#mermaid-svg-8ckfpFdpHSIQn57u .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-8ckfpFdpHSIQn57u .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-8ckfpFdpHSIQn57u .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-8ckfpFdpHSIQn57u .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-8ckfpFdpHSIQn57u .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-8ckfpFdpHSIQn57u .cluster text{fill:#333;}#mermaid-svg-8ckfpFdpHSIQn57u .cluster span{color:#333;}#mermaid-svg-8ckfpFdpHSIQn57u div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-8ckfpFdpHSIQn57u :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 小拓展: 迭代器的这种分类方式是由容器的底层结构来决定的
迭代器类型性质上分类功能 及 示例单向InputIterator支持 单链表、哈希表双向BidirectionalItreator支持 /- - 双向链表、红黑树map和set随机RandomAccessIterator支持 / - - / / - vector、string、deque
可以看到算法库里面的sort迭代器类型是随机RandomAccessIterator类型的所以不可以用算法库中的sort以list中的reverse为例迭代器是双向BidirectionalItreator类型的。
1.2.7 list的迭代器失效
list中insert 插入元素并不会导致迭代器失效 vector 中的 insert插入元素导致迭代器失效是因为vector 中的 insert 会去扩容挪动数据而 list 中的 insert 不会进行扩容挪动数据 前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响
void TestListIterator1()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){//erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给其赋值l.erase(it); it;}
}
——————————————————————————————————————————————————————————————————————————————
// 改正
void TestListIterator()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it); // it l.erase(it);}
}二、list的模拟实现
2.1 定义一个结构体实现list的节点
templateclass T
struct list_node//struct默认是公有的不受访问限定符限制
{T _data;list_nodeT*_next;list_nodeT*_prev;list_node(const T xT())//拷贝构造:_data(x),_next(nullptr),_prev(nullptr){}
};2.2 list的成员变量
templateclass T
class list
{typedef list_nodeT Node;
public:private:Node* _head;
};2.3 list迭代器的封装实现
list 的迭代器不再使用原生指针因为
首先如果list 的迭代器使用原生指针那对迭代器解引用得到的是一个节点但是我们是希望对迭代器解引用可以得到节点里面存储的元素数据其次 list 在底层的物理空间并不连续如果使用原生指针作为 list 的迭代器那对迭代器执行 操作并不会让迭代器指向下一个节点。 所以需要对 list 的迭代器进行封装并对一些运算符进行重载以实现迭代器的效果。
2.3.1 普通迭代器
//迭代器的封装和运算符重载
templateclass T
struct __list_iterator
{typedef list_nodeTNode;typedef __list_iteratorT self;Node* _node;__list_iterator(Node* node)//构造:_node(node){}self operator()//前置{_node _node-_next;return *this;}self operator(int)//后置{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;}T operator*()//因为要修改数据所以返回数据的{return _node-_data;}bool operator(const self s){return _node s._node;}bool operator!(const self s){return _node !s._node ;}
};迭代器不需要实现析构函数、拷贝构造函数、赋值运算符重载函数直接使用默认生成的就可以所以浅拷贝就足够了不需要深拷贝
2.3.2 const迭代器
上述实现了普通迭代器那 const 迭代器该怎样实现呢 所谓const 迭代器本质是限制迭代器指向的内容不能修改而 const 迭代器自身可以修改它可以指向其他节点。 const iterator这种写法const 限制的就是迭代器本身会让迭代器无法实现 等操作(所以const迭代器不是对普通迭代器const修饰)。
为了实现const迭代器有两种方式
单独写一个 _list_const_iterator 的类
templateclass T
struct __list_const_iterator
{typedef list_nodeTNode;typedef __list_const_iteratorT self;Node* _node;__list_const_iterator(Node* node):_node(node){}self operator(){_node _node-_next;return *this;}self operator(int){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;}const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}bool operator(const self s){return _node s._node;}bool operator!(const self s){return _node ! s._node;}
};在普通迭代器的基础上再传递一个模板参数让编译器来生成
templateclass T,class Ref,class Ptr
struct __list_iterator
{typedef list_nodeTNode;typedef __list_iteratorT,Ref,Ptr self;Node* _node;__list_iterator(Node* node):_node(node){}self operator(){_node _node-_next;return *this;}self operator(int){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;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator(const self s) {return _node s._node;}bool operator!(const self s){return _node ! s._node;}
};2.4 list成员函数
2.4.1 构造函数
list 本质上是一个带头双向循环链表。
void empty_init()
{_head new Node;//这里需要传个值所以在拷贝构造的地方给个匿名对象_head-_next _head;_head-_prev _head;
}
list()
{empty_init();
}2.4.2 拷贝构造函数
list(const listT lt)//---lt是一个const类型的
{empty_init();for (auto e : lt){push_back(e);}
}2.4.3 赋值运算符重载
//两种写法
listint operator(const listint lt)
{if(this!lt){clear();//释放lt3;---不清哨兵位的头结点可以继续插入for (auto e : lt)//遍历lt1{push_back(e);//把lt1中的数据插入到lt3}}return *this;
}
____________________________________________________________________________________
void swap(listT lt)
{std::swap(_head,lt._head);//交换头指针std::swap(_size, lt._size);
}
listint operator(listint lt)
{swap(lt);return *this;
}2.4.4 迭代器相关
//普通迭代器
iterator begin()
{return _head-_next;
}
iterator end()
{return _head;
}
//const迭代器
const_iterator begin()const
{return _head-_next;
}
const_iterator end()const
{return _head;
}2.4.5 insert
iterator insert(iterator pos, const T val)
{Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);
}2.4.6 erase
iterator erase(iterator pos)
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;cur nullptr;prev-_next next;next-_prev prev;_size--;return iterator(next);//返回pos的下一个位置
}2.4.7 push_back()
void push_back(const T x)
{
//找尾Node* tail _head-_prev;
//插入节点 Node* newnode new Node(x);tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;
}
————————————————————————————————————————————————————————————————————————————————
//直接复用insert
void push_back(const T x)
{insert(end(),x);
}2.4.8 push_front()
void push_front(const T x)
{insert(begin(), x);
}2.4.9 pop_back()
void pop_back(const T x)
{erase(--end());
}2.4.10 pop_front()
void pop_front(const T x)
{erase(begin());
}2.4.11 size()
size_t size()
{return _size;
}2.4.12 clear()
void clear()
{iterator it begin();while (it ! end()){it erase(it);//返回下一个位置的迭代器}
}2.4.13 析构函数
~list()
{clear();delete _head;_head nullptr;
}三、list与vector的对比
