网页设计制作报价表_app是干什么用的_今日头条号官网_百度seo培训班

---

前言

今天我们一起来看看C++中stl库里list是什么样子的，以及模拟实现list~

---

一、list 的用法

1. list 简介

第一个参数是模板类型，第二个参数是空间配置器我们先暂时不管他。

list的在stl中就是一个双向带头循环链表，它的使用比vector简单一些。

stl这些风格接口都是一样的，他的构造也是这样。

因为list是链式结构，因此他的访问和遍历不会用到operator[]，而是通过迭代器来遍历，对于插入删除操作除了push_back,insert等等这些,还提供了头插头删这样的接口，因为他们不用进行数据的挪动。

---

2. 用法代码演示

1）头/尾 插/删和迭代器遍历

#include<list>int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_front(30);lt.push_front(88);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_back();for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_front();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;return 0;
}

---

2）insert与erase

首先，list的底层空间不是连续的，不能直接通过偏移量访问指定位置（如lt.begin() + 5会报错）。其次，insert操作不会导致迭代器失效，因为list的插入操作不需要扩容，插入后迭代器仍指向有效的逻辑位置。相反，erase操作会导致迭代器失效，删除后需要用返回值更新迭代器以避免野指针。最后，在删除元素时（如删除偶数），应通过erase返回的迭代器更新循环变量，确保迭代器有效。

void test02()
{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;//list的空间不是连续的，+5 并不能找到list中第5个位置，这样写编译器会报错的//lt.insert(lt.begin() + 5, 10);list<int>::iterator it = lt.begin();while (it != lt.end()){it++;}lt.insert(it, 89);for (auto e : lt){cout << e << " ";}cout << endl;//对于insert，迭代器不会失效，因为插入数据list不牵扯扩容，it所指向的逻辑位置也不发生改变//库里的没找到会返回last的位置it = find(lt.begin(), lt.end(), 3);if (it != lt.end()){lt.insert(it, 30);// insert以后，it不失效*it *= 100;}for (auto e : lt){cout << e << " ";}cout << endl;//但是对于erase，使用过后迭代器会失效it = find(lt.begin(), lt.end(), 2);if (it != lt.end()){lt.erase(it);// erase以后，it失效，她的空间已经没了，就是一个野指针//*it *= 100;}for (auto e : lt){cout << e << " ";}cout << endl;//要解决这个问题，可以拿iterator做返回值接收，更新it的值it = lt.begin();//还是我们的老朋友，删除list中偶数while (it != lt.end()){if (*it % 2 == 0){//就是这里it = lt.erase(it);}elseit++;}for (auto e : lt){cout << e << " ";}cout << endl;
}

---

3）排序sort相关

由于list的迭代器是双向的，不能直接用标准库的sort（因为那是针对随机访问迭代器设计的快排），所以list自带了sort方法，它内部用的是归并排序。接着，代码还演示了两种反转方式：你可以用标准库的reverse函数，也可以直接用list的reverse方法。二者效果相同。

void test03()
{list<int> lt;lt.push_back(5);lt.push_back(4);lt.push_back(3);lt.push_back(2);lt.push_back(1);//库中的sort不可以，因为库中的排序是快排，迭代器的种类是随机，而这里迭代器的种类是双向//sort(lt.begin(), lt.end());//因此库中提供了一种底层为归并排序的排序lt.sort();for (auto e : lt){cout << e << " ";}cout << endl;//list中还有类似逆置，交换这样的，库中和这里的都可以用reverse(lt.begin(), lt.end());for (auto e : lt){cout << e << " ";}cout << endl;lt.reverse();for (auto e : lt){cout << e << " ";}cout << endl;
}

当然，list中的排序我们是不建议用的，要对list中的数据进行排序，我们应该将其转化成vector，然后调用快排，最后在拷贝回去。

下面这是一段性能测试的代码：
可以看到，越大数据下快排性能越好

void test_op()
{srand(time(0));const int N = 100000;vector<int> v;v.reserve(N);list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand();lt2.push_back(e);lt1.push_back(e);}// 拷贝到vector排序，排完以后再拷贝回来int begin1 = clock();// 先拷贝到vectorfor (auto e : lt1){v.push_back(e);}// 排序sort(v.begin(), v.end());// 拷贝回去size_t i = 0;for (auto& e : lt1){e = v[i++];}int end1 = clock();int begin2 = clock();lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

---

4）其他相关

第一是remove，它用来删除链表中指定的值，找到了就删，找不到就不做任何操作。这个操作比较简单直接。

第二个是unique，它用来去除链表中的重复元素，但通常需要先排序，这样可以确保去重更高效。unique只会保留相邻元素中的一个，所以排序是去重前的重要一步。

第三个是splice，它用来将一段结点转移到另一个结点的后面。splice有几种用法，可以转移整个list、单个元素或一段区间的元素。splice不会创建新元素，而是直接在链表节点间重新链接，效率很高。

