STL中的list以及简单实现

embedded/2024/10/19 17:44:17/

STL的list的底层结构其实就是带头双向循环双向链表

带头双向循环双向链表又简单又好用，效率又高，所以其结构是完美的（对于链表而言）：

其中一个原因：有哨兵位的头节点，又循环，找尾很方便，也就是有着O(1)的时间复杂度的插入删除

1.list的构造：

(constructor)构造函数声明

接口说明

list (size_type n, const value_type& val = value_type())
构造的 list 中包含 n 个值为 val 的 元素

list()

构造空的 list
list (const list& x)
拷贝构造函数
list (InputIterator first, InputIterator last)
用 [first, last) 区间中的元素构造 list

2.list iterator的使用 ： 

函数声明

接口说明

begin +  end
返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器
rbegin + rend
返回第一个元素的 reverse_iterator, 即 end 位置 ， 返回最后一个元素下一个位 置的 reverse_iterator, 即 begin 位置

说到迭代器遍历的话，与string，vector都一样；

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";
}
cout << endl;for (auto e : lt)
{cout << e << " ";
}
cout << endl;

是否还支持下标+【】？ list就没有支持方括号了:
比如说从第一个开始到size,下标倒是能想办法获取，但是方括号不支持了，支持 operator [ ] 的话，成本会很高，比如说我要获取我的第3个数据，第5个数据，我是不是得从头开始挨着挨着往后才能遍历获取到第3个，第5个？从功能上来说，从可行性上来说，可以实现的。这个角度来说，语法支持，那它是可以实现 operator [ ] 的。只不过 list 的 operator [ ] 是O(N)，但是之前像string，vector 的 operator [ ] 是O(1)，因为之前像数组这种结构呢，它是连续的物理空间，想获取第几个的话，它的物理空间是连续的，我有指向，你开始的指针，你想获取第二个我是不是加a就过去了，对不对？但是这个地方这些链表呢，它的底层的这些节点呢都是不连续的，你加I你就加不过去，在这个地方，所以我们在这呢是不能这样玩的，不支持 operator [ ] 的。 

​

链表：（空间展示）

​

数组： （空间展示）

​

可以看出：list的迭代器的实现就不再是原生指针了：（不支持+/-）

#include<iostream>
#include<list>using namespace std;int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();lt.erase(it + 3);//二进制“+”:“std::_List_iterator<std::_List_val<std::_List_simple_types<_Ty>>>”不定义该运算符或到预定义运算符可接收的类型的转换return 0;
}

扩展：不同结构带来的各自不同所属迭代器的性质区别 

​

决定了可以使用那些算法 ：

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();// 不支持，算法中的sort要求随机迭代器//sort(lt.begin(), lt.end());string s("dadawdfadsa");cout << s << endl;//string的迭代器就能被支持sort(s.begin(), s.end());cout << s << endl;
}
【注意】
1. begin 与 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动
2. rbegin(end) 与 rend(begin) 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动

3.list capacity：

函数声明

接口说明

empty
检测 list 是否为空，是返回 true ，否则返回 false
size
返回 list 中有效节点的个数

4.list element access：

函数声明

接口说明

front
返回 list 的第一个节点中值的引用
back
返回 list 的最后一个节点中值的引用

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 中的有效元素

其实list库中还有一个接口：emplace_back 与push_back功能类似，但是emplace_back的效率相对较高，而且，emplace_back支持直接传构造对象的参数：

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

算法库中还有自己定义实现的sort（底层是归并）{因为算法库的sort（底层主要是快排，递归深度过大才会选择堆排）不支持list结构（于swap基本一样的处境）}，而且sort都是默认升序 。如果想实现降序的话要用到仿函数（greater这个模板）：

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);for (auto e : lt)
{cout << e << " ";
}
cout << endl;// 升序
lt.sort();// 降序 - 仿函数
// less<int> ls;
// greater<int> gt;
// lt.sort(gt);
lt.sort(greater<int>());//使用匿名对象

但是，list中的sort的效率并不是很高，下面我们拿vector与其对比：

注意：要在release版本，不要在debug版本下对比两者，因为debug没有优化，可能起不到公平的对比：

