深入理解C++ stl::list 底层实现+模拟实现

server/2025/3/14 9:31:38/

                        欢迎来到干货小仓库!!!

              "人生没有 Ctrl - Z ，但永远可以 push 新版本"

1.list的介绍

①stl::list的底层实现是带头双向循环链表结构。

②list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

③双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

2.list的使用

2.1list的构造

构造函数接口说明
list(size_t n , const T& val = T())构造的list中包含n个值的val 元素
list()构造空的list
list(const list& x)拷贝构造函数
list(InputIterator first ,InputIterator last)用[ first , last) 区间中的元素构造list
int main()
{list<int> lt1;                         // 构造空的lt1list<int> lt2(4, 100);                 // lt2中放4个值为100的元素list<int> lt3(l2.begin(), l2.end());  // 用lt2的[begin(), end()）左闭右开的区间构造lt3list<int> lt4(l3);                    // 用l3拷贝构造lt4return 0;
}

2.2 list iterator的使用

注意:list的迭代器的底层是链表的节点,其访问链表中的数据，是通过操作符重载的方式来进行实现的。

函数声明接口说明
begin + end返回第一个元素的迭代器 + 返回最后一个元素的下一个位置的迭代器
rbegin + rend返回第一个元素的reverse_iterator即end位置 + 返回最后一个元素的下一个位置的reverse_iterator,即begin位置

2.3 list 关于容量的函数

函数声明接口说明
empty()检测 list 是否为空，是返回  true ，不是则返回 false。
size()返回 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);cout <<"size:"<< lt.empty() << endl;cout <<"empty:"<< lt.size() << endl;return  0;
}

2.4 list 中的数据访问函数

函数声明接口说明
front返回 list 的第一个节点中的引用
back返回 list 的最后一个节点中的值的引用

2.5 list 关于数据的函数

函数声明接口说明
push_front在 list 首元素前插入值为 val 的元素
pop_front删除 list 中的第一个元素
push_back在 list 尾部插入值为 val 的元素
pop_back删除 list 中最后一个元素
insert在 list 的 pos  位置中插入值为 val 的元素
erase删除 list 中 pos 位置的元素
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;
}

2.6 list 迭代器失效

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

示例:

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

3.list中的 sort 和算法库中的区别

list 中的 sort 底层实现是 归并排序 实现的。(时间复杂度高，效率低)

算法库中的 sort 底层是 快排 实现的。(时间复杂度低，效率高)

效率测试和对比：

4.list的模拟实现及正向和反向迭代器解析

4.1list的迭代器封装

list 的迭代器 和 string和vector迭代器的区别：

首先我们得清楚，list 中每一个节点，在空间都是非连续存储的，不像string 和 vector 的迭代器一样直接对迭代器++/-- 即可，由于其底层是内置类型的指针形似而它们在内存中存储数据又是在连续的空间上存储的，不需要我们进行因此我们在对迭代器做 ++/ -- 等操作的时候重载运算符。

我们应该怎么办呢？

通过封装迭代器，对++、--等运算符实现重载。

迭代器的成员变量的解析:

4.2迭代器模板参数的解析

4.3正向迭代器模拟实现

template<class T>
struct list_node
{list_node<T>* _next=nullptr;list_node<T>* _prev=nullptr;T _val;list_node(const T& val = T()):_val(val){}
};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->_val;}Ptr operator->(){return &_node->_val;}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) const{return _node != it._node;}bool operator==(const Self& it) const{return _node == it._node;}
};

4.4反向迭代器模拟实现

原理和正向迭代器差不多，反向迭代器的成员变量的类型是 正向迭代器，通过操作符重载的方式实现逻辑变化，反向迭代器的操作符重载实现，底层原理都是去调用 正向迭代器 的操作符重载，唯一区别就是逻辑不同。

template<class iterator,class Ref,class Ptr>
struct Reverse_iterator
{
public:typedef Reverse_iterator<iterator,  Ref,  Ptr> Self;iterator _it;Reverse_iterator(iterator it):_it(it){ }Self operator++(){--_it;return *this;}Self operator--(){++_it;return  *this;}Ref operator*(){iterator tmp = _it;return  *(--tmp);}Ptr operator->(){return &(operator*());}bool operator!=(const Self& s) const{return _it != s._it;}
};

4.5 list 函数模拟实现

