当前位置： 首页 > news >正文

SLT—List详解

news 来源：原创 2024/9/19 14:21:47

1.list概述

相较于 vector 的连续线性空间，list 就显得复杂很多，它的好处是每次插入或删除一个数据，就配置或释放一个元素空间。因此，list 对于空间的运用有绝对的精准，一点也不浪费。对于任何位置的元素进行插入或者元素移除，list 永远是常数时间（O(N)）。

list 和 vector 是两个最常被使用的容器，什么时机下最适合使用哪一种容器，必须视元素的多寡、元素的构造复杂度、 元素存取行为的特征而定。

下图是 list 示意图 : 环状链表的尾端加上一个空白节点，符合“前闭后开”区间。

2.list的使用

list 中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

(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 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;
}

(2) list iterator

暂时将迭代器理解成一个指针，该指针指向 list 中的某个节点。

 

【注意】
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;
}

(3) list capacity

(4) list element access（元素访问）

(5) list modifiers（修改器）

#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{list<int> ilist; cout << "size=" << ilist.size() << endl;// size=0ilist.push_back(0); ilist.push_back(1); ilist.push_back(2); ilist.push_back(3); ilist.push_back(4); cout << "size=" << ilist.size() << endl;//size=5list<int>::iterator ite; for (ite = ilist.begin(); ite != ilist.end(); ++ite){cout << *ite << ' ';//0 1 2 3 4}cout << endl;ite = find(ilist.begin(), ilist.end(), 3);if (ite != ilist.end()){ilist.insert(ite, 99);}cout << "size=" << ilist.size() << endl;// size=6cout << *ite << endl;// 3for (ite = ilist.begin(); ite != ilist.end(); ++ite)//0 1 2 99 3 4cout << *ite << ' ';cout << endl;ite = find(ilist.begin(), ilist.end(), 1); if (ite != ilist.end())cout << *(ilist.erase(ite)) << endl;//2for (ite = ilist.begin(); ite != ilist.end(); ++ite)//0 2 99 3 4cout << *ite << ' ';cout << endl;
}

(6) list迭代器失效

前面说过，此处可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致 list 的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。这在 vector 是不成立的，因为 vector 的常茹操作可能造成记忆体重新配置，导致原有的迭代器全部失效。 
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);}
}

3.list的模拟实现

(1) list的节点（ListNode）

list 本身和 list 的节点是不同的结构，需要分开设计，以下是根据 STL 设计的 list 的节点（ListNode）结构：

template <class T>
struct ListNode // struct默认成员是公有的
{ListNode(const T& val = T()):_prev(nullptr),_next(nullptr),_data(val){}ListNode<T>* _prev;ListNode<T>* _next;T _data;
};

(2) list的迭代器（ListIterator）

list 不能再像 vector 一样以普通指针作为迭代器，因为其节点不保证在存储空间里连续存在。list迭代器必须有能力指向list节点，并有能力进行正确的递增、递减、取值、成员存取等操作。所谓“list 正确的递增、递减、取值、成员存取”操作是指，递增时指向下一个节点，递减时指向下一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。

由于STL list是一个双向链表，迭代器必须具备迁移，后移的能力，所以 list 提供的是 Birdirectional Iterator（双向）

List 的迭代器

迭代器有两种实现方式，具体应根据容器底层数据结构实现：

1. 原生态指针，比如：vector

2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：

（1）指针可以解引用，迭代器的类中必须重载 operator*()

（2）指针可以通过->访问其所指空间成员，迭代器类中必须重载 oprator->()

（3）指针可以++向后移动，迭代器类中必须重载 operator++() 与 operator++(int)

至于 operator--() / operator--(int) 释放需要重载，根据具体的结构来抉择，双向链表可以向前 移动，所以需要重载，如果是forward_list（单向）就不需要重载--

（4）迭代器需要进行是否相等的比较，因此还需要重载 operator==() 与 operator!=()

//List的迭代器类模版，实例化了两个类
template<class T, class Ref, class Ptr>
class ListIterator
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}T& operator*(){//取得是节点的数值return (*_pNode)._data;}T* operator->(){return &(operator*());}Self& operator++(){_pNode = (*_pNode)._next;return *this;}Self operator++(int)//前置++{Self tmp = *this;_pNode = (*_pNode)._next;return tmp;//返回++之前的}Self& operator--(){_pNode = (*_pNode)._prev;return *this;}Self operator--(int){Self tmp = *this;_pNode = _pNode._prev;return tmp;//返回++之前的}bool operator!=(const Self& l){return !(_pNode == l._pNode);}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;//迭代器的内部要有一个普通指针，指向list的节点
};

(3) list的数据结构

STL list 不仅是一个双向链表，而且还是一个环状双向链表。所以它只需要一个指针，就可以完整表现整个链表。

//list类
template<class T>
class list // class 默认是私有的
{typedef ListNode<T> Node;
public:typedef Node* PNode;//实现...private:PNode _pHead;//只需要一个指针，完成整个双向环状链表size_t _size;//STL中没有，自己实现为了方便加的};

(4) list的构造与内存管理 

如果将指针刻意置于尾端的一个空白节点，_pHead便能符合STL对于“前闭后开”去区间的要求，成为 list 迭代器。

