【C++】list容器的基本使用

一、list是什么

list的底层结构是带头双向循环链表。

相较于 vector 的连续线性空间，list 就显得复杂很多，它是由一个个结点构成，每个结点申请的空间并不是连续的，它的好处是每次插入或删除一个数据，就配置或释放一个元素空间，我们不用在意扩容问题了，也不用单独写扩容函数了，list对于任何位置的元素进行插入或者元素移除，时间复杂度都是O(1)，它的缺点是不支持随机访问，即通过下标直接访问对应元素，这是由于它的底层是链表，链表中的结点在空间上分配是不连续的。

二、list容器的基本使用

1、构造函数

这里的allocator是空间配置器，我们这里先不用管它(认为它不存在)，等到后面的篇章会具体讲解它的作用。 其中，(1)是默认构造 (2)是n个val构造 (3)是迭代器区间构造 (4)是拷贝构造。

2、析构函数

释放每个结点申请的空间资源。

3、赋值重载

它的操作数是两个已有的list对象。

4、迭代器

(1)使用

list的迭代器和vector的迭代器在用法上一模一样。

使用迭代器可以进行遍历：

#include <iostream>
#include <list>
using namespace std;

void test_list1()
{
	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;
}

int main()
{
	test_list1();
	return 0;
}

运行结果：

支持迭代器，就支持范围for，因为范围for的底层就是迭代器。

void test_list1()
{
	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;
}

int main()
{
	test_list1();
	return 0;
}

运行结果：

(2)分类

迭代器从功能上进行分类，分为iterator、const_iterator、reverse_iterator、const_reverse_iterator这四类，它还可以从性质上进行分类，分为单向迭代器、双向迭代器、随机迭代器。

单向迭代器包括(forward)：forward_list / unordered_map... 它只支持++

双向迭代器(bidirectional)包括：list / map / set... 它只支持++ / --

随机迭代器(random access)包括：vector / string / deque... 它支持++ / -- / + / -

它们的底层结构决定它们的性质，它们的底层结构也决定它们可以使用哪些算法。

比如：

C++标准库中sort的模板参数是RandomAccessIterator，从它的名字中可以看出它只接收随机迭代器，如果传一个单向迭代器，它也可以接收，但运行时会发生错误即程序不能正常运行。

C++标准库中reverse的模板参数是BidirectionalIterator，从它的名字中可以看出它只接收双向迭代器，如果传一个单向迭代器，它也可以接收，但运行时会发生错误即程序不能正常运行。如果传一个随机迭代器，也可以正常使用，因为随机迭代器的范围更广，凡是支持单向迭代器或者双向迭代器的都支持随即迭代器。

出现InputIterator，说明单向/双向/随机迭代器都可以使用这个函数。

5、成员函数

(1)empty()

判断容器内节点个数是否为空，若为空返回true，否则返回false。

(2)size()

返回容器内节点个数。

(3)front()

reference 就是list<T>中的T，T是模板参数。front就是用来返回第一个结点的值。

(4)back()

 返回最后一个结点的值。

(5)assign()

用于赋值。(1)是用一段迭代区间赋值 (2)是用n个val赋值

(6)push_front()

头插，头部插入一个新结点。

(7)pop_front()

头删，删除头部的结点。 

(8)push_back()

尾插，尾部插入一个新结点。

(9)pop_back()

尾删，删除尾部的结点。

(10)emplace_back()

它的功能和push_back()差不多，但有不同之处，现阶段我们就把它当作push_back()使用。

struct AA
{
	AA(int a1, int a2)
		:_a1(a1)
		, _a2(a2)
	{}
private:
	int _a1;
	int _a2;
};

void test_list2()
{
	list<AA> lt;

	AA aa1(1, 1);
	lt.push_back(aa1);
	lt.push_back(AA(2,2));
	//lt.push_back(3,3); //err，这里会报错


	lt.emplace_back(aa1);
	lt.emplace_back(AA(2,2));
	lt.emplace_back(3,3); //ok,与push_back()的不同之处，它支持直接传构造A对象的参数
}

int main()
{
	test_list2();
	return 0;
}

(10)insert()

(1)是在pos位置前插入val (2)是在pos位置前插入n个val (3)是在pos位置前插入一段迭代区间。 

