C++ 数据结构速查

1. 概览对比

以下是算法题中最常用的 10 种 C++ 数据结构的一览。记住这张表，遇到新题先想「用哪个结构最合适」。

2. vector（动态数组）

vector 是最常用的容器，本质是可自动扩容的数组。尾部操作 O(1)，随机访问 O(1)，中间插入/删除 O(n)。绝大多数题目优先考虑 vector。

核心 API

#include <bits/stdc++.h>
using namespace std;

int main() {
    // ── 声明 ──────────────────────────────────
    vector<int> v;                  // 空 vector
    vector<int> v2(5, 0);          // 5 个 0
    vector<int> v3 = {3, 1, 4, 1, 5};

    // ── 增删 ──────────────────────────────────
    v3.push_back(9);               // [3,1,4,1,5,9]
    v3.pop_back();                 // [3,1,4,1,5]
    v3.insert(v3.begin() + 2, 99); // [3,1,99,4,1,5]
    v3.erase(v3.begin() + 2);     // [3,1,4,1,5]

    // ── 访问 ──────────────────────────────────
    cout << v3[0];                 // 3  (无越界检查)
    cout << v3.front();            // 3
    cout << v3.back();             // 5
    cout << v3.size();             // 5

    // ── 算法 ──────────────────────────────────
    sort(v3.begin(), v3.end());            // [1,1,3,4,5]
    reverse(v3.begin(), v3.end());         // [5,4,3,1,1]
    auto it = max_element(v3.begin(), v3.end());
    cout << *it;                           // 5

    // ── 二维 vector（图的邻接表）──────────────
    int n = 5;
    vector<vector<int>> adj(n);
    adj[0].push_back(1);
    adj[0].push_back(2);
}

适用场景

• 默认首选——几乎所有题目都可以用 vector 存储数据。
• 需要随机访问（下标访问）时。
• 只在尾部增删时（O(1)）；中间插删频繁则考虑 list 或换思路。
• 图的邻接表：vector<vector<int>> adj(n)。

3. stack（栈）

后进先出（LIFO）容器。只能操作栈顶，无法遍历。底层默认用 deque 实现。算法题中常用于括号匹配、DFS 迭代化、单调栈。

核心 API

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;

    st.push(1);   // [1]
    st.push(2);   // [1, 2]
    st.push(3);   // [1, 2, 3]

    cout << st.top();   // 3（不弹出）
    st.pop();           // 弹出 3，[1, 2]

    // ⚠️ pop() 无返回值！正确姿势：
    int x = st.top();  // 先取值
    st.pop();           // 再弹出

    cout << st.size();  // 1
    cout << st.empty(); // false → 0

    // ── 经典用法：单调栈（下一个更大元素）──────
    vector<int> nums = {2, 1, 2, 4, 3};
    vector<int> res(nums.size(), -1);
    stack<int> mono; // 存下标
    for (int i = 0; i < (int)nums.size(); i++) {
        while (!mono.empty() && nums[mono.top()] < nums[i]) {
            res[mono.top()] = nums[i];
            mono.pop();
        }
        mono.push(i);
    }
    // res = [2, 2, 4, -1, -1]
}

适用场景

• 括号/标签匹配类题目。
• 需要「最近未处理元素」语义时——单调栈（下一个更大元素、柱状图最大矩形）。
• DFS 的迭代实现（用 stack 替代递归调用栈）。
• 后缀表达式求值、逆波兰计算器。

4. queue（队列）

先进先出（FIFO）容器。只能从队头取、队尾入，无法随机访问。BFS 的标配结构。

核心 API

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;

    q.push(1);    // 入队，队列：[1]
    q.push(2);    // [1, 2]
    q.push(3);    // [1, 2, 3]

    cout << q.front(); // 1（队头）
    cout << q.back();  // 3（队尾）
    q.pop();           // 出队，[2, 3]

    // ── 经典用法：BFS（二叉树层序遍历）─────────
    // struct TreeNode { int val; TreeNode *left, *right; };
    // queue<TreeNode*> bfs;
    // bfs.push(root);
    // while (!bfs.empty()) {
    //     int sz = bfs.size();   // 当前层节点数
    //     for (int i = 0; i < sz; i++) {
    //         auto node = bfs.front(); bfs.pop();
    //         if (node->left)  bfs.push(node->left);
    //         if (node->right) bfs.push(node->right);
    //     }
    // }
}

适用场景

• BFS（广度优先搜索）——二叉树层序遍历、最短路（无权图）。
• 任务队列、生产者-消费者模型。
• 需要严格 FIFO 顺序处理时。

5. deque（双端队列）

