C++ STL list基本用法

C++ STL list基本用法

内容

好的，我来详细讲解C++ STL中的std::list用法及其优势，同时对比手写链表的差异。内容分三个部分：

一、STL list 核心用法

1. 基本操作

#include

// 初始化

std::list myList; // 空链表

std::list myList2(5, 100); // 5个元素，每个都是100

std::list copiedList(myList2); // 拷贝构造

// 插入元素

myList.push_front(10); // 头部插入

myList.push_back(20); // 尾部插入

auto it = myList.begin();

advance(it, 1); // 移动迭代器

myList.insert(it, 15); // 在第二个位置插入15

// 删除元素

myList.pop_front(); // 删除头部

myList.pop_back(); // 删除尾部

myList.erase(it); // 删除迭代器指向元素

myList.remove(100); // 删除所有值为100的元素

// 遍历

for(auto& num : myList) { /* 范围for循环 */ }

for(auto it = myList.begin(); it != myList.end(); ++it) { /* 迭代器遍历 */ }

2. 关键特性

// 合并排序的链表（要求两个链表已排序）

std::list listA {1, 3, 5};

std::list listB {2, 4, 6};

listA.merge(listB); // listA变为[1,2,3,4,5,6]，listB为空

// 排序（时间复杂度 O(n log n)）

myList.sort();

// 去重（需先排序）

myList.unique();

// 反转链表

myList.reverse();

3. 迭代器失效规则

安全操作：

insert 不会使其他迭代器失效

erase 仅使被删除元素的迭代器失效

二、STL list 对比手写链表的六大优势

特性

STL list

手写链表

内存管理

自动分配/释放，无内存泄漏

需手动管理，易出现内存错误

异常安全

严格保证操作原子性

需自行实现回滚逻辑

算法集成

内置sort/merge/unique等算法

需重新实现基础算法

迭代器支持

双向迭代器，支持STL算法

通常仅实现基础遍历

时间复杂度

插入/删除 O(1)，排序 O(n log n)

需自行优化算法效率

代码健壮性

经过数十年工业级验证

自实现代码可能存在隐藏BUG

典型场景对比：插入10万元素

// STL list（简洁安全）

std::list stlList;

for(int i=0; i<100000; ++i) {

stlList.push_back(i);

}

// 手写链表（易出错示例）

struct Node {

int data;

Node* next;

Node(int d) : data(d), next(nullptr) {}

};

Node* head = nullptr;

Node* tail = nullptr;

for(int i=0; i<100000; ++i) {

Node* newNode = new Node(i);

if(!tail) {

head = tail = newNode;

} else {

tail->next = newNode; // 容易忘记维护tail指针

tail = newNode; // 若此处抛出异常会导致内存泄漏

}

}

// 必须额外编写析构函数释放内存

三、何时选择手写链表？

尽管STL list优势明显，但在以下特殊场景可能需要手写：

极致性能需求：需要实现lock-free链表等高级结构

特殊内存管理：使用内存池或特定硬件内存区域

定制数据结构：例如跳跃链表、异或链表等变种

总结建议

优先使用STL list：适用于99%的常规场景

性能关键处验证：若怀疑STL性能，先用profiler测试

学习价值：手写链表可作为学习数据结构的练习，但生产环境慎用

通过STL list可以显著提升开发效率，同时避免大量底层错误。其内置算法和异常安全特性使其成为C++开发中最可靠的顺序容器之一。