C++ STL 容器详解与选型指南

常用操作

#include <vector>
#include <iostream>

int main() {
    // 多种初始化方式
    std::vector<int> v1;              // 空 vector
    std::vector<int> v2(5);           // 5 个 0
    std::vector<int> v3(5, 10);       // 5 个 10
    std::vector<int> v4 = {1, 2, 3, 4, 5}; // 初始化列表

    // 容量管理
    v1.reserve(100);                  // 预留 100 个元素空间
    std::cout << "size: " << v4.size() << std::endl;     // 当前元素数量
    std::cout << "capacity: " << v4.capacity() << std::endl; // 当前容量

    // 访问元素
    std::cout << "front: " << v4.front() << std::endl;   // 第一个元素
    std::cout << "back: " << v4.back() << std::endl;     // 最后一个元素
    std::cout << "at(2): " << v4.at(2) << std::endl;     // 安全访问

    // 修改操作
    v4.push_back(6);                    // 尾部添加
    v4.insert(v4.begin() + 2, 100);     // 中间插入
    v4.erase(v4.begin() + 1);           // 删除
    v4.pop_back();                      // 删除尾部

    // 高级操作
    std::sort(v4.begin(), v4.end());    // 排序
    v4.resize(10, 0);                   // 调整大小
    return 0;
}

性能优化技巧

// 预分配避免频繁扩容
void vector_reserve_demo() {
    // ❌ 错误做法：不预分配
    std::vector<int> bad_vec;
    for (int i = 0; i < 10000; ++i) {
        bad_vec.push_back(i); // 可能触发多次内存重新分配
    }

    // ✅ 正确做法：预分配容量
    std::vector<int> good_vec;
    good_vec.reserve(10000);  // 一次性分配足够内存
    for (int i = 0; i < 10000; ++i) {
        good_vec.push_back(i); // 不会触发重新分配
    }
}

// 高效删除元素
void vector_erase_demo() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // ❌ 低效：从前往后删除
    for (auto it = vec.begin(); it != vec.end();) {
        if (*it % 2 == 0) {
            it = vec.erase(it); // O(n) 操作，总体 O(n²)
        } else {
            ++it;
        }
    }

    // ✅ 高效：使用 remove_if + erase
    vec.erase(
        std::remove_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }),
        vec.end()
    ); // O(n) 操作
}

// 使用 emplace 避免不必要的拷贝
void modern_vector_usage() {
    std::vector<std::pair<int, std::string>> vec;

    // ❌ 创建临时对象再拷贝
    vec.push_back(std::make_pair(1, "hello"));
    vec.push_back({2, "world"});

    // ✅ 直接在容器中构造对象
    vec.emplace_back(3, "modern"); // 直接构造，避免拷贝
    vec.emplace_back(4, "cpp");
}

2. list（双向链表）

核心特性

• 底层实现：双向链表，元素非连续存储
• 任意位置操作：插入/删除 O(1)
• 随机访问：O(n)，需遍历
• 内存开销：每个节点需额外存储前后指针

常用操作

#include <list>
#include <iostream>