void test_list3()
{
	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;

	//在第3个位置前(整体位置是从0开始编号的)插入30
	//lt.insert(lt.begin() + 3, 30); //list容器不支持+,所以这行代码会报错

	list<int>::iterator it = lt.begin();
	int k = 3;
	while (k--)
	{
		++it;//list容器支持++,所以这行代码会报错
	}
	lt.insert(it, 30);  //(1)
	for (auto e : lt)
		cout << e << " ";
	cout << endl;
}

int main()
{
	test_list3();
	return 0;
}

运行结果： 

(11)erase()

 (1)删除pos位置上的值 (2)删除一段迭代区间

void test_list4()
{
	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;

	int x;
	cin >> x;
	list<int>::iterator it = find(lt.begin(),lt.end(),x);
	if (it != lt.end()) //找到了
		lt.erase(it); //(1)
	else
		cout << "不存在:" << x << endl;
	for (auto e : lt)
		cout << e << " ";
	cout << endl;

}

int main()
{
	test_list4();
	return 0;
}

输入4，运行结果： 

(12)clear()

清空所有结点数据。

(13)resize()

将结点个数更新到n，假设原先节点个数为k。

1、k > n

释放k - n个结点

2、k < n

增加n - k个节点，结点中的内容自己可以传，也可以不传，用默认的缺省值。

因为list的底层是链表，所以没有扩容这一说法。

(14)reverse()

逆置结点的顺序。

void test_list5()
{
	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;

	lt.reverse();
	for (auto e : lt)
		cout << e << " ";
	cout << endl;

    //reverse(lt.begin(),lt.end()); //这里的算法库中的reverse也支持list容器的逆置
}

int main()
{
	test_list5();
	return 0;
}

运行结果：

(15)sort()

 由于算法库中的sort不支持list容器的迭代器，所以这里它自己实现了一个。

void test_list6()
{
	list<int> lt;
	lt.push_back(20);
	lt.push_back(40);
	lt.push_back(50);
	lt.push_back(30);
	lt.push_back(10);
	for (auto e : lt)
		cout << e << " ";
	cout << endl;

	//默认排升序
	lt.sort(); //(1)
	for (auto e : lt)
		cout << e << " ";
	cout << endl;

}

int main()
{
	test_list6();
	return 0;
}

运行结果： 

如果想要排降序，就要借助仿函数：

void test_list6()
{
	list<int> lt;
	lt.push_back(20);
	lt.push_back(40);
	lt.push_back(50);
	lt.push_back(30);
	lt.push_back(10);
	for (auto e : lt)
		cout << e << " ";
	cout << endl;

	//排降序
	greater<int> gt;
	lt.sort(gt);
	for (auto e : lt)
		cout << e << " ";
	cout << endl;

}

int main()
{
	test_list6();
	return 0;
}

运行结果：

(16)merge()

合并两个链表，前提是这两个链表需要有序。 

void test_list7()
{
	list<int> first, second;

	first.push_back(3);
	first.push_back(6);
	first.push_back(1);

	second.push_back(2);
	second.push_back(5);
	second.push_back(4);

	first.sort();
	second.sort();

	first.merge(second); //合并后，second这个链表就空了，相当于将它移到first上了

	for (auto e : first)
		cout << e << " ";
	cout << endl;

	cout << "----------" << endl;

	for (auto e : second) //second中已经没有数据了
		cout << e << " ";
	cout << endl;

	cout << "----------" << endl;
}

int main()
{
	test_list7();
	return 0;
}

运行结果： 

 (17)unique()

去重，删除容器中与val值一样的结点，只保留第一个。删除时要保证重复的数据紧挨着，否则会删不干净，建议删除前先排序。

void test_list8()
{
	list<int> lt;
	lt.push_back(5);
	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(2);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(5);
	for (auto e : lt)
		cout << e << " ";
	cout << endl;

	lt.sort();

	lt.unique();
	for (auto e : lt)
		cout << e << " ";
	cout << endl;
}

int main()
{
	test_list8();
	return 0;
}

运行结果： 

(18)remove()

对val进行查找，如果找到就删除，否则什么也不做。 

(19)remove_if()

给定一个条件，如果满足就删除，否则什么也不做。

(20)splice()

 (1)是将x中全部结点转移到当前容器中的pos位置之前的位置处 (2)是将x中i位置的结点转移到当前容器中的pos位置之前的位置处 (3)是将x中的一段迭代区间上的结点转移到当前容器中的pos位置之前的位置处