void test_op1()
{srand(time(0));const int N = 1000000;list<int> lt1;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();// 排序sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}void test_op2()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand()+i;lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();// 拷贝vectorvector<int> v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}
int main()
{test_op1();test_op2();return 0;
}

其实list库中还有reverse()，但其实和算法中的reverse一样：（历史原因）

lt.reverse();
reverse(lt.begin(), lt.end());

splice也是list库中的接口，可以剪切自己或别人，将剪切的片段或元素添加到自己本身位置，它实现的是一种粘接，与复制粘贴不一样，他会影响对方，会夺取对方（从对方身上拔下来）

// 一个链表节点转移给另一个链表
std::list<int> mylist1, mylist2;
std::list<int>::iterator it;// set some initial values:
for (int i = 1; i <= 4; ++i)mylist1.push_back(i);      // mylist1: 1 2 3 4for (int i = 1; i <= 3; ++i)mylist2.push_back(i * 10);   // mylist2: 10 20 30it = mylist1.begin();
++it;                         // points to 2mylist1.splice(it, mylist2); 
// mylist1: 1 10 20 30 2 3 4
// mylist2 (empty)
// "it" still points to 2 (the 5th element

6.list的迭代器失效：

可将迭代器暂时理解成类似于指针， 迭代器失效即迭代器所指向的节点的无 效，即该节点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 ，因此 在 list 中进行插入 时是不会导致 list 的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭 代器，其他迭代器不会受到影响： 
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);// insert以后迭代器不失效
list<int>::iterator it = lt.begin();
lt.insert(it, 10);
*it += 100;print_container(lt);// erase以后迭代器失效
// 我们应该将erase后，保留迭代器
// 删除所有的偶数
it = lt.begin();
while (it != lt.end())
{if (*it % 2 == 0){it = lt.erase(it);}++it;
}print_container(lt);

7.list的底层的简单实现：

实现代码+测试代码：

#pragma once
#include<assert.h>namespace home
{template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()):_data(data),_next(nullptr),_prev(nullptr){}};封装//template<class T>//struct list_iterator//{//	typedef list_node<T> Node;//	typedef list_iterator<T> Self;//	Node* _node;//	list_iterator(Node* node)//		:_node(node)//	{}//	T& operator*()//	{//		return _node->_data//	}//	T* operator->()//	{//		//返回地址//		return &(_node->_data);//	}//	Self& operator++()//	{//		//我多写this->是为了方便理解//		this->_node = _node->_next;//		return *this;//	}//	Self operator++(T)//	{//		Self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	Self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	Self operator--(T)//	{//		Self tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	bool operator!=(const Self& s)const//	{//		return _node != s._node;//	}//	bool operator==(const Self& s)const//	{//		return _node == s._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* node)//		:_node(node)//	{}//	const T& operator*()//	{//		return _node->_data;//	}//	const T* operator->()//	{//		//返回地址//		return &(_node->_data);//	}//	Self& operator++()//	{//		//我多写this->是为了方便理解//		this->_node = _node->_next;//		return *this;//	}//	Self operator++(T)//	{//		Self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	Self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	Self operator--(T)//	{//		Self tmp(*this);//		_node = _node->_prev//		return tmp;//	}//	bool operator!=(const Self& s)const//	{//		return _node != s._node;//	}//	bool operator==(const Self& s)const//	{//		return _node == s._node;//	}//};//其实const_iteerator与iterator基本相似，可以用两个模板进行封装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;}Ptr operator->(){return &(_node->_data);}Self& operator++(){this->_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_next;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const Self& s)const{return _node != s._node;}bool operator==(const Self& s)const{return _node == s._node;}};template<class T>class list{typedef list_node<T> Node;public:/*typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*///两个模板typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//匿名+隐式类型转换return _head->_next;}iterator end(){return  _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}//空初始化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);}}//拷贝构造list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//赋值拷贝list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}void swap(list<T> lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}void push_back(const T& x){insert(end(), x);}void front_back(const T& x){insert(begin(), x);}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);newnode->_prev = prev;prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos){assert(pos != end());//不可以删头节点Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;prev->_prev = prev;delete pos._node;--_size;return next;}size_t size()const{return _size;}bool empty()const{return _size == 0;}private:Node* _head;size_t _size;};struct AA{int _a1 = 1;int _a2 = 1;};// 按需实例化// T* const ptr1// const T* ptr2template<class Container>void print_container(const Container& con){// const iterator -> 迭代器本身不能修改// const_iterator -> 指向内容不能修改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;}void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;print_container(lt);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 << ":" << (*ita)._a2 << endl;// 特殊处理，本来应该是两个->才合理，为了可读性，省略了一个->cout << ita->_a1 << ":" << ita->_a2 << endl;cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;++ita;}cout << endl;}void test_list2(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);// insert以后迭代器不失效list<int>::iterator it = lt.begin();lt.insert(it, 10);*it += 100;print_container(lt);// erase以后迭代器失效// 删除所有的偶数it = lt.begin();while (it != lt.end()){if (*it % 2 == 0){it = lt.erase(it);}it++;}print_container(lt);}void test_list3(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2(lt1);print_container(lt1);print_container(lt2);list<int> lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);lt1 = lt3;print_container(lt1);print_container(lt3);}void func(const list<int>& lt){print_container(lt);}void test_list4(){// 直接构造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;*/}
}