int main() {
    std::list<int> numbers = {1, 2, 3, 4, 5};

    // 添加元素
    numbers.push_back(10);
    numbers.push_front(0);

    // 中间插入
    auto it = numbers.begin();
    std::advance(it, 2); // 找到第 3 个位置
    numbers.insert(it, 100); // O(1) 插入

    // 删除元素
    numbers.erase(numbers.begin());
    numbers.pop_back();

    // 链表特有操作
    numbers.sort();      // 链表排序
    numbers.reverse();   // 反转链表
    numbers.unique();    // 去重（需先排序）

    // 遍历
    for (auto num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

适用场景

• 需要频繁在中间位置插入删除元素
• 对随机访问要求不高
• 需要高效的链表合并操作（splice）

3. deque（双端队列）

核心特性

• 底层实现：分段连续存储（多段数组）
• 头尾操作：push_front/push_back均为 O(1)
• 随机访问：O(1)，但比 vector 略慢
• 中间操作：插入/删除 O(n)

常用操作

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;

    // 双端操作
    dq.push_front(1); // 头部插入
    dq.push_back(2);  // 尾部插入
    dq.push_front(0); // 头部插入
    dq.push_back(3);  // 尾部插入

    // 随机访问
    std::cout << "第一个元素：" << dq[0] << std::endl;
    std::cout << "最后一个元素：" << dq[dq.size()-1] << std::endl;

    // 删除操作
    dq.pop_front(); // 头部删除
    dq.pop_back();  // 尾部删除
    return 0;
}

适用场景

• 需要频繁在两端插入删除
• 偶尔需要随机访问
• 实现滑动窗口算法
• 双向缓冲区

4. array（固定数组）

核心特性

• 底层实现：编译期定长的连续数组
• 随机访问：O(1)
• 大小固定：无法动态扩容
• 安全访问：提供 at() 方法进行边界检查

常用操作

#include <array>
#include <iostream>

int main() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};

    // 访问元素
    std::cout << "第一个元素：" << arr[0] << std::endl;
    std::cout << "最后一个元素：" << arr.back() << std::endl;

    // 安全访问
    try {
        std::cout << arr.at(10) << std::endl; // 抛出异常
    } catch (const std::out_of_range& e) {
        std::cout << "越界访问：" << e.what() << std::endl;
    }

    // 遍历
    for (auto num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

适用场景

• 元素数量固定且已知
• 需要替代原生数组，提供更安全的接口
• 存储配置信息、坐标等固定长度数据

四、关联容器详解

1. set/multiset（集合）

核心特性

• 底层实现：红黑树（平衡二叉搜索树）
• 自动排序：元素按升序排列
• 查找效率：O(log n)
• 唯一性：set 不允许重复，multiset 允许重复

常用操作

#include <set>
#include <iostream>

int main() {
    // set：唯一元素
    std::set<int> unique_set = {3, 1, 4, 1, 5}; // {1, 3, 4, 5}

    // multiset：允许重复
    std::multiset<int> multi_set = {3, 1, 4, 1, 5}; // {1, 1, 3, 4, 5}

    // 插入元素
    unique_set.insert(2);
    unique_set.insert(3); // 重复，不会插入

    // 查找元素
    auto it = unique_set.find(3);
    if (it != unique_set.end()) {
        std::cout << "找到元素：" << *it << std::endl;
    }

    // 删除元素
    unique_set.erase(4);

    // 遍历
    for (auto num : unique_set) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 范围查找
    auto lower = unique_set.lower_bound(2); // >=2 的最小元素
    auto upper = unique_set.upper_bound(4); // >4 的最小元素
    return 0;
}

适用场景

• 需要去重且有序的集合
• 频繁查找、插入、删除操作
• 需要范围查询（lower_bound/upper_bound）

2. map/multimap（映射）

核心特性

• 底层实现：红黑树，存储键值对
• 自动排序：按键值升序排列
• 查找效率：O(log n)
• 唯一性：map 键唯一，multimap 允许重复键

常用操作

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<std::string, int> student_scores;

    // 插入元素
    student_scores["Alice"] = 95;
    student_scores["Bob"] = 87;
    student_scores["Charlie"] = 92;

    // 安全插入：只有键不存在时才插入
    auto result = student_scores.insert({"David", 88});
    if (result.second) {
        std::cout << "David 插入成功" << std::endl;
    }

    // emplace：直接在容器内构造对象
    student_scores.emplace("Eve", 91);

    // 查找的多种方式
    // 方式 1：使用 find（推荐）
    auto it = student_scores.find("Alice");
    if (it != student_scores.end()) {
        std::cout << "Alice 的分数：" << it->second << std::endl;
    }

    // 方式 2：使用 count + operator[]
    if (student_scores.count("Bob")) {
        std::cout << "Bob 的分数：" << student_scores["Bob"] << std::endl;
    }

    // 删除元素
    student_scores.erase("Charlie");

    // 遍历
    for (const auto& pair : student_scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

适用场景

• 键值对存储，需要按键快速查找
• 需要有序遍历键值对
• 实现字典、配置表、计数器等

五、无序关联容器详解

1. unordered_set/unordered_map

核心特性

• 底层实现：哈希表
• 查找效率：平均 O(1)，最坏 O(n)
• 元素无序：不保持插入顺序
• 自定义类型：需提供哈希函数和相等比较函数

常用操作

#include <unordered_map>
#include <iostream>
#include <string>

// 自定义类型的哈希函数
struct Person {
    std::string name;
    int age;
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            return hash<string>()(p.name) ^ hash<int>()(p.age);
        }
    };
}

