概念
std::list 是标准模板库（STL）提供的一个容器类，它实现了双向链表的数据结构。
实现原理
内部结构
双向链表由多个节点连接而成。其中每个节点包含三个部分：
- 内容/数据域：用于存储实际的数据元素。
- 前驱：指向前一个节点的指针。
- 后继：指向后一个节点的指针。
节点管理
当创建一个 std::list 对象时，它会维护一个头节点和尾节点，用于标记链表的起始和结束位置。头节点和尾节点通常是虚拟节点，不存储实际的数据，仅用于简化链表的操作。
插入操作
- 在头部插入：创建一个新节点，将新节点的
next指针指向原来的头节点的下一个节点，将原来头节点的下一个节点的prev指针指向新节点，然后更新头节点的next指针指向新节点，新节点的prev指针指向头节点。 - 在尾部插入：创建一个新节点，将新节点的
prev指针指向原来的尾节点的前一个节点，将原来尾节点的前一个节点的next指针指向新节点，然后更新尾节点的prev指针指向新节点，新节点的next指针指向尾节点。 - 在中间插入：先找到插入位置的节点，创建一个新节点，调整新节点和相邻节点的
prev和next指针，以将新节点插入到合适的位置。
删除操作
- 删除头部元素：找到头节点的下一个节点，将头节点的
next指针指向该节点的下一个节点，将该节点下一个节点的prev指针指向头节点，然后释放该节点的内存。
- 删除尾部元素：找到尾节点的前一个节点，将尾节点的
prev指针指向该节点的前一个节点，将该节点前一个节点的next指针指向尾节点，然后释放该节点的内存。 - 删除中间元素：找到要删除的节点，调整其相邻节点的
prev和next指针，跳过该节点，然后释放该节点的内存。
查找操作
从头节点开始遍历整个链表，直到找到指定元素或遍历完整个链表。
基本操作与方法接口
定义、初始化和赋值
#include <iostream>
#include <list>int main()
{// 定义一个空的 list，存储 int 类型的元素std::list<int> List1;// 定义并初始化一个包含 5 个元素，每个元素都是默认值（0）的 liststd::list<int> List2(5);// 定义并初始化一个包含 5 个元素，每个元素的值都是 10 的 liststd::list<int> List3(5, 10);// 用另一个 list 初始化新的 liststd::list<int> List4(List3);// 用另一个 list 的迭代器范围初始化新的 liststd::list<int> List5(List4.begin(), List4.end());// 使用"拷贝初始化"初始化 liststd::list<int> List6 = { 1, 2, 3, 4, 5 };// 使用"直接列表初始化"初始化 liststd::list<int> List7{ 1, 2, 3, 4, 5 };
}元素访问
front
访问第一个元素
List.front()
List.front() = 6; //将第一个元素赋值为6back
访问最后一个元素
List.back();
List.back() = 6; //将最后一个元素赋值为6迭代器
list 的节点在内存中是离散分布的，只能通过节点的指针依次访问相邻的节点。因此，其迭代器只支持双向访问，即可以使用 ++ 和 -- 操作符将迭代器向前或向后移动一个位置，但不支持随机访问操作。以下是 list 迭代器不支持的操作：
算术运算：不能使用 + 和 - 运算符将迭代器直接移动多个位置，因为要访问指定位置的元素，必须从当前位置开始，沿着链表依次遍历，时间复杂度为 (O(n))（较高）。如果非要使用 +- 运算，可以使用 std::advance 泛型算法。
部分比较运算：虽然可以使用 == 和 != 来判断两个迭代器是否相等，但不支持 >、<、<=、>= 等比较运算符，因为链表节点在内存中没有连续的地址顺序，无法直接比较位置关系。
正向迭代器
begin：返回容器中第一个元素的正向迭代器
end：返回容器中最后一个元素的后一个位置的正向迭代器
#include <iostream>
#include <list>int main()
{std::list<int> List(5);// 使用正向迭代器为list赋值for (std::list<int>::iterator it = List.begin(); it != List.end(); ++it){*it = 3;}// 使用正向迭代器遍历list并打印其值for (std::list<int>::iterator it = List.begin(); it != List.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;
}
cbegin：返回容器中第一个元素的正向常量迭代器
cend：返回容器中最后一个元素的后一个位置的正向常量迭代器
常量迭代器的特点是，它只能用于读取元素，不能通过它来修改所指向的元素，这有助于在需要保证数据不被修改的场景下使用。
#include <iostream>
#include <list>int main()
{std::list<int> List = {1, 2, 3, 4, 5 };// 遍历容器并输出元素for (std::list<int>::const_iterator it = List.cbegin(); it != List.cend(); ++it){// 可以读取元素std::cout << *it << " ";// 以下代码会编译错误，因为不能通过常量迭代器修改元素// *it = 10;}std::cout << std::endl;
}
反向迭代器
rbegin：返回容器中最后一个元素的反向迭代器
rend：返回容器中第一个元素的前一个位置的反向迭代器
#include <iostream>
#include <list>int main()
{std::list<int> List = {1, 2, 3, 4, 5 };std::list<int>::reverse_iterator rit = List.rbegin();*rit = 23;std::cout << *rit;
}
crbegin：返回容器中第一个元素的反向常量迭代器
crend：返回容器中最后一个元素的后一个位置的反向常量迭代器
#include <iostream>
#include <list>int main()
{std::list<int> List = {1, 2, 3, 4, 5 };//反向迭代器倒序遍历容器std::list<int>::const_reverse_iterator rit1 = List.crbegin();while (rit1 != List.crend()){std::cout << *rit1 << " "; //先打印再自增++rit1;}std::cout << std::endl;/*不能使用下面的方法来正序遍历迭代器。 因为list 的迭代器是双向迭代器，不是随机访问迭代器，不能使用 rit2 - 1 这样的操作std::list<int>::const_reverse_iterator rit2 = List.crend();while (rit2 != List.crbegin()){std::cout << *(rit2 - 1) << " ";--rit2;}std::cout << std::endl;*///反向迭代器正序遍历容器std::list<int>::const_reverse_iterator rit2 = List.crend();while (rit2 != List.crbegin()){--rit2; //先自减再打印std::cout << *rit2 << " ";}std::cout << std::endl;
}
对于反向迭代器：rbegin和crbegin到rend和crend为迭代器的正方向。rbegin和crbegin小于rend和crend，rbegin和crbegin通过自加可以到达rend和crend的位置。rend和crend大于rbegin和crbegin，rend和crend通过自减可以到达rbegin和crbegin的位置。
基于范围的for循环
注意向vector写入元素时，for循环中要加引用符&。原因见：C++杂项（更新中）_std::operator==<std::vector<std::vector<int, std::-CSDN博客
#include <iostream>
#include <list>using namespace std;int main()
{list<int> List = {1, 2, 3, 4, 5 };for (int num : List){cout << num;}cout << endl;for (int& num : List){num = 9;cout << num;}cout << endl;for (int num : List){cout << num;}cout << endl;
}
容量
empty
判断容器是否为空，如果为空则返回 true，否则返回 false。
List.empty()size
返回当前存储的元素个数
List.size()max_size
返回可容纳的最大元素数量，即一直向list中添加元素直到溢出时的元素个数
List.max_size()修改器
clear
清除list中的所有内容
List.clear()insert
在指定位置插入元素
#include <iostream>
#include <list>
#include <array>// 打印vector中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 2, 3, 4, 5 };// 1. 在指定位置插入单个元素List.insert(List.begin(), 10);std::cout << "在指定位置插入单个元素: ";printList(List);// 2. 在指定位置插入多个相同值的元素List.insert( -- List.end(), 3, 20);std::cout << "在指定位置插入多个相同值的元素: ";printList(List);// 3. 在指定位置插入另一个容器的元素范围std::array<int, 2> a = { 30, 40 };List.insert(List.begin(), a.begin(), a.end());std::cout << "在指定位置插入另一个容器的元素范围: ";printList(List);// 4. 在指定位置插入初始化列表中的元素List.insert(List.end(), { 50, 60 });std::cout << "在指定位置插入初始化列表中的元素: ";printList(List);
}
emplace
原位构造元素
未完待续
emplace_back
在容器末尾原位构造元素
未完待续
emplace_front
在容器头部原位构造元素
未完待续
erase
移除单个元素
iterator erase(iterator position);
position：这是一个迭代器，指向要移除的元素。
返回一个迭代器，该迭代器指向被移除元素之后的那个元素。若移除的是列表的最后一个元素，就返回 end() 迭代器。
移除一个范围内的元素
iterator erase(iterator first, iterator last);
first 和 last：这是两个迭代器，它们定义了要移除的元素范围 [first, last)。也就是说，这个范围包含 first 指向的元素，但不包含 last 指向的元素。
返回一个迭代器，该迭代器指向被移除范围之后的第一个元素。若移除的是列表末尾的元素，就返回 end() 迭代器。
#include <iostream>
#include <list>
#include <iterator>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };printList(List);List.erase(List.begin());printList(List);// 保存开始迭代器向前移动2个位置的迭代器auto it1 = List.begin();std::advance(it1, 2);// 保存结束迭代器向前移动3个位置的迭代器auto it2 = List.end();std::advance(it2, -3);List.erase(it1, it2);printList(List);
}
push_front
将元素添加到容器开头
List.push_back("abc") //将“abc”插入List开头push_back
将元素添加到容器末尾
List.push_back("abc") //将“abc”插入List末尾pop_front
移除开头元素
List.pop_front()pop_back
移除末尾元素
List.pop_back()resize
改变存储元素的个数
#include <iostream>
#include <list>
#include <iterator>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 2, 3 };std::cout << "原始List： ";printList(List);List.resize(5);std::cout << "增加大小到 5 后： ";printList(List);List.resize(2);std::cout << "减少大小到 2 后： ";printList(List);List.resize(6, 4);std::cout << "增加大小到 6 并将新增的元素赋予默认值 4 后： ";printList(List);List.resize(3, 3);std::cout << "减少大小到 3 并将新增的元素（实际没有）赋予默认值 3 后： ";printList(List);
}
swap
交换两个list中的内容
#include <iostream>
#include <list>
#include <iterator>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List1 = { 1, 2, 3 };std::list<int> List2 = { 4, 5 };List1.swap(List2);std::cout << "List1: ";printList(List1);std::cout << "List2: ";printList(List2);
}
assign
将值赋给容器
#include <iostream>
#include <list>
#include <string>int main()
{std::list<char> List;// 使用Lambda表达式打印list中的元素auto print_list = [&](){for (char c : List){std::cout << c << ' ';}std::cout << '\n';};List.assign(5, 'a');print_list();const std::string extra = "hello world";List.assign(extra.begin(), extra.end());print_list();List.assign({ 'C', '+', '+', '1', '1' });print_list();
}
操作
sort
对元素进行排序
有两种重载形式。第一种是升序排序，第2种是按照自定义的比较规则排序。
void sort();template< class Compare >
void sort( Compare comp );#include <functional> //std::greater<int>()
#include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List{ 8, 7, 5, 9, 0, 1, 3, 2, 6, 4 };std::cout << "初始：";printList(List);List.sort();std::cout << "升序：";printList(List);List.sort(std::greater<int>());std::cout << "降序：";printList(List);
}
merge
合并两个有序列表，准确来说是按照一定比较规则将指定列表中的元素剪切至原列表中。
默认比较方式
void merge( list& other );
void merge( list&& other );
other：要合并到当前列表的另一个 std::list 对象，可以是左值引用或右值引用。
功能：将 other 列表中的所有元素合并到当前列表中，合并后 other 列表会变为空。两个列表都必须按照默认的比较规则（通常是 operator<）进行排序。
示例代码：
#include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List1 = { 5, 9, 1, 3, 3 };std::list<int> List2 = { 8, 7, 2, 3, 4, 4 };List1.sort();List2.sort();std::cout << "list1："; printList(List1);std::cout << "list2："; printList(List2);List1.merge(List2);std::cout << "合并后的list1："; printList(List1);std::cout << "合并后的list2："; printList(List2);
}
自定义比较方式
template< class Compare >
void merge( list& other, Compare comp );
template< class Compare >
void merge( list&& other, Compare comp );
other：要合并到当前列表的另一个 std::list 对象，可以是左值引用或右值引用。
comp：一个二元比较函数，用于定义元素的排序规则。该函数接受两个参数，返回一个布尔值，表示第一个参数是否应该排在第二个参数之前（如果返回的值为true，那么第一个参数要在第二个参数前）。
功能描述：将 other 列表中的所有元素合并到当前列表中，合并后 other 列表会变为空。两个列表都必须按照 comp 指定的比较规则进行排序。
示例代码：
#include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}// 自定义比较函数，按降序排序
bool greater(int a, int b)
{return a > b;
}int main()
{std::list<int> List1 = { 5, 9, 1, 3, 3 };std::list<int> List2 = { 8, 7, 2, 3, 4, 4 };List1.sort(greater);List2.sort(greater);std::cout << "list1："; printList(List1);std::cout << "list2："; printList(List2);List1.merge(List2, greater);std::cout << "合并后的list1："; printList(List1);std::cout << "合并后的list2："; printList(List2);
}
splice
从另一个 list 中移动元素
转移整个列表
void splice(const_iterator position, list& other);
void splice(const_iterator position, list&& other);
position：这是一个常量迭代器，它指定了在目标列表中插入元素的位置。
other：这是要转移元素的源列表，可以是左值引用或者右值引用。
功能：把 other 列表中的所有元素转移到目标列表的 position 位置之前，转移完成后，other 列表会变为空。
转移单个元素
void splice(const_iterator position, list& other, const_iterator it);
void splice(const_iterator position, list&& other, const_iterator it);
参数说明：
position：常量迭代器，指定在目标列表中插入元素的位置。
other：源列表，可以是左值引用或者右值引用。
it：常量迭代器，指向 other 列表中要转移的单个元素。
功能描述：把 other 列表中 it 所指向的元素转移到目标列表的 position 位置之前，转移后，该元素会从 other 列表中移除。
转移元素范围
void splice(const_iterator position, list& other, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& other, const_iterator first, const_iterator last);
参数说明：
position：常量迭代器，指定在目标列表中插入元素的位置。
other：源列表，可以是左值引用或者右值引用。
first 和 last：常量迭代器，定义了要转移的元素范围 [first, last)，也就是包含 first 指向的元素，但不包含 last 指向的元素。
功能描述：把 other 列表中 [first, last) 范围内的元素转移到目标列表的 position 位置之前，转移后，这些元素会从 other 列表中移除。
代码示例
#include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List1 = { 1, 2, 3 };std::list<int> List2 = { 4, 5, 6 };// 把 List2 的所有元素转移到 List1 的开头List1.splice(List1.begin(), List2);std::cout << "List1: "; printList(List1);std::cout << "List2: "; printList(List2);std::list<int> List3 = { 1, 2, 3 };std::list<int> List4 = { 4, 5, 6 };// 把 List4 的第二个元素转移到 list1 的开头List3.splice(List3.begin(), List4, ++List4.begin());std::cout << "List3: "; printList(List3);std::cout << "List4: "; printList(List4);std::list<int> List5 = { 1, 2, 3, 4, 5, 6 };std::list<int> List6 = { 7, 8, 9 };// 把 List5 的第二个到倒数第二个之间的元素转移到 list6 的开头List6.splice(List6.begin(), List5, ++List5.begin(), --List5.end());std::cout << "List5: "; printList(List5);std::cout << "List6: "; printList(List6);
}
remove
移除列表中所有值等于指定值的元素
C++20前，该方法没有返回值； C++20及C++20后，该方法返回移除的数量。
#include <list>
#include <iostream>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 100, 2, 3, 10, 1, 11, -1, 12 };auto count = List.remove(1);std::cout << "移除了 " << count << " 个等于 1 的元素\n";printList(List);
}
remove_if
移除满足特定标准的元素
C++20前，该方法没有返回值； C++20及C++20后，该方法返回移除的数量。
void remove_if( UnaryPredicate p );
size_type remove_if( UnaryPredicate p );p：一个一元谓词函数（关于谓词函数的相关知识可以查看：C++杂项（更新中）_std::operator==<std::vector<std::vector<int, std::-CSDN博客），接受列表元素类型的参数，返回一个布尔值。如果返回 true，则表示该元素需要被移除。
#include <list>
#include <iostream>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}// 定义一个一元谓词函数，判断元素是否为奇数
bool isOdd(int num)
{return num % 2 != 0;
}int main()
{std::list<int> List = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };// 移除所有奇数元素List.remove_if(isOdd);// 输出移除元素后的列表printList(List);
}
reverse
逆转容器中的元素顺序
List.reverse()unique
从列表中移除连续重复的元素，仅保留每个连续重复元素序列中的第一个元素
默认比较方式
void unique(); (C++20 前)
size_type unique(); (C++20 起)返回值：移除的元素数量。
功能：使用 operator== 来比较相邻的元素，移除所有连续重复的元素，只保留每个连续重复元素序列中的第一个元素。
#include <iostream>
#include <list>// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, 1, 2, 2, 2, 3, 3, 1, 1 };List.unique();printList(List);
}
自定义比较方式
template< class BinaryPredicate >
void unique( BinaryPredicate p ); (C++20 前)template< class BinaryPredicate >
size_type unique( BinaryPredicate p ); (C++20 起)p：一个二元谓词函数 （关于谓词函数的相关知识可以查看：C++杂项（更新中）_std::operator==<std::vector<std::vector<int, std::-CSDN博客），用于比较相邻的元素。该函数接受两个参数，返回一个布尔值，表示这两个参数是否被视为相等。
返回值：移除的元素数量。
功能：使用用户提供的二元谓词 p 来比较相邻的元素，移除所有被 p 判断为相等的连续元素，只保留每个连续重复元素序列中的第一个元素。
#include <iostream>
#include <list>// 自定义二元谓词，判断两个元素的绝对值是否相等
bool absEqual(int a, int b)
{return std::abs(a) == std::abs(b);
}// 打印List中的元素
void printList(const std::list<int>& List)
{for (int num : List){std::cout << num << " ";}std::cout << std::endl;
}int main()
{std::list<int> List = { 1, -1, 2, 2, -2, 3, 3, -1, 1 };List.unique(absEqual);printList(List);
}
参考与引用
C++ STL list 容器详解-CSDN博客
C++——list的简介及使用_c++ list-CSDN博客
std::list - cppreference.com
百度安全验证
未完待续
写出容器方法的底层实现原理和复杂度。
未完待续
