【C++初阶】List使用特性及其模拟实现

server/2024/10/18 8:36:08/

1. list的介绍及使用

1.1 list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

1.2 list的使用

 1.2.1 list的构造

 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

void TestList1()
{list<int> l1;                         // 构造空的l1list<int> l2(4, 100);                 // l2中放4个值为100的元素list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3list<int> l4(l3);                    // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };// 用迭代器方式打印l5中的元素list<int>::iterator it = l5.begin();while (it != l5.end()){cout << *it << " ";++it;}       cout << endl;// C++11范围for的方式遍历for (auto& e : l5)cout << e << " ";cout << endl;
}

1.2.2 list iterator的使用 

 此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点

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

 

注意： 

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动 


// list迭代器的使用
// 注意：遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{// 注意这里调用的是list的 begin() const，返回list的const_iterator对象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";// *it = 10; 编译不通过}cout << endl;
}void TestList2()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// list<int>::iterator it = l.begin();   // C++98中语法auto it = l.begin();                     // C++11之后推荐写法while (it != l.end()){cout << *it << " ";++it;}cout << endl;// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();auto rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;
}

1.2.3 list capacity 

 empty 检测list是否为空，是返回true，否则返回false
size 返回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中的有效元素 


// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList3()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4，头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}// insert /erase 
void TestList4()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素，即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}// resize/swap/clear
void TestList5()
{// 用数组来构造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素list<int> l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout << l2.size() << endl;
}

1.2.6 list的迭代器失效 （难点）

 我们已经说过可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(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 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}

 所以实际上该迭代器在底层实现时，最后返回的是下一个节点的地址，所以我们每次都要给他赋值才行！！！


2. list的深度剖析及模拟实现

2.1 模拟实现list

#pragma oncenamespace bit
{template <class T>struct ListNode {ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}};template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}//++itSelf& 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;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};//template<class T>//struct ListConstIterator//{//	typedef ListNode<T> Node;//	typedef ListConstIterator<T> Self;//	Node* _node;//	ListConstIterator(Node* node)//		:_node(node)//	{}//	const T& operator*()//	{//		return _node->_data;//	}//	const T* operator->()//	{//		return &(_node->_data);//	}//	//++it//	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;//	}//	bool operator!=(const Self& it)//	{//		return _node != it._node;//	}//	bool operator==(const Self& it)//	{//		return _node == it._node;//	}//};template<class T>class list{typedef ListNode<T> Node;public:/*typedef ListIterator<T> iterator;typedef ListConstIterator<T> const_iterator;*/typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return reverse_iterator(end());}const_reverse_iterator rend() const{return reverse_iterator(begin());}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);}}//lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//lt1 = lt2;list<T>& operator=(list<T> lt){swap(lt);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}/*void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}*/void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}size_t size() const{return _size;}bool empty(){return _size == 0;}private:Node* _head;size_t _size;};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 += 10;cout << *it << " ";++it;}cout << endl;lt.push_front(10);lt.push_front(20);lt.push_front(30);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;}struct A{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}};void test_list2(){list<A> lt;A aa1(1, 1);A aa2 = { 1, 1 };lt.push_back(aa1);lt.push_back(aa2);lt.push_back(A(2, 2));//匿名对象lt.push_back({ 3, 3 }); //单参数类型构造函数支持隐式类型转换，多参数也可以支持lt.push_back({ 4, 4 });A* ptr = &aa1;(*ptr)._a1;ptr->_a1;list<A>::iterator it = lt.begin();while (it != lt.end()){//*it += 10;//cout << (*it)._a1 << ":" << (*it)._a2 << endl;cout << it->_a1 << ":" << it->_a2 << endl;//编译器帮我们省略了一个->方便我们使用cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;++it;}cout << endl;}//void PrintList(const list<int>& clt)//{//	list<int>::const_iterator it = clt.begin();//权限可以缩小，不可变大//	while (it != clt.end())//	{//		//*it += 10;//		cout << *it << " ";//		++it;//	}//	cout << endl;//}void PrintList(list<int>& clt){list<int>::reverse_iterator it = clt.rbegin();//权限可以缩小，不可变大while (it != clt.rend()){//*it += 10;cout << *it << " ";++it;}cout << endl;}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);PrintList(lt);list<int> lt1(lt);PrintList(lt1);}
}

2.2 list的反向迭代器

namespace bit
{// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}};// vector和list反向迭代器实现
}

 这是一个通用的反向迭代器！！！

我们可以看到其底层是怎么样来实现这样的功能的！！！


3. list与vector的对比

