【STL深入浅出】list探秘与实战

2024-06-04 07:44
文章标签 stl list 探秘 深入浅出 实战

本文主要是介绍【STL深入浅出】list探秘与实战，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

📃博客主页： 小镇敲码人
💚代码仓库，欢迎访问
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏
🌏 任尔江湖满血骨，我自踏雪寻梅香。 万千浮云遮碧月，独傲天下百坚强。 男儿应有龙腾志，盖世一意转洪荒。 莫使此生无痕度，终归人间一捧黄。🍎🍎🍎
❤️ 什么？你问我答案，少年你看，下一个十年又来了 💞 💞 💞

【STL深入浅出】list探秘与实战

  • 🌆 list容器简单介绍
  • 🌆 list的容器部分方法的使用介绍
    • ❇️ list对象的构造以及访问
    • ❇️ 头插和头删
    • ❇️ 尾插和尾删
    • ❇️ 反向迭代器访问元素
    • ❇️ list的插入和删除
    • ❇️ list的迭代器失效问题
    • ❇️ clear函数和size函数
    • ❇️ 其它的操作
  • 🌆 list容器的模拟实现
    • ❇️ list容器的成员变量
    • ❇️ list容器中的迭代器模拟实现
      • ✴️ 普通的迭代器和const迭代器
      • ✴️ 反向迭代器的实现
    • ❇️ list容器方法的模拟实现
      • ✴️ list类中的类型
      • ✴️ list的构造函数
      • ✴️ 迭代器的方法函数
      • ✴️ 尾插和尾删
      • ✴️ 头插和头删
      • ✴️ 插入和删除
      • ✴️ clear和size以及析构函数
      • ✴️ 赋值运算符重载函数
      • ✴️ 交换函数
  • 🌆 list方法的测试
    • ❇️ 测试构造函数
    • ❇️ 测试头插和头删
    • ❇️ 测试尾插和尾删
    • ❇️ 反向迭代器测试
    • ❇️ 插入和删除函数测试
    • ❇️ clear和size函数测试
    • ❇️ swap函数测试
    • ❇️ list排序效率测试

🌆 list容器简单介绍

list容器的底层是带头双向循环链表，和前面两个物理空间连续的容器string、vector不同的是，list容器的物理空间不再连续，在实现迭代器的时候就要更加麻烦了，并且这次我们还将模拟实现反向迭代器。

和其他容器相比list容器的优势在于，插入、删除很方便，不需要挪动数据。

但是也有劣势，就是list容器不支持[]随机访问，只能通过迭代器来一个个的遍历访问。
C++11中还增加了forward_list容器，forward_list容器和list容器的区别在于forward_list容器的底层是单链表。

🌆 list的容器部分方法的使用介绍

❇️ list对象的构造以及访问

在这里插入图片描述
c++98提供了以上四种构造函数，alloc是内存池，我们现在可以不用管。

构造以及访问演示：

#include<iostream>
#include<list>using namespace std;void Test1()//测试构造函数
{list<int> list1;//空的构造list<int> list2(4, -1);//3个元素每个元素为-1list<int> list3(list2.begin(), list2.end());//迭代器区间构造list<int> list4(list2);//拷贝构造//普通迭代器访问list2list<int>::iterator it = list2.begin();while (it != list2.end()){cout << *it << " ";it++;}cout << endl;//也可以使用范围for来访问for (auto& i : list3){cout << i << " ";}cout << endl;//也可以使用范围for来访问for (auto& i : list4){cout << i << " ";}cout << endl;
}int main()
{Test1();return 0;
}

运行结果：

在这里插入图片描述

这里重新理解一下迭代器：

1.具有像指针一样的行为，通过运算符重载来实现，有*,++,--等行为。
2. 是一个类型，可能直接就是原生指针类型的typedef，也可能是自己自定义的类型。因为原生指针无法满足我们访问的需求，原生指针++的地址是紧接着的下一个地址，但是不是所有的容器物理空间都是连续存储的，迭代器++的意义在于访问元素，如果你++之后没有指向下一个元素的地址，就无法满足我们的要求，我们需要自定义一个类型，以此在自己实现++操作，经过这个操作之后，我们的迭代器将指向下一个元素的地址。至于细节我们稍后便会模拟实现。

❇️ 头插和头删

在这里插入图片描述
在这里插入图片描述

和vector容器不同的是，list容器还单独实现了头插和头删，可能是这两个操作在链表这个数据结构里用的比较多，使用起来很简单：

#include<iostream>
#include<list>using namespace std;void Test2()//头插和头删
{list<int> list1;for (int i = 0; i < 10; ++i)list1.push_front(i);//依次头插cout << "list1: ";for (auto& i : list1){cout << i << " ";}cout << endl;list1.pop_front();//头删list1.pop_front();//头删cout << "list1: ";for (auto& i : list1){cout << i << " ";}cout << endl;
}int main()
{Test2();return 0;
}

运行结果：