template<class T>
struct list_node
{list_node<T>* _next=nullptr;list_node<T>* _prev=nullptr;T _val;list_node(const T& val = T()):_val(val){}
};
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;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&,const T*> reverse_const_iterator;//反向迭代器reverse_iterator rbegin(){return reverse_iterator(_head);}reverse_iterator rend(){return reverse_iterator(_head->_next);}//const 反向迭代器reverse_const_iterator rbegin() const{return reverse_const_iterator(_head);}reverse_const_iterator rend() const{return reverse_const_iterator(_head->_next);}//正向迭代器iterator begin(){//return _head->_next;return iterator(_head->_next);}iterator end(){return _head;//return iterator(_head);}//const 正向迭代器const_iterator begin() const {//return _head->_next;return const_iterator(_head->_next);}const_iterator end() const {//return _head;return const_iterator(_head);}void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_sz = 0;}list(){empty_init();}list(const list<T>&  lt){empty_init();auto it = lt.begin();while (it != lt.end()){push_back(*it);++it;}}void swap( list<T>& lt){std::swap(_head, lt._head);std::swap(_sz, lt._sz);}list<T>& operator=(list<T> lt){swap(lt);return *this;}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(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}//pos之前插入iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;newnode->_next = cur;++_sz;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_sz;return next;}size_t size(){return _sz;}void clear(){list<T>::iterator it = begin();while (it != end()){it = erase(it);}_sz = 0;}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _sz; //用于记录list中有效数据的个数
};

5. list 和 vector的对比

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

觉得不错的，大家可以点点赞 +  收藏!!!

谢谢大家的支持。


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

相关文章

5-24 色彩与风格——T2IA自适应

5-24 色彩与风格——T2IA自适应

前言&#xff1a; 上一节我们介绍了ControlNet中的inpaint局部重绘 主要介绍ControlNet中的T2IA自适应。 色彩风格的参考和借鉴能力&#xff0c;有点类似于5-17 reference参考图 或者 5-16 画面风格迁移-shuffle洗牌 。当然在硬件的要求&#xff0c;软件的算法实现和使用方式…
阅读更多...
WPF有哪些使用率高的框架

WPF有哪些使用率高的框架

架构类库 Community Toolkit MVVMMVVM Light UI类库 MahApps.MetroMaterial Design In XAML Toolkit 图标类库 MahApps.Metro.IconPacks
阅读更多...
rStar论文精读

rStar论文精读

论文简介 论文标题&#xff1a;《Mutual reasoning makes smaller LLMs stronger problem-solvers》 论文地址&#xff1a;https://arxiv.org/abs/2408.06195 录用会议&#xff1a;ICLR2025 背景与挑战 挑战1&#xff1a;在SLM中平衡exploration与exploitation。一些方法有很…
阅读更多...
Chrome 扩展开发 API实战：Extension（五）

Chrome 扩展开发 API实战：Extension（五）

Chrome.bookmarks API 技术文档 1. 引言 在开发 Chrome 扩展程序时&#xff0c;书签的管理是一项常见需求。chrome.bookmarks API 提供了一套强大的接口&#xff0c;允许开发者创建、查询、更新、移动和删除书签。本文将详细介绍如何使用该 API 来操作浏览器中的书签。 2. 权…
阅读更多...
结构型模式---享元模式

结构型模式---享元模式

概念 享元模式是一种结构型设计模式&#xff0c;他摒弃了在每个对象中保存所有数据的方式&#xff0c;通过共享多个对象所共有的相同状态&#xff0c;让你能在有限的内存容量中载入更多对象。享元模式将原始类中的数据分为内在状态数据和外在状态数据。 内在状态&#xff1a;就…
阅读更多...
《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（42）九龙神火罩拓扑 - 课程表排序（拓扑排序）

《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（42）九龙神火罩拓扑 - 课程表排序（拓扑排序）

《灵珠觉醒：从零到算法金仙的C++修炼》卷三天劫试炼（42）九龙神火罩拓扑 - 课程表排序（拓扑排序） 哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的九龙神火罩大阵，阵中有一座巨大的九龙神火罩，罩身闪烁着神秘的光芒。大阵入口处有一块巨大的石碑，上面…
阅读更多...
MySQL 8 设置允许远程连接（Windows环境）

MySQL 8 设置允许远程连接（Windows环境）

&#x1f31f; MySQL 8 设置允许远程连接&#xff08;Windows环境&#xff09; 在开发和部署应用时&#xff0c;经常需要从远程主机连接到MySQL数据库。默认情况下&#xff0c;MySQL仅允许本地连接&#xff0c;因此需要进行一些配置才能允许远程访问。今天&#xff0c;我将详细…
阅读更多...
机器学习中常用的避免过拟合的方法有哪些

机器学习中常用的避免过拟合的方法有哪些

在机器学习和深度学习中&#xff0c;避免过拟合是提高模型泛化能力的关键。以下是一些常用的避免过拟合的方法&#xff1a; 1. ​增加数据量 ​原理&#xff1a;更多的数据可以帮助模型学习到数据的本质规律&#xff0c;而不是噪声。​方法&#xff1a; 收集更多的真实数据。使…
阅读更多...
最新文章

Copyright @ 2022~2023