09.【C++】list链表（STL中的列表容器，C++封装的带头双向链表，可实现指定类型的增删查改，迭代器操作等功能）

目录

一. list的介绍及使用

1.1 list的介绍

1.2 list的使用

1.2.1 list的构造

1.2.2 list iterator迭代器的使用

1.2.3 list size & empty 大小判空

1.2.4 list element access 头尾引用

1.2.5 list modifiers 增删查改

1.2.6 list的迭代器失效

1.2.7 list 排序的使用

二. list的模拟实现

2.1 模拟实现list

三. list与vector的对比

一. list的介绍及使用

1.1 list的介绍

        list文档介绍

1.2 list的使用

        list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

1.2.1 list的构造

#include<iostream>
#include<list>
using namespace std;
// list的构造
void test_list1()
{
    list<int> l1;                         // (2) 构造空的l1
    list<int> l2(4, 100);                 // (1) l2中放4个值为100的元素
    list<int> l3(l2.begin(), l2.end());   // (4) 用l2的[begin(), end()）左闭右开的区间构造l3
    list<int> l4(l3);                     // (3) 用l3拷贝构造l4

    int array[] = { 16,2,77,29 };         // (5) 以数组为迭代器区间构造l5
    list<int> l5(array, array + sizeof(array) / sizeof(int));

    list<int> l6{ 1,2,3,4,5 };            // (6) 列表格式初始化C++11

    // 用迭代器方式打印l5中的元素
    list<int>::iterator it = l5.begin();
    while (it != l5.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // C++11范围for的方式遍历
    for (auto& e : l5)
        cout << e << " ";
    cout << endl;
}
int main()
{
    test_list1();
	return 0;
}

1.2.2 list iterator迭代器的使用

        此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

示例： 

#include<algorithm>
#include<iostream>
#include<list>
#include<vector>
using namespace std;
// 打印函数
template<typename T>
void Print(T ls)
{
    for (auto a : ls)
        cout << a << " ";
    cout << endl;
}
void test_list4()
{
    int array[] = { 16,2,77,29 };         // 以数组为迭代器区间构造
    list<int> l1(array, array + sizeof(array) / sizeof(int));
    Print(l1);
    //sort(l1.begin(), l1.end());   //报错：不定义该运算符或到预定义运算符可接收的类型的转换
    reverse(l1.begin(), l1.end());  // list是BidirectionalIterator
    Print(l1);                      // 只能用BidirectionalIterator迭代器和向前兼容的迭代器支持的算法
                                    // sort函数在algorithm算法库里是RandomAccessIterator，所以list不能用

    vector<int> v1(array, array + sizeof(array) / sizeof(int));
    Print(v1);
    sort(v1.begin(), v1.end());     // vector是RandomAccessIterator
    Print(v1);                      // 能用RandomAccessIterator迭代器和向前兼容的迭代器支持的算法
    reverse(v1.begin(), v1.end());  // sort函数vector迭代器本来就支持
    Print(v1);                      // reverse函数是RandomAccessIterator迭代器向前兼容的迭代器支持的算法
    
    // 但是list库里自己定义了sort函数
    cout << endl;
    l1.sort();
    Print(l1);
}
int main()
{
    test_list4();
    return 0;
}

【注意】

        1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

        2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动 

1.2.3 list size & empty 大小判空

1.2.4 list element access 头尾引用

示例：1.2.3、1.2.4

#include<iostream>
#include<list>
using namespace std;
// 打印函数
template<typename T>
void Print(list<T> ls)
{
    for (auto a : ls)
        cout << a << " ";
    cout << endl;
}
void test_list2()
{
    int array[] = { 16,2,77,29 };         // 以数组为迭代器区间构造
    list<int> l1(array, array + sizeof(array) / sizeof(int));
    Print(l1);
    cout << l1.size() << endl;  // (1) 返回l1的size
    cout << l1.empty() << endl; // (2) 返回l1是否为空
    cout << l1.front() << endl; // (3) 返回l1首元素的引用
    cout << l1.back() << endl;  // (4) 返回l1最后一个元素的引用
}
int main()
{
    test_list2();
    return 0;
}

1.2.5 list modifiers 增删查改

        list中还有一些操作，需要用到时大家可参阅list的文档说明。

示例1：（1）~（8）

#include<iostream>
#include<list>
using namespace std;
// 打印函数
template<typename T>
void Print(list<T> ls)
{
    for (auto a : ls)
        cout << a << " ";
    cout << endl;
}
void test_list3()
{
    int array[] = { 16,2,77,29 };         // 以数组为迭代器区间构造
    list<int> l1(array, array + sizeof(array) / sizeof(int));
    Print(l1);

    l1.push_front(100); // (1) 头插
    Print(l1);

    l1.pop_front();     // (2) 头删
    Print(l1);

    l1.push_back(99);   // (3) 尾插
    Print(l1);

    l1.pop_back();      // (4) 尾删
    Print(l1);
    cout << endl;

    list<int>::iterator pos = find(l1.begin(),l1.end(),77);
    l1.insert(pos, 55); // (5) 指定位置之前插入 在77之前插入55
    Print(l1);

    pos = find(l1.begin(), l1.end(), 2);
    l1.erase(pos);      // (6) 删除指定位置的元素 删除2
    Print(l1);
    cout << endl;

    list<int> l2(3, 100);
    swap(l1, l2);       // (7) 交换两个列表的元素，大小可以不同
    Print(l1);
    Print(l2);

    l1.clear();
    Print(l1);          // (8) 清空列表的元素
    cout << "clear" << endl;
}
int main()
{
    test_list3();
    return 0;
}

示例2：（9）

move链表 (1)	void splice (iterator position, list& x);  // 把 x 的所有元素移到 position 前面
move链表的某个迭代器指向的元素(2)	void splice (iterator position, list& x, iterator i);  // 把 x 的 i 迭代器指向的元素移到 position 前
move链表的一段区间的元素 (3)	void splice (iterator position, list& x, iterator first, iterator last); // 把 x 的从 [first, last) 迭代器之间的元素移到 position 前

        注意，splice可以移动其他链表的元素，也可以移动自身链表的元素。

#include<iostream>
#include<list>
using namespace std;
// 打印函数
template<typename T>
void Print(T ls)
{
    for (auto a : ls)
        cout << a << " ";
    cout << endl;
}
void test_list5()
{
    int array1[] = {1,2,3,8,9,10 };        // 以数组为迭代器区间构造l1
    list<int> l1(array1, array1 + sizeof(array1) / sizeof(int));
    int array2[] = { 4,5,6,7 };           // 以数组为迭代器区间构造l2
    list<int> l2(array2, array2 + sizeof(array2) / sizeof(int));

    list<int>::iterator it = find(l1.begin(), l1.end(), 3);
    ++it;
    l1.splice(it, l2);      // (1) 将l2的所有元素移到l1的3元素之后
    Print(l1);
    Print(l2);
    cout << "splice" << endl;

    l1.splice(l1.begin(), l1, --l1.end());
    Print(l1);              // (2) 将l1的最后一个元素移动到第一个元素之前
    l1.splice(l1.end(), l1, l1.begin());
    Print(l1);              // (2) 将l1的第一个元素移动到最后一个元素的位置

    it = find(l1.begin(), l1.end(), 5);
    l1.splice(l1.begin(), l1, ++it, l1.end());
    Print(l1);              // (3) 将l1的从5后面到最后一个元素启动到第一个元素之前
}
int main()
{
    test_list5();
    return 0;
}

1.2.6 list的迭代器失效

        前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

1.2.7 list 排序的使用

        list自带的sort排序效果较差，不如list拷贝到vector调用算法库排序在拷贝回list效果好。

注意：排序测试不要用Debug，用Release测试出的才是真实水平。

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

void test_op1()
{
	srand(time(0));
	const int N = 1000000;

	list<int> lt1;
	vector<int> v;

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

	// 算法库中的sort
	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	// list自己的sort
	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

void test_op2()
{
	srand(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);
	}
	// list拷贝给vector，用算法库将vector排序，在把vector拷贝回list
	int begin1 = clock();
	// 拷贝vector
	vector<int> v(lt2.begin(), lt2.end());
	// 排序
	sort(v.begin(), v.end());
	// 拷贝回lt2
	lt2.assign(v.begin(), v.end());
	int end1 = clock();

	// list自带的sort
	int begin2 = clock();
	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()
{
	test_op1();		// vector调用库函数sort排序，和list自带排序对比
	cout << endl;
	test_op2();		// list拷贝到vector排完序再拷贝回list，和list自带排序对比
	return 0;		//总结：list自带的排序效果差
}

二. list的模拟实现

2.1 模拟实现list

        【免费】C++list的模拟实现资源-CSDN文库

三. list与vector的对比

        vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下： 

总结：