void test04()
{int myints[] = { 17,89,7,14 };/*std::list<int> mylist(myints, myints + 4);//remove是删除特定的值，找到了就删除，没找到就什么也不干mylist.remove(890);for (auto e : mylist){cout << e << " ";}cout << endl*/;//unique是去重，一般要先排序，这要去重效率高//mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77, 15.3,  72.25, 72.25, 73.0,  73.35//mylist.unique();           //  2.72,  3.14, 12.15, 12.77 15.3,  72.25, 73.0,  73.35std::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 30for (auto e : mylist1){cout << e << " ";}cout << endl;for (auto e : mylist2){cout << e << " ";}cout << endl << endl;it = mylist1.begin();++it;                         // points to 2//转移是从iterator的位置，转移另一个list （整个/第i个位置/一个迭代区间）// 全部转移mylist1.splice(it, mylist2);// 部分转移//mylist1.splice(it, mylist2, ++mylist2.begin());//mylist1.splice(it, mylist2, ++mylist2.begin(), mylist2.end());//转移自己//mylist1.splice(mylist1.begin(), mylist1, ++mylist1.begin(), mylist1.end());for (auto e : mylist1){cout << e << " ";}cout << endl;for (auto e : mylist2){cout << e << " ";}cout << endl;
}

二、list模拟实现

1. 结点类模板list_node

首先，要写出一个list，就需要先写出它的每一个结点的构成，这里的结构是我们之前学过的双向链表，为了泛用性，list的结点数据可以是任意类型的数据，因此我们需要写成类模板。

与双向链表一样，我们这里有三个变量分别是_next（后继）, _prev（前驱）, val（值），
并利用初始化模板将其初始化

template<class T>
struct list_node
{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}
};

---

2. 定义迭代器

1）为什么要专门封装一个迭代器？

list不想string和vector，它们两个的底层是由数组实现的，它们的迭代器就是其原生指针，因为原生指针就可以满足迭代器的行为。

迭代器所需要做到的行为如下：
*：解引用获取迭代器对应的值，类似与指针解引用获得值
!=：如：判断迭代器到没到end（）等应用
++/--：迭代器迭代到下一个地点

对于vector来说，他的迭代器可以完美符合以上几点，因为vector底层空间是连续的，是数组，就像这样：

但是，对于list还能这样吗？
答案是不能，因为list底层不是连续的，*it并不是对应的值，而是一个结点,++it并不能让it指向下一个结点，因为空间是不连续的，++后指到哪里谁也不知道。

因此现有的迭代器的行为不符合我们的预期，我们期望的是迭代器表层使用的方式是一致的，因此我们写一个类，封装迭代器,用运算符重载来改变迭代器的行为，使他符合我们的预期。

---

2）迭代器类的实现

（1）普通迭代器

初始化

Node* _node;
__list_iterator(Node* node):_node(node)
{}

---

operator*与operator->

我们先不关心它的返回值，我们先来让他符合我们的预期。

我们想让*返回的不是它的结点，而是结点中的值。
我们想让->返回的是T类型值（结构体）的地址。
注意：

Ref operator* ()
{return _node->_val;
}Ptr operator-> ()
{return &_node->_val;
}

---

operator++

我们想让operator++能到下一个结点的位置，--同理，因此需要让_node = _node->next，而不是指针地址的++,因为结点与结点之间空间是不连续的。

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

---

operator!=

我们想让迭代器的对应的结点与结点比较，而不是迭代器本身。

bool operator!= (const self& it)
{return _node != it._node;
}bool operator== (const self& it)
{return _node == it._node;
}

---

（2）const迭代器——参数T以及为什么有三个参数？

在学习list迭代器的封装时，我们发现了一个很神奇的现象，就是迭代器的模板参数居然有3个！！！

这是为什么呢？

有T在这个地方我们都能理解，因为迭代器的类型就是T，也就是我们list的类型，那为什么还要这个Ref和Ptr呢？

其实原因都是const迭代器搞的鬼。

我们在实现const的版本的时候，遇到一些非常坑的问题。

首先，这样设计const迭代器可以吗？
// typedef const __list_iterator<T> const_iterator;
答案是不可以，因为这样设计const迭代器是不行的，因为const迭代器期望指向内容不能修改
这样设计是迭代器本身不能修改，我们迭代器本身是要++的，不能改变的是它的值。

第二个问题，我们发现，const迭代器与普通迭代器的不同仅仅是因为迭代器所指向的值不能修改，那const迭代器不就是重载operator*的时候加一个const吗？
//typedef __list_const_iterator const_iterator;
但是问题是，这样设计太冗余了，有大量重复的代码，改变的仅仅是operator*前加const以及函数名字。

因此我们的解决方法是：增加一个模板参数Ref，它的作用是typedef定义const_iterator的时候，传得参数有一个是const与普通迭代器不一样，而operator*的返回值就使用Ref.
而Ref就是T的引用，与返回值保持一致.

像这样：

---

那么，第三个参数Ptr是什么呢？

类似于operator*，在对自定义类型解引用的方式还有->。

比如我们下面有一个类：

class A
{
public:A(int a = 0, int b = 0): _a(a), _b(b){}int _a;int _b;
};

我们想对这个类用迭代器遍历它的值有两种方式：

