🗃️ STL Containers: vector, map, unordered_map Module 3

Bạn đang build hệ thống quản lý kho hàng cho một sàn e-commerce. Backend team cần: tra cứu sản phẩm theo SKU trong O(1), hiển thị danh mục theo thứ tự giá, và lưu danh sách hàng trong giỏ có thứ tự thêm vào. Ba nhu cầu khác nhau — ba container khác nhau. Chọn sai container, hệ thống chậm gấp 100 lần khi scale lên triệu sản phẩm.

STL (Standard Template Library) là kho vũ khí có sẵn của C++. Bạn không cần tự implement linked list hay hash table — STL đã làm hết, và làm tốt hơn bạn 99% trường hợp. Bài này tập trung vào ba container chiếm 90% use case thực tế: vector, map, và unordered_map.

🎯 Mục tiêu

Nắm vững ba container cốt lõi: std::vector, std::map, std::unordered_map
Biết khi nào dùng cái nào — decision matrix rõ ràng, không đoán mò
Thuộc bảng complexity cho mỗi operation (insert, lookup, delete)
Sử dụng structured bindings (C++17) để iterate map gọn gàng
Hiểu iterator basics — keo dán giữa containers và algorithms
Nhận diện anti-pattern phổ biến khi chọn container sai

1. STL Container Landscape — Bức Tranh Toàn Cảnh

🧠 Mental Model

STL có ~15 container, nhưng thực tế bạn chỉ cần nhớ ba nhóm chính:

┌────────────────────────────────────────────────────────────────┐
│                    STL Container Family                        │
│                                                                │
│  📦 Sequence Containers (có thứ tự thêm vào)                   │
│  ├── std::vector      ← ⭐ Dùng nhiều nhất                     │
│  ├── std::deque       ← Push/pop hai đầu                      │
│  ├── std::list        ← Doubly-linked list                    │
│  └── std::array       ← Fixed-size, stack-allocated           │
│                                                                │
│  🌳 Associative Containers (sorted by key, Red-Black Tree)     │
│  ├── std::map         ← ⭐ Key-value, sorted                   │
│  ├── std::set         ← Unique keys, sorted                   │
│  ├── std::multimap    ← Duplicate keys OK                     │
│  └── std::multiset    ← Duplicate keys OK                     │
│                                                                │
│  #️⃣ Unordered Containers (hash table)                          │
│  ├── std::unordered_map  ← ⭐ Key-value, O(1) lookup           │
│  ├── std::unordered_set  ← Unique keys, O(1) lookup           │
│  ├── std::unordered_multimap                                   │
│  └── std::unordered_multiset                                   │
└────────────────────────────────────────────────────────────────┘

Ba Container Chiến Lược

Trong thực tế production, 90% thời gian bạn chỉ cần ba container:

Container	Khi nào dùng	Ví dụ thực tế
`std::vector`	Cần danh sách có thứ tự, truy cập index	Giỏ hàng, danh sách kết quả
`std::map`	Cần key-value sorted	Bảng xếp hạng, log theo timestamp
`std::unordered_map`	Cần key-value tra cứu nhanh	Cache, đếm tần suất, lookup by ID

💡 Quy tắc vàng

Không biết chọn gì? Bắt đầu với std::vector. Nếu cần key-value lookup → unordered_map. Chỉ dùng map khi thật sự cần sorted keys.

2. std::vector — Ôn Tập Nhanh

Đã cover chi tiết ở Bài 03: Vector First. Đây là phần ôn tập ngắn gọn những điểm quan trọng nhất.

2.1 Đặc Điểm Cốt Lõi

Bộ nhớ liên tục (contiguous) — cache-friendly, nhanh hơn list trên hardware hiện đại
Random access O(1) — truy cập vec[i] tức thì
push_back amortized O(1) — thỉnh thoảng reallocate, nhưng trung bình vẫn O(1)
Default choice cho mọi sequence data

cpp

#include <vector>
#include <iostream>

int main() {
    std::vector<int> scores = {95, 87, 92, 78, 88};

    scores.push_back(91);           // Thêm cuối — O(1) amortized
    scores[2] = 100;                // Random access — O(1)

    // Range-based for (C++11)
    for (int score : scores) {
        std::cout << score << " ";
    }
    // Output: 95 87 100 78 88 91
}

2.2 Complexity Table — vector