两端都可以 O(1) 插入/删除，同时支持 O(1) 随机访问。比 vector 和 queue 更灵活，但内存分配更复杂（分块）。单调双端队列（monotonic deque）是滑动窗口最值的经典技巧。

核心 API

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> dq;

    dq.push_back(1);   // [1]
    dq.push_back(2);   // [1, 2]
    dq.push_front(0);  // [0, 1, 2]

    cout << dq.front(); // 0
    cout << dq.back();  // 2
    cout << dq[1];      // 1（O(1) 随机访问）

    dq.pop_front();     // [1, 2]
    dq.pop_back();      // [1]

    // ── 经典用法：单调队列（滑动窗口最大值）─────
    // 维护一个单调递减的下标队列
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    deque<int> mono;  // 存下标
    vector<int> result;

    for (int i = 0; i < (int)nums.size(); i++) {
        // 移除超出窗口的下标
        while (!mono.empty() && mono.front() < i - k + 1)
            mono.pop_front();
        // 移除比当前元素小的下标（它们不可能是最大值）
        while (!mono.empty() && nums[mono.back()] < nums[i])
            mono.pop_back();
        mono.push_back(i);
        if (i >= k - 1)
            result.push_back(nums[mono.front()]);
    }
    // result = [3, 3, 5, 5, 6, 7]
}

适用场景

• 滑动窗口最大/最小值——用单调递减/递增 deque 维护窗口内的有效候选，O(n) 解决。
• 需要同时在两端操作时（如回文检测、双端 BFS）。
• stack 和 queue 的底层实现，直接用 deque 可以结合两者能力。

6. priority_queue（堆）

默认是最大堆（堆顶为最大值）。插入和删除堆顶均为 O(log n)，查看堆顶 O(1)。是 Top-K、Dijkstra、任务调度等题目的核心工具。

核心 API

三种声明方式

#include <bits/stdc++.h>
using namespace std;

int main() {
    // ── 最大堆（默认）────────────────────────
    priority_queue<int> maxPq;
    maxPq.push(3); maxPq.push(1); maxPq.push(4);
    cout << maxPq.top(); // 4
    maxPq.pop();
    cout << maxPq.top(); // 3

    // ── 最小堆 ───────────────────────────────
    priority_queue<int, vector<int>, greater<int>> minPq;
    minPq.push(3); minPq.push(1); minPq.push(4);
    cout << minPq.top(); // 1

    // ── pair 最小堆（Dijkstra 常用）──────────
    priority_queue<
        pair<int,int>,
        vector<pair<int,int>>,
        greater<pair<int,int>>
    > dijkPq;
    dijkPq.push({5, 0}); // {distance, node}
    dijkPq.push({2, 1});
    auto [d, u] = dijkPq.top(); // d=2, u=1

    // ── 自定义比较器 ─────────────────────────
    auto cmp = [](pair<int,int> a, pair<int,int> b) {
        return a.second > b.second; // 按 second 升序（最小堆）
    };
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   decltype(cmp)> customPq(cmp);

    // ── Top-K 模式（用大小 k 的最小堆）──────
    vector<int> nums = {3, 1, 5, 2, 4};
    int k = 3;
    priority_queue<int, vector<int>, greater<int>> kHeap;
    for (int x : nums) {
        kHeap.push(x);
        if ((int)kHeap.size() > k) kHeap.pop();
    }
    // kHeap 里剩下的是前 k 大元素
    cout << kHeap.top(); // 3（第 k 大）
}

适用场景

• Top-K 问题：用大小 k 的最小堆，O(n log k)。
• Dijkstra 最短路：用 {dist, node} 的最小堆。
• 合并 k 个有序链表：用 {val, listIndex} 的最小堆。
• 贪心调度：总是处理「优先级最高」的任务。
• 第 K 大/小——O(n log k) 解法（快速选择是 O(n) 但常数大）。

7. map（有序映射）

基于红黑树的有序键值对容器。键自动升序排列，所有操作 O(log n)。支持 lower_bound/upper_bound 范围查询，这是 unordered_map 不具备的能力。

核心 API

#include <bits/stdc++.h>
using namespace std;