    // List的构造list(){CreateHead();//产生一个空链表(一个指向自己的空节点)}list(int n, const T& value = T()){CreateHead();while (n--){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);first++;}}//深拷贝list(const list<T>& l){CreateHead();list<T> tmp(l.begin(), l.end());swap(tmp);}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete[] _pHead;_pHead = nullptr;}private:void CreateHead(){_pHead = new Node[1];//配置一个节点空间，头尾指向自己_pHead->_next = _pHead;_pHead->_prev = _pHead;}

当我们以 push_back( )将新元素插入于list尾端时，此时函数内部调用 insert( ) :

void push_back(const T& val){ insert(end(), val);}

insert( ) 是一个重载函数，有多种形式，其中最简单的一种如下，首先配置并构造一个节点，然后在尾端进行适当的指针操作，将新节点插入进去：

// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{PNode tmp = new Node[1];tmp->_data = val;PNode pcur = pos._pNode->_prev;pcur->_next = tmp;tmp->_prev = pcur;pos._pNode->_prev = tmp;tmp->_next = pos._pNode;++_size;return tmp;
}

插入完成之后，新节点将位于插入点所指向之节点的前方—这是STL对于“插入操作”的标准规范。

(5) list的元素操作

list 提供的元素操作有很多，这里只实现部分操作。

// List Modify
void push_back(const T& val)
{insert(end(), val);
}
void pop_back()
{erase(--end());
}
void push_front(const T& val)
{insert(begin(), val);
}
void pop_front()
{erase(begin());
}
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{PNode tmp = new Node[1];tmp->_data = val;PNode pcur = pos._pNode->_prev;pcur->_next = tmp;tmp->_prev = pcur;pos._pNode->_prev = tmp;tmp->_next = pos._pNode;++_size;return tmp;
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{PNode pcur = pos._pNode->_prev;PNode pnext = pos._pNode->_next;pcur->_next = pnext;pnext->_prev = pcur;delete[] pos._pNode;--_size;return pnext;
}
//清除整个链表
void clear()
{auto cur = begin();while (cur != end()){cur = erase(cur);}
}

(6) 模拟实现.h

#include<iostream>
#include<list>
#include<algorithm>
#include<assert.h>
using namespace std;namespace zyt
{//List的节点类template <class T>struct ListNode // struct默认成员是公有的{ListNode(const T& val = T()):_prev(nullptr), _next(nullptr), _data(val){}ListNode<T>* _prev;ListNode<T>* _next;T _data;};//List的迭代器类模版，实例化了两个类template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}T& operator*(){return (*_pNode)._data;}T* operator->(){return &(operator*());}Self& operator++(){_pNode = (*_pNode)._next;return *this;}Self operator++(int)//前置++{Self tmp = *this;_pNode = (*_pNode)._next;return tmp;//返回++之前的}Self& operator--(){_pNode = (*_pNode)._prev;return *this;}Self operator--(int){Self tmp = *this;_pNode = _pNode._prev;return tmp;//返回++之前的}bool operator!=(const Self& l){return !(_pNode == l._pNode);}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;};//list类template<class T>class list // class 默认是私有的{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:///// List的构造list(){CreateHead();//产生一个空链表(一个指向自己的空节点)}list(int n, const T& value = T()){CreateHead();while (n--){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);first++;}}//深拷贝list(const list<T>& l){CreateHead();list<T> tmp(l.begin(), l.end());swap(tmp);}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete[] _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return ((*_pHead)._next);}iterator end(){return _pHead;}const_iterator begin() const{return ((*_pHead)._next);}const_iterator end() const{return _pHead;}///// List Capacitysize_t size()const{return _size;}bool empty()const{return _pHead->_next == _pHead;}// List AccessT& front(){return *begin();}const T& front()const{return *begin();}T& back(){return *end();}const T& back()const{return *end();}// List Modifyvoid push_back(const T& val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){PNode tmp = new Node[1];tmp->_data = val;PNode pcur = pos._pNode->_prev;pcur->_next = tmp;tmp->_prev = pcur;pos._pNode->_prev = tmp;tmp->_next = pos._pNode;++_size;return tmp;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){PNode pcur = pos._pNode->_prev;PNode pnext = pos._pNode->_next;pcur->_next = pnext;pnext->_prev = pcur;delete[] pos._pNode;--_size;return pnext;}//清除整个链表void clear(){auto cur = begin();while (cur != end()){cur = erase(cur);}}void swap(list<T>& l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:void CreateHead(){_pHead = new Node[1];//配置一个节点空间，头尾指向自己_pHead->_next = _pHead;_pHead->_prev = _pHead;}private:PNode _pHead;size_t _size;};
}

(7) 测试.cpp

// 打印各类容器（类）
template<class T>
void PrintList(const zyt::list<T>& l)
{auto it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;
}void TestList3()
{int array[] = { 1, 2, 3, 4, 5 };//zyt::list<int> l(array, array + sizeof(array) / sizeof(array[0]));zyt::list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);PrintList(l);auto pos = l.begin();l.insert(l.begin(), 0);PrintList(l);++pos;l.insert(pos, 2);PrintList(l);l.erase(l.begin());l.erase(pos);PrintList(l);// pos指向的节点已经被删除，pos迭代器失效cout << *pos << endl;auto it = l.begin();while (it != l.end()){it = l.erase(it);}cout << l.size() << endl;
}// PushBack()/PopBack()/PushFront()/PopFront()
void TestList2()
{// 测试PushBack与PopBackzyt::list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);PrintList(l);l.pop_back();l.pop_back();PrintList(l);l.pop_back();cout << l.size() << endl;// 测试PushFront与PopFrontl.push_front(1);l.push_front(2);l.push_front(3);PrintList(l);l.pop_front();l.pop_front();PrintList(l);l.pop_front();cout << l.size() << endl;
}// 测试List的构造
void TestList1()
{zyt::list<int> l1;zyt::list<int> l2(10, 5);PrintList(l2);int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };zyt::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));PrintList(l3);zyt::list<int> l4(l3);PrintList(l4);l1 = l4;PrintList(l1);
}
int main()
{TestList1();return 0;
}