1. 通过重载的operator*解引用，然后.出A类的_a和_b.
2. 通过operator->直接访问到_a和_b.

而对于const对象，我们就不能直接调用operator->，因为会造成权限放大，所以我们引入了第三个模板参数Ptr表示T类型的指针，用它来区别const对象和普通对象。
因此operator->的返回值就成了Ptr。

实际上，传不同的模板参数，就是生成了不同的模板，我们这样写其实就是让编译器帮我们写了之前那个冗余的写法，是我们代码更简洁，可读性更高~

---

（3）迭代器代码实现

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){return _node != it._node;}bool operator== (const self& it){return _node == it._node;}};

---

3. list类实现

1）成员变量

对于每一个链表，我们需要直到它的哨兵位，还有它的大小。

private:Node* _head;size_t _size;

---

2）迭代器接口相关

前面我们定义了迭代器类，现在我们要用它获取begin()与end()。

对于带头双向循环链表来说，begin()是第一个位置的元素，也就是哨兵位的下一个，end()是最后一个元素的下一个位置，也就是又回到了哨兵位。

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin()
{//这里做了隐式类型转换return _head->_next;//也可以写成这样//return iterator(head->_next);
}iterator end()
{//这里做了隐式类型转换return _head;//也可以写成这样//return iterator(head);
}const const_iterator begin() const
{return _head->_next;
}const const_iterator end() const
{return _head;
}

---

3）构造相关

构造函数：

void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}list()
{empty_init();
}

拷贝构造：
这里依然沿用vector那里拷贝构造的思想，复用push_back来做到深拷贝。

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);
}T& operator=(list<T> lt)
{swap(lt);return *this;
}

析构函数
复用clear，再把头结点清理掉。

对于clear来说，vector的空间要释放必须完全释放，所以它只清理值，不回收空间，而list结点之间不连续，因此可以直接回收空间，当然，哨兵位是不动的。

~list()
{clear();delete _head;_head = nullptr;
}void clear()
{iterator it = begin();while (it != end()){it = erase(it);}_size = 0;
}

---

4）插入删除相关

（1）insert与erase及其迭代器失效问题

insert任意位置插入
逻辑完全就是双链表的逻辑，先开辟出新结点空间，在改变对应的指向。

insert无法对pos进行断言，哪里插入都可以。

iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;return newnode;
}

因为list空间是不连续的，因此这里也不用扩容，对于insert来说，迭代器不失效。

---

erase删除任意位置的数据

erase需要对pos位置进行断言，pos不能改变我们的头结点，而end()就是头结点。

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;--_size;return next;
}

因为删除了这一个结点，而迭代器又指向这个结点空间，因此erase后迭代器会失效，是铁铁的野指针！

---

（2）头插/头删/尾插/尾删

逻辑与vector一样，直接复用insert与erase就好。

void push_back(const T& x)
{/*Node* newnode = new Node(x);newnode->_next = head;newnode->_prev = head->_prev;head->_prev->_next = newnode;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());
}

---

三、list与vector对比

下面是 vector 和 list 的对比表格，涵盖了它们的主要特性和性能：

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

总结

• vector 更适合需要频繁随机访问和对存储效率要求较高的场景，但在插入和删除时性能较低。
• list 更适合需要频繁插入和删除操作的场景，尤其是在中间位置进行操作时效率高，但不支持随机访问。

---

模拟实现list完整代码

#pragma once
#include<assert.h>
#include<iostream>
using namespace std;namespace jyf
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_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){return _node != it._node;}bool operator== (const self& it){return _node == it._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;iterator begin(){//这里做了隐式类型转换return _head->_next;//也可以写成这样//return iterator(head->_next);}iterator end(){//这里做了隐式类型转换return _head;//也可以写成这样//return iterator(head);}const const_iterator begin() const{return _head->_next;}const const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}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);}T& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}void push_back(const T& x){/*Node* newnode = new Node(x);newnode->_next = head;newnode->_prev = head->_prev;head->_prev->_next = newnode;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());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;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;--_size;return next;}size_t size(){return _size;}private:Node* _head;size_t _size;};void Print(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){// (*it) += 1;cout << *it << " ";++it;}cout << endl;}void test_list01(){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()){cout << *it << " ";++it;}cout << endl;for (auto& e : lt){cout << e << " ";}cout << endl;}class A{public:A(int a = 0, int b = 0): _a(a), _b(b){}int _a;int _b;};void test_list02(){list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));list<A>::iterator it = lt.begin();while (it != lt.end()){cout << (*it)._a << " " << (*it)._b << endl;++it;}cout << endl;it = lt.begin();while (it != lt.end()){cout << it->_a << " " << it->_b << endl;++it;}cout << endl;}void test_list03(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);lt.push_front(7);lt.push_front(8);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_front();lt.pop_back();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);for (auto e : lt){cout << e << " ";}cout << endl;cout << lt.size() << endl;}void test_list04(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;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);for (auto e : lt2){cout << e << " ";}cout << endl;lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;}
}

到这里模拟实现list就结束啦~

谢谢大家！