std::list是 STL 中的双向链表容器,要想使用要包含头文件“#includelist”你可以把它理解成每个元素除了存自己的值还保存前一个和后一个元素的位置所以它特别适合频繁插入、删除的场景。list的底层通常是双向链表不是连续内存这意味着不能像vector那样随机访问在任意已知位置插入、删除很方便1 基本定义方式listint lst;指定大小listint lst(5);指定大小和初值listint lst(5, 10); 10 10 10 10 10列表初始化listint lst {1, 2, 3, 4, 5};拷贝构造listint lst2(lst1);2 常用操作尾插、头插listint lst; lst.push_back(10); lst.push_back(20); 10 20 lst.push_front(5); 5 10 20尾删、头删lst.pop_back(); 删除最后一个元素 lst.pop_front(); 删除第一个元素访问首尾元素前提是链表非空cout lst.front() endl; cout lst.back() endl;获取大小cout lst.size() endl;判断是否为空if (lst.empty()) { cout empty endl; }清空lst.clear();3 遍历 list因为list不支持下标访问所以通常用范围 forfor (int x : lst) { cout x ; }迭代器for (auto it lst.begin(); it ! lst.end(); it) { cout *it ; }插入和删除list的强项就在这里insert()在某个迭代器位置前插入元素listint lst {1, 2, 3}; 1 2 3 auto it lst.begin(); it; // 指向 2 lst.insert(it, 100); 1 100 2 3erase()删除某个位置的元素auto it lst.begin(); it; // 指向第二个元素 lst.erase(it);erase()删除整个区间lst.erase(lst.begin(), lst.end());4 list 特有/常用操作remove()删除所有值等于某个值的元素listint lst {1, 2, 3, 2, 4}; 1, 2, 3, 2, 4 lst.remove(2); 1 3 4unique()删除连续重复元素只保留一个listint lst {1, 1, 2, 2, 2, 3, 1}; lst.unique(); 1 2 3 1 如果想全局去重通常先排序再 unique()sort()链表自带排序listint lst {4, 2, 5, 1, 3}; lst.sort(); 1 2 3 4 5也可以自定义排序规则lst.sort(greaterint()); 降序排序 注意 list 不能直接用 std::sort 因为 std::sort 需要随机访问迭代器 list 只有双向迭代器所以要用 lst.sort()reverse()反转链表lst.reverse();merge()合并两个有序链表listint a {1, 3, 5}; listint b {2, 4, 6}; a.merge(b); 注意要求两个链表原本有序否则结果不正确。 结果 a 变成 1 2 3 4 5 6 b 变成空splice()把一个链表中的节点直接转移到另一个链表中listint a {1, 2, 3}; listint b {10, 20}; auto it a.begin(); it; // 指向2 a.splice(it, b); 结果 a: 1 10 20 2 3 b: 空5 list 不支持的操作不能下标访问 lst[0]; // 错 不能 at() lst.at(0); // 错 不能用 std::sort(lst.begin(), lst.end()) sort(lst.begin(), lst.end()); // 错 应该写lst.sort();6 时间复杂度整体上插删快、查找慢、不能随机访问7 和vector的对比所以一般来说如果你主要是访问、遍历、尾部添加用vector如果你主要是频繁在中间/头部插入删除考虑list不过在实际开发中vector用得通常远比list多。8 使用list的注意点1很多人一听链表插删快就以为list很强但如果你要先“找到那个位置”往往还是要遍历成本是 O(n)。举例假设有 100000 个元素你要删“第 100 个元素”。对于listlst[99] 是错的因为 list 不支持随机访问 你只能这样去查找 auto it lst.begin(); for (int i 0; i 99; i) { it; } 查完再删除 lst.erase(it); 这里分两步 第一步找到第 100 个元素。要从头走 99 次复杂度 O(n) 第二步删除它。删除本身复杂度 O(1) 所以总复杂度O(n) O(1) O(n)对于vector:vector 可以直接定位第 100 个元素 v.erase(v.begin() 99); 第一步定位。v.begin() 99 是随机访问复杂度 O(1) 第二步删除。但删除后面元素要整体前移所以是 O(n) 所以总复杂度也是O(1) O(n) O(n)总体来说要想删除元素要先查找元素。如果list中已知要删除元素的迭代器位置那么list删除是o(1)很快。但如果不知道list要查找元素是o(n)。而vector慢在删除元素查找很快因为可以随机访问。所以删除元素list不一定比vector快2list最不适合做的事就是频繁按下标访问。优点迭代器一般比较稳定插入其他元素时已有元素的迭代器通常不失效删除某个元素时只有指向该元素的迭代器失效即原来指向它的迭代器不能再用了。删除时的正确做法接住 erase() 的返回值 listint lst {1, 2, 3}; auto it next(lst.begin()); // 指向2 it lst.erase(it); // 删除2返回指向3的迭代器 cout *it endl; // 39 list优缺点优点头部、尾部插入删除效率高在任意位置插入删除效率高已知该位置迭代器时插入删除一般不会导致其他元素位置整体搬移迭代器在很多插删操作后仍然有效被删元素除外缺点不支持随机访问不能lst[3]不能直接用at()查找某个位置慢额外指针开销较大list的每个元素除了存你真正的数据还要额外存链接前后节点的指针所以比vector更占内存。