在这里插入图片描述

❇️ 尾插和尾删

除了头插和头删，list的容器也实现尾插和尾删的方法。

在这里插入图片描述
在这里插入图片描述
代码演示：

#include<iostream>
#include<list>using namespace std;void Test3()//尾插和尾删
{list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);//依次尾插cout << "list1: ";for (auto& i : list1){cout << i << " ";}cout << endl;list1.pop_back();//尾删list1.pop_back();//尾删cout << "list1: ";for (auto& i : list1){cout << i << " ";}cout << endl;
}int main()
{Test3();return 0;
}

运行结果：

在这里插入图片描述

❇️ 反向迭代器访问元素

反向迭代器和它的名字一样，是反着来访问元素的，我们来看具体的例子：

#include<iostream>
#include<list>using namespace std;void Test4()//反向迭代器
{list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);//依次尾插元素进入list1容器中//先正向迭代器正常访问list<int>::iterator it1 = list1.begin();//调用正向迭代器的begin函数，得到访问的开始迭代器cout << "list1: ";while (it1 != list1.end()){cout << *it1 << " ";it1++;}cout << endl;//反向迭代器访问list<int>::reverse_iterator it2 = list1.rbegin();//调用反向迭代器的rbegin函数，得到访问的开始迭代器cout << "list1 r: ";while (it2 != list1.rend()){cout << *it2 << " ";it2++;}cout << endl;}
int main()
{Test4();return 0;
}

运行结果：

在这里插入图片描述
反向迭代器和普通迭代器的类型是不同的，所以它们的起始迭代器的类型也不同，注意不要访问错了，否则类型不同会报错的。

❇️ list的插入和删除

在这里插入图片描述
在这里插入图片描述

接口和前面的顺序容器基本没有区别，我们只演示最简单的接口：

演示代码：

#include<iostream>
#include<list>using namespace std;void Test5()//insert and erase display
{list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);//依次尾插元素进入list1容器中my_list::print_list(list1);//打印list1.insert(list1.begin(),1000);//头插一个1000my_list::print_list(list1);//打印list1.insert(list1.end(), 1000);//尾插一个1000my_list::print_list(list1);//打印auto it = std::find(list1.begin(), list1.end(), 8);//在list1对象中找一个值为8的元素，并返回它的迭代器if (it != list1.end())list1.erase(it);//删除元素8my_list::print_list(list1);//打印it = std::find(list1.begin(), list1.end(), 10);//在list1对象中找一个值为10的元素，并返回它的迭代器if(it != list1.end())list1.erase(it);//删除元素10my_list::print_list(list1);//打印//头插一个999，再尾插一个999，看find函数会返回谁的迭代器list1.push_front(999);list1.push_back(999);my_list::print_list(list1);//打印it = std::find(list1.begin(), list1.end(), 999);//在list1对象中找一个值为10的元素，并返回它的迭代器if (it != list1.end())list1.erase(it);//删除元素10my_list::print_list(list1);//打印}
int main()
{Test5();return 0;
}

运行结果：

在这里插入图片描述

因为打印链表这个代码会重复很多，所以我们在我们自己的命名空间里面实现了一个打印函数模板，如果想打印链表，直接调用这个函数就可以了：

在这里插入图片描述

另外我们还用到了find函数来找某个元素的位置，如果这个元素不存在，find函数会返回last迭代器，也就是我们传的区间的末尾，如果这个元素存在，就返回第一次找到的迭代器。

在这里插入图片描述

在这里插入图片描述

❇️ list的迭代器失效问题

和string、vector容器一样list容器也有迭代器失效的问题，我们具体来看它们是否有所不同。

list的迭代器失效在插入的时候不会出现，因为插入时，迭代器it的节点指针不受影响，插入只会新增节点，不会对原先节点的地址产生任何影响。
所以迭代器失效只会出现在删除的时候，因为删除后，这个迭代器内部节点指针被释放了，一般是为空，这个时候你对它使用任何操作都是非法的。

下面是具体迭代器失效的例子：

#include<iostream>
#include<list>using namespace std;void Test6()//删除导致list迭代器失效
{list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);my_list::print_list(list1); auto it = list1.begin();while (it != list1.end()){list1.erase(it);it++;//错误，此时it迭代器内部的节点已经被释放，相当于it已经失效}my_list::print_list(list1);
}
int main()
{Test6();return 0;
}

运行结果：

在这里插入图片描述

改进办法就是在这个迭代器失效之前，就更新即可：

#include<iostream>
#include<list>using namespace std;void Test6()//删除导致list迭代器失效
{list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);my_list::print_list(list1); auto it = list1.begin();while (it != list1.end()){list1.erase(it++);//后置++，it++的返回值是it,但是自己的值已经改变了，erase传进去的是operator++的返回值,}my_list::print_list(list1);
}
int main()
{Test6();return 0;
}

运行结果：

在这里插入图片描述

程序正常运行，迭代器失效的问题已经解决。