Operation	Complexity	Ghi chú
`push_back`	O(1) amortized	Reallocate khi hết capacity
`pop_back`	O(1)
`operator[]`	O(1)	Không bounds-check
`.at(i)`	O(1)	Có bounds-check, throw `out_of_range`
`insert(pos, val)`	O(n)	Dịch chuyển phần tử phía sau
`erase(pos)`	O(n)	Dịch chuyển phần tử phía sau
`find` (linear)	O(n)	Không có `.find()`, dùng `std::find`
`size()`	O(1)

3. std::map — Ordered Key-Value Store

3.1 Cấu Trúc Bên Trong

std::map được implement bằng Red-Black Tree (cây nhị phân cân bằng). Điều này có nghĩa:

Keys luôn sorted — iterate sẽ ra thứ tự tăng dần
Mọi operation chính đều O(log n)
Key phải implement operator< (hoặc cung cấp custom comparator)

         ┌────────┐
         │keyboard│
         │  79.99 │
         └───┬────┘
        ╱         ╲
  ┌────────┐   ┌────────┐
  │  book  │   │ laptop │
  │  19.99 │   │ 999.99 │
  └────────┘   └───┬────┘
                    ╲
                ┌────────┐
                │ mouse  │
                │  29.99 │
                └────────┘

  → Traverse in-order: book, keyboard, laptop, mouse (sorted!)

3.2 API Cơ Bản

cpp

#include <map>
#include <string>
#include <iostream>

int main() {
    std::map<std::string, double> prices;

    // ── INSERT ──────────────────────────────────────
    prices["laptop"] = 999.99;              // operator[] — insert hoặc overwrite
    prices["mouse"] = 29.99;
    prices.insert({"keyboard", 79.99});     // insert — KHÔNG overwrite nếu key tồn tại
    prices.emplace("book", 19.99);          // emplace — construct in-place

    // ── LOOKUP ──────────────────────────────────────
    double laptopPrice = prices["laptop"];       // ⚠️ Tạo entry mới nếu key không tồn tại!
    double mousePrice  = prices.at("mouse");     // ✅ Throw exception nếu key không tồn tại

    // ── CHECK EXISTENCE ─────────────────────────────
    if (prices.count("tablet") == 0) {
        std::cout << "Không có tablet trong kho\n";
    }

    // C++20: contains() — đọc rõ ràng hơn count()
    if (!prices.contains("tablet")) {
        std::cout << "Vẫn không có tablet\n";
    }

    // ── FIND ────────────────────────────────────────
    auto it = prices.find("keyboard");
    if (it != prices.end()) {
        std::cout << "Tìm thấy: " << it->second << "\n";  // 79.99
    }

    // ── DELETE ───────────────────────────────────────
    prices.erase("book");               // Xóa theo key
    prices.erase(prices.begin());       // Xóa theo iterator

    // ── ITERATE — C++17 Structured Bindings ─────────
    for (const auto& [product, price] : prices) {
        std::cout << product << ": $" << price << "\n";
    }
    // Output SORTED theo key:
    // keyboard: $79.99
    // laptop: $999.99
    // mouse: $29.99
}

3.3 Range Queries — Sức Mạnh Riêng Của map

Lợi thế lớn nhất của std::map so với unordered_map: range queries.

cpp

std::map<int, std::string> leaderboard = {
    {1500, "Alice"}, {1200, "Bob"}, {1800, "Charlie"},
    {900, "Diana"}, {2100, "Eve"}
};

// Tìm tất cả player có điểm >= 1200 và < 1800
auto lower = leaderboard.lower_bound(1200);  // Iterator đến key >= 1200
auto upper = leaderboard.lower_bound(1800);  // Iterator đến key >= 1800

std::cout << "Players trong khoảng [1200, 1800):\n";
for (auto it = lower; it != upper; ++it) {
    std::cout << "  " << it->second << ": " << it->first << " điểm\n";
}
// Output:
//   Bob: 1200 điểm
//   Alice: 1500 điểm

💡 Khi nào dùng std::map

Cần keys sorted (bảng xếp hạng, timeline, price range)
Cần range queries (lower_bound, upper_bound)
Cần iterate theo thứ tự (print sorted output)
Key là custom type mà bạn chưa viết hash function

3.4 Complexity Table — map

Operation	Complexity	Ghi chú
`insert` / `emplace`	O(log n)	Tìm vị trí trong tree
`operator[]`	O(log n)	Insert default nếu key chưa có
`.at(key)`	O(log n)	Throw nếu key không tồn tại
`.find(key)`	O(log n)	Trả về iterator
`.count(key)`	O(log n)	0 hoặc 1
`.erase(key)`	O(log n)
`.lower_bound(key)`	O(log n)	Iterator đến key >= input
`.upper_bound(key)`	O(log n)	Iterator đến key > input
Iterate (begin→end)	O(n)	In-order traversal

