C++上机考试冲刺（三）—STL容器与常用数据结构

上机考试很少要求重新实现一整套通用容器。真正需要掌握的是：根据操作选择合适的数据结构，记住高频接口和复杂度，并避免在遍历过程中误用已经失效的迭代器。

本文采用 STL 优先策略。数组、栈、队列、优先队列、集合和哈希表直接使用标准库；链表只保留在线评测平台常见的节点操作。

一、先根据操作选择容器

主要需求	优先选择	关键复杂度与限制
动态连续数组、按下标访问	std::vector	下标 O(1)，尾部追加均摊 O(1)，中间插入/删除 O(n)
固定长度连续数组	std::array<T, N>	长度在编译期确定，按下标访问 O(1)
两端频繁插入和删除	std::deque	两端操作 O(1)，支持随机访问，但内存不保证整体连续
已知位置的频繁插入/删除	std::list	已有迭代器时插入/删除 O(1)，不支持随机访问，查找位置仍为 O(n)
后进先出	std::stack	push()、pop()、top() 通常为 O(1)
先进先出	std::queue	push()、pop()、front() 通常为 O(1)
动态取得最大值或最小值	std::priority_queue	top() 为 O(1)，push()、pop() 为 O(log n)
键有序、需要范围查找	std::map、std::set	查找、插入、删除为 O(log n)
只关心快速键查找	std::unordered_map、std::unordered_set	平均 O(1)，最坏 O(n)；不保证遍历顺序

不要看到“插入删除 O(1)”就默认选择 std::list。算法题经常需要按下标访问、排序和利用缓存局部性，std::vector 通常更简单。只有题目确实围绕链表位置操作，并且已经持有目标迭代器时，std::list 的优势才成立。

二、std::vector：默认的动态数组

#include <vector>

std::vector<int> values{3, 1, 4};
values.push_back(1);
values.emplace_back(5);

const int first = values.front();
const int last = values.back();
const int value = values[2];

values.pop_back(); // 不返回被删除的元素，调用前必须非空。

reserve() 与 resize() 不同

std::vector<int> values;
values.reserve(100); // size() 仍为 0，只预留容量。
values.resize(100);  // size() 变为 100，新元素进行值初始化。

• 已知大约会追加多少元素时，可使用 reserve() 减少重新分配；
• 需要立即通过下标访问 0 到 n - 1 时，应构造 std::vector<T>(n) 或调用 resize(n)；
• reserve(n) 之后直接写 values[0] 仍然越界。

迭代器与引用失效

std::vector 扩容时会把元素迁移到新的存储区域，原有指针、引用和迭代器都会失效。即使没有扩容，在中间插入或删除也会使操作位置及其后的迭代器失效。

因此，不要长期保存 &values[0] 或某个迭代器后继续无条件 push_back()。如果确实要通过下标记录位置，保存整数下标通常比保存迭代器更容易重新定位。

三、有序容器与哈希容器

1. std::map 与 std::unordered_map

#include <string>
#include <unordered_map>

std::unordered_map<std::string, int> frequency;
for (const std::string& word : words) {
    ++frequency[word];
}

operator[] 在键不存在时会插入一个值初始化的元素。对计数很方便，但只想查询时可能造成意外修改：

const auto iterator = frequency.find("error");
if (iterator != frequency.end()) {
    std::cout << iterator->second << '\n';
}

选择依据：

• 需要按键排序输出、查找前驱后继或执行范围查询：使用 std::map；
• 只关心键到值的快速映射：优先 std::unordered_map；
• 题目要求确定的遍历顺序时，不要依赖哈希表当前“看起来稳定”的输出顺序。

2. std::set 与 std::unordered_set

集合只保存键，适合判重和成员检查：

#include <unordered_set>
#include <vector>

std::vector<int> deduplicate(const std::vector<int>& values) {
    std::unordered_set<int> seen;
    std::vector<int> result;
    result.reserve(values.size());

    for (int value : values) {
        if (seen.insert(value).second) {
            result.push_back(value);
        }
    }
    return result;
}

insert() 返回的 std::pair 中，第二项表示本次是否真的插入了新元素。上面的写法既完成判重，又保留第一次出现的顺序。

