【C++】第九节：list

embedded/2024/11/24 6:40:15/

1、list的介绍及使用

1.1 list的介绍

list - C++ 参考

1.2 list的使用

1.2.1 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 arr[] = { 16,2,77,29 };list<int> l5(arr, arr + sizeof(arr) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };list<int>::iterator it = l5.begin();while (it != l5.end()){cout << *it << " ";++it;}cout << endl;for (auto& e : l6){cout << e << " ";}cout << endl;
}

1.2.2 list iterator的使用

// 注意：遍历链表只能用迭代器和范围for
void TestList2()
{int arr[] = { 1,2,3,4,5,6,7,8,9,0 };list<int> l(arr, arr + sizeof(arr) / sizeof(arr[0]));// 使用正向迭代器遍历list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;// 使用反向迭代器遍历list<int>::reverse_iterator rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;// 使用for循环遍历// 注意这里调用的是list的begin() const，返回list的const_iterator对象for (list<int>::const_iterator cit = l.begin(); cit != l.end(); ++cit){cout << *cit << " ";//*cit = 10; // 编译不通过}cout << endl;
}

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

void TestList3()
{int arr[] = { 1,2,3 };list<int> l(arr, arr + sizeof(arr) / sizeof(arr[0]));// 在l的尾部插入4，头部插入0l.push_back(4);l.push_front(0);for (auto& e : l){cout << e << " ";}cout << endl;// 获取链表第二个节点auto pos = ++l.begin();// 在pos位置之前插入7l.insert(pos, 7);// 用迭代器区间插入vector<int> v{ 4,5,6 };l.insert(pos, v.begin(), v.end());for (auto& e : l){cout << e << " ";}cout << endl;// 删除pos位置上的元素l.erase(pos);for (auto& e : l){cout << e << " ";}cout << endl;
}
void TestList4()
{int arr[] = { 1,2,3 };list<int> l1(arr, arr + sizeof(arr) / sizeof(arr[0]));// 交换l1和l2中的元素list<int> l2;l1.swap(l2);for (auto& e : l1){cout << e << " ";}cout << endl;for (auto& e : l2){cout << e << " ";}cout << endl;// 清空l2中的元素l2.clear();cout << l2.size() << endl;
}

1.2.6 list operations

void TestList5()
{list<int> 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();for (auto e : lt){cout << e << " ";}cout << endl;//sort(lt.begin(), lt.end()); // 报错，因为list底层是双向迭代器，而sort需要随机迭代器// 升序 < less//lt.sort(); // 降序 > greater//greater<int> gt;//lt.sort(gt);lt.sort(greater<int>()); // 匿名对象for (auto e : lt){cout << e << " ";}cout << endl;
}

void TestList6();
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(3);lt.push_back(3);lt.push_back(3);lt.push_back(5);lt.push_back(5);lt.push_back(3);for (auto e : lt){cout << e << " ";}cout << endl;lt.sort(); // 先排序lt.unique();// 再去重for (auto e : lt){cout << e << " ";}cout << endl;lt.remove(3);for (auto e : lt){cout << e << " ";}cout << endl;
}

1.2.7 list迭代器失效

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