//将一个链表的结点转移给另一个链表
void test_list9()
{
    list<int> mylist1, mylist2;
    list<int>::iterator it;

    //先插入一些值
    for (int i = 1; i <= 4; ++i)
        mylist1.push_back(i);      // mylist1: 1 2 3 4

    for (int i = 1; i <= 3; ++i)
        mylist2.push_back(i * 10);   // mylist2: 10 20 30

    cout << "初始值：" << endl;
    for (auto e : mylist1)
        cout << e << " ";
    cout << endl;
    for (auto e : mylist2)
        cout << e << " ";
    cout << endl;

    cout << "---------------" << endl;

    it = mylist1.begin();
    ++it;                     

    mylist1.splice(it, mylist2); //(1)
    // mylist1: 1 10 20 30 2 3 4
    // mylist2中的数据已经没有了
    // "it" 仍然指向2 

    cout << "第一次调用splice后：" << endl;
    for (auto e : mylist1)
        cout << e << " ";
    cout << endl;
    for (auto e : mylist2)
        cout << e << " ";
    cout << endl;

    cout << "---------------" << endl;

    mylist2.splice(mylist2.begin(), mylist1, it); //(2)
    // mylist1: 1 10 20 30 3 4
    // mylist2: 2
    // "it"现在是无效的
    cout << "第二次调用splice后：" << endl;
    for (auto e : mylist1)
        cout << e << " ";
    cout << endl;
    for (auto e : mylist2)
        cout << e << " ";
    cout << endl;

    cout << "---------------" << endl;
}

int main()
{
	test_list9();
	return 0;
}

运行结果： 

根据它的功能，我们还可以调整当前链表的结点顺序：

//调整当前链表结点的顺序
void test_list10()
{
	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_back(6);

	cout << "转移前:" << endl;
	for (auto e : lt)
		cout << e << " ";
	cout << endl;

	//现要求将6这个结点转移到1这个结点的前面去
	lt.splice(lt.begin(), lt, --lt.end());

	cout << "转移后:" << endl;
	for (auto e : lt)
		cout << e << " ";
	cout << endl;
}

int main()
{
    test_list10();
    return 0;
}

三、排序效率

这里我们将list容器中的sort与算法库中的sort进行效率对比，看看哪个更优。

(1)对比一

#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

void test_op1()
{
	srand((unsigned int)time(0));
	const int N = 1000000;
	list<int> lt1;
	vector<int> v;

	for (int i = 0;i < N;++i) //随机生成100万个数据
	{
		auto e = rand() + i;
		lt1.push_back(e);
		v.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	cout << "vector sort:" << end1 - begin1 << endl;
	cout << "list sort:" << end2 - begin2 << endl;
}

int main()
{
	test_op1();
	return 0;
}

在Debug环境下的运行结果：

可以看到list排序优势更大，那是因为在Debug环境下，优化不是很大，运行结果不具有参考价值，在release环境下，双方优化都是最大的，这才公平。

在Realse环境下运行结果：

实际上，算法库中的sort效率是更好的。 

(2)对比二

#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

void test_op2()
{
	srand((unsigned int)time(0));
	const int N = 1000000;
	list<int> lt1;
	list<int> lt2;

	for (int i = 0;i < N;++i)
	{
		auto e = rand() + i;
		lt1.push_back(e);
		lt2.push_back(e);
	}

	int begin1 = clock();
	vector<int> v(lt2.begin(), lt2.end()); //迭代器区间构造
	sort(v.begin(), v.end()); //用算法库中的sort进行排序
	lt2.assign(v.begin(), v.end()); //再拷贝回lt2
	int end1 = clock();

	int begin2 = clock();
	lt1.sort(); //直接调用list中的sort进行排序
	int end2 = clock();

	cout << "list copy vector sort copy list sort:" << end1 - begin1 << endl;
	cout << "list sort:" << end2 - begin2 << endl;
}

int main()
{
	test_op2();
	return 0;
}

在Release环境下运行结果： 

这差距就出来了， 在begin1~end1这段时间内做的事情比begin2~end2这段时间内做的还要多，结果花费的时间还少，说明了当数据量比较大时，list中的sort排序效率很低。不如先把它的值拷贝给vector容器，然后排序，排完再拷贝回来。

四、list容器与vector容器的对比

五、结语

本篇内容到这里就结束了，主要讲了list容器的基本使用，希望对大家有些许收获，祝大家天天开心！