list内
std::list 是 C++ 标准模板库（STL）中的一个双向链表容器。它是一种序列式容器，支持高效的插入和删除操作，特别是在非连续存储的情况下。
1. std::list 的主要特点
std::list 的主要特点双向链表：
std::list是一个双向链表，链表中的每个元素都包含指向前一个和后一个元素的指针。这样可以使得在链表中间插入或删除元素的操作非常高效（O(1) 时间复杂度）。随机访问慢：由于链表不支持随机访问，不能通过下标直接访问元素，因此与
std::vector相比，访问链表中的元素效率较低（O(n) 时间复杂度）。适用于频繁插入/删除的场景：当应用程序频繁需要在序列中间进行插入或删除操作时，
std::list是一个很好的选择。
2. std::list 的常用方法
std::list 的常用方法2.1 插入元素
push_back(const T& value)：在链表的尾部插入元素value。std::list<int> myList; myList.push_back(10); // 在尾部插入 10 myList.push_back(20); // 在尾部插入 20push_front(const T& value)：在链表的头部插入元素value。myList.push_front(5); // 在头部插入 5insert(iterator position, const T& value)：在迭代器position所指向的位置之前插入元素value。auto it = myList.begin(); std::advance(it, 1); // 将迭代器移动到第二个元素的位置 myList.insert(it, 15); // 在第二个元素之前插入 15emplace(iterator position, Args&&... args)：在迭代器position所指向的位置原位构造元素。myList.emplace(myList.begin(), 100); // 在头部插入 100
2.2 删除元素
pop_back()：移除链表尾部的元素。myList.pop_back(); // 删除尾部元素pop_front()：移除链表头部的元素。myList.pop_front(); // 删除头部元素erase(iterator position)：删除迭代器position所指向的元素。auto it = myList.begin(); std::advance(it, 1); // 将迭代器移动到第二个元素 myList.erase(it); // 删除第二个元素clear()：删除链表中的所有元素。myList.clear(); // 清空链表
2.3 访问元素
front()：返回链表头部的元素。int firstElem = myList.front();back()：返回链表尾部的元素。int lastElem = myList.back();
2.4 遍历元素
使用迭代器遍历：
for (auto it = myList.begin(); it != myList.end(); ++it) { std::cout << *it << " "; }使用范围循环遍历：
for (int elem : myList) { std::cout << elem << " "; }
2.5 其他操作
size()：返回链表中的元素个数。std::cout << "Size: " << myList.size() << std::endl;empty()：检查链表是否为空。如果链表为空，则返回true。if (myList.empty()) { std::cout << "List is empty" << std::endl; }sort()：对链表中的元素进行排序。myList.sort(); // 升序排序reverse()：将链表中的元素顺序反转。myList.reverse(); // 反转链表merge(list<T>& otherList)：将otherList与当前链表合并，合并后otherList变为空。std::list<int> otherList = {3, 6, 9}; myList.merge(otherList);unique()：移除链表中连续相等的重复元素。myList.unique(); // 移除连续相同的元素
3. 示例代码
#include <iostream>
#include <list>
int main() {
std::list<int> myList = {10, 20, 30};
// 插入元素
myList.push_back(40); // 尾部插入
myList.push_front(5); // 头部插入
// 遍历链表
for (const auto& elem : myList) {
std::cout << elem << " ";
}
std::cout << std::endl;
// 访问头尾元素
std::cout << "Front: " << myList.front() << std::endl;
std::cout << "Back: " << myList.back() << std::endl;
// 删除元素
myList.pop_back(); // 删除尾部元素
myList.pop_front(); // 删除头部元素
// 排序和反转
myList.sort();
myList.reverse();
// 遍历排序和反转后的链表
for (const auto& elem : myList) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}4. std::list 的常见应用场景
std::list 的常见应用场景1. 频繁插入/删除操作
当需要频繁在序列的头部或中间进行插入和删除操作时，std::list 的双向链表结构能够提供常数时间的效率，而不像 std::vector 那样会引发元素移动和内存重新分配。
2. 任务队列管理
在任务调度系统中，可能需要随时对队列中的任务进行插入或删除操作。std::list 允许在任意位置高效地插入或移除任务。
3. 链表操作
有时在处理链表结构时，手动维护指针比较复杂，而使用 std::list 能够提供链表的所有功能（如插入、删除、排序、反转等）并且更安全。
4. 需要动态增长的序列
当序列的大小不确定并且可能频繁变化时，std::list 可以通过其链表特性高效地扩展而不需要像 std::vector 那样预分配或重新分配内存。
5. 总结
push_back()
在链表尾部插入元素
push_front()
在链表头部插入元素
pop_back()
删除链表尾部的元素
pop_front()
删除链表头部的元素
insert()
在指定位置插入元素
erase()
删除指定位置的元素
front()
返回链表头部的元素
back()
返回链表尾部的元素
size()
返回链表中的元素个数
empty()
检查链表是否为空
sort()
对链表中的元素进行排序
reverse()
反转链表中的元素顺序
merge()
合并两个链表
unique()
移除连续的重复元素
std::list 适合在需要频繁插入和删除操作的场景下使用，尤其是在不需要随机访问的情况下，其效率比 std::vector 更高。
Last updated