void TestListIterator1()
{int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(arr, arr + sizeof(arr) / sizeof(arr[0]))；auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值l.erase(it);++it;}
}// 改正
void TestListIterator()
{int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(arr, arr + sizeof(arr) / sizeof(arr[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it++作为参数传递给l.erase()}
}

2、list的模拟实现

2.1 模拟实现list

namespace yf
{// list的节点类（模板类）template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;// T不一定是int，所以不能直接给0，要用匿名对象list_node(const T& x = T()) :_data(x), _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* node):_node(node){}// 前置++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;}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;}};template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;const_iterator begin() const{// 这里跳到迭代器的构造函数创建了一个新的const_iterator对象，// 使其指向_head->_next节点return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){//return iterator(_head->_next);return _head->_next; // list_node<T>*会被隐式类型转换为iteator对象}iterator end(){//return iterator(_head);return _head;}// 空初始化void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}// 无参构造函数list(){empty_init();}// lt2(lt1)list(const list<T>& lt){// 先构造一个空的lt2empty_init();for (auto e : lt){push_back(e);}}void swap(list<int>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// lt3 = lt2list<int>& operator=(list<int> lt){swap(lt);return *this;}~list(){clear();delete _head;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){insert(end(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}// 在pos位置之前插入，返回新插入的位置iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}// 删除pos节点，返回pos节点的下一个节点的迭代器iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;--_size;return iterator(next);}size_t size(){return _size;}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 += 20;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list2(){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> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt2.push_back(50);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;}struct AA{AA(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;};void test_list3(){list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));list<AA>::iterator it = lt.begin();while (it != lt.end()){cout << it->_a1 << " " << it->_a2 << endl;cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;++it;}cout << endl;}//template<typename T>//void print_list(const list<T>& lt)//{//	// list<T>是未实例化的类模板，编译器不能去他里面找//	// 编译器无法判断list<T>::const_iterator是内嵌类型，还是静态成员变量//	// 前面加一个typename就是告诉编译器，这是一个类型，等list<T>实例化//	// 再去类里面找//	typename list<T>::const_iterator it = lt.begin();//	while (it != lt.end())//	{//		cout << *it << " ";//		++it;//	}//	cout << endl;//}template<typename Container>void print_container(const Container& con){typename Container::const_iterator it = con.begin();while (it != con.end()){cout << *it << " ";++it;}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);print_container(lt);vector<string> v;v.push_back("11111111111");v.push_back("11111111111");v.push_back("11111111111");v.push_back("11111111111");print_container(v);}
}

3、list与vector的对比


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

相关文章

HAProxy面试题及参考答案（精选80道面试题）

HAProxy面试题及参考答案（精选80道面试题）

目录 什么是 HAProxy？ HAProxy 主要有哪些功能？ HAProxy 的关键特性有哪些？ HAProxy 的主要功能是什么？ HAProxy 的作用是什么？ 解释 HAProxy 在网络架构中的作用。 HAProxy 与负载均衡器之间的关系是什么？ HAProxy 是如何实现负载均衡的？ 阐述 HAProxy 的四层…
阅读更多...
「Chromeg谷歌浏览器/Edge浏览器」篡改猴Tempermongkey插件的安装与使用

「Chromeg谷歌浏览器/Edge浏览器」篡改猴Tempermongkey插件的安装与使用

1. 谷歌浏览器安装及使用流程 1.1 准备篡改猴扩展程序包。 因为谷歌浏览器的扩展商城打不开&#xff0c;所以需要准备一个篡改猴压缩包。 其他浏览器只需打开扩展商城搜索篡改猴即可。 没有压缩包的可以进我主页下载。 也可直接点击下载&#xff1a;Chrome浏览器篡改猴(油猴…
阅读更多...
【c++丨STL】list模拟实现（附源码）

【c++丨STL】list模拟实现（附源码）

&#x1f31f;&#x1f31f;作者主页&#xff1a;ephemerals__ &#x1f31f;&#x1f31f;所属专栏&#xff1a;C、STL 目录 前言 一、节点、迭代器以及函数声明 二、list功能实现 1. 节点 2. 迭代器 迭代器的默认构造 operator* operator-> 前置和-- 后置和--…
阅读更多...
【华为云函数工作流】python的函数中如何获取请求链接中带的参数

【华为云函数工作流】python的函数中如何获取请求链接中带的参数

背景 通过调用函数的url&#xff0c;将参数传递给函数执行&#xff0c;函数里如何获取这个参数 过程 下一个简单的demo如下 参考这个链接https://support.huaweicloud.com/devg-functiongraph/functiongraph_02_0420.html写一个demo&#xff0c;这个是百度视频云获取token的…
阅读更多...
【MySQL】mysql常用不常用法（持续更新）

【MySQL】mysql常用不常用法（持续更新）

注意&#xff1a;对数据做操作时做好备份 1、查询mysql数据表中某字段有重复的数据 适用场景&#xff0c;如&#xff1a; 用户表同名的有那些人&#xff0c;那些名称是重复出现的 SQL语法&#xff1a; SELECT t.*, COUNT(*) AS x_count FROM [table_name] t GROUP BY [检查…
阅读更多...
vue2 src_Todolist编辑($nextTick)

vue2 src_Todolist编辑($nextTick)

main.js //引入Vue import Vue from "vue"; //引入App import App from ./App;//关闭Vue的生产提示 Vue.config.productionTip false;new Vue({el: #app,render: h > h(App),beforeCreate() {//事件总线Vue.prototype.$bus this;} });App.vue <template>…
阅读更多...
Sickos1.1 详细靶机思路 实操笔记

Sickos1.1 详细靶机思路 实操笔记

Sickos1.1 详细靶机思路 实操笔记 免责声明 本博客提供的所有信息仅供学习和研究目的&#xff0c;旨在提高读者的网络安全意识和技术能力。请在合法合规的前提下使用本文中提供的任何技术、方法或工具。如果您选择使用本博客中的任何信息进行非法活动&#xff0c;您将独自承担…
阅读更多...
蓝桥杯每日真题 - 第20天

蓝桥杯每日真题 - 第20天

题目&#xff1a;&#xff08;机房&#xff09; 题目描述&#xff08;13届 C&CG题&#xff09; 解题思路&#xff1a; 这道题目可以看作在一个无向图中查找两点之间的最短路径。题目中的 n 台电脑和 n−1 根网线形成了一棵树&#xff0c;树是一个特殊的无向图&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023