4.list与vector的区别 

vector 与 list 都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 【2024高教社杯全国大学生数学建模竞赛】B题模型建立求解
  • 最新OpenStreetMap POI数据（附下载教程）
  • ctfshow-web入门-sql注入（web237-web240）insert 注入
  • Elasticsearch的使用
  • 【C++模版初阶】——我与C++的不解之缘（七）
  • 舒适度和音质再升级，南卡OE Pro2以标杆级实力，体验革命性提升！
  • 【VB6|第27期】如何在VB6中使用Shell函数实现同步执行
  • USB通信协议基础概念
  • ROADM（可重构光分插复用器）-介绍
  • YOLOv5： 从0开始搭建环境进行模型训练
  • 传统CV算法——基于Opencv的多目标追踪算法
  • 【盖世汽车-注册安全分析报告】
  • 亿发：中小型制造企业数字化转型典型场景、痛点、解决方案
  • 2024 数学建模高教社杯 国赛（A题）| “板凳龙”舞龙队 | 建模秘籍文章代码思路大全
  • 理解Sigmoid激活函数原理和实现
  • Java程序员幽默爆笑锦集
  • python_bomb----数据类型总结
  • vue自定义指令实现v-tap插件
  • 从0实现一个tiny react（三）生命周期
  • 警报：线上事故之CountDownLatch的威力
  • 看域名解析域名安全对SEO的影响
  • 前端js -- this指向总结。
  • 前端之React实战：创建跨平台的项目架构
  • 深入浏览器事件循环的本质
  • 腾讯优测优分享 | Android碎片化问题小结——关于闪光灯的那些事儿
  • 一份游戏开发学习路线
  • PostgreSQL之连接数修改
  • 微龛半导体获数千万Pre-A轮融资，投资方为国中创投 ...
  • ​​​​​​​​​​​​​​汽车网络信息安全分析方法论
  • ​​​​​​​sokit v1.3抓手机应用socket数据包： Socket是传输控制层协议，WebSocket是应用层协议。
  • ​补​充​经​纬​恒​润​一​面​
  • ​香农与信息论三大定律
  • ​一、什么是射频识别?二、射频识别系统组成及工作原理三、射频识别系统分类四、RFID与物联网​
  • ​一些不规范的GTID使用场景
  • ​字​节​一​面​
  • # 飞书APP集成平台-数字化落地
  • ######## golang各章节终篇索引 ########
  • #微信小程序：微信小程序常见的配置传旨
  • （145）光线追踪距离场柔和阴影
  • （2024.6.23）最新版MAVEN的安装和配置教程（超详细）
  • (8)Linux使用C语言读取proc/stat等cpu使用数据
  • (Matlab)基于蝙蝠算法实现电力系统经济调度
  • （仿QQ聊天消息列表加载）wp7 listbox 列表项逐一加载的一种实现方式，以及加入渐显动画...
  • （附源码）c#+winform实现远程开机（广域网可用）
  • （考研湖科大教书匠计算机网络）第一章概述-第五节1：计算机网络体系结构之分层思想和举例
  • （十）c52学习之旅-定时器实验
  • (使用vite搭建vue3项目（vite + vue3 + vue router + pinia + element plus）)
  • (四)js前端开发中设计模式之工厂方法模式
  • (新)网络工程师考点串讲与真题详解
  • （最简单，详细，直接上手）uniapp/vue中英文多语言切换
  • ****** 二十三 ******、软设笔记【数据库】-数据操作-常用关系操作、关系运算
  • ./configure,make,make install的作用(转)
  • .Net mvc总结
  • .NET Standard、.NET Framework 、.NET Core三者的关系与区别？
  • .net wcf memory gates checking failed