int main() {
    map<string, int> mp;

    // ── 插入/更新 ─────────────────────────────
    mp["apple"] = 3;          // 插入
    mp["banana"] = 5;
    mp["apple"]++;            // 更新：apple → 4

    // ── 查找 ──────────────────────────────────
    if (mp.count("apple"))    // 存在
        cout << mp["apple"];  // 4
    auto it = mp.find("grape");
    if (it == mp.end()) cout << "not found";

    // ⚠️ mp[key] 会自动插入默认值！判断存在用 count/find
    // mp["cherry"]; // 现在 cherry 在 map 里了，值为 0

    // ── 删除 ──────────────────────────────────
    mp.erase("banana");

    // ── 有序遍历（键升序）────────────────────
    for (auto& [k, v] : mp)
        cout << k << ": " << v << '\n';

    // ── 范围查询（lower/upper_bound）─────────
    map<int, string> m2 = {{1,"a"},{3,"c"},{5,"e"},{7,"g"}};
    auto lo = m2.lower_bound(3); // 指向 3 → "c"
    auto hi = m2.upper_bound(5); // 指向 7 → "g"
    for (auto i = lo; i != hi; ++i)
        cout << i->first << ' '; // 3 5
}

适用场景

• 需要有序遍历键时（map 自动排序）。
• 需要 lower_bound / upper_bound（区间查询、前驱后继）。
• 键的范围未知但需要按键范围查询时。
• 不需要有序时用 unordered_map——O(log n) vs O(1) 均摊差距在大数据量时明显。

8. unordered_map（哈希表）

基于哈希表的键值对容器。均摊 O(1) 查找/插入/删除，无序。是算法题中最常用的映射结构，适合频率统计、记忆化搜索、Two Sum 等场景。

核心 API

#include <bits/stdc++.h>
using namespace std;

int main() {
    unordered_map<int, int> mp;

    // ── 频率统计 ──────────────────────────────
    vector<int> nums = {1, 2, 1, 3, 2, 1};
    for (int x : nums) mp[x]++;
    // mp: {1→3, 2→2, 3→1}

    // ── 查找 ──────────────────────────────────
    cout << mp.count(1);  // 1（存在）
    cout << mp.count(9);  // 0（不存在）
    cout << mp[1];        // 3

    // ── Two Sum 经典写法 ──────────────────────
    vector<int> arr = {2, 7, 11, 15};
    int target = 9;
    unordered_map<int, int> seen; // val → index
    for (int i = 0; i < (int)arr.size(); i++) {
        int need = target - arr[i];
        if (seen.count(need)) {
            cout << seen[need] << ' ' << i; // 0 1
            break;
        }
        seen[arr[i]] = i;
    }

    // ── 性能优化：提前分配桶 ─────────────────
    unordered_map<int,int> bigMap;
    bigMap.reserve(1024); // 减少 rehash 次数
}

适用场景

• Two Sum / 配对问题：边扫描边查 target-x 是否已存在。
• 频率统计：统计每个元素出现次数。
• 记忆化搜索（dfs + memo）：用 unordered_map 存已算过的状态。
• 字符/单词计数。
• 需要有序遍历时改用 map。

9. set（有序集合）

基于红黑树的有序唯一元素集合。所有操作 O(log n)，元素自动排序且唯一。支持 lower_bound/upper_bound，可以查前驱后继。multiset 允许重复元素。

核心 API

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;

    // ── 插入/删除 ─────────────────────────────
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(1);   // 重复，忽略
    // s = {1, 3, 4}

    s.erase(3);    // s = {1, 4}
    cout << s.count(1); // 1
    cout << s.count(9); // 0

    // ── 有序遍历 ──────────────────────────────
    for (int x : s) cout << x << ' '; // 1 4

    // ── lower_bound / upper_bound ─────────────
    set<int> s2 = {1, 3, 5, 7, 9};
    auto lo = s2.lower_bound(4); // 指向 5（第一个 >= 4）
    auto hi = s2.upper_bound(7); // 指向 9（第一个 > 7）
    cout << *lo << ' ' << *hi;  // 5 9

    // 前驱（最大的 < 4）：
    auto it = s2.lower_bound(4);
    if (it != s2.begin()) cout << *prev(it); // 3

    // ── multiset（允许重复）───────────────────
    multiset<int> ms = {1, 2, 2, 3};
    ms.erase(ms.find(2)); // 只删一个 2 → {1, 2, 3}
    // ms.erase(2);        // ⚠️ 会删掉所有 2！
}

适用场景

• 需要有序且不重复的集合时。
• 查询前驱（最大的 < x）：--s.lower_bound(x)。
• 查询后继（最小的 > x）：s.upper_bound(x)。
• 动态维护有序序列（边插边查最值）。
• 只需判重不需有序时用 unordered_set——O(1) vs O(log n)。

10. unordered_set（哈希集合）

基于哈希表的唯一元素集合。均摊 O(1) 插入/删除/查找，无序。用于快速判断元素是否存在或去重，比 set 快但不支持范围查询。

核心 API

#include <bits/stdc++.h>
using namespace std;