int main() {
    // unordered_map 基本用法
    std::unordered_map<std::string, int> word_count;

    // 插入元素
    word_count["hello"] = 1;
    word_count["world"] = 2;
    word_count["hello"]++;

    // 查找元素
    auto it = word_count.find("hello");
    if (it != word_count.end()) {
        std::cout << "hello 出现次数：" << it->second << std::endl;
    }

    // 遍历（无序）
    for (const auto& pair : word_count) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 自定义类型使用
    std::unordered_map<Person, int> person_map;
    person_map[{ "Alice", 25 }] = 100;
    return 0;
}

适用场景

• 需要极速查找，不关心元素顺序
• 高频查询的缓存系统
• 计数器、频率统计
• 去重操作

六、容器适配器详解

1. stack（栈）

核心特性

• 底层实现：基于 deque 或 list
• 后进先出：LIFO（Last-In-First-Out）
• 操作限制：只能在栈顶插入删除

常用操作

#include <stack>
#include <iostream>

int main() {
    std::stack<int> s;

    // 入栈
    s.push(1);
    s.push(2);
    s.push(3);

    // 访问栈顶
    std::cout << "栈顶元素：" << s.top() << std::endl;

    // 出栈
    s.pop();
    std::cout << "出栈后栈顶：" << s.top() << std::endl;

    // 栈大小
    std::cout << "栈大小：" << s.size() << std::endl;
    return 0;
}

适用场景

• 函数调用栈
• 表达式求值
• 括号匹配
• 深度优先搜索（DFS）

2. queue（队列）

核心特性

• 底层实现：基于 deque 或 list
• 先进先出：FIFO（First-In-First-Out）
• 操作限制：队尾插入，队头删除

常用操作

#include <queue>
#include <iostream>

int main() {
    std::queue<int> q;

    // 入队
    q.push(1);
    q.push(2);
    q.push(3);

    // 访问队头
    std::cout << "队头元素：" << q.front() << std::endl;

    // 出队
    q.pop();
    std::cout << "出队后队头：" << q.front() << std::endl;

    // 访问队尾
    std::cout << "队尾元素：" << q.back() << std::endl;
    return 0;
}

适用场景

• 任务调度
• 消息队列
• 广度优先搜索（BFS）
• 缓存管理

3. priority_queue（优先队列）

核心特性

• 底层实现：基于 vector 的二叉堆（最大堆）
• 优先级排序：默认最大元素在队首
• 操作效率：push/pop为 O(log n)，top为 O(1)

常用操作

#include <queue>
#include <iostream>
#include <functional> // 用于 greater

int main() {
    // 默认最大堆
    std::priority_queue<int> max_heap;
    max_heap.push(3);
    max_heap.push(1);
    max_heap.push(4);
    max_heap.push(2);
    std::cout << "最大堆：";
    while (!max_heap.empty()) {
        std::cout << max_heap.top() << " "; // 4 3 2 1
        max_heap.pop();
    }
    std::cout << std::endl;

    // 最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(3);
    min_heap.push(1);
    min_heap.push(4);
    min_heap.push(2);
    std::cout << "最小堆：";
    while (!min_heap.empty()) {
        std::cout << min_heap.top() << " "; // 1 2 3 4
        min_heap.pop();
    }
    std::cout << std::endl;
    return 0;
}

适用场景

• 任务优先级调度
• 求 Top K 问题
• 堆排序
• Dijkstra 算法等图算法

七、容器性能对比与选型指南

1. 时间复杂度对比

2. 选型原则

选型口诀

• 随机访问选 vector：需要快速随机访问，尾部操作多
• 头尾操作多选 deque：需要频繁在两端插入删除
• 中间操作频繁选 list：需要任意位置高效插入删除
• 快速查找选 unordered：不关心顺序，追求极致查找效率
• 有序需求选 map/set：需要有序遍历、范围查询

常见场景推荐

• 90% 场景：优先选择 vector，通用性强
• 查找场景：unordered_map/unordered_set（O(1) 查找）
• 有序场景：map/set（需要排序或范围查询）
• 频繁插入删除：list 或 deque（根据位置选择）
• 队列/栈：queue/stack（基于 deque）

3. 性能实测数据

根据实际测试（100 万次操作）：

八、STL 容器内存管理

1. 内存分配机制

STL 容器使用分配器（Allocator）管理内存，默认使用 std::allocator。容器在需要时动态分配内存，自动处理内存的分配和释放。

vector 扩容策略

