This programming guide is only available in Vietnamese. Switch to Vietnamese to read the full article.

Thư viện chuẩn STL (Standard Template Library) cung cấp nhiều hơn chỉ std::vector và std::string. Bài học này khám phá các container mạnh mẽ khác: std::deque (Double-Ended Queue) cho truy cập O(1) ở cả hai đầu, std::list (Doubly-Linked List) cho chèn/xóa O(1) ở bất kỳ vị trí nào, và các container kết hợp khóa-giá trị như std::map (sắp xếp) và std::unordered_map (hash table). Hiểu rõ khi nào sử dụng mỗi container là chìa khóa để viết code C++ hiệu quả.

1. Tổng quan: Sequence vs Associative Containers

STL chia container thành hai loại chính: Sequence Containers (vector, deque, list) lưu trữ các phần tử theo thứ tự và cho phép truy cập theo chỉ số, và Associative Containers (map, set, unordered_map, unordered_set) lưu trữ các cặp khóa-giá trị và tối ưu hóa cho tìm kiếm nhanh.

So sánh nhanh:

• std::vector: Mảng động, O(1) access, O(1) push_back nhưng O(n) insert/erase ở giữa.
• std::deque: Queue hai đầu, O(1) push_front/push_back, O(n) insert/erase ở giữa.
• std::list: Danh sách liên kết, O(1) insert/erase mọi vị trí nếu có iterator, nhưng O(n) access theo chỉ số.
• std::map: Cây tìm kiếm đỏ-đen, O(log n) insert/search/delete, phần tử sắp xếp.
• std::unordered_map: Hash table, O(1) insert/search/delete trung bình, không sắp xếp.
• std::set: Giống map nhưng chỉ lưu khóa (không có giá trị), phần tử sắp xếp.

2. std::deque: Double-Ended Queue (Hàng đợi hai đầu)

std::deque cho phép chèn và xóa hiệu quả ở cả hai đầu mà không cần reallocate toàn bộ dữ liệu như vector. Nó thực hiện điều này bằng cách chia dữ liệu thành các "khối" (blocks) nhỏ và quản lý con trỏ đến các khối này.

Cấu trúc bộ nhớ của std::deque:

std::deque trong RAM:

┌─────────────────────┐
│ Map (mảng con trỏ) │─→ Block 0 ──→ [10, 20, 30, ...]
│ front_ptr ───┐     │─→ Block 1 ──→ [40, 50, 60, ...]
│ back_ptr ────┘     │─→ Block 2 ──→ [70, 80, ...]
└─────────────────────┘

Với cấu trúc này:
- push_front/push_back: O(1)
- pop_front/pop_back: O(1)
- Truy cập deque[i]: O(1)
- insert/erase ở giữa: O(n)
              

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {5, 10};

    // O(1) chèn ở cả hai đầu
    dq.push_front(1);      // dq = {1, 5, 10}
    dq.push_back(15);      // dq = {1, 5, 10, 15}

    std::cout << "Front: " << dq.front() << std::endl;  // 1
    std::cout << "Back: " << dq.back() << std::endl;    // 15

    // O(1) xóa ở cả hai đầu
    dq.pop_front();        // dq = {5, 10, 15}
    dq.pop_back();         // dq = {5, 10}

    // O(1) truy cập theo chỉ số
    std::cout << "Element at 0: " << dq[0] << std::endl;

    // Duyệt
    for (int val : dq) {
        std::cout << val << " ";
    }

    return 0;
}

Khi nào dùng std::deque?

Sử dụng deque khi bạn cần thêm/xóa phần tử ở cả hai đầu một cách thường xuyên (ví dụ: xử lý task queue, buffer vòng), hoặc khi không cần chèn/xóa ở giữa mà chủ yếu tác động ở hai đầu.

3. std::list: Doubly-Linked List (Danh sách liên kết kép)

std::list là danh sách liên kết, mỗi phần tử chứa con trỏ đến phần tử trước và sau. Điều này cho phép chèn/xóa O(1) ở bất kỳ vị trí nào nếu bạn có iterator, nhưng truy cập theo chỉ số phải duyệt từ đầu (O(n)).

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {10, 20, 30};

    // Chèn ở đầu: O(1)
    lst.push_front(5);     // lst = {5, 10, 20, 30}

    // Chèn ở cuối: O(1)
    lst.push_back(40);     // lst = {5, 10, 20, 30, 40}

    // Tìm và chèn ở giữa: O(n) để tìm, O(1) để chèn
    auto it = lst.begin();
    std::advance(it, 2);   // Di chuyển iterator đến phần tử thứ 2
    lst.insert(it, 15);    // Chèn 15 trước vị trí it

    std::cout << "List sau insert: ";
    for (int val : lst) {
        std::cout << val << " ";  // 5 10 15 20 30 40
    }

    // Xóa phần tử
    lst.remove(20);        // Xóa tất cả 20 (chỉ trong list)

    return 0;
}

