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

  • Post author:
  • Post category:其他



目录


一.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_front
	l2.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;

	//中间删——erase
	l2.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()效率要高很多很多。



版权声明:本文为weixin_69283129原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。