void vector_memory_analysis() {
    std::vector<int> vec;
    std::cout << "空 vector 大小：" << sizeof(vec) << "字节" << std::endl;
    for (int i = 1; i <= 5; ++i) {
        vec.push_back(i);
        std::cout << "元素数：" << vec.size() << ", 容量：" << vec.capacity() << std::endl;
    }
}

输出结果（不同编译器可能不同）：

空 vector 大小：24 字节
元素数：1, 容量：1
元素数：2, 容量：2
元素数：3, 容量：4
元素数：4, 容量：4
元素数：5, 容量：8

2. 内存优化技巧

预分配容量

// ❌ 错误做法：频繁扩容
std::vector<int> bad_vec;
for (int i = 0; i < 10000; ++i) {
    bad_vec.push_back(i); // 可能触发多次内存重新分配
}

// ✅ 正确做法：预分配
std::vector<int> good_vec;
good_vec.reserve(10000); // 一次性分配足够内存
for (int i = 0; i < 10000; ++i) {
    good_vec.push_back(i); // 不会触发重新分配
}

释放多余内存

std::vector<int> vec;
vec.reserve(1000); // ... 添加元素后，实际只用了 100 个
vec.shrink_to_fit(); // 释放多余内存

3. 自定义分配器

#include <vector>
#include <memory>
#include <iostream>

template<typename T>
class MyAllocator : public std::allocator<T> {
public:
    // 重写 allocate 和 deallocate
    T* allocate(std::size_t n) {
        std::cout << "Allocating " << n << " elements" << std::endl;
        return std::allocator<T>::allocate(n);
    }
    void deallocate(T* p, std::size_t n) {
        std::cout << "Deallocating " << n << " elements" << std::endl;
        std::allocator<T>::deallocate(p, n);
    }
};

int main() {
    std::vector<int, MyAllocator<int>> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.pop_back();
    return 0;
}

九、常见误区与最佳实践

1. 常见误区

误区 1：list 查找也不慢？

• 事实：list 查找是 O(n)，只有插入删除快
• 建议：除非需要频繁中间插入删除，否则优先选择 vector

误区 2：map 查找就是快？

• 事实：unordered_map 查找是 O(1)，比 map 的 O(log n) 更快
• 建议：不关心顺序时优先选择 unordered_map

误区 3：容器默认线程安全？

• 事实：STL 默认不线程安全
• 建议：多线程环境需加锁或使用并发容器

误区 4：vector 扩容特别慢？

• 事实：vector 扩容是摊销 O(1)，不要过度担心
• 建议：合理使用 reserve() 预分配即可

2. 最佳实践

迭代器失效问题

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();

// ❌ 错误：插入可能导致扩容，迭代器失效
vec.push_back(6);
// std::cout << *it << std::endl; // 未定义行为

// ✅ 正确：重新获取迭代器
it = vec.begin();
std::cout << *it << std::endl; // 安全

使用 emplace 避免拷贝

std::vector<std::string> vec;

// ❌ 创建临时对象再拷贝
vec.push_back(std::string("hello"));

// ✅ 直接在容器中构造对象
vec.emplace_back("hello"); // 避免拷贝

合理选择删除方式

std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// ❌ 低效：从前往后删除
for (auto it = vec.begin(); it != vec.end();) {
    if (*it % 2 == 0) {
        it = vec.erase(it); // O(n) 操作，总体 O(n²)
    } else {
        ++it;
    }
}

// ✅ 高效：使用 remove_if + erase
vec.erase(
    std::remove_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }),
    vec.end()
); // O(n) 操作

十、总结

STL 容器是 C++ 编程中不可或缺的工具，选择合适的容器能显著提升程序性能。掌握各容器的特性、时间复杂度、适用场景，是成为高效 C++ 程序员的关键。

核心要点总结：

1. vector 是 90% 场景的首选：随机访问快，尾部操作高效
2. unordered 系列查找最快：不关心顺序时优先选择
3. list 只适合极少数场景：频繁中间插入删除才考虑
4. 合理使用 reserve 预分配：避免 vector 频繁扩容
5. 理解迭代器失效规则：插入删除操作后需重新获取迭代器

通过本文的系统学习，相信你已经掌握了 STL 容器的核心知识。在实际开发中，根据具体需求选择合适的容器，配合性能分析工具验证效果，才能写出既高效又健壮的 C++ 代码。