❇️ clear函数和size函数

clear函数会把除头节点外的所有节点都pop掉
代码演示：

#include<iostream>
#include<list>using namespace std;void Test7()//clear函数，size
{list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);cout << list1.size() << endl;list1.clear();cout << list1.size() << endl;
}
int main()
{Test7();return 0;
}

运行结果：

在这里插入图片描述
在这里插入图片描述

❇️ 其它的操作

链表还有一些其它的操作，像排序链表（sort）、去重（unique),逆序（把链表中元素的存储位置反过来）不是较为常用，我们不再介绍，如果有兴趣，自行查阅文档

在这里插入图片描述

🌆 list容器的模拟实现

❇️ list容器的成员变量

通过看源码，我们发现，list容器中就只有一个节点指针类型的变量。
在这里插入图片描述
link_type是一个指针类型：
在这里插入图片描述

下面是_list_node的定义:
它是一个模板类：

在这里插入图片描述

这里节点类型里面next和pre使用的是void *万能指针我们不用管，我们使用正常类型就行。

我们自己实现的list_node：

   template<class T>struct List_node{struct List_node<T>* pre_;struct List_node<T>* next_;T val_;List_node(const T& x = T()):val_(x),pre_(nullptr),next_(nullptr)//构造函数{}};

❇️ list容器中的迭代器模拟实现

迭代器我们实现了三个，但准确来讲只有两个。

在这里插入图片描述
c++中struct可以不要。名称<模板参数>就代表类型。

✴️ 普通的迭代器和const迭代器

前面已经阐述了迭代器的基本概念，下面我们来看下一下，普通迭代器的模拟实现，首先我们要先明确这个迭代器需要什么成员变量，要一个节点指针就够我们完成所有操作了，其次我们的迭代器还应该设计为模板类型的，因为节点的指针是一个模板类型。

然后我们需要考虑，我们的普通迭代器和const迭代器的区别是什么，不就在解引用和->（对于list中保存的是结构体成员来说）吗，因为如果解引用返回的是一个const类型的值，它就不可修改呀，解引用返回的是值的引用，而operator ->重载函数返回的是那个值的地址。我们给这两个返回值弄成模板的形式不就行了吗？const迭代器就传const 引用，这样避免了代码的冗余。

迭代器不需要析构函数，因为节点的空间不是我们开的，我们不需要负责释放。

代码实现：

	template<class T, class Ref, class Ptr>struct list_iterator{typedef List_node<T> Link_type;//给模板节点类型起别名typedef list_iterator<T, Ref, Ptr> self;//给这个比较长的类型起别名，等会要做返回值使用typedef list_iterator<T, T&, T*>             iterator;typedef Ref Ref;//把这个模板类型变成我们类里面的类型，之后反向迭代器要使用typedef Ptr Ptr;//把这个模板类型变成我们类里面的类型，之后反向迭代器要使用list_iterator() {};//空的构造函数list_iterator(Link_type* x) :node(x)//用节点指针构造的构造函数{}list_iterator(const iterator& x) : node(x.node)//拷贝构造函数{}Ref operator*() const//返回这个值的引用{return node->val_;}Ptr operator->() const//返回这个节点指针，让迭代器可以使用箭头访问这个节点的值（主要用于list保存的结构体类型的情况）{return &node->val_;}self operator++(int)//后置++{self tmp(node);node = node->next_;return tmp;}self& operator++()//前置++{node = node->next_;return *this;}self operator--()//前置--{node = node->pre_;return *this;}self operator--(int)//后置--{self tmp(node);//先构造现在的迭代器node = node->pre_;//再更新当前迭代器的nodereturn tmp;//返回的是没--前的迭代器}bool operator!=(const self& x) const //判断迭代器是否相等，看他们保存的节点指针是否一样即可{return node != x.node;}bool operator==(const self& x) const{return node == x.node;}Link_type* node;};

迭代器这个类型的目的就在于模拟指针的行为，所以运算符重载是它的核心语法。

注释已经说的很清楚了，我们对一些核心部分做一下阐述：

  1. 前置++（-- ）和后置++（- -），我们之前已经阐述过，这里代码的实现部分，相信不难理解，++需要迭代器保存这个节点的下一个节点的指针，直接把next_赋值给它即可，但是要注意，后置++的返回值还是原先那个迭代器，没有发生改变。

  2. 迭代器比较部分的实现逻辑是比较这些迭代器保存的节点指针是否相等，不能直接比较迭代器是否一样，这样会导致无限递归下去，也不能比较迭代器的地址，因为迭代器的地址是不同的，两个不同的迭代器变量，它们的内存地址可能不同，但是保存的节点指针可能相同。

  3. 迭代器构造部分，直接把节点指针赋值给当前迭代器的节点指针变量即可。

  4. Ref是引用类型的模板参数，Ptr是指针类型的模板参数，Ref做operator*函数的返回值（节点指针值的引用），Ptr做operator->函数的返回值（节点返回值的地址）。

const迭代器和普通迭代器我们只需要在模板传参上传不同的类型，就可以利用这一个迭代器代码，实现两个出来。

✴️ 反向迭代器的实现

我们可以思考一下反向迭代器和正向普通的迭代器的区别和共同点：

  1. 共同点：都是迭代器，利用运算符重载函数模仿指针的行为，以完成容器的遍历。
  2. 区别：反向迭代器是反着来遍历的，它的++和正向迭代器的--一样，它的--和正向迭代器的++一样。

所以其实区别很小，我们可以利用模板传正向迭代器的类型给反向迭代器，然后创建一个正向迭代器的类型作为它的成员变量，通过这个正向迭代器的操作来实现反向迭代器的一系列操作，这样我们的反向迭代器就是一个类模板，它不仅适用于list的反向迭代器实现，也适用于其它容器的反向迭代器的实现。

typename的作用是告诉编译器我们起别名的是一个类型而不是静态变量，因为在类里面，静态变量也是这样来访问的。


namespace my_reverse_iterator
{template<class Iterator>struct reverse_iterator{typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef typename reverse_iterator<Iterator> Self;reverse_iterator() {};//空的构造reverse_iterator(Iterator it) : it1(it)//用Iterator构造{}Ref operator*() const//解引用操作，去调用it1的解引用{return *it1;}Ptr operator->() const//->操作，去调用it1的operator->操作{return &(*it1);}Self& operator--()//前置-- 前置--，去调用it1的前置或者后置++均可{++it1;return *this;}Self operator--(int)//后置-- 后置--，去调用it1的前置或者后置++均可，要提前保存没有++的it1，然后返回{Self tmp(it1);++it1;return tmp;}Self& operator++()//前置++ 和前置--类似{--it1;return *this;}Self& operator++(int)//后置++ 和后置--类似{Self tmp(it1);--it1;return tmp;}bool operator!=(const Self& x)//调用it1 的!= 操作{return it1 != x.it1;}bool operator==(const Self& x)//调用it1 的 == 操作{return it1 == x.it1;}private:Iterator it1;//创建Iterator类型的it1对象，复用这个类型的操作};
}

我们上面的代码相当于是一个复用，像一个模具一样，适用于所有的容器的反向迭代器，复用的是这个容器的迭代器操作，因为每个容器的迭代器的操作是不同的，所以我们要写成类模板的形式。

❇️ list容器方法的模拟实现

完整的代码：

template<class T>class list{public:typedef struct List_node<T> list_type;//给类模板起别名，因为后面我们用的比较多，这个类模板的类型名字太长了typedef struct list_iterator<T,T&,T*> iterator;//普通给迭代器类型起别名typedef struct list_iterator<T,const T&,const T*> const_iterator;//给const迭代器类型起别名typedef struct my_reverse_iterator::reverse_iterator<iterator> reverse_iterator;//给反向迭代器类型起别名void Init_empty()//初始化list的容器，因为list的底层是带头的，所以就算是空构造也要给这个对象创建一个头节点{Head_ = new list_type;//开空间//初始化Head_->val_ = T();Head_->pre_ = Head_;Head_->next_ = Head_;}list()//空的构造{Init_empty();}list(const list& x)//拷贝构造{Init_empty();for (auto i: x)//复用尾插和迭代器{push_back(i);}}list(size_t n, const T& val = T())//普通构造{Init_empty();//初始化头节点for (int i = 0; i < n; ++i)//尾插数据push_back(val);}list(int n, const T& val = T())//普通构造{Init_empty();for (int i = 0; i < n; ++i)push_back(val);}template <class InputIterator>list(InputIterator first, InputIterator last)//迭代器区间构造{Init_empty();//初始化头节点while (first != last)//迭代器遍历并初始化{push_back(*first);first++;}}list<T>& operator=(const list<T>& x)//赋值运算符重载{list<T> tmp(x);//复用拷贝构造std::swap(tmp.Head_,Head_);//交换它们的Head_节点return *this;}iterator begin()//普通迭代器的开始访问函数，从头节点的下一个节点开始访问{return Head_->next_;}iterator end()//普通迭代器的结束访问函数，访问到头节点就不能访问了，因为是双向循环链表{return Head_;}const_iterator begin() const{return Head_->next_;}const_iterator end() const{return Head_;}reverse_iterator rbegin()//反向迭代器的开始访问函数，从普通迭代器的end()前面的那个节点开始访问。{return --end();}reverse_iterator rend()//和end()一样{return end();}void push_back(const T& val)//尾插{list_type* newnode = new list_type(val);//创建新的节点list_type* tail = Head_->pre_;//保存尾节点newnode->pre_ = tail;//先把新节点的前驱节点指向尾节点newnode->next_ = Head_;//再把新节点的后继节点指向头节点Head_->pre_ = newnode;//更新头节点的前驱节点tail->next_ = newnode;//更新尾节点的后继节点}void pop_back()//尾删{assert(Head_->next_ != Head_);//检查list中是否还有数据list_type* tail = Head_->pre_;//先保存尾节点tail->pre_->next_ = Head_;//把尾节点的前驱节点的后继节点指向head_Head_->pre_ = tail->pre_;//再把头节点的前驱节点指向尾节点的前驱节点delete tail;//释放当前尾节点的空间}void push_front(const T& val)//头插{list_type* newnode = new list_type(val);//创建新的节点newnode->next_ = Head_->next_;//新节点的next先指向头节点的nextnewnode->pre_ = Head_;//新节点的前驱节点指向Head_Head_->next_ = newnode;//头节点的后继节点指向新节点}void pop_front()//头删{assert(Head_->next_ != Head_);//如果只剩下头节点，就不能继续删除了list_type* node = Head_->next_;//先保存要删除的节点，防止重新链接之后找不到，造成内存泄漏Head_->next_ = node->next_;//先把头节点的后继节点指向待删除节点的后继节点node->next_ ->pre_ = Head_;//再把待删除节点的后继节点的前驱节点指向头节点delete node;//释放node节点}iterator insert(iterator position, const T& val)//在position迭代器指向的地址之前，插入元素val{list_type* newnode = new list_type(val);//创建新的节点list_type* pre = position.node->pre_;//链接起来pre->next_ = newnode;newnode->pre_ = pre;newnode->next_ = position.node;position.node->pre_ = newnode;return --position;//返回第一个新插入元素的迭代器}iterator erase(iterator position){assert(position.node != Head_);//检查是否还有节点list_type* pre = position.node->pre_;//保存前驱节点//链接pre->next_ = position.node->next_;position.node->next_->pre_ = pre;//删除delete position.node;//返回被删除的最后一个位置的下一个元素的迭代器return iterator(pre->next_);}size_t size() const{list_type* cur = Head_->next_;//保存头节点的后继节点size_t size = 0;//保存节点的个数while (cur != Head_){cur = cur->next_;//继续遍历size++;}return size;}void clear() {list_type* cur = Head_->next_;//保存头节点的后继节点while (cur != Head_)//如果cur不等于Head_节点就继续{list_type* next = cur->next_;//先保存后继节点delete cur;//释放当前节点cur = next;}//不要忘记更新头节点的链接，不然就会指向野指针了Head_->next_ = Head_;Head_->pre_ = Head_;}void swap(list<T>& x){std::swap(Head_, x.Head_);}~list(){clear();//调用析构函数delete Head_;//释放头节点Head_ = nullptr;}private:list_type* Head_;};

✴️ list类中的类型

在这里插入图片描述
有一个节点类型，其余是迭代器类型，我们没有实现const的反向迭代器的rbegin、rend()函数，其实加个const即可（也不麻烦），所以迭代器类型只有3个。

✴️ list的构造函数

      void Init_empty()//初始化list的容器，因为list的底层是带头的，所以就算是空构造也要给这个对象创建一个头节点{Head_ = new list_type;//开空间//初始化Head_->val_ = T();Head_->pre_ = Head_;Head_->next_ = Head_;}list()//空的构造{Init_empty();}list(const list& x)//拷贝构造{Init_empty();for (auto i: x)//复用尾插和迭代器{push_back(i);}}list(size_t n, const T& val = T())//普通构造{Init_empty();//初始化头节点for (int i = 0; i < n; ++i)//尾插数据push_back(val);}list(int n, const T& val = T())//普通构造{Init_empty();for (int i = 0; i < n; ++i)push_back(val);}template <class InputIterator>list(InputIterator first, InputIterator last)//迭代器区间构造{Init_empty();//初始化头节点while (first != last)//迭代器遍历并初始化{push_back(*first);first++;}}

构造函数部分较为简单，主要复用了push_back的操作，和之前的string和vector容器没有太大的区别。

✴️ 迭代器的方法函数

	  iterator begin()//普通迭代器的开始访问函数，从头节点的下一个节点开始访问{return Head_->next_;}iterator end()//普通迭代器的结束访问函数，访问到头节点就不能访问了，因为是双向循环链表{return Head_;}const_iterator begin() const{return Head_->next_;}const_iterator end() const{return Head_;}reverse_iterator rbegin()//反向迭代器的开始访问函数，从普通迭代器的end()前面的那个节点开始访问。{return --end();}reverse_iterator rend()//和end()一样{return end();}

这里迭代器的类型和节点指针的类型不同，为什么能通过呢？因为编译器会去调用对应的迭代器的构造函数，相当于隐式的构造了一个临时变量出来。我们在测试迭代器的时候可以顺便来看一下是否是这样。

✴️ 尾插和尾删

      void push_back(const T& val)//尾插{list_type* newnode = new list_type(val);//创建新的节点list_type* tail = Head_->pre_;//保存尾节点newnode->pre_ = tail;//先把新节点的前驱节点指向尾节点newnode->next_ = Head_;//再把新节点的后继节点指向头节点Head_->pre_ = newnode;//更新头节点的前驱节点tail->next_ = newnode;//更新尾节点的后继节点}void pop_back()//尾删{assert(Head_->next_ != Head_);//检查list中是否还有数据list_type* tail = Head_->pre_;//先保存尾节点tail->pre_->next_ = Head_;//把尾节点的前驱节点的后继节点指向head_Head_->pre_ = tail->pre_;//再把头节点的前驱节点指向尾节点的前驱节点delete tail;//释放当前尾节点的空间}

带头双向循环链表的尾插和尾删操作和单链表的尾插、尾删操作类似，需要注意的是不要让本来要删除和指向的节点找不到了。需要删除的节点要提前保存。如果不能理解可以画出逻辑图，自己对照着看，熟练之后就不需要画了。

✴️ 头插和头删

类似的逻辑。不再重复赘述。

	void push_front(const T& val)//头插{list_type* newnode = new list_type(val);//创建新的节点newnode->next_ = Head_->next_;//新节点的next先指向头节点的nextnewnode->pre_ = Head_;//新节点的前驱节点指向Head_Head_->next_ = newnode;//头节点的后继节点指向新节点}void pop_front()//头删{assert(Head_->next_ != Head_);//如果只剩下头节点，就不能继续删除了list_type* node = Head_->next_;//先保存要删除的节点，防止重新链接之后找不到，造成内存泄漏Head_->next_ = node->next_;//先把头节点的后继节点指向待删除节点的后继节点node->next_ ->pre_ = Head_;//再把待删除节点的后继节点的前驱节点指向头节点delete node;//释放node节点}

✴️ 插入和删除

我们还需要一个支持删除任意迭代器的节点的erase函数，和插入元素到任意迭代器之前的insert函数:
实际编程中，我们可以先写这个插入和删除函数，然后上述的尾插、尾删、头插和头删就可以复用了。

       iterator insert(iterator position, const T& val)//在position迭代器指向的地址之前，插入元素val{list_type* newnode = new list_type(val);//创建新的节点list_type* pre = position.node->pre_;//链接起来pre->next_ = newnode;newnode->pre_ = pre;newnode->next_ = position.node;position.node->pre_ = newnode;return --position;//返回第一个新插入元素的迭代器}iterator erase(iterator position){assert(position.node != Head_);//检查是否还有节点list_type* pre = position.node->pre_;//保存前驱节点//链接pre->next_ = position.node->next_;position.node->next_->pre_ = pre;//删除delete position.node;//返回被删除的最后一个位置的下一个元素的迭代器return iterator(pre->next_);}

✴️ clear和size以及析构函数

clear函数会释放除头节点外的所有节点，size则是统计除头节点外的节点的数量，析构函数我们会复用clear函数：

size_t size() const{list_type* cur = Head_->next_;//保存头节点的后继节点size_t size = 0;//保存节点的个数while (cur != Head_){cur = cur->next_;//继续遍历size++;}return size;}void clear() {list_type* cur = Head_->next_;//保存头节点的后继节点while (cur != Head_)//如果cur不等于Head_节点就继续{list_type* next = cur->next_;//先保存后继节点delete cur;//释放当前节点cur = next;}//不要忘记更新头节点的链接，不然就会指向野指针了Head_->next_ = Head_;Head_->pre_ = Head_;}~list(){clear();//调用析构函数delete Head_;//释放头节点Head_ = nullptr;}

✴️ 赋值运算符重载函数

在这里插入图片描述
复用拷贝构造函数。

       list& operator= (const list& x)//赋值运算符重载{list<T> tmp(x);//复用拷贝构造std::swap(x.Head_, Head_);//交换它们的Head_节点return *this;}

✴️ 交换函数

在这里插入图片描述
在这里插入图片描述

        void swap(list<T>& x)//在类里面实现{std::swap(Head_, x.Head_);}template<class T>void swap(list<T>& x, list<T>& y)//在类外面实现{x.swap(y);}

🌆 list方法的测试

❇️ 测试构造函数

#include"list.h"void Test1()//测试构造函数
{my_list::list<int> list1;//空的构造my_list::list<int> list2(4, -1);//3个元素每个元素为-1my_list::list<int> list3(list2.begin(), list2.end());//迭代器区间构造my_list::list<int> list4(list2);//拷贝构造my_list::list<int> list5(5, -1);list5 = list2;//赋值运算符重载//普通迭代器访问list2my_list::list<int>::iterator  it = list2.begin();while (it != list2.end()){cout << *it << " ";it++;}cout << endl;//也可以使用范围for来访问for (auto& i : list3){cout << i << " ";}cout << endl;//也可以使用范围for来访问for (auto& i : list4){cout << i << " ";}cout << endl;my_list::print_list(list5);
}int main()
{Test1();return 0;
}

运行结果：

在这里插入图片描述

❇️ 测试头插和头删

#include"list.h"void Test2()//头插和头删
{my_list::list<int> list1;for (int i = 0; i < 10; ++i)list1.push_front(i);//依次头插cout << "list1: ";for (auto& i : list1){cout << i << " ";}cout << endl;list1.pop_front();//头删list1.pop_front();//头删cout << "list1: ";for (auto& i : list1){cout << i << " ";}cout << endl;
}int main()
{Test2();return 0;
}

运行结果：

在这里插入图片描述

❇️ 测试尾插和尾删

#include"list.h"void Test3()//尾插和尾删
{my_list::list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);//依次尾插cout << "list1: ";for (auto& i : list1){cout << i << " ";}cout << endl;list1.pop_back();//尾删list1.pop_back();//尾删cout << "list1: ";for (auto& i : list1){cout << i << " ";}cout << endl; 
}int main()
{Test3();return 0;
}

运行结果：

在这里插入图片描述

❇️ 反向迭代器测试

#include"list.h"void Test4()//反向迭代器
{my_list::list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);//依次尾插元素进入list1容器中//先正向迭代器正常访问my_list::list<int>::iterator it1 = list1.begin();//调用正向迭代器的begin函数，得到访问的开始迭代器cout << "list1: ";while (it1 != list1.end()){cout << *it1 << " ";it1++;}cout << endl;//反向迭代器访问my_list::list<int>::reverse_iterator it2 = list1.rbegin();//调用反向迭代器的rbegin函数，得到访问的开始迭代器cout << "list1 r: ";while (it2 != list1.rend()){cout << *it2 << " ";it2++;}cout << endl;
}int main()
{Test4();return 0;
}

运行结果：

在这里插入图片描述

我们可以通过调试看一下，begin()和rbegin返回节点指针类型然后去调用构造函数的过程：
begin() :

在这里插入图片描述
rbegin():
会先去构造Iterator类型，再使用这个Iterator去构造reverse_iterator类型：

在这里插入图片描述

在这里插入图片描述

❇️ 插入和删除函数测试

#include"list.h"void Test5()//insert and erase display
{my_list::list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);//依次尾插元素进入list1容器中my_list::print_list(list1);//打印list1.insert(list1.begin(),1000);//头插一个1000my_list::print_list(list1);//打印list1.insert(list1.end(), 1000);//尾插一个1000my_list::print_list(list1);//打印list1.erase(list1.begin());//头删my_list::print_list(list1);//打印list1.erase(--list1.end());//尾删my_list::print_list(list1);//打印
}int main()
{Test5();return 0;
}

运行结果：

在这里插入图片描述

❇️ clear和size函数测试

#include"list.h"void Test7()//clear函数，size
{my_list::list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);cout << list1.size() << endl;list1.clear();cout << list1.size() << endl;
}int main()
{Test7();return 0;
}

运行结果：

在这里插入图片描述

❇️ swap函数测试

#include"list.h"void Test8()//swap函数
{list<int> list1;for (int i = 0; i < 10; ++i)list1.push_back(i);list<int> list2;for (int i = 15; i < 25; ++i)list2.push_back(i);my_list::print_list(list1);my_list::print_list(list2);std::swap(list1, list2);my_list::print_list(list1);my_list::print_list(list2);
}int main()
{Test7();return 0;
}

运行结果：
在这里插入图片描述

❇️ list排序效率测试

list容器不支持下标访问，但是它也有排序函数，我们不需要关心它的底层是如何来实现的，就只是简单来比较一下它和vector容器排序的效率。

我们准备了两个函数：

  1. 第一个函数单纯比较list和vector容器的排序的效率。
  2. 第二个函数比较list容器排序和把list容器中的数据拷贝到vector,排完序后再拷贝回list容器的效率。
#include"list.h"void Test9()
{srand(time(0));const int N = 1000000;list<int> lt1;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand();lt1.push_back(e);v.push_back(e);}int begin1 = clock();//vector中排序// sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();//list排序lt1.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}void Test10()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand();lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();//先把数据拷贝到vector,排完序后再拷贝回list的时间// vectorvector<int> v(lt2.begin(), lt2.end());// sort(v.begin(), v.end());// lt2lt2.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();//单纯的list的排序lt1.sort();int end2 = clock();printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}int main()
{Test9();Test10();return 0;
}

运行结果（100w个数据有大量重复数据，随机数只有3w多个，Release下测试对递归有优化）：

在这里插入图片描述
可以看到即使是拷贝了两次，在vector排序都比直接在list中快。

少量重复数据测试结果(给随机数+i可以减少重复)：

在这里插入图片描述

少量重复数据都比之前快了。

但是list容器排序的效率依旧比vector慢了不少，所以这个实际中这个list的排序基本没什么用，都尽量在vector中排序。

这篇关于【STL深入浅出】list探秘与实战的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1029467。

相关文章

React+TS前台项目实战（十七）-- 全局常用组件Dropdown封装

React+TS前台项目实战（十七）-- 全局常用组件Dropdown封装

文章目录 前言Dropdown组件1. 功能分析2. 代码+详细注释3. 使用方式4. 效果展示 总结 前言 今天这篇主要讲全局Dropdown组件封装，可根据UI设计师要求自定义修改。 Dropdown组件 1. 功能分析 （1）通过position属性,可以控制下拉选项的位置 （2）通过传入width属性, 可以自定义下拉选项的宽度 （3）通过传入classN
阅读更多...
-bash: /bin/mv: Argument list too long mv

-bash: /bin/mv: Argument list too long mv

把labels下的所有文件mv到img文件夹下： mv labels/* img/ 报错： -bash: /bin/mv: Argument list too long  mv # Using find ... -exec + find folder2 -name '*.*' -exec mv --target-directory=folder '{}' +   # Using xar
阅读更多...
C语言入门系列：探秘二级指针与多级指针的奇妙世界

C语言入门系列：探秘二级指针与多级指针的奇妙世界

文章目录 一，指针的回忆杀1，指针的概念2，指针的声明和赋值3，指针的使用3.1 直接给指针变量赋值3.2 通过*运算符读写指针指向的内存3.2.1 读3.2.2 写 二，二级指针详解1，定义2，示例说明3，二级指针与一级指针、普通变量的关系3.1，与一级指针的关系3.2，与普通变量的关系,示例说明 4，二级指针的常见用途5，二级指针扩展到多级指针 小结 C语言的学习之旅中，二级
阅读更多...
PyTorch模型_trace实战：深入理解与应用

PyTorch模型_trace实战：深入理解与应用

pytorch使用trace模型 1、使用trace生成torchscript模型2、使用trace的模型预测 1、使用trace生成torchscript模型 def save_trace(model, input, save_path):traced_script_model = torch.jit.trace(model, input)<
阅读更多...
C++标准模板库STL介绍

C++标准模板库STL介绍

STL的六大组成部分 STL（Standard Template Library）是 C++ 标准库中的一个重要组成部分，提供了丰富的通用数据结构和算法，使得 C++ 编程变得更加高效和方便。STL 包括了 6 大类组件，分别是算法（Algorithm）、容器（Container）、空间分配器（Allocator）、迭代器（Iterator）、函数对象（Functor）、适配器（Adapter）
阅读更多...
MyBatis-Plus常用注解详解与实战应用

MyBatis-Plus常用注解详解与实战应用

MyBatis-Plus 是一个 MyBatis 的增强工具，在 MyBatis 的基础上只做增强不做改变，为简化开发、提高效率而生。它提供了大量的常用注解，使得开发者能够更方便地进行数据库操作。 MyBatis-Plus 提供的注解可以帮我们解决一些数据库与实体之间相互映射的问题。 @TableName @TableName 用来指定表名 在使用 MyBatis-Plus 实现基本的 C
阅读更多...
［大师C语言(第三十六篇)］C语言信号处理：深入解析与实战

［大师C语言(第三十六篇)］C语言信号处理：深入解析与实战

引言 在计算机科学中，信号是一种软件中断，它允许进程之间或进程与内核之间进行通信。信号处理是操作系统中的一个重要概念，它允许程序对各种事件做出响应，例如用户中断、硬件异常和系统调用。C语言作为一门接近硬件的编程语言，提供了强大的信号处理能力。本文将深入探讨C语言信号处理的技术和方法，帮助读者掌握C语言处理信号的高级技巧。 第一部分：C语言信号处理基础 1.1 信号的概念 在Unix-lik
阅读更多...
Java零基础-集合：List

Java零基础-集合：List

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云；欢迎大家常来逛逛   今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。   我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初
阅读更多...
CSS列表属性：list-style系列属性详解

CSS列表属性：list-style系列属性详解

CSS（层叠样式表）是用于控制网页样式的一种语言，它允许开发者以一种非常灵活的方式来设置网页元素的外观。在CSS中，list-style属性族是专门用来设置列表样式的。列表是网页设计中常见的元素，它们可以是有序列表（<ol>）或无序列表（<ul>）。list-style系列属性允许你自定义列表项前的标记，包括类型、位置和图像。 1. list-style-type list-style-typ
阅读更多...
MATLAB算法实战应用案例精讲-【数模应用】三因素方差

MATLAB算法实战应用案例精讲-【数模应用】三因素方差

目录 算法原理 SPSSAU 三因素方差案例 1、背景 2、理论 3、操作 4、SPSSAU输出结果 5、文字分析 6、剖析 疑难解惑 均方平方和类型？ 事后多重比较的类型选择说明？ 事后多重比较与‘单独进行事后多重比较’结果不一致？ 简单效应是指什么？ 边际估计均值EMMEANS是什么？ 简单简单效应？ 关于方差分析时的效应量? SPSSAU-案例 一、案例
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2