第9章：顺序容器（Sequential Containers）

一、导读

1.1 本章学习目标

第9章深入讲解C++标准库的顺序容器。本章核心目标：

掌握各种顺序容器：vector、list、deque
理解容器的性能差异：随机访问vs插入删除
学会使用容器适配器：stack、queue、priority_queue
理解迭代器失效：什么操作会导致迭代器失效
掌握容器的通用操作：大小、清空、交换

1.2 为什么本章如此重要

容器是C++ STL的核心组件。选择合适的容器对程序性能有重大影响。vector是最常用的容器，但在频繁插入删除的场景下，list可能更合适。

1.3 核心问题引导

vector、list、deque的底层实现分别是什么？

什么操作会导致vector的迭代器失效？

stack和queue默认使用什么容器实现？

如何根据需求选择合适的容器？

二、核心概念详解

9.1 顺序容器概览

容器	底层结构	随机访问	头部插入	尾部插入	中间插入
vector	动态数组	O(1)	O(n)	摊还O(1)	O(n)
list	双向链表	O(n)	O(1)	O(1)	O(1)
deque	分段数组	O(1)	O(1)	O(1)	O(n)
forward_list	单向链表	O(n)	O(1)	O(n)	O(1)
array	固定数组	O(1)	-	-	-

9.2 vector详解

cpp

#include <iostream>
#include <vector>

int main() {
    // 初始化
    std::vector<int> v1;
    std::vector<int> v2 = {1, 2, 3, 4, 5};
    std::vector<int> v3(5, 42);
    std::vector<int> v4(v2);
    
    // 基本操作
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    
    std::cout << "Size: " << v1.size() << std::endl;
    std::cout << "Capacity: " << v1.capacity() << std::endl;
    
    // 访问
    std::cout << v1[0] << std::endl;       // 10
    std::cout << v1.at(1) << std::endl;    // 20（带边界检查）
    std::cout << v1.front() << std::endl;  // 10
    std::cout << v1.back() << std::endl;   // 30
    
    // 插入和删除
    v1.insert(v1.begin() + 1, 15);
    v1.erase(v1.begin());
    v1.pop_back();
    
    // 预分配
    v1.reserve(100);
    
    // shrink_to_fit
    v1.shrink_to_fit();
    
    return 0;
}

9.3 list和deque

cpp

#include <iostream>
#include <list>
#include <deque>

int main() {
    // list：双向链表
    std::list<int> l = {1, 2, 3, 4, 5};
    l.push_front(0);
    l.push_back(6);
    l.sort();
    l.reverse();
    l.unique();  // 删除相邻重复元素
    
    for (int x : l) std::cout << x << " ";
    std::cout << std::endl;
    
    // list特有操作
    l.splice(l.begin(), l, l.end());  // 移动元素
    
    // deque：双端队列
    std::deque<int> d;
    d.push_front(1);
    d.push_back(2);
    d.push_front(0);
    d.push_back(3);
    
    for (int x : d) std::cout << x << " ";
    std::cout << std::endl;
    
    // deque支持随机访问
    std::cout << d[0] << std::endl;
    std::cout << d.at(1) << std::endl;
    
    return 0;
}

9.4 容器适配器

cpp

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

int main() {
    // stack：后进先出（默认使用deque）
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    
    std::cout << "Stack top: " << s.top() << std::endl;
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << std::endl;
    
    // queue：先进先出（默认使用deque）
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    
    std::cout << "Queue front: " << q.front() << std::endl;
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << std::endl;
    
    // priority_queue：优先队列（最大堆）
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    
    std::cout << "Priority queue: ";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;
    
    // 使用vector作为stack的底层容器
    std::stack<int, std::vector<int>> vs;
    
    return 0;
}

9.5 迭代器失效

cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // push_back可能导致迭代器失效（如果扩容）
    auto it = v.begin() + 2;
    v.push_back(6);  // 可能扩容
    // *it;  // 可能崩溃！
    
    // 安全做法：重新获取迭代器
    it = v.begin() + 2;
    
    // insert使插入点之后的迭代器失效
    v.insert(v.begin() + 1, 100);
    
    // erase使被删除元素之后的迭代器失效
    it = v.begin() + 1;
    v.erase(it);
    
    // 在遍历中删除元素的正确方式
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) {
            it = v.erase(it);  // erase返回下一个有效迭代器
        } else {
            ++it;
        }
    }
    
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    return 0;
}

三、实战案例

3.1 使用栈实现括号匹配

cpp

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string &s) {
    std::stack<char> st;
    
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    
    return st.empty();
}

int main() {
    std::cout << isBalanced("({[]})") << std::endl;  // 1
    std::cout << isBalanced("({[})]") << std::endl;  // 0
    std::cout << isBalanced("((()))") << std::endl;  // 1
    return 0;
}

四、本章小结

第9章介绍了C++顺序容器：vector（动态数组）、list（双向链表）、deque（双端队列），以及容器适配器stack、queue、priority_queue。选择容器时要考虑操作的性能需求。

五、思考与练习

思考题

vector扩容时容量增长策略是什么？

为什么deque的两端操作都是O(1)？

容器适配器的底层容器可以自定义吗？

如何在遍历过程中安全地删除元素？

编程练习

使用queue实现广度优先搜索。

使用两个栈实现一个队列。

实现一个简单的LRU缓存。