vectorlist
底
层
结
构		动态顺序表，一段连续空间带头结点的双向循环链表
随
机
访
问		支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素效率O(N)
插
入
和
删
除		任意位置插入和删除效率低，需要搬移元素，时间复杂
度为O(N)，插入时有可能需要增容，增容：开辟新空
间，拷贝元素，释放旧空间，导致效率更低		任意位置插入和删除效率高，不需要搬移元素，时间复杂度为
O(1)
空
间
利
用
率		底层为连续空间，不容易造成内存碎片，空间利用率
高，缓存利用率高		底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭
代
器		原生态指针对原生态指针(节点指针)进行封装
迭
代
器
失
效		在插入元素时，要给所有的迭代器重新赋值，因为插入
元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效		插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使
用
场
景		需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问


http://www.ppmy.cn/server/5681.html

相关文章

基于Kubernetes集群构建MongoDB

基于Kubernetes集群构建MongoDB

基于Kubernetes集群构建MongoDB 作者：行癫（盗版必究） 一：基础环境 1.Kubernetes集群正常运行 2.Harbor私有仓库正常运行 二：MongoDB项目部署 ​ MongoDB项目对应Kubernetes的yaml文件： --- apiVersion: v1 kind: Namespace metadata:name: m
阅读更多...
论文笔记：Large Language Model for Participatory Urban Planning

论文笔记：Large Language Model for Participatory Urban Planning

202402 arxiv 大模型城市规划 引入了一个基于LLM的多代理协作框架&#xff0c;模拟规划师和数千名具有不同特征和背景的居民&#xff0c;用于参与式城市规划——>生成考虑居民多样化需求的城市区域土地利用规划为了提高讨论的效率&#xff0c;论文采用了鱼缸讨论机制&#…
阅读更多...
请编写函数fun，它的功能是：求出1到1000之内能被7或11整除、但不能同时被7和11整除的所有整数并将它们放在a所指的数组中，通过n返回这些数的个数。

请编写函数fun，它的功能是：求出1到1000之内能被7或11整除、但不能同时被7和11整除的所有整数并将它们放在a所指的数组中，通过n返回这些数的个数。

本文收录于专栏：算法之翼 https://blog.csdn.net/weixin_52908342/category_10943144.html 订阅后本专栏全部文章可见。 本文含有题目的题干、解题思路、解题思路、解题代码、代码解析。本文分别包含C语言、C++、Java、Python四种语言的解法和详细的解析。 题干 请编写函数fu…
阅读更多...
meta-llama/Meta-Llama-3-8B

meta-llama/Meta-Llama-3-8B

https://huggingface.co/meta-llama/Meta-Llama-3-8B 型号细节 Meta开发并发布了Meta Llama 3家族大型语言模型(LLM),这是一组预训练和指令微调的生成性文本模型,大小为8B和70B参数。Llama 3指令微调模型针对对话用例进行了优化,在常见的行业基准测试中表现优于许多可用的开源…
阅读更多...
el-select下拉框远程搜索且多选时，编辑需要回显的一个简单案例

el-select下拉框远程搜索且多选时，编辑需要回显的一个简单案例

前端业务开发中不管使用vue2~3&#xff0c;还是react&#xff0c;angular各种前端技术栈&#xff0c;经常会遇到这种业务。一个下拉框Select中&#xff0c;不仅需要需要支持远程模糊搜索&#xff0c;还需要支持多选。并且在编辑时&#xff0c;还能正常把已经多选好的内容回显到…
阅读更多...
SpringCloud知识01

SpringCloud知识01

1、数据库创建选择 2、定时任务的实现方式 3、分片原理 4、框架图 5、XXL-Job报错Logback configuration error detected 解决&#xff1a; &#xff08;1&#xff09; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-bo…
阅读更多...
蓝桥杯2024年第十五届省赛

蓝桥杯2024年第十五届省赛

E:宝石组合 根据给的公式化简后变为gcd(a,b,c)根据算数基本定理&#xff0c;推一下就可以了 然后我们对1到mx的树求约数&#xff0c;并记录约数的次数&#xff0c;我们选择一个最大的且次数大于等3的就是gcd int mx; vector<int> g[N]; vector<int> cnt[N]; int…
阅读更多...
部署Hyperledger Fabric测试区块链网络

部署Hyperledger Fabric测试区块链网络

一. 快速启动区块链测试网络 启动Fabric虚拟机 将 fabric-samples.zip 拷贝进虚拟机 ubzip fabric-samples.zip 解压并重命名为fabric-samples mv fabric-samples-main fabric-samples 拷贝bin和config目录 cd fabric-samples cp ~/fabric/bin bin -r cp ~/fabric/config …
阅读更多...
最新文章

Copyright @ 2022~2023