C++标准模板库（STL）list双向链表容器

陈一男学习网站[ ChenYinan.com ] - CCF - NOI - 菜鸟教程 - 编程题库 - C++语言 - API

一. 定义与基本概念

在C++的标准模板库（STL）中，list是一个双向链表容器，位于<list>头文件中。它允许在序列中的任何位置进行高效的插入和删除操作。与其他容器（如vector）不同，list中的元素在内存中不是连续存储的，而是通过节点之间的指针相互连接。

二. 创建list对象

默认构造：可以创建一个空的list对象。例如，std::list<int> myList;创建了一个空的、用于存储int类型元素的list。

从其他容器初始化：可以使用另一个容器（如数组、vector等）来初始化list。

int arr[] = {1, 2, 3}; 
std::vector<int> v = {4, 5, 6}; 
std::list<int> myList1(arr, arr + sizeof(arr)/sizeof(arr[0])); 
std::list<int> myList2(v.begin(), v.end());

这里分别使用数组arr和vector v来初始化list对象myList1和myList2。

三. list的基本操作

1. 元素访问

由于list是双向链表结构，不支持像vector那样的随机访问（即不能使用[]运算符进行访问）。如果要访问list中的元素，通常需要使用迭代器。

std::list<int> myList = {1, 2, 3};
std::list<int>::iterator it = myList.begin();
std::cout << *it << std::endl;

这里通过迭代器it访问list中的第一个元素。

2. 添加元素

push_back()和push_front()：push_back()用于在list的末尾添加一个元素，push_front()用于在list的开头添加一个元素。

std::list<int> myList;
myList.push_back(3);
myList.push_front(1);

此时myList包含两个元素，1在开头，3在末尾。

insert()：可以在list的指定位置插入一个或多个元素。

std::list<int> myList = {1, 3};
std::list<int>::iterator it = myList.begin();
++it;
myList.insert(it, 2);

这里在list中1和3之间插入了元素2。

3. 删除元素

pop_back()和pop_front()：pop_back()用于删除list末尾的一个元素，pop_front()用于删除list开头的一个元素。

std::list<int> myList = {1, 2, 3};
myList.pop_front();
myList.pop_back();

操作后myList中只剩下元素2。

erase()：可以删除list中指定位置的元素。

std::list<int> myList = {1, 2, 3};
std::list<int>::iterator it = myList.begin();
++it;
myList.erase(it);

这里删除了myList中的元素2。

4. 获取list的大小：使用size()方法可以获取list中元素的个数。

std::list<int> myList = {1, 2, 3}; 
std::cout << myList.size() << std::endl;    // 会输出3，表示list中有3个元素

四. 迭代器操作

list提供了双向迭代器，支持向前和向后遍历。

std::list<int> myList = {1, 2, 3};
// 向前遍历
for (std::list<int>::iterator it = myList.begin(); it!= myList.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;
// 向后遍历
for (std::list<int>::reverse_iterator rit = myList.rbegin(); rit!= myList.rend(); ++rit) {
    std::cout << *rit << " ";
}
std::cout << std::endl;

这里使用begin()、end()、rbegin()和rend()方法分别获取正向和反向迭代器的起始和结束位置。

五. 排序与合并操作

排序：可以使用sort()方法对list中的元素进行排序。

std::list<int> myList = {3, 1, 2};
myList.sort();
for (std::list<int>::iterator it = myList.begin(); it!= myList.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

这里会对myList中的元素按照升序进行排序并输出。

合并：可以使用merge()方法将两个已排序的list对象合并为一个。

std::list<int> list1 = {1, 3, 5};
std::list<int> list2 = {2, 4, 6};
list1.sort();
list2.sort();
list1.merge(list2);
for (std::list<int>::iterator it = list1.begin(); it!= list1.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

这里先对list1和list2进行排序，然后将list2合并到list1中，最后输出合并后的结果。

六. list的特性与注意事项

内存布局与性能：由于list中的元素是通过指针连接的，在中间插入和删除元素的操作效率很高（时间复杂度为$O(1)$），不需要像vector那样移动大量元素。但是，随机访问元素的效率很低（时间复杂度为$O(n)$），因为需要从链表的一端开始逐个遍历节点。

迭代器失效：在对list进行插入或删除操作时，只有指向被操作元素的迭代器会失效（如果是删除操作）或者需要重新定位（如果是插入操作），其他迭代器仍然有效。这与vector有所不同，在vector中，插入或删除操作可能会导致大量迭代器失效。