4. std::unordered_map — Hash Table

4.1 Cấu Trúc Bên Trong

std::unordered_map là hash table — key được hash thành index, tra cứu gần như tức thì.

  Key: "laptop"
    │
    ▼  hash("laptop") = 42
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │     │     │  …  │ [42]│     │     │  …  │     │
  │     │     │     │  ↓  │     │     │     │     │
  └─────┴─────┴─────┴──┬──┴─────┴─────┴─────┴─────┘
                        │
                   ┌────▼─────┐
                   │ "laptop" │
                   │  999.99  │
                   └──────────┘

  → hash(key) → bucket index → truy cập trực tiếp: O(1) average

4.2 API Cơ Bản

API gần như giống hệt std::map — bạn có thể swap giữa hai container chỉ bằng thay đổi type declaration:

cpp

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, double> prices;

    // Cùng API như map
    prices["laptop"] = 999.99;
    prices["mouse"] = 29.99;
    prices.insert({"keyboard", 79.99});
    prices.emplace("book", 19.99);

    // Lookup — cùng cú pháp, nhưng O(1) thay vì O(log n)
    auto it = prices.find("laptop");
    if (it != prices.end()) {
        std::cout << "Giá laptop: $" << it->second << "\n";
    }

    // C++17 structured bindings — cùng syntax
    for (const auto& [product, price] : prices) {
        std::cout << product << ": $" << price << "\n";
    }
    // ⚠️ Output KHÔNG sorted — thứ tự phụ thuộc hash function
    // Có thể ra: mouse, laptop, book, keyboard (random order)
}

4.3 Hash Collisions — Khi O(1) Biến Thành O(n)

Khi hai key khác nhau hash ra cùng bucket → collision. STL xử lý bằng chaining (linked list trong mỗi bucket).

  Bucket [42]:  "laptop" → "tablet" → "phone"  (3 collisions!)
                   ↓          ↓          ↓
               tìm tuần tự → O(n) worst case

⚠️ Hash Collision Degrades Performance

Với hash function tệ, unordered_map thoái hóa thành O(n) cho mọi operation. Điều này thường xảy ra khi:

Dùng custom type mà hash function quá đơn giản
Quá nhiều key hash ra cùng giá trị
Giải pháp: dùng reserve() để giảm rehashing, viết hash function tốt cho custom types

4.4 Performance Tuning

cpp

std::unordered_map<std::string, int> wordCount;

// ✅ Reserve buckets trước nếu biết approximate size
// Giảm rehashing, tăng performance đáng kể
wordCount.reserve(10000);

// Kiểm tra load factor
std::cout << "Buckets: " << wordCount.bucket_count() << "\n";
std::cout << "Load factor: " << wordCount.load_factor() << "\n";
std::cout << "Max load factor: " << wordCount.max_load_factor() << "\n";

4.5 Key Requirements

std::unordered_map yêu cầu key phải hashable:

Key Type	Có sẵn `std::hash`?	Ghi chú
`int`, `long`, `double`	✅ Có	Primitive types
`std::string`	✅ Có	Dùng thoải mái
`std::pair`	❌ Không	Phải tự viết hash
Custom `struct`/`class`	❌ Không	Phải tự viết hash + `operator==`

cpp

// Custom hash cho struct
struct Point {
    int x, y;
    bool operator==(const Point& other) const = default;  // C++20
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        auto h1 = std::hash<int>{}(p.x);
        auto h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);  // Combine hashes
    }
};

std::unordered_map<Point, std::string, PointHash> grid;
grid[{0, 0}] = "origin";
grid[{1, 2}] = "target";

4.6 Complexity Table — unordered_map

Operation	Average	Worst Case	Ghi chú
`insert` / `emplace`	O(1)	O(n)	Rehashing khi load factor cao
`operator[]`	O(1)	O(n)	Insert default nếu key chưa có
`.find(key)`	O(1)	O(n)	Hash collision
`.count(key)`	O(1)	O(n)
`.erase(key)`	O(1)	O(n)
`reserve(n)`	O(n)	O(n)	Gọi một lần, tiết kiệm nhiều lần
Iterate	O(n)	O(n)	Thứ tự random

5. map vs unordered_map — Ma Trận Quyết Định

5.1 Bảng So Sánh Head-to-Head

