C++标准模板库（STL）list双向链表容器
一. 定义与基本概念
在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中，插入或删除操作可能会导致大量迭代器失效。
