C++

容器适配器与特殊容器

学习 stack、queue、priority_queue 以及现代词汇类型如 span、string_view 和 optional。了解适配器何时能简化你的代码。

什么是容器适配器？

容器适配器是现有容器的包装器，提供受限的接口。它们通过隐藏完整的容器 API 来强制执行特定的访问模式：

- std::stack ── LIFO（后进先出），默认基于 deque
- std::queue ── FIFO（先进先出），默认基于 deque
- std::priority_queue ── 最大堆，默认基于 vector

适配器不提供迭代器──你只能访问顶部/前端元素。这种限制是有意为之的：它使代码意图更清晰，并防止意外误用。

栈和队列实战

栈和队列是用于解析、BFS/DFS、撤销系统和任务调度的基础数据结构。

stack_queue.cpp
#include <stack>
#include <queue>
#include <string>
#include <iostream>

// Check if parentheses are balanced using a stack
bool is_balanced(const std::string& expr) {
    std::stack<char> stk;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            stk.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stk.empty()) return false;
            char top = stk.top();
            stk.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stk.empty();
}

int main() {
    std::cout << std::boolalpha;
    std::cout << is_balanced("({[]})") << '\n';   // true
    std::cout << is_balanced("({[}])") << '\n';   // false

    // Queue — BFS-style task processing
    std::queue<std::string> tasks;
    tasks.push("compile");
    tasks.push("link");
    tasks.push("run tests");

    while (!tasks.empty()) {
        std::cout << "Processing: " << tasks.front() << '\n';
        tasks.pop();   // removes from front
    }
}

优先队列（堆）

std::priority_queue 默认是最大堆──top() 返回最大的元素。要实现最小堆，使用 std::greater 作为比较器。

priority_queue.cpp
#include <queue>
#include <vector>
#include <functional>
#include <iostream>
#include <string>

struct Task {
    int priority;
    std::string name;
};

int main() {
    // Max-heap (default) — largest first
    std::priority_queue<int> max_heap;
    max_heap.push(30);
    max_heap.push(10);
    max_heap.push(50);
    max_heap.push(20);

    while (!max_heap.empty()) {
        std::cout << max_heap.top() << ' ';  // 50 30 20 10
        max_heap.pop();
    }
    std::cout << '\n';

    // Min-heap — smallest first
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(30);
    min_heap.push(10);
    min_heap.push(50);
    std::cout << "Min: " << min_heap.top() << '\n';  // 10

    // Custom comparator with lambda
    auto cmp = [](const Task& a, const Task& b) {
        return a.priority < b.priority;  // higher priority first
    };
    std::priority_queue<Task, std::vector<Task>, decltype(cmp)> task_queue(cmp);
    task_queue.push({3, "low priority"});
    task_queue.push({10, "critical"});
    task_queue.push({7, "medium"});

    while (!task_queue.empty()) {
        auto& t = task_queue.top();
        std::cout << "[" << t.priority << "] " << t.name << '\n';
        task_queue.pop();
    }
}

std::span ── 连续数据的非拥有视图（C++20）

std::span 是对连续元素序列的轻量级非拥有视图。它替代了传递 (pointer, size) 对的容易出错的模式。

span_example.cpp
#include <span>
#include <vector>
#include <array>
#include <iostream>
#include <numeric>

// span accepts vector, array, C-array — anything contiguous
void print_stats(std::span<const int> data) {
    if (data.empty()) return;
    std::cout << "Size: " << data.size() << '\n';
    std::cout << "First: " << data.front() << '\n';
    std::cout << "Last:  " << data.back() << '\n';

    int sum = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "Sum:   " << sum << '\n';

    // Subviews
    auto first3 = data.first(3);   // first 3 elements
    auto last2  = data.last(2);    // last 2 elements
    auto mid    = data.subspan(1, 3);  // 3 elements starting at index 1
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::array<int, 5> arr = {10, 20, 30, 40, 50};
    int c_arr[] = {100, 200, 300, 400, 500};

    print_stats(vec);     // works with vector
    print_stats(arr);     // works with array
    print_stats(c_arr);   // works with C-array
}

string_view 和 optional

std::string_view（C++17）是对字符串的非拥有只读引用。对于只需要读取的函数，它避免了复制或分配 std::string 的开销：

void greet(std::string_view name) {  // no copy, no allocation
    std::cout << "Hello, " << name << '\n';
}
greet("world");               // works with string literals
greet(std::string{"world"});  // works with std::string

std::optional（C++17）表示一个可能存在也可能不存在的值──它是「魔法值」或原始指针用于表示缺失的类型安全替代品：

std::optional<int> find_index(std::span<const int> data, int target) {
    for (int i = 0; i < data.size(); ++i)
        if (data[i] == target) return i;
    return std::nullopt;  // not found
}
auto idx = find_index(vec, 42);
if (idx) std::cout << "Found at " << *idx << '\n';
std::cout << idx.value_or(-1) << '\n';  // -1 if empty
常见陷阱

由于 std::string_view 和 std::span 是非拥有的，如果底层数据被销毁，它们很容易变成悬空引用：

std::string_view bad() {
    std::string temp = "hello";
    return temp;  // DANGLING — temp destroyed at end of scope
}

永远不要返回指向局部变量的 string_view 或 span。它们作为函数参数是安全的（调用者的数据在调用期间存活），但作为返回值是危险的，除非你能保证数据源比视图存活更久。

同样的规则适用于 std::span──它内部只是一个指针和一个大小，没有所有权语义。

最佳实践

当你想要强制规范元素的访问方式时，使用容器适配器：

- 当只有 LIFO 访问有意义时，使用 std::stack 而不是原始的 deque 或 vector。这使意图显而易见，并防止意外的随机访问。
- 使用 std::queue 进行 FIFO 处理（任务队列、BFS）。
- 使用 std::priority_queue 进行调度、Dijkstra 算法或任何你总是需要极端元素的场景。

如果你需要迭代、在任意点查询大小或中间序列访问，请直接使用底层容器。

关键要点
  • 容器适配器（stack、queue、priority_queue）限制接口以强制使用规范
  • std::priority_queue 默认是最大堆──使用 std::greater 实现最小堆
  • std::span（C++20）提供对连续数据的非拥有视图，替代 (pointer, size) 对
  • std::string_view（C++17）避免为只读使用复制字符串──但要注意悬空引用
  • std::optional（C++17）是表示「可能没有值」的类型安全方式，无需魔法哨兵值
  • 非拥有视图（span、string_view）绝不能比它们引用的数据存活更久

测验 — 检验你的知识

(15 经验值)

1. 哪种容器适配器提供 FIFO（先进先出）行为？

2. `std::priority_queue<int>` 的 `top()` 默认返回什么？

3. 为什么返回指向局部 `std::string` 的 `std::string_view` 是危险的？

上一课
关联容器：map、set、unordered_map
下一课
迭代器：STL 的粘合剂