Bộ điều hợp container & Container đặc biệt

Learn about stack, queue, priority_queue, and modern vocabulary types like span, string_view, and optional. Understand when adaptors simplify your code.

What Are Container Adaptors?

Container adaptors are wrappers around existing containers that provide a restricted interface. They enforce a specific access pattern by hiding the full container API:

- std::stack — LIFO (Last In, First Out), backed bydequeby default
- std::queue — FIFO (First In, First Out), backed bydequeby default
- std::priority_queue — max-heap, backed byvectorby default

Adaptors do not provide iterators — you can only access the top/front element. This restriction is intentional: it makes the code's intent clearer and prevents accidental misuse.

Stack and Queue in Action

Stacks and queues are fundamental data structures used in parsing, BFS/DFS, undo systems, and task scheduling.

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
    }
}

Priority Queue (Heap)

std::priority_queueis a max-heap by default —top()returns the largest element. For a min-heap, usestd::greateras the comparator.

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 — Non-Owning View of Contiguous Data (C++20)

std::spanlà chế độ xem nhẹ, không sở hữu đối với một chuỗi các phần tử liền kề. Nó thay thế kiểu dễ xảy ra lỗi khi chuyển các cặp(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 and optional

std::string_view (C++17) là tham chiếu không sở hữu, chỉ đọc đối với một chuỗi. Nó tránh được chi phí sao chép hoặc phân bổstd::stringcho các chức năng chỉ cần đọc:

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::tùy chọn (C++17) represents a value that might or might not be present — a type-safe replacement for "magic values" or raw pointers to indicate absence:

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

Lỗi thường gặp

Vìstd::string_viewvàstd::spankhông sở hữu nên chúng có thể dễ dàng bị treo nếu dữ liệu cơ bản bị hủy:

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

Never return a string_view or span to a local variable. They are safe for function parameters (the caller's data outlives the call), but dangerous as return values unless you can guarantee the source outlives the view.

The same applies to std::span — nó chỉ là một con trỏ và một kích thước bên trong, không có ngữ nghĩa về quyền sở hữu.

Thực hành tốt

Sử dụng bộ điều hợp vùng chứa khi bạn muốn thực thi kỷ luật về cách truy cập các phần tử:

- Sử dụngstd::stackthay vìdequehoặcvectorthô khi chỉ truy cập LIFO mới có ý nghĩa. Điều này làm cho mục đích rõ ràng và ngăn chặn việc truy cập ngẫu nhiên.
- Sử dụngstd::queueđể xử lý FIFO (hàng đợi tác vụ, BFS).
- Sử dụngstd::priority_queueđể lập lịch, thuật toán Dijkstra hoặc bất kỳ tình huống nào mà bạn luôn muốn phần tử cực trị.

Nếu bạn cần lặp lại, truy vấn kích thước tại các điểm tùy ý hoặc truy cập giữa chuỗi, hãy sử dụng trực tiếp vùng chứa bên dưới.

Điểm chính

Bộ điều hợp vùng chứa (stack,queue,priority_queue) hạn chế giao diện để thực thi kỷ luật sử dụng
Theo mặc định,std::priority_queuelà vùng heap tối đa - sử dụngstd::greatercho vùng heap tối thiểu
std::span(C++20) cung cấp chế độ xem không sở hữu đối với dữ liệu liền kề, thay thế các cặp(pointer, size)
std::string_view(C++17) tránh sao chép chuỗi để sử dụng chỉ đọc — nhưng hãy chú ý đến các tham chiếu lơ lửng
std::optional(C++17) là cách an toàn về loại để thể hiện "có thể không có giá trị" mà không có giá trị trọng điểm ma thuật
Chế độ xem không sở hữu (span,string_view) không bao giờ được tồn tại lâu hơn dữ liệu mà chúng tham chiếu

Câu đố — Kiểm tra kiến thức

(15 XP)

1. Bộ chuyển đổi vùng chứa nào cung cấp hành vi FIFO (Vào trước, ra trước)?

2. What type does`std::priority_queue<int>`return from`top()`by default?

3. Why is returning a`std::string_view`to a local`std::string`dangerous?

Vùng chứa kết hợp: bản đồ, bộ, unordered_map

Tiếp

Iterators: The STL Glue