C++——STL容器之list链表的讲解

目录

一.list的介绍

二.list类成员函数的讲解

        2.2迭代器

三.添加删除数据：

        3.1添加：

        3.2删除数据

 四.排序及去重函数：

错误案例如下：

方法如下：

---

一.list的介绍

        list列表是序列容器，允许在序列内的任何位置执行插入元素或者删除元素等操作。list列表容器的底层是由链表封装而成，并且该链表的类型还是带头双向循环链表。

二.list类成员函数的讲解

        对于list容器的成员函数们， 它们与vector与String容器的功能作用相差不大，都是增删查改，能够通过迭代器遍历或者修改容器中某个元素的数据。由于前者与后两者底层类型的不同，侧面表现出了list容器的使用是即插即用， 不需要扩容缩容，意味着不会有reserve()、shrink_to_fit()等函数，

       

        2.2迭代器

        list链表容器的迭代器与String和Vector的迭代器也不同，后两者是使用的原生指针，由于连续地址空间的缘故，指针只需要通过增加或者减少类型的字节，便可以定位到具体的位置。

        而对于List容器而言，它的元素是一个接一个的节点，每个节点是由指针相连，所以各个节点的地址并不是连续的，那么使用原生指针去寻找元素位置会相当复杂，所以list的迭代器是一种新型迭代器，采用自定义类型制造而出。

        虽说list迭代器的底层与string,vector的迭代器并不同，但是使用方式都一样：

vector<T>:: iterator vt=v.begin();

String:: iterator st=s.begin();

list<T>::iterator lt=l.begin();

都是通过类域加作用域限定符 iterator的方式去定义。 

         在迭代器中，也是分为普通迭代器、const迭代器、反向迭代器、const反向迭代器。其各个成员作用也与之前讲String、vector容器一样，这里就不再过多讲解了。不清楚的话可以翻一翻我之前写的String和vector容器的讲解.

 这里直接上练习代码：

#include<iostream>
#include<list>
int main(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);for (auto& e:l1) {cout << e << " ";}cout << endl;list<int>::iterator lit1 = l1.begin();while (lit1 != l1.end()) {cout << ++(*lit1) << " ";++lit1;}cout << endl;cout << "--------------------------------------------" << endl;//反向迭代器list<int>::reverse_iterator lit2 = l1.rbegin();while (lit2 != l1.rend()) {cout << ++(*lit2) << " ";++lit2;}cout << endl;//const反向迭代器list<int>::const_reverse_iterator lit3 = l1.crbegin();while (lit3!= l1.crend()) {cout << (*lit3) << " ";//cout << ++(*lit3) << " ";			//报错++lit3;}cout << endl;//const正向迭代器list<int>::const_iterator lit4 = l1.cbegin();while (lit4 != l1.cend()) {//cout << ++(*lit3) << " ";			//报错cout << (*lit4) << " ";++lit4;}cout << endl;}return 0;}

运行结果： 

 

 

 

三.添加删除数据：

        3.1添加：

int main(){list<double> l2;//尾插l2.push_back(9.25);l2.push_back(60.10);l2.push_back(32.19);l2.push_back(58.79);//头插l2.insert(l2.begin(), 3.14);for (auto& e : l2) {cout << e << "  ";}cout << endl;//尾插l2.insert(l2.end(),999.99);for (auto& e : l2) {cout << e << "  ";}cout << endl;//中间插//find是std库函数中的auto pos = find(l2.begin(), l2.end(), 32.19);l2.insert(pos, 46.99);for (auto& e : l2) {cout << e << "  ";}cout << endl;//头插push_frontl2.push_front(12.66);for (auto& e : l2) {cout << e << "  ";}cout << endl;return 0;}

 

 

        注：对于insert来说，它的形参需要指定指针类型的pos位置，而pos位置需要自己去定位链表，上图代码中我是通过库函数find去进行定位的，list容器本身并不会提供find函数，因为库中的find函数形参以及返回值就可以很好的帮助我们进行定位。

并且之前我讲过vector容器中，insert函数会引发指针失效问题，在list中，insert函数不会引发该问题。

 

 

 

        3.2删除数据

    list<char> l2;l2.push_back('a');l2.push_back('b');l2.push_back('c');l2.push_back('d');for (auto& e : l2) {cout << e << "  ";}cout << endl;//尾删l2.pop_back();for (auto& e : l2) {cout << e << "  ";}cout << endl;//头删l2.pop_front();for (auto& e : l2) {cout << e << "  ";}cout << endl;//中间删——erasel2.push_back('h');l2.push_back('i');l2.push_back('j');l2.push_back('k');for (auto& e : l2) {cout << e << "  ";}cout << endl;//find是std库函数中的auto pos = find(l2.begin(), l2.end(), 'p');//l2.erase(pos);		//找不到的删会报异常for (auto& e : l2) {cout << e << "  ";}cout << endl;pos = find(l2.begin(), l2.end(), 'h');l2.erase(pos);for (auto& e : l2) {cout << e << "  ";}cout << endl;

运行结果： 

 

 

 四.排序及去重函数：

 

void Test6() {list<int> l1;l1.push_back(34);l1.push_back(100);l1.push_back(26);l1.push_back(79);l1.push_back(83);l1.push_back(0);l1.push_back(34);l1.push_back(55);l1.push_back(13);for (auto& e : l1) {cout << e << " ";}cout << endl;//排序l1.sort();for (auto& e : l1) {cout << e << " ";}cout << endl;}

 

 sort()函数可对list对象的元素进行整体排序。

        去重就是对该链表对象进行遍历，将元素值相同的多个元素进行删除，只保留唯一一个值节点 。

 

对上面对象l1进行元素去重：

l1.unique();cout << "去重后的链表：";for (auto& e : l1) {cout << e << " ";}cout << endl;

结果： 

 

        这里讲一下unique函数的真正用法，虽然unique函数可以对链表进行元素去重，但前提是该链表一定处于完全有序的状态才行！！！ 

        若链表不是有序的，去重也就是无效的！！！

错误案例如下：

    list<int> l2;l2.push_back(34);l2.push_back(100);l2.push_back(26);l2.push_back(79);l2.push_back(83);l2.push_back(0);l2.push_back(34);l2.push_back(55);l2.push_back(13);cout << "原链表：";for (auto& e : l2) {cout << e << " ";}cout << endl;l2.unique();//注：34仍是俩个，没有被去除cout << "去重后的链表：";for (auto& e : l2) {cout << e << " ";}cout << endl;

 

        原链表是无序的，使用unique函数后，该链表还是有多个重复元素存在！

        最后强调一下：list容器的sort排序函数并不好用，排序效率低下，尽量少用！若想进行高效排序，可以利用vector容器搭配std库中的sort函数进行。 

方法如下：

void Test_Sort(){list<int> lt1;lt1.push_back(15);lt1.push_back(9);lt1.push_back(3);lt1.push_back(10);lt1.push_back(80);    lt1.push_back(5);lt1.push_back(-3);lt1.push_back(0);lt1.push_back(42);//假设链表中有这么多数据vector<int> v;    //创建vector对象v.reserve(9);    //根据链表对象的数据个数开辟空间//通过遍历lt1链表，将链表中的数据一个一个尾插到vector对象v中，for (auto e : lt1){v.push_back(e);}//使用vector方式进行std库中的sort排序sort(v.begin(), v.end());size_t i = 0;//最后将vector排好序的数据在传回lt1中for (auto& e : lt1){e = v[i++];}}

        若是list容器对象需要排序的数据量过大的话，利用vector排序+sort的方式可比直接用list.sort()效率要高很多很多。