C++ 序列容器详解 - 元素码农

发布时间: 2025-03-23 10:17

↑

# C++ 序列容器详解

序列容器是C++标准库中最基础和常用的容器类型,它们按照线性的方式存储和组织元素。本文将详细介绍C++中的主要序列容器类型,包括它们的特点、实现原理和使用场景。

## 主要序列容器类型

### vector

vector是最常用的序列容器,它在内存中以连续数组的方式存储元素。

#### 特点
- 随机访问元素 O(1)
- 在末尾添加/删除元素 均摊O(1) 
- 在中间插入/删除元素 O(n)
- 动态扩容时需要重新分配内存并复制元素

#### 实现原理
```cpp
template <class T, class Allocator = allocator<T>>
class vector {
    T* _M_start;         // 指向数组起始位置
    T* _M_finish;        // 指向最后一个元素的下一个位置
    T* _M_end_of_storage; // 指向分配的内存末尾
    // ...
};
```

#### 使用示例
```cpp
#include <vector>

std::vector<int> vec = {1, 2, 3, 4, 5};

// 添加元素
vec.push_back(6);  // O(1)

// 随机访问
int third = vec[2];  // O(1)

// 插入元素
vec.insert(vec.begin() + 2, 10);  // O(n)
```

### deque

deque(double-ended queue)是一个双端队列容器,支持在两端高效地插入和删除元素。

#### 特点
- 随机访问元素 O(1)
- 在两端添加/删除元素 O(1)
- 在中间插入/删除元素 O(n)
- 内存不要求连续,通过多个固定大小的块来存储

#### 实现原理
```cpp
template <class T, class Allocator = allocator<T>>
class deque {
    struct _Deque_iterator {
        T* cur;    // 当前元素
        T* first;  // 当前缓冲区的起始
        T* last;   // 当前缓冲区的结束
        T** node;  // 指向map中的当前节点
    };
    T** _M_map;      // 控制中心
    size_t _M_map_size; // map大小
    // ...
};
```

#### 使用示例
```cpp
#include <deque>

std::deque<int> dq = {1, 2, 3};

// 两端操作
dq.push_front(0);  // 在前端添加
dq.push_back(4);   // 在后端添加

// 随机访问
int val = dq[2];  // O(1)
```

### list

list是一个双向链表容器,支持在任何位置常数时间的插入和删除操作。

#### 特点
- 不支持随机访问
- 在任何位置插入/删除元素 O(1)
- 内存不要求连续
- 每个元素额外存储前后指针

#### 实现原理
```cpp
template <class T, class Allocator = allocator<T>>
class list {
    struct _List_node {
        _List_node* _M_next;
        _List_node* _M_prev;
        T _M_data;
    };
    _List_node* _M_node;  // 指向末尾的空节点
    size_t _M_size;
    // ...
};
```

#### 使用示例
```cpp
#include <list>

std::list<int> lst = {1, 2, 3};

// 在任意位置插入
auto it = std::next(lst.begin());
lst.insert(it, 10);  // O(1)

// 删除元素
lst.remove(2);  // O(1)
```

### forward_list

forward_list是一个单向链表容器,比list更节省内存但功能较少。

#### 特点
- 不支持随机访问
- 只能从前向后遍历
- 只存储一个前向指针,内存开销小
- 不能反向遍历

#### 实现原理
```cpp
template <class T, class Allocator = allocator<T>>
class forward_list {
    struct _Fwd_list_node {
        _Fwd_list_node* _M_next;
        T _M_data;
    };
    _Fwd_list_node* _M_head;  // 指向第一个节点
    // ...
};
```

#### 使用示例
```cpp
#include <forward_list>

std::forward_list<int> fl = {1, 2, 3};

// 在开头插入
fl.push_front(0);

// 在指定位置后插入
auto it = fl.begin();
fl.insert_after(it, 10);
```

## 序列容器的选择

在实际应用中选择合适的序列容器需要考虑以下因素:

1. 访问模式
- 需要随机访问 -> vector
- 主要在两端操作 -> deque
- 频繁在中间插入删除 -> list

2. 内存限制
- 内存要求连续 -> vector
- 允许不连续 -> deque/list
- 内存非常受限 -> forward_list

3. 迭代器失效
- vector: 插入/删除时可能导致所有迭代器失效
- deque: 插入/删除可能导致部分迭代器失效
- list/forward_list: 只有被删除元素的迭代器失效

## 性能对比

| 操作 | vector | deque | list | forward_list |
|------|---------|--------|------|------------|
| 随机访问 | O(1) | O(1) | O(n) | O(n) |
| 头部插入 | O(n) | O(1) | O(1) | O(1) |
| 尾部插入 | O(1)* | O(1) | O(1) | 不支持 |
| 中间插入 | O(n) | O(n) | O(1) | O(1) |
| 内存开销 | 低 | 中 | 高 | 中 |

*: 均摊复杂度

## 最佳实践

1. 默认使用vector
- vector是最通用和高效的序列容器
- 连续内存有利于CPU缓存
- 支持随机访问

2. 特殊场景考虑其他容器
- 频繁在两端操作 -> deque
- 频繁在中间插入删除 -> list
- 内存受限且只需要单向遍历 -> forward_list

3. 避免过早优化
- 先使用vector实现
- 在性能出现问题时再考虑其他容器
- 通过性能测试验证选择

## 总结

C++标准库提供了多种序列容器,每种容器都有其特定的使用场景和性能特点。理解这些容器的实现原理和性能特征,有助于我们在实际开发中选择最合适的容器类型。在大多数情况下,vector是最好的默认选择,只有在特定场景下才需要考虑其他容器类型。