Feature	`std::map`	`std::unordered_map`
Cấu trúc bên trong	Red-Black Tree	Hash Table
Ordering	✅ Sorted theo key	❌ Không có thứ tự
Lookup	O(log n)	O(1) average
Insert	O(log n)	O(1) average
Delete	O(log n)	O(1) average
Memory	Ít hơn	Nhiều hơn (hash buckets)
Range query	✅ `lower_bound`/`upper_bound`	❌ Không hỗ trợ
Worst case	O(log n) guaranteed	O(n) — hash collision
Key requirement	`operator<`	`std::hash` + `operator==`
Iterator stability	✅ Stable	❌ Invalidated on rehash
Cache performance	Kém (pointer chasing)	Tốt hơn (array-based)

5.2 Container Selection Flowchart

  Cần lưu trữ dữ liệu gì?
  │
  ├── Key-Value pairs?
  │   ├── Cần keys sorted?
  │   │   ├── Yes → Cần range queries (lower_bound, upper_bound)?
  │   │   │         ├── Yes → ✅ std::map
  │   │   │         └── No  → ✅ std::map (vẫn cần sorted)
  │   │   │
  │   │   └── No  → Cần worst-case O(log n) guarantee?
  │   │             ├── Yes → ✅ std::map
  │   │             └── No  → ✅ std::unordered_map (default choice!)
  │   │
  │   └── Unique keys?
  │       ├── Yes → (theo flow trên)
  │       └── No  → std::multimap hoặc std::unordered_multimap
  │
  └── Chỉ cần sequence?
      ├── Fixed size, biết lúc compile → std::array
      ├── Dynamic, truy cập random   → ✅ std::vector (default!)
      ├── Insert/delete ở hai đầu    → std::deque
      └── Insert/delete ở giữa nhiều → std::list

🔴 Anti-Pattern: Dùng map khi không cần sorted keys

cpp

// ❌ SAI — Trả giá O(log n) cho mỗi lookup mà không cần sorted order
std::map<std::string, UserProfile> userCache;
// Mỗi lookup = O(log n), triệu users = rất chậm

// ✅ ĐÚNG — O(1) lookup khi không cần sorted
std::unordered_map<std::string, UserProfile> userCache;
// Mỗi lookup = O(1), triệu users = vẫn nhanh

Đây là anti-pattern phổ biến nhất. Nhiều developer dùng std::map theo thói quen mà không nghĩ xem có thật sự cần sorted keys hay không. Kết quả: chậm hơn 5-10x cho lookup-heavy workloads.

6. Iterator Basics — Keo Dán Giữa Container và Algorithm

6.1 Iterator Là Gì?

Iterator là con trỏ trừu tượng — nó trỏ đến một phần tử trong container, và bạn có thể di chuyển qua các phần tử mà không cần biết container implement thế nào.

  vector:  [10] [20] [30] [40] [50]
            ↑                    ↑    ↑
          begin()             last  end()  ← end() trỏ SAU phần tử cuối!

  Half-open range: [begin, end)
  → begin trỏ đến phần tử đầu
  → end trỏ đến VỊ TRÍ SAU phần tử cuối (sentinel)

6.2 Cú Pháp Cơ Bản

cpp

#include <vector>
#include <map>
#include <iostream>

int main() {
    std::vector<int> nums = {10, 20, 30, 40, 50};

    // ── Iterator thủ công ────────────────────────
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        std::cout << *it << " ";  // Dereference: *it
    }

    // ── Range-based for (dùng iterator ngầm) ────
    for (int n : nums) {
        std::cout << n << " ";
    }
    // Hai cách trên cho kết quả giống hệt nhau!

    // ── Find + iterator check ────────────────────
    std::map<std::string, int> ages = {
        {"Alice", 25}, {"Bob", 30}, {"Charlie", 35}
    };

    auto it = ages.find("Bob");
    if (it != ages.end()) {
        std::cout << "Bob is " << it->second << " years old\n";
    } else {
        std::cout << "Bob not found\n";
    }

    // ── const_iterator — read-only access ────────
    for (auto cit = ages.cbegin(); cit != ages.cend(); ++cit) {
        // cit->second = 100;  // ❌ Compile error: const_iterator
        std::cout << cit->first << ": " << cit->second << "\n";
    }
}

6.3 Quy Tắc Quan Trọng

Luôn check != end() trước khi dereference iterator từ find()
Range-based for dùng iterator under the hood — ưu tiên dùng khi có thể
const auto& trong range-based for để tránh copy không cần thiết
Iterator invalidation: insert/erase có thể làm iterator cũ vô hiệu

⚠️ Iterator Invalidation

