c++中如何使用list链表_c++ list容器插入与删除元素【汇总】

std::list插入需按场景选择：push_back/push_front用于头尾O(1)插入，insert依赖迭代器实现中间插入；删除用erase（按迭代器）或成员remove（按值）；迭代器仅在所指节点被删时失效；实际中vector/deque常优于list。

list 插入元素：用 push_back、push_front、insert 区分场景

插入不等于“随便塞”，std::list 是双向链表，push_back 和 push_front 是 O(1) 操作，适合在头尾追加；中间插入必须用 insert，但它依赖迭代器，不能用下标。

• push_back(x)：末尾插入，最常用，无性能顾虑
• push_front(x)：开头插入，同样高效，适合实现栈或队列头部操作
• insert(it, x)：在迭代器 it 指向位置前插入，it 必须合法（不能是 end() 以外的无效值）
• 想在第 N 个位置插入？得先用 std::next(begin(), N) 移动迭代器，list 不支持随机访问

#include 
#include 
int main() {
    std::list lst = {1, 2, 3};
    lst.push_back(4);        // {1,2,3,4}
    lst.push_front(0);       // {0,1,2,3,4}
    auto it = std::next(lst.begin(), 2); // 指向 2
    lst.insert(it, 99);      // {0,1,99,2,3,4}
}

list 删除元素：避免用错 erase 和 remove

erase 是容器成员函数，按迭代器或范围删除，返回下一个有效迭代器；remove 是算法（也存在于 list 成员中），按值删除所有匹配项，不移动迭代器——但注意：标准库 std::remove 对

list 无效，必须用 lst.remove(x) 成员版。

• erase(it)：删单个，返回下一个迭代器，循环中删除要接住返回值，否则迭代器失效
• erase(first, last)：删区间，last 是开区间终点，erase(begin(), end()) 清空整个 list
• lst.remove(x)：成员函数，删所有等于 x 的节点，比 erase + find 组合更安全高效
• 误用 std::remove(lst.begin(), lst.end(), x) 不会生效，因为那是“重排+返回新尾”，对链表无意义

std::list lst = {1, 2, 3, 2, 4, 2};
// ✅ 正确：成员 remove 删所有 2
lst.remove(2);  // {1,3,4}

// ✅ 正确：erase 遍历时接返回值
for (auto it = lst.begin(); it != lst.end(); ) {
    if (*it == 3) it = lst.erase(it);  // 返回下一个
    else ++it;
}

list 迭代器失效规则：只在被删节点上失效，其余全安全

这是 list 和 vector 最关键区别：只要没删掉某个节点，指向它的迭代器就永远有效。插入、移动、排序都不让它失效。唯一失效场景就是该节点被 erase 或 remove 掉。

• 插入任意位置不影响现有迭代器
• sort()、merge()、splice() 全部不导致迭代器失效
• 但一旦调用 erase(it)，那个 it 就不能再用，哪怕只是读 *it 都是未定义行为
• 用 remove(x) 后，所有指向被删节点的迭代器全部失效，但其他节点的迭代器照常可用

性能与替代建议：别为“链表”而链表

std::list 真正优势只有频繁首尾增删 + 迭代器长期持有 + 不需要缓存友好性。实际项目中，多数所谓“需要链表”的场景，std::vector 配合 erase-remove idiom 或 std::deque 更快且内存更紧凑。

• 随机访问需求？立刻换 vector 或 deque
• 插入/删除集中在两端？deque 通常比 list 快 2–5 倍（局部性更好）
• 需要稳定迭代器但操作不频繁？考虑 vector + 索引映射，或 std::forward_list（单向、更轻量）
• list 每个节点额外 2 个指针开销，小对象时内存浪费明显

真正难的不是记住怎么写 insert，而是判断此刻是否真该用 list。很多崩溃和慢，源于把 list 当成“万能动态结构”来用。