四、栈、队列与优先队列

这三类是容器适配器，只暴露受限制的接口，不提供迭代器。

#include <queue>
#include <stack>

std::stack<int> stack;
stack.push(10);
const int latest = stack.top();
stack.pop();

std::queue<int> queue;
queue.push(10);
const int earliest = queue.front();
queue.pop();

std::priority_queue<int> maxHeap;
maxHeap.push(10);
maxHeap.push(30);
const int maximum = maxHeap.top(); // 30

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

pop() 都不返回元素，应先读取 top() 或 front()，再删除；调用这些函数前必须确认容器非空。

五、std::pair、结构化绑定与自定义记录

#include <string>
#include <utility>

std::pair<int, std::string> record{7, "online"};
const auto [id, state] = record; // C++17 结构化绑定

当字段有清楚的业务含义时，优先定义结构体，而不是让 first、second 承担过多含义：

struct Task {
    int id;
    int priority;
};

六、贯穿场景：支持取消和更新的优先任务调度

设计一个任务队列：

• ADD id priority：添加任务；同一 id 再次添加表示更新优先级；
• CANCEL id：取消任务；
• RUN：执行当前优先级最高的任务，优先级相同时先执行 id 较小的任务；
• 没有可执行任务时输出 EMPTY。

std::priority_queue 不支持从中间删除元素。可采用“延迟删除”：哈希表保存每个任务当前有效的优先级，堆中允许保留旧记录；访问堆顶时再丢弃失效记录。

// verify: cpp17
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

struct Task {
    int id;
    int priority;
};

struct LowerPriority {
    bool operator()(const Task& left, const Task& right) const {
        if (left.priority != right.priority) {
            return left.priority < right.priority;
        }
        return left.id > right.id;
    }
};

using TaskHeap = std::priority_queue<Task, std::vector<Task>, LowerPriority>;