cpp

std::vector<int> nums = {1, 2, 3, 4, 5};

// ❌ NGUY HIỂM — erase invalidates iterator phía sau
for (auto it = nums.begin(); it != nums.end(); ++it) {
    if (*it % 2 == 0) {
        nums.erase(it);  // 💥 Iterator invalidated!
    }
}

// ✅ AN TOÀN — erase trả về iterator hợp lệ tiếp theo
for (auto it = nums.begin(); it != nums.end(); ) {
    if (*it % 2 == 0) {
        it = nums.erase(it);  // erase trả về iterator tiếp theo
    } else {
        ++it;
    }
}

// ✅ C++20 — std::erase_if (sạch nhất)
std::erase_if(nums, [](int n) { return n % 2 == 0; });

7. Structured Bindings (C++17) — Cú Pháp Sạch Cho Map

7.1 Before vs After

Structured bindings là một trong những feature đáng upgrade lên C++17 nhất — đặc biệt khi làm việc với std::map.

cpp

std::map<std::string, double> prices = {
    {"laptop", 999.99}, {"mouse", 29.99}, {"keyboard", 79.99}
};

// ❌ TRƯỚC C++17 — verbose, khó đọc
for (auto it = prices.begin(); it != prices.end(); ++it) {
    std::cout << it->first << ": $" << it->second << "\n";
}

// ❌ C++11 — tốt hơn nhưng vẫn cồng kềnh
for (const auto& pair : prices) {
    std::cout << pair.first << ": $" << pair.second << "\n";
}

// ✅ C++17 Structured Bindings — sạch, rõ ràng, ý nghĩa
for (const auto& [product, price] : prices) {
    std::cout << product << ": $" << price << "\n";
}

7.2 Structured Bindings Với Nhiều Kiểu Dữ Liệu

cpp

// ── Với std::pair ────────────────────────────────
auto [minIt, maxIt] = std::minmax_element(vec.begin(), vec.end());

// ── Với std::tuple ───────────────────────────────
std::tuple<std::string, int, double> student = {"Alice", 22, 3.8};
auto [name, age, gpa] = student;

// ── Với struct ───────────────────────────────────
struct Point { double x, y, z; };
Point origin = {0.0, 0.0, 0.0};
auto [x, y, z] = origin;

// ── Với insert result ────────────────────────────
auto [iterator, wasInserted] = prices.insert({"tablet", 499.99});
if (wasInserted) {
    std::cout << "Đã thêm: " << iterator->first << "\n";
} else {
    std::cout << "Key đã tồn tại, không insert\n";
}

💡 insert() trả về pair<iterator, bool>

Structured bindings biến return value của insert() thành hai biến rõ ràng:

iterator — trỏ đến phần tử vừa insert (hoặc phần tử đã tồn tại)
wasInserted — true nếu insert thành công, false nếu key đã có

Không cần nhớ .first, .second nữa!

8. Business Example — Hệ Thống Quản Lý Kho Hàng

8.1 Data Model

cpp

#include <map>
#include <unordered_map>
#include <vector>
#include <string>
#include <iostream>
#include <iomanip>

struct Product {
    std::string sku;
    std::string name;
    double price;
    int quantity;
};

class InventorySystem {
private:
    // O(1) tra cứu theo SKU — use case chính: tìm sản phẩm nhanh
    std::unordered_map<std::string, Product> productsBySku;

    // Sorted theo giá — use case: hiển thị sản phẩm từ rẻ → đắt
    std::map<double, std::vector<std::string>> productsByPrice;

public:
    // ── CRUD Operations ──────────────────────────

    void addProduct(const Product& product) {
        productsBySku[product.sku] = product;
        productsByPrice[product.price].push_back(product.sku);
        std::cout << "✅ Đã thêm: " << product.name
                  << " (SKU: " << product.sku << ")\n";
    }

    Product* findBySku(const std::string& sku) {
        auto it = productsBySku.find(sku);
        if (it != productsBySku.end()) {
            return &it->second;
        }
        return nullptr;  // Không tìm thấy
    }

    void updateQuantity(const std::string& sku, int delta) {
        auto* product = findBySku(sku);
        if (product) {
            product->quantity += delta;
            std::cout << "📦 " << product->name
                      << " — số lượng mới: " << product->quantity << "\n";
        } else {
            std::cout << "❌ SKU không tồn tại: " << sku << "\n";
        }
    }