Khi nào dùng std::list?

Dùng list khi bạn thường xuyên chèn/xóa ở giữa container và không cần truy cập nhanh theo chỉ số. Ví dụ: LRU cache, task scheduler với insertion/deletion thường xuyên.

4. std::map & std::unordered_map: Key-Value Storage

Map lưu trữ các cặp (khóa, giá trị) và tối ưu cho việc tìm kiếm theo khóa. std::map dùng cây tìm kiếm đỏ-đen (O(log n)), còn std::unordered_map dùng hash table (O(1) trung bình).

#include <iostream>
#include <map>
#include <unordered_map>

int main() {
    // std::map: Sắp xếp tự động theo khóa
    std::map<std::string, int> ages;
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    // Duyệt: tự động sắp xếp theo khóa
    std::cout << "Ordered map:\n";
    for (const auto& pair : ages) {
        std::cout << pair.first << " -> " << pair.second << "\n";
    }  // Alice -> 30, Bob -> 25, Charlie -> 35

    // std::unordered_map: Không sắp xếp, hash table
    std::unordered_map<std::string, int> scores;
    scores["Python"] = 9;
    scores["JavaScript"] = 8;
    scores["C++"] = 10;

    // Tìm kiếm: O(1) trung bình vs O(log n) cho map
    if (scores.find("C++") != scores.end()) {
        std::cout << "Found C++: " << scores["C++"] << "\n";
    }

    return 0;
}

Bảng So sánh: std::map vs std::unordered_map

5. std::set & std::unordered_set: Unique Elements

std::set và std::unordered_set giống map nhưng chỉ lưu khóa (không có giá trị), và tự động đảm bảo tất cả phần tử là duy nhất. Sử dụng khi bạn cần đếm phần tử duy nhất hoặc kiểm tra sự tồn tại.

#include <iostream>
#include <set>
#include <unordered_set>

int main() {
    // std::set: Phần tử duy nhất, sắp xếp
    std::set<int> primes = {2, 3, 5, 7, 11};
    primes.insert(13);     // Thêm 13
    primes.insert(5);      // Không thêm (5 đã tồn tại)

    std::cout << "Primes set size: " << primes.size() << "\n";  // 6

    // std::unordered_set: Phần tử duy nhất, không sắp xếp
    std::unordered_set<std::string> visited;
    visited.insert("home");
    visited.insert("shop");
    visited.insert("home");    // Không thêm (đã tồn tại)

    // Kiểm tra sự tồn tại
    if (visited.count("shop")) {
        std::cout << "Already visited shop\n";
    }

    return 0;
}

6. Container Selection Guide: Bảng quyết định

Chọn container đúng là điều cơ bản nhất trong C++ hiệu quả. Dưới đây là sơ đồ quyết định:

Câu hỏi: Tôi cần gì?

1. Cần truy cập nhanh theo chỉ số (O(1))?
   -> Có: std::vector hoặc std::deque
   -> Không: tiếp tục 2

2. Cần chèn/xóa ở giữa thường xuyên?
   -> Có: std::list
   -> Không: tiếp tục 3

3. Cần tìm kiếm theo khóa?
   -> Có: std::map (nếu cần sắp xếp) hoặc std::unordered_map (nếu cần tốc độ)
   -> Không: tiếp tục 4

4. Cần các phần tử duy nhất?
   -> Có: std::set (sắp xếp) hoặc std::unordered_set (không sắp xếp)
   -> Không: quay lại bước 1
              

Bảng so sánh toàn diện:

* = Chỉ ở hai đầu, ** = Nếu có iterator, N/A = Không áp dụng

7. Code thực hành toàn diện: containers_demo.cpp

Ví dụ dưới đây minh họa cách sử dụng tất cả các container:

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <set>

int main() {
    // ===== Vector: Truy cập nhanh =====
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::cout << "Vector[2]: " << vec[2] << "\n";

    // ===== Deque: Queue hai đầu =====
    std::deque<std::string> queue;
    queue.push_back("task1");
    queue.push_back("task2");
    queue.pop_front();  // Remove task1

    // ===== List: Chèn/xóa ở giữa =====
    std::list<int> lst = {10, 30, 50};
    auto it = lst.begin();
    ++it;
    lst.insert(it, 20);  // Chèn 20 giữa 10 và 30

    // ===== Map: Tìm theo khóa + sắp xếp =====
    std::map<std::string, int> dict;
    dict["apple"] = 5;
    dict["banana"] = 3;
    std::cout << "apple count: " << dict["apple"] << "\n";

    // ===== Unordered_map: Tìm theo khóa nhanh =====
    std::unordered_map<int, std::string> cache;
    cache[1] = "one";
    cache[2] = "two";

    // ===== Set: Phần tử duy nhất =====
    std::set<int> unique_nums = {1, 2, 2, 3, 3, 3};
    std::cout << "Unique count: " << unique_nums.size() << "\n";  // 3

    return 0;
}