http://www.ppmy.cn/embedded/93339.html

相关文章

思特威正式发布子品牌飞凌微，首发产品定位智驾视觉处理

思特威正式发布子品牌飞凌微，首发产品定位智驾视觉处理

2024年8月8日&#xff0c;中国上海 — 思特威&#xff08;上海&#xff09;电子科技股份有限公司&#xff08;股票简称&#xff1a;思特威&#xff0c;股票代码&#xff1a;688213&#xff09;正式发布全资子公司品牌——飞凌微电子&#xff08;Flyingchip™&#xff0c;以下简…
阅读更多...
分布式领域扩展点设计稿

分布式领域扩展点设计稿

分布式领域扩展点设计稿 背景坐标设计理念设计图Quick Start相关组件 背景 随着交易业务和基础知识的沉淀&#xff0c;愈发觉得扩展点可以在大型交易分布式架构中可以做更多的事情。 经过一个月的思考&#xff0c;决定将 单点领域扩展点&#xff08;savior-ext&#xff09; 从…
阅读更多...
基于VEH的无痕HOOK

基于VEH的无痕HOOK

这里的无痕HOOK指的是不破坏程序机器码，这样就可以绕过CRC或MD5的校验。 VEH利用了Windows的调试机制和异常处理，人为抛出异常，从异常的上下文中获取寄存器信息。 DLL入口 // dllmain.cpp : 定义 DLL 应用程序的入口点。 #include "pch.h" #include "CHoo…
阅读更多...
uniapp 自定义图片预览组件PicturePreview（Vue3、组合式、ts）

uniapp 自定义图片预览组件PicturePreview（Vue3、组合式、ts）

组件 <template><view class"preview-container" :style"{display: show ? block : none}"><view class"f-c-c close" click"close"><YcSvgIcon name"close" width"15rpx" height"15…
阅读更多...
python游戏开发之五子棋游戏制作

python游戏开发之五子棋游戏制作

五子棋是一种源自中国的传统棋类游戏&#xff0c;起源可以追溯到古代。它是一种两人对弈的游戏&#xff0c;使用棋盘和棋子进行。棋盘通常是一个 1515 的网格&#xff0c;棋子分为黑白两色&#xff0c;双方轮流在棋盘上落子。游戏的目标是通过在棋盘上落子&#xff0c;使自己的…
阅读更多...
【GCC】基于延迟梯度的带宽估计：速率控制状态机的理解

【GCC】基于延迟梯度的带宽估计：速率控制状态机的理解

这部分是一个难点，决定了目标码率。参考了很多大神的分析，大神都很牛x，分析的都很到位。回顾下之前的学习，发现还是在 基于延迟的排队梯度这块，其根本目的就是本文的预估一个下一步的码率出来。之前的文章都在分析“基于延迟梯度的带宽估计” 的一些原理。接收端在RTCP中增…
阅读更多...
Spring Boot 3.0 热部署

Spring Boot 3.0 热部署

idea开发环境下的spring boot 3.0热部署启用非常简单&#xff0c;并没有网上教程讲的需要对idea做一些设置。 只需引入依赖&#xff1a; developmentOnly org.springframework.boot:spring-boot-devtools其他不需要做任何设置。 服务启动中&#xff0c;改了代码或配置后&…
阅读更多...
C++ 重要特性探究

C++ 重要特性探究

shared_from_this 使用分析 场景 类的成员函数需要获取指向自身的shared_ptr的时候类成员函数传递shared_ptr给其他函数或者对象的时候&#xff0c;目的是为了管理对象生命周期使用方法 首先类必须继承 std::enable_shared_from_this<T>必须使用 shared_from_this 获取指…
阅读更多...
最新文章

Copyright @ 2022~2023