    // ── Range Query: sản phẩm trong khoảng giá ──
    void showPriceRange(double minPrice, double maxPrice) const {
        auto lower = productsByPrice.lower_bound(minPrice);
        auto upper = productsByPrice.upper_bound(maxPrice);

        std::cout << "\n💰 Sản phẩm trong khoảng $"
                  << minPrice << " - $" << maxPrice << ":\n";
        std::cout << std::string(50, '-') << "\n";

        for (auto it = lower; it != upper; ++it) {
            for (const auto& sku : it->second) {
                auto productIt = productsBySku.find(sku);
                if (productIt != productsBySku.end()) {
                    const auto& [_, product] = *productIt;
                    std::cout << std::left << std::setw(12) << product.sku
                              << std::setw(20) << product.name
                              << "$" << std::fixed << std::setprecision(2)
                              << product.price << "\n";
                }
            }
        }
    }

    // ── Report: tất cả sản phẩm sorted by price ─
    void showAllSortedByPrice() const {
        std::cout << "\n📊 Toàn bộ kho hàng (sorted by price):\n";
        std::cout << std::string(55, '=') << "\n";
        std::cout << std::left << std::setw(12) << "SKU"
                  << std::setw(20) << "Tên" << std::setw(10) << "Giá"
                  << "Số lượng\n";
        std::cout << std::string(55, '-') << "\n";

        for (const auto& [price, skus] : productsByPrice) {
            for (const auto& sku : skus) {
                auto it = productsBySku.find(sku);
                if (it != productsBySku.end()) {
                    const auto& p = it->second;
                    std::cout << std::left << std::setw(12) << p.sku
                              << std::setw(20) << p.name
                              << "$" << std::setw(9) << std::fixed
                              << std::setprecision(2) << p.price
                              << p.quantity << "\n";
                }
            }
        }
    }
};

8.2 Chạy Hệ Thống

cpp

int main() {
    InventorySystem inventory;

    // Thêm sản phẩm
    inventory.addProduct({"SKU-001", "Chuột Logitech", 29.99, 150});
    inventory.addProduct({"SKU-002", "Bàn phím cơ", 79.99, 80});
    inventory.addProduct({"SKU-003", "Laptop Dell XPS", 1299.99, 25});
    inventory.addProduct({"SKU-004", "USB-C Hub", 49.99, 200});
    inventory.addProduct({"SKU-005", "Monitor 27\"", 349.99, 40});
    inventory.addProduct({"SKU-006", "Webcam HD", 69.99, 90});

    // Tra cứu nhanh theo SKU — O(1)
    auto* product = inventory.findBySku("SKU-003");
    if (product) {
        std::cout << "\n🔍 Tìm thấy: " << product->name
                  << " — $" << product->price << "\n";
    }

    // Cập nhật số lượng
    inventory.updateQuantity("SKU-001", -10);  // Bán 10 chuột

    // Range query — sản phẩm $50 - $100
    inventory.showPriceRange(50.0, 100.0);

    // Report toàn bộ kho, sorted by price
    inventory.showAllSortedByPrice();

    return 0;
}

9. Fast Exercise — Chọn Container Đúng

🧠 Quiz

Bài tập: Cho mỗi use case sau, chọn container phù hợp nhất và giải thích tại sao.

Use case 1: Đếm tần suất mỗi từ trong một văn bản (word frequency counter).

A) std::vector<std::pair<std::string, int>>
B) std::map<std::string, int>
C) std::unordered_map<std::string, int>
D) std::set<std::string>

Đáp án

C) std::unordered_map<std::string, int>

Cần key-value (từ → số lần xuất hiện) → loại D (set chỉ lưu key)
Không cần sorted output → loại B (map sorted nhưng O(log n) cho mỗi insert)
Vector + pair → phải linear search O(n) mỗi lần tra cứu → loại A
unordered_map: insert O(1), lookup O(1) — tối ưu nhất cho bài toán đếm

cpp

std::unordered_map<std::string, int> wordFreq;
for (const auto& word : words) {
    wordFreq[word]++;  // O(1) per word
}

🧠 Quiz

Use case 2: Hệ thống log cần lưu events theo timestamp, và hỗ trợ query "tất cả events từ 10:00 đến 11:00".

A) std::vector<Event>
B) std::unordered_map<Timestamp, Event>
C) std::map<Timestamp, Event>
D) std::deque<Event>

Đáp án

C) std::map<Timestamp, Event>

Cần range query (10:00 → 11:00) → chỉ map hỗ trợ lower_bound/upper_bound
unordered_map không hỗ trợ range query → loại B
vector/deque phải sort rồi binary search → phức tạp hơn, không tự maintain order → loại A, D