void removeStaleTasks(
    TaskHeap& heap,
    const std::unordered_map<int, int>& activePriorities
) {
    while (!heap.empty()) {
        const Task& task = heap.top();
        const auto iterator = activePriorities.find(task.id);

        if (iterator != activePriorities.end()
            && iterator->second == task.priority) {
            return;
        }
        heap.pop();
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int operationCount = 0;
    std::cin >> operationCount;

    TaskHeap heap;
    std::unordered_map<int, int> activePriorities;

    for (int i = 0; i < operationCount; ++i) {
        std::string command;
        std::cin >> command;

        if (command == "ADD") {
            int id = 0;
            int priority = 0;
            std::cin >> id >> priority;
            activePriorities[id] = priority;
            heap.push(Task{id, priority});
        } else if (command == "CANCEL") {
            int id = 0;
            std::cin >> id;
            activePriorities.erase(id);
        } else if (command == "RUN") {
            removeStaleTasks(heap, activePriorities);
            if (heap.empty()) {
                std::cout << "EMPTY\n";
                continue;
            }

            const Task task = heap.top();
            heap.pop();
            activePriorities.erase(task.id);
            std::cout << task.id << '\n';
        }
    }

    return 0;
}

输入：

8
ADD 101 5
ADD 102 8
ADD 103 8
CANCEL 102
RUN
ADD 101 10
RUN
RUN

输出：

103
101
EMPTY

执行过程

1. 102 和 103 的优先级相同，堆顶原本会优先选择 id 更小的 102；
2. CANCEL 102 只从哈希表删除任务，堆中的旧记录暂时保留；
3. 第一次 RUN 检查堆顶，发现 102 已失效，于是弹出它并执行 103；
4. ADD 101 10 把哈希表中的当前优先级更新为 10，旧的优先级 5 记录因此失效；
5. 第二次 RUN 执行新的 101，第三次 RUN 清理旧记录后输出 EMPTY。

每条堆记录最多入堆和出堆一次。一次 ADD 为 O(log q)，CANCEL 平均为 O(1)；RUN 可能连续清理多个旧记录，但整个操作序列的堆操作总量为 O(q log q)。堆最多保留 O(q) 条记录，这正是延迟删除换取简单更新逻辑的空间代价。

七、链表的考场模板

在线评测平台通常给出节点定义：

struct ListNode {
    int value;
    ListNode* next;
};

1. 反转单链表

ListNode* reverseList(ListNode* head) {
    ListNode* previous = nullptr;
    ListNode* current = head;

    while (current != nullptr) {
        ListNode* next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

每次修改 current->next 前，必须先保存原来的下一节点。时间复杂度为 O(n)，额外空间为 O(1)。

2. 快慢指针判断环

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

时间复杂度为 O(n)，额外空间为 O(1)。平台拥有节点时，不要在解题函数中自行 delete 节点，除非题目明确把内存管理职责交给提交代码。

八、两类代表题

代表题二：括号匹配

#include <stack>
#include <string>

bool isValidBrackets(const std::string& text) {
    std::stack<char> openings;

    for (char ch : text) {
        if (ch == '(' || ch == '[' || ch == '{') {
            openings.push(ch);
            continue;
        }

        if (ch != ')' && ch != ']' && ch != '}') {
            continue;
        }
        if (openings.empty()) {
            return false;
        }

        const char left = openings.top();
        openings.pop();
        const bool matched = (left == '(' && ch == ')')
            || (left == '[' && ch == ']')
            || (left == '{' && ch == '}');
        if (!matched) {
            return false;
        }
    }

    return openings.empty();
}

时间和空间复杂度均为 O(n)。

代表题三：无权图最短边数

#include <queue>
#include <vector>

std::vector<int> shortestDistances(
    const std::vector<std::vector<int>>& graph,
    int start
) {
    std::vector<int> distance(graph.size(), -1);
    std::queue<int> pending;

    distance[static_cast<std::size_t>(start)] = 0;
    pending.push(start);

    while (!pending.empty()) {
        const int node = pending.front();
        pending.pop();

        for (int next : graph[static_cast<std::size_t>(node)]) {
            if (distance[static_cast<std::size_t>(next)] != -1) {
                continue;
            }
            distance[static_cast<std::size_t>(next)]
                = distance[static_cast<std::size_t>(node)] + 1;
            pending.push(next);
        }
    }
    return distance;
}

每个顶点和每条边只被处理常数次，时间复杂度为 O(V + E)，空间复杂度为 O(V)，不包含输入图本身。

九、常见错误

• 把 reserve() 当成 resize()，随后直接通过下标写入；
• 在 std::vector 扩容、插入或删除后继续使用旧迭代器；
• 只查询哈希表却使用 operator[]，意外插入新键；
• 依赖 std::unordered_map 的遍历顺序；
• 调用 top()、front()、back() 或 pop() 前没有判空；
• 把 std::priority_queue 的比较器方向理解反；
• 认为 std::list 的任意位置查找也是 O(1)；
• 反转链表时先覆盖 next，导致剩余链表丢失；
• 在平台管理链表节点时擅自释放内存。

十、考前速查清单

std::vector<int> values;
values.push_back(value);

std::unordered_map<int, int> count;
++count[key];
if (count.find(key) != count.end()) {
    // key exists in C++17
}

std::stack<int> stack;
std::queue<int> queue;
std::priority_queue<int> maxHeap;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

• 动态数组默认 std::vector；
• 两端操作使用 std::deque；
• 有序范围查询使用 std::map、std::set；
• 快速键查找使用哈希容器，但不依赖其顺序；
• 需要动态最值时使用 std::priority_queue；
• 容器适配器先取值、后 pop()；
• 链表先保存下一节点，再修改指针。

十一、C++20 可选补充

C++20 为关联容器增加了 contains(key)，可以直接判断键是否存在。C++17 中统一使用 find(key) != end()，避免在考试中误用不可用的接口。

十二、已有专题与延伸练习

已有文章可用于第二轮深入复习：

• CPP学习笔记—标准模板库（STL）中的容器
• CPP学习笔记—unordered_map
• CPP学习笔记—priority_queue

练习题：

• LeetCode 20：有效的括号
• LeetCode 347：前 K 个高频元素
• LeetCode 933：最近的请求次数
• LeetCode 141：环形链表

参考资料

• C++17 工作草案 N4659
• Microsoft Learn：C++ 标准库容器
• Microsoft Learn：迭代器
• Microsoft Learn：priority_queue 类