int main() {
    unordered_set<int> s;

    s.insert(1); s.insert(2); s.insert(3);
    s.insert(1); // 重复，忽略

    cout << s.count(1); // 1（存在）
    cout << s.count(9); // 0（不存在）

    s.erase(2);
    cout << s.size(); // 2

    // ── 常见用法：去重 ────────────────────────
    vector<int> nums = {3,1,4,1,5,9,2,6,5};
    unordered_set<int> seen(nums.begin(), nums.end());
    // seen 包含所有不重复元素（无序）

    // ── 常见用法：visited 集合（BFS/DFS）─────
    unordered_set<int> visited;
    // dfs(node) { if (visited.count(node)) return; visited.insert(node); ... }
}

适用场景

• 快速判断元素是否出现过（visited 数组的替代方案，键不是连续整数时）。
• 对元素去重（不关心顺序）。
• 需要有序或范围查询时改用 set。

11. pair / tuple

pair 存两个值，tuple 存任意多个值。常用于在容器中绑定多个属性（如坐标 {x,y}、带权边 {dist, node}），或作为 map/set 的键。C++17 结构化绑定让解包更简洁。

核心用法

#include <bits/stdc++.h>
using namespace std;

int main() {
    // ── pair 基础 ─────────────────────────────
    pair<int, string> p1 = {1, "hello"};
    auto p2 = make_pair(2, "world");

    cout << p1.first;   // 1
    cout << p1.second;  // "hello"

    // C++17 结构化绑定
    auto [num, str] = p1;
    cout << num << ' ' << str;

    // ── pair 排序（先按 first，再按 second）──
    vector<pair<int,int>> v = {{3,1},{1,3},{3,0},{1,2}};
    sort(v.begin(), v.end());
    // 结果: {1,2},{1,3},{3,0},{3,1}

    // ── 自定义排序 ────────────────────────────
    sort(v.begin(), v.end(), [](const pair<int,int>& a,
                                 const pair<int,int>& b){
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second; // second 降序
    });

    // ── tuple（三个或更多值）─────────────────
    tuple<int, string, double> t = {42, "cpp", 3.14};
    cout << get<0>(t); // 42
    cout << get<1>(t); // "cpp"

    auto [id, name, score] = t; // 解包

    // ── 在 priority_queue 中使用 pair ─────────
    // priority_queue<pair<int,int>, vector<pair<int,int>>,
    //                greater<pair<int,int>>> minHeap;
    // minHeap.push({dist, node});
}

适用场景

• 需要把多个值捆绑在一起放入容器（如 priority_queue 中存 {distance, node}）。
• 函数需要返回两个值时用 pair 或 tuple 代替 out 参数。
• 自定义排序时用 pair 组合多个排序键（主键.second 次键）。

12. string（字符串）

C++ string 是动态字符数组，支持大多数 STL 算法。注意 find 返回 string::npos（不是 -1）表示未找到，substr 返回新字符串（O(n)）。

核心 API

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "hello world";

    // ── 基础操作 ──────────────────────────────
    cout << s.size();        // 11
    cout << s[0];            // 'h'
    cout << s.substr(6, 5);  // "world"（从 6 开始，长度 5）

    s.push_back('!');        // "hello world!"
    s += " cpp";             // "hello world! cpp"

    // ── 查找 ──────────────────────────────────
    size_t pos = s.find("world");
    if (pos != string::npos)
        cout << pos;         // 6
    // ⚠️ 未找到返回 string::npos，不是 -1！

    // ── 排序/反转 ─────────────────────────────
    string t = "dcba";
    sort(t.begin(), t.end());    // "abcd"
    reverse(t.begin(), t.end()); // "dcba"

    // ── 类型转换 ──────────────────────────────
    int n = stoi("42");          // string → int
    long l = stol("123456789");  // string → long
    double d = stod("3.14");     // string → double
    string num = to_string(100); // int → string

    // ── 按分隔符切分（stringstream）──────────
    string line = "a,b,c,d";
    stringstream ss(line);
    string token;
    while (getline(ss, token, ','))
        cout << token << '\n'; // a b c d（各占一行）

    // ── 字符频率统计 ──────────────────────────
    string word = "abracadabra";
    unordered_map<char,int> freq;
    for (char c : word) freq[c]++;
    // freq: {a→5, b→2, r→2, c→1, d→1}
}

适用场景

• 字符频率统计：unordered_map<char,int> 或直接 int freq[256]。
• 滑动窗口（最长无重复子串等）：双指针 + unordered_map/set。
• 回文检测：双指针从两端向中间。
• 字符串比较/排序：C++ string 直接支持 ==、<、> 按字典序比较。

13. 选择指南

遇到新题时，先想清楚需要什么操作，再选数据结构。下面是常见场景的快速决策。