cpp

auto from = events.lower_bound(Timestamp{"10:00"});
auto to   = events.lower_bound(Timestamp{"11:00"});
for (auto it = from; it != to; ++it) { /* process */ }

🧠 Quiz

Use case 3: Cache kết quả API calls, key là URL string, value là response. Không cần sorted, cần tra cứu nhanh nhất có thể.

A) std::map<std::string, Response>
B) std::unordered_map<std::string, Response>
C) std::vector<std::pair<std::string, Response>>
D) std::set<std::string>

Đáp án

B) std::unordered_map<std::string, Response>

Cache cần O(1) lookup — unordered_map là lựa chọn tối ưu
Không cần sorted → map lãng phí O(log n) → loại A
vector phải linear search → O(n) → loại C
set không lưu value → loại D

10. Spot The Bug 🐛

🐛 Spot The Bug — Tìm lỗi trong code sau

cpp

std::map<std::string, int> inventory;
inventory["apple"] = 10;
inventory["banana"] = 5;
inventory["cherry"] = 8;

// Kiểm tra tồn kho
std::cout << "Số lượng grape: " << inventory["grape"] << "\n";
std::cout << "Tổng loại sản phẩm: " << inventory.size() << "\n";

🔍 Lỗi và giải thích

Bug: inventory["grape"] tạo một entry mới với key "grape" và value 0 (default-constructed int).

Dòng đầu in ra 0 — trông đúng nhưng thực ra đã modify map!
Dòng sau in 4 thay vì 3 — vì "grape" đã được thêm vào

Fix: Dùng .find() hoặc .count() để check tồn tại:

cpp

// ✅ Cách 1: find()
auto it = inventory.find("grape");
if (it != inventory.end()) {
    std::cout << "Số lượng grape: " << it->second << "\n";
} else {
    std::cout << "Không có grape trong kho\n";
}

// ✅ Cách 2: C++20 contains()
if (inventory.contains("grape")) {
    std::cout << "Số lượng grape: " << inventory.at("grape") << "\n";
}

🔴 Gotcha: operator[] Trên Map Tạo Entry Mới!

Đây là gotcha phổ biến nhất khi dùng std::map và std::unordered_map.

operator[] có side effect: nếu key chưa tồn tại, nó tự động tạo entry mới với value được default-constructed (0 cho int, "" cho string, v.v.).

Quy tắc:

Muốn đọc → dùng .find() hoặc .at() hoặc .contains() (C++20)
Muốn ghi (insert/update) → dùng operator[] thoải mái
Đừng bao giờ dùng operator[] để check tồn tại

11. Production Scenario — Chọn Sai Container, Hậu Quả Thật

📝 Tình huống thực tế

Context: Hệ thống recommendation engine xử lý 10 triệu users. Mỗi user có profile được lưu trong map theo user ID.

Code ban đầu (viết bởi junior developer):

cpp

// ❌ Dùng std::map — O(log n) cho mỗi lookup
std::map<uint64_t, UserProfile> userProfiles;
// 10M users → log₂(10M) ≈ 23 comparisons per lookup
// 100K requests/sec × 23 comparisons = bottleneck!

Sau khi refactor:

cpp

// ✅ Dùng std::unordered_map — O(1) cho mỗi lookup
std::unordered_map<uint64_t, UserProfile> userProfiles;
userProfiles.reserve(12'000'000);  // Reserve 120% capacity
// 100K requests/sec × O(1) = smooth sailing

Kết quả: Latency p99 giảm từ 45ms xuống 3ms — 15x improvement chỉ bằng thay đổi một dòng type declaration.

12. Tổng Hợp Complexity — Bảng Cheat Sheet

Operation	`vector`	`map`	`unordered_map`
Access by index	✅ O(1)	❌ N/A	❌ N/A
Access by key	❌ O(n)	O(log n)	✅ O(1)
Insert end	✅ O(1)*	N/A	N/A
Insert by key	N/A	O(log n)	✅ O(1)
Delete by key	❌ O(n)	O(log n)	✅ O(1)
Find	❌ O(n)	O(log n)	✅ O(1)
Sorted iteration	❌ Phải sort	✅ Tự động	❌ Không
Range query	❌ Không	✅ Có	❌ Không
Memory	Compact	Trung bình	Nhiều nhất
Cache-friendly	✅ Rất tốt	❌ Kém	Trung bình

* amortized O(1)

Checklist ghi nhớ

✅ Checklist triển khai

[ ] std::vector là default choice cho sequence — contiguous memory, cache-friendly
[ ] std::unordered_map là default choice cho key-value — O(1) average lookup
[ ] std::map chỉ khi cần sorted keys hoặc range queries (lower_bound/upper_bound)
[ ] operator[] trên map tạo entry mới nếu key chưa có — dùng find() để check
[ ] Structured bindings (C++17): auto [key, value] cho code sạch hơn
[ ] Iterator pattern: luôn check != end() trước khi dereference
[ ] reserve() cho unordered_map khi biết approximate size — giảm rehashing
[ ] Custom hash cần thiết cho custom types làm key trong unordered_map
[ ] Iterator invalidation: cẩn thận erase/insert trong khi iterate

🗃️ STL Containers: vector, map, unordered_map Module 3 ​

1. STL Container Landscape — Bức Tranh Toàn Cảnh ​

🧠 Mental Model ​

Ba Container Chiến Lược ​

2. std::vector — Ôn Tập Nhanh ​

2.1 Đặc Điểm Cốt Lõi ​

2.2 Complexity Table — vector ​

3. std::map — Ordered Key-Value Store ​

3.1 Cấu Trúc Bên Trong ​

3.2 API Cơ Bản ​

3.3 Range Queries — Sức Mạnh Riêng Của map ​

3.4 Complexity Table — map ​

4. std::unordered_map — Hash Table ​

4.1 Cấu Trúc Bên Trong ​

4.2 API Cơ Bản ​

4.3 Hash Collisions — Khi O(1) Biến Thành O(n) ​

4.4 Performance Tuning ​

4.5 Key Requirements ​

4.6 Complexity Table — unordered_map ​

5. map vs unordered_map — Ma Trận Quyết Định ​

5.1 Bảng So Sánh Head-to-Head ​

5.2 Container Selection Flowchart ​

6. Iterator Basics — Keo Dán Giữa Container và Algorithm ​

6.1 Iterator Là Gì? ​

6.2 Cú Pháp Cơ Bản ​

6.3 Quy Tắc Quan Trọng ​

7. Structured Bindings (C++17) — Cú Pháp Sạch Cho Map ​

7.1 Before vs After ​

7.2 Structured Bindings Với Nhiều Kiểu Dữ Liệu ​

8. Business Example — Hệ Thống Quản Lý Kho Hàng ​

8.1 Data Model ​

8.2 Chạy Hệ Thống ​

9. Fast Exercise — Chọn Container Đúng ​

10. Spot The Bug 🐛 ​

11. Production Scenario — Chọn Sai Container, Hậu Quả Thật ​

12. Tổng Hợp Complexity — Bảng Cheat Sheet ​

Checklist ghi nhớ ​

Liên kết học tiếp ​

🗃️ STL Containers: vector, map, unordered_map Module 3

1. STL Container Landscape — Bức Tranh Toàn Cảnh

🧠 Mental Model

Ba Container Chiến Lược

2. std::vector — Ôn Tập Nhanh

2.1 Đặc Điểm Cốt Lõi

2.2 Complexity Table — vector

3. std::map — Ordered Key-Value Store

3.1 Cấu Trúc Bên Trong

3.2 API Cơ Bản

3.3 Range Queries — Sức Mạnh Riêng Của map

3.4 Complexity Table — map

4. std::unordered_map — Hash Table

4.1 Cấu Trúc Bên Trong

4.2 API Cơ Bản

4.3 Hash Collisions — Khi O(1) Biến Thành O(n)

4.4 Performance Tuning

4.5 Key Requirements

4.6 Complexity Table — unordered_map

5. map vs unordered_map — Ma Trận Quyết Định

5.1 Bảng So Sánh Head-to-Head

5.2 Container Selection Flowchart

6. Iterator Basics — Keo Dán Giữa Container và Algorithm

6.1 Iterator Là Gì?

6.2 Cú Pháp Cơ Bản

6.3 Quy Tắc Quan Trọng

7. Structured Bindings (C++17) — Cú Pháp Sạch Cho Map

7.1 Before vs After

7.2 Structured Bindings Với Nhiều Kiểu Dữ Liệu

8. Business Example — Hệ Thống Quản Lý Kho Hàng

8.1 Data Model

8.2 Chạy Hệ Thống

9. Fast Exercise — Chọn Container Đúng

10. Spot The Bug 🐛

11. Production Scenario — Chọn Sai Container, Hậu Quả Thật

12. Tổng Hợp Complexity — Bảng Cheat Sheet

Checklist ghi nhớ

Liên kết học tiếp