1. list容器概述
list是C++标准模板库(STL)中提供的一种序列容器,它基于双向链表数据结构实现。与vector和array等连续存储的容器不同,list的元素在内存中是非连续存储的,每个元素都包含指向前驱和后继节点的指针。
提示:list特别适合频繁插入和删除操作的场景,因为它的时间复杂度是O(1),而vector在中间插入删除的时间复杂度是O(n)。
1.1 list的核心特性
list的主要特点包括:
- 双向链表结构:每个节点包含指向前驱和后继的指针
- 动态内存分配:不需要预先分配固定大小的内存空间
- 非连续存储:元素在内存中分散存储,通过指针连接
- 迭代器稳定性:插入操作不会使现有迭代器失效(删除操作会使被删除元素的迭代器失效)
1.2 list与vector的对比
| 特性 | list | vector |
|---|---|---|
| 存储结构 | 双向链表 | 动态数组 |
| 随机访问 | 不支持,O(n) | 支持,O(1) |
| 插入删除 | 任意位置O(1) | 尾部O(1),其他位置O(n) |
| 内存使用 | 每个元素额外存储两个指针 | 仅存储元素,可能有预留空间 |
| 迭代器类型 | 双向迭代器 | 随机访问迭代器 |
| 缓存友好性 | 差(非连续存储) | 好(连续存储) |
在实际开发中,选择list还是vector需要根据具体场景:
- 如果需要频繁在中间位置插入删除元素,list更合适
- 如果需要快速随机访问元素,vector更合适
- 如果内存占用是关键考量,vector通常更节省内存
2. list的迭代器详解
2.1 迭代器基本概念
迭代器是STL中用于遍历容器元素的抽象概念,它提供了统一的访问接口,使得算法可以独立于具体容器实现。list的迭代器属于双向迭代器,支持以下操作:
- 递增(++):移动到下一个元素
- 递减(--):移动到上一个元素
- 解引用(*):访问当前元素
- 成员访问(->):访问当前元素的成员
- 相等比较(==, !=):判断两个迭代器是否指向同一元素
2.2 list迭代器的实现原理
list迭代器的底层实现是一个封装了节点指针的类,它重载了各种操作符来模拟指针行为。下面是简化后的迭代器类框架:
cpp复制template<class T>
struct ListIterator {
typedef ListNode<T>* NodePtr;
NodePtr current; // 指向当前节点的指针
// 解引用操作符重载
T& operator*() {
return current->value;
}
// 前置递增操作符重载
ListIterator& operator++() {
current = current->next;
return *this;
}
// 后置递增操作符重载
ListIterator operator++(int) {
ListIterator tmp = *this;
++(*this);
return tmp;
}
// 相等比较操作符重载
bool operator==(const ListIterator& other) const {
return current == other.current;
}
// 不等比较操作符重载
bool operator!=(const ListIterator& other) const {
return !(*this == other);
}
};
2.3 const迭代器的实现技巧
为了同时支持普通迭代器和const迭代器,STL采用了模板参数化的设计:
cpp复制template<class T, class Ref, class Ptr>
struct ListIterator {
// ...
Ref operator*() { return current->value; }
Ptr operator->() { return ¤t->value; }
// ...
};
// 在list类中定义迭代器类型
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
这种设计避免了代码重复,通过模板参数区分了普通迭代器和const迭代器。
3. list的核心接口解析
3.1 元素访问接口
list提供了一系列元素访问接口,但不像vector那样支持随机访问:
cpp复制// 返回第一个元素的引用
T& front();
const T& front() const;
// 返回最后一个元素的引用
T& back();
const T& back() const;
注意:对空list调用front()或back()是未定义行为,可能导致程序崩溃。
3.2 插入和删除接口
list的插入和删除操作是其核心优势所在:
cpp复制// 在指定位置前插入元素
iterator insert(iterator pos, const T& value);
// 在尾部插入元素
void push_back(const T& value);
// 在头部插入元素
void push_front(const T& value);
// 删除指定位置的元素
iterator erase(iterator pos);
// 删除尾部元素
void pop_back();
// 删除头部元素
void pop_front();
3.3 emplace_back与push_back的区别
emplace_back是C++11引入的新接口,它支持就地构造元素:
cpp复制// 传统push_back需要先构造对象再拷贝/移动
list.push_back(MyClass(arg1, arg2));
// emplace_back直接在容器内构造对象
list.emplace_back(arg1, arg2);
emplace_back的优势在于:
- 避免了临时对象的构造和析构
- 支持隐式类型转换
- 对于不可拷贝/移动的类型也能使用
3.4 splice接口详解
splice是list特有的接口,用于在list之间转移节点:
cpp复制// 将整个other转移到当前list的pos位置前
void splice(iterator pos, list& other);
// 将other中的it元素转移到当前list的pos位置前
void splice(iterator pos, list& other, iterator it);
// 将other中的[first, last)范围内的元素转移到当前list的pos位置前
void splice(iterator pos, list& other, iterator first, iterator last);
splice操作的特点:
- 时间复杂度O(1),非常高效
- 不会导致元素的拷贝或移动
- 被转移的元素迭代器仍然有效
- 操作后,other中的相应元素被移除
4. list的排序效率问题
4.1 list::sort的实现
list提供了自己的sort成员函数,而不是使用通用的std::sort算法,这是因为:
- std::sort需要随机访问迭代器,而list只提供双向迭代器
- list::sort可以利用链表特性实现更高效的归并排序
list::sort的时间复杂度是O(n log n),空间复杂度是O(1)。
4.2 与vector排序的性能对比
虽然list::sort专门为链表优化,但在实际测试中,将list元素拷贝到vector中排序再拷贝回来,往往比直接使用list::sort更快。原因包括:
- 缓存局部性:vector连续存储更利于CPU缓存
- 算法优化:std::sort针对随机访问做了大量优化
- 减少指针操作:链表排序涉及大量指针操作,开销较大
性能对比示例代码:
cpp复制void benchmarkSort() {
const int N = 100000;
std::list<int> lst;
std::vector<int> vec;
// 填充随机数据
for (int i = 0; i < N; ++i) {
int val = rand();
lst.push_back(val);
vec.push_back(val);
}
// 测试list排序
auto start = std::chrono::high_resolution_clock::now();
lst.sort();
auto end = std::chrono::high_resolution_clock::now();
std::cout << "list::sort time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms\n";
// 测试vector排序
start = std::chrono::high_resolution_clock::now();
std::sort(vec.begin(), vec.end());
end = std::chrono::high_resolution_clock::now();
std::cout << "std::sort time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms\n";
// 测试拷贝到vector排序再拷贝回来
std::list<int> lst2;
for (int i = 0; i < N; ++i) {
lst2.push_back(rand());
}
start = std::chrono::high_resolution_clock::now();
std::vector<int> temp(lst2.begin(), lst2.end());
std::sort(temp.begin(), temp.end());
lst2.assign(temp.begin(), temp.end());
end = std::chrono::high_resolution_clock::now();
std::cout << "copy-sort-copy time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms\n";
}
5. 手写简化版list实现
5.1 节点结构设计
list的基本构建块是节点,每个节点包含数据和前后指针:
cpp复制template<typename T>
struct ListNode {
T value;
ListNode* prev;
ListNode* next;
ListNode(const T& val = T())
: value(val), prev(nullptr), next(nullptr) {}
};
5.2 迭代器实现
迭代器需要封装节点指针并重载相关操作符:
cpp复制template<typename T>
class ListIterator {
ListNode<T>* current;
public:
typedef T value_type;
typedef T& reference;
typedef T* pointer;
typedef std::bidirectional_iterator_tag iterator_category;
explicit ListIterator(ListNode<T>* node = nullptr) : current(node) {}
reference operator*() const { return current->value; }
pointer operator->() const { return ¤t->value; }
ListIterator& operator++() {
current = current->next;
return *this;
}
ListIterator operator++(int) {
ListIterator tmp = *this;
++(*this);
return tmp;
}
ListIterator& operator--() {
current = current->prev;
return *this;
}
ListIterator operator--(int) {
ListIterator tmp = *this;
--(*this);
return tmp;
}
bool operator==(const ListIterator& other) const {
return current == other.current;
}
bool operator!=(const ListIterator& other) const {
return !(*this == other);
}
};
5.3 list类框架
list类需要管理节点生命周期并提供容器接口:
cpp复制template<typename T>
class List {
ListNode<T>* head; // 哨兵节点
size_t count;
public:
typedef ListIterator<T> iterator;
typedef const ListIterator<T> const_iterator;
List() : count(0) {
head = new ListNode<T>();
head->prev = head->next = head;
}
~List() {
clear();
delete head;
}
iterator begin() { return iterator(head->next); }
const_iterator begin() const { return const_iterator(head->next); }
iterator end() { return iterator(head); }
const_iterator end() const { return const_iterator(head); }
bool empty() const { return count == 0; }
size_t size() const { return count; }
void push_back(const T& value) {
insert(end(), value);
}
void push_front(const T& value) {
insert(begin(), value);
}
iterator insert(iterator pos, const T& value) {
ListNode<T>* newNode = new ListNode<T>(value);
ListNode<T>* current = pos.current;
newNode->prev = current->prev;
newNode->next = current;
current->prev->next = newNode;
current->prev = newNode;
++count;
return iterator(newNode);
}
iterator erase(iterator pos) {
ListNode<T>* toDelete = pos.current;
iterator ret(toDelete->next);
toDelete->prev->next = toDelete->next;
toDelete->next->prev = toDelete->prev;
delete toDelete;
--count;
return ret;
}
void clear() {
while (!empty()) {
erase(begin());
}
}
};
5.4 迭代器失效问题
list的迭代器失效规则:
- 插入操作不会使任何迭代器失效
- 删除操作会使被删除元素的迭代器失效,其他迭代器不受影响
- splice操作不会使任何迭代器失效,包括被转移元素的迭代器
6. list的高级特性与技巧
6.1 隐式类型转换构造
C++11引入了initializer_list支持,使得list可以方便地初始化:
cpp复制list<int> lst = {1, 2, 3, 4, 5};
实现原理是在list类中添加如下构造函数:
cpp复制List(std::initializer_list<T> init) : List() {
for (const auto& item : init) {
push_back(item);
}
}
6.2 按需实例化特性
模板类的一个特点是按需实例化,即只有在实际使用时才会生成具体代码。这意味着:
- 模板中的语法错误在未使用时不会被发现
- 可以减少不必要的代码生成
- 可以编写更通用的模板代码
例如:
cpp复制template<typename Container>
void printContainer(const Container& c) {
auto it = c.begin();
while (it != c.end()) {
*it += 10; // 这个错误在使用const容器前不会被发现
++it;
}
// ...
}
// 使用时才会发现错误
const list<int> clst = {1, 2, 3};
printContainer(clst); // 编译错误:尝试修改const元素
6.3 list的性能优化技巧
- 批量插入优化:预先分配节点内存
- 自定义分配器:针对特定场景优化内存分配
- 移动语义:对于大对象使用移动而非拷贝
- 避免不必要的排序:考虑是否真的需要排序
- 选择合适的容器:评估是否真的需要list的特性
7. list在实际开发中的应用场景
7.1 适合使用list的场景
- 需要频繁在中间位置插入删除元素
- 需要保证插入删除操作不使其他元素的迭代器失效
- 元素较大,移动开销大
- 需要稳定的元素地址(指针/引用不会失效)
7.2 不适合使用list的场景
- 需要频繁随机访问元素
- 内存受限的环境(list有较高的内存开销)
- 对缓存友好性要求高的场景
- 元素较小且数量巨大
7.3 list的替代方案
- vector:适合随机访问和尾部操作
- deque:适合头部和尾部操作
- forward_list:更节省内存的单向链表
- 自定义数据结构:针对特定需求优化
在实际项目中,我经常遇到需要在中间位置频繁插入删除元素的场景,这时list就显示出它的优势。例如在实现一个文本编辑器时,每一行文本可以使用list来存储,因为用户可能在任意位置插入或删除字符。不过要注意,对于小型元素或不需要频繁中间操作的情况,vector通常是更好的选择。