Thư viện STL trong C++: map, set và thuật toán

Trong bài này chúng ta sẽ học thư viện STL trong C++: cách STL tổ chức thành container, iterator và thuật toán, cách dùng std::map để tra cứu theo khóa, std::set để lưu tập không trùng, và các thuật toán có sẵn như sort, find_if, count_if kết hợp với lambda. Dùng tốt STL thì rất nhiều đoạn code vòng lặp tự viết sẽ được thay bằng một dòng.

Bài 25 trong Serie Lập trình C++ từ A tới Z

Table of Contents

Thư viện STL trong C++ là gì?

STL (Standard Template Library) là phần thư viện chuẩn của C++ chứa các cấu trúc dữ liệu và thuật toán viết sẵn bằng template. std::vector mà chúng ta dùng từ chương 2 chính là một phần của STL.

STL gồm 3 thành phần ăn khớp với nhau:

Container (vùng chứa): các cấu trúc lưu dữ liệu như vector, map, set.
Iterator (bộ duyệt): đối tượng giống con trỏ, dùng để đi qua từng phần tử của container.
Algorithm (thuật toán): các hàm như sort, find, làm việc trên một đoạn phần tử xác định bằng 2 iterator.

Giống như kệ sách (container), người thủ thư đi dọc kệ chỉ vào từng cuốn (iterator), và các quy trình như “xếp theo tên”, “tìm cuốn xuất bản năm 2021” (algorithm). Quy trình không cần biết kệ làm bằng gì, chỉ cần có người chỉ vào từng cuốn.

Iterator

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> maSach = {1003, 1001, 1002};

    for (auto it = maSach.begin(); it != maSach.end(); ++it)
        std::cout << *it << ' ';
    std::cout << '\n';

    auto it = maSach.begin();
    ++it;                                  // sang phan tu thu 2
    std::cout << "Phan tu thu 2: " << *it << '\n';
    std::cout << "So phan tu tu it toi het: " << (maSach.end() - it) << '\n';
    return 0;
}

begin() trỏ tới phần tử đầu tiên, end() trỏ tới sau phần tử cuối cùng. end() không phải một phần tử, không được đọc *end().
*it đọc phần tử, ++it sang phần tử tiếp theo, giống con trỏ ở bài mảng và con trỏ trong C++.
Vòng lặp for (const auto& x : v) mà chúng ta hay dùng thực chất được trình biên dịch dịch thành vòng lặp iterator như trên.

std::map: tra cứu theo khóa

std::map<Khoa, GiaTri> lưu các cặp khóa và giá trị, tra cứu theo khóa rất nhanh. Ví dụ tra tên sách theo mã sách:

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

int main()
{
    std::map<int, std::string> sach;          // ma sach -> ten sach
    sach[1003] = "Lap trinh C++";
    sach[1001] = "Clean Code";
    sach.insert({1002, "Cau truc du lieu"});

    std::cout << "Sach 1001: " << sach[1001] << '\n';

    for (const auto& [ma, ten] : sach)        // tu sap xep theo khoa
        std::cout << "  " << ma << ": " << ten << '\n';

    auto it = sach.find(9999);
    if (it == sach.end())
        std::cout << "Khong co sach 9999\n";

    sach.erase(1003);
    std::cout << "Con " << sach.size() << " dau sach\n";
    return 0;
}

Thêm bằng sach[khoa] = giaTri hoặc insert({khoa, giaTri}). Mỗi khóa chỉ có một giá trị.
std::map luôn giữ các khóa theo thứ tự tăng dần, nên duyệt ra theo mã 1001, 1002, 1003 dù thêm vào lộn xộn.
for (const auto& [ma, ten] : sach) là cú pháp structured binding của C++17, tách mỗi cặp thành 2 biến cho dễ đọc.
find(khoa) trả về iterator tới phần tử, không có thì trả về end().

Ví dụ đời thường: std::map giống mục lục sách, tra theo từ khóa là ra ngay số trang, không phải lật từng trang như tìm trong vector. Với 1 triệu phần tử, map chỉ cần khoảng 20 bước so sánh, còn duyệt vector có thể mất 1 triệu bước.

Toán tử [] tự thêm khóa mới

Đây là lỗi hay gặp nhất với std::map:

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

int main()
{
    std::map<int, std::string> sach = {{1001, "Clean Code"}, {1002, "Lap trinh C++"}};

    std::cout << "Truoc: " << sach.size() << " dau sach\n";
    if (sach[9999] == "")                      // chi muon kiem tra, nhung [] tu them khoa moi
        std::cout << "Khong co sach 9999\n";
    std::cout << "Sau:   " << sach.size() << " dau sach\n";

    std::cout << "Dung count: " << sach.count(5555) << ", size van la " << sach.size() << '\n';
    return 0;
}

Chỉ định kiểm tra mà kho sách tự nhiên có thêm một cuốn mã 9999 với tên rỗng. Khi khóa chưa có, sach[khoa] tạo mới phần tử với giá trị mặc định rồi mới trả về.

Lưu ý: Muốn kiểm tra khóa có tồn tại không thì dùng count(khoa) hoặc find(khoa), không dùng []. Muốn đọc giá trị mà khóa phải tồn tại thì dùng at(khoa): khóa không có sẽ ném ngoại lệ std::out_of_range thay vì âm thầm thêm mới.

Ứng dụng: đếm số lần xuất hiện

Chính hành vi tự tạo của [] lại rất tiện khi đếm. Đếm mỗi cuốn được mượn bao nhiêu lượt:

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

int main()
{
    std::vector<std::string> lichSuMuon = {"C++", "Python", "C++", "Clean Code", "C++", "Python"};

    std::map<std::string, int> soLan;
    for (const std::string& ten : lichSuMuon)
        soLan[ten]++;                          // khoa chua co thi tao moi voi gia tri 0

    for (const auto& [ten, lan] : soLan)
        std::cout << ten << ": " << lan << " luot\n";
    return 0;
}

Lần đầu gặp “Python”, soLan["Python"] tạo phần tử với giá trị 0 rồi ++ thành 1. Không cần kiểm tra trước.

unordered_map

std::unordered_map dùng giống hệt std::map, nhưng không giữ thứ tự khóa và thường tra cứu nhanh hơn (dùng bảng băm). Cần duyệt theo thứ tự thì dùng map, chỉ cần tra cứu nhanh thì dùng unordered_map.

std::set: tập không trùng lặp

std::set lưu các phần tử không trùng nhau và có thứ tự:

#include <iostream>
#include <set>
#include <string>

int main()
{
    std::set<std::string> theLoai;
    theLoai.insert("Lap trinh");
    theLoai.insert("Kinh te");
    theLoai.insert("Lap trinh");             // trung, khong them
    theLoai.insert("Dien tu");

    std::cout << "Co " << theLoai.size() << " the loai:";
    for (const std::string& t : theLoai)
        std::cout << " [" << t << "]";
    std::cout << '\n';

    std::cout << "Co the loai 'Kinh te'? " << theLoai.count("Kinh te") << '\n';
    return 0;
}

Thêm “Lap trinh” lần thứ hai không có tác dụng, nên chỉ có 3 thể loại. Dùng set khi cần trả lời câu hỏi “đã có chưa?”, ví dụ danh sách mã thẻ đang bị khóa, các thể loại sách hiện có.

Lambda: hàm không tên

Trước khi sang thuật toán, chúng ta cần lambda, cách viết một hàm nhỏ ngay tại chỗ dùng:

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> soNgayMuon = {5, 20, 12, 30, 9};
    int han = 14;

    auto quaHan = [han](int ngay) { return ngay > han; };     // bat bien han tu ben ngoai

    std::cout << "20 ngay qua han? " << quaHan(20) << '\n';
    std::cout << "So phieu qua han: " << std::count_if(soNgayMuon.begin(), soNgayMuon.end(), quaHan) << '\n';
    return 0;
}

Cú pháp [danh sách bắt](tham số) { thân hàm }:

[han]: bắt biến han từ bên ngoài vào để dùng trong lambda. [] rỗng là không bắt gì, [&han] là bắt theo tham chiếu.
(int ngay): tham số như hàm thường.
Lambda gán được vào biến bằng auto rồi gọi như hàm: quaHan(20).

Các thuật toán trong algorithm

Thư viện <algorithm> có hơn 100 thuật toán. Một số thuật toán dùng nhiều nhất, áp dụng cho kho sách:

#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

struct Sach
{
    std::string ten;
    int nam;
    int luotMuon;
};

int main()
{
    std::vector<Sach> kho = {
        {"Lap trinh C++", 2020, 35},
        {"Clean Code", 2008, 52},
        {"Cau truc du lieu", 2015, 18},
        {"Python co ban", 2021, 40},
    };

    std::sort(kho.begin(), kho.end(),
              [](const Sach& a, const Sach& b) { return a.luotMuon > b.luotMuon; });
    std::cout << "Muon nhieu nhat: " << kho[0].ten << " (" << kho[0].luotMuon << " luot)\n";

    auto moi = std::find_if(kho.begin(), kho.end(), [](const Sach& s) { return s.nam >= 2021; });
    if (moi != kho.end())
        std::cout << "Sach xuat ban tu 2021: " << moi->ten << '\n';

    int namCu = std::count_if(kho.begin(), kho.end(), [](const Sach& s) { return s.nam < 2016; });
    std::cout << "So sach truoc 2016: " << namCu << '\n';

    int tongLuot = std::accumulate(kho.begin(), kho.end(), 0,
                                   [](int tong, const Sach& s) { return tong + s.luotMuon; });
    std::cout << "Tong luot muon: " << tongLuot << '\n';

    auto cuNhat = std::min_element(kho.begin(), kho.end(),
                                   [](const Sach& a, const Sach& b) { return a.nam < b.nam; });
    std::cout << "Sach cu nhat: " << cuNhat->ten << " (" << cuNhat->nam << ")\n";
    return 0;
}

Thuật toán	Làm gì	Trả về
`std::sort(dau, cuoi, soSanh)`	Sắp xếp theo hàm so sánh	Không trả về, sửa tại chỗ
`std::find_if(dau, cuoi, dieuKien)`	Tìm phần tử đầu tiên thỏa điều kiện	Iterator, không thấy thì là `cuoi`
`std::count_if(dau, cuoi, dieuKien)`	Đếm phần tử thỏa điều kiện	Số lượng
`std::accumulate(dau, cuoi, banDau, gop)`	Gộp tất cả thành một giá trị	Kết quả gộp
`std::min_element`, `std::max_element`	Tìm phần tử nhỏ nhất, lớn nhất	Iterator

Hàm so sánh của std::sort trả về true khi a phải đứng trước b. Đổi lambda là sắp theo tiêu chí khác ngay: theo năm, theo tên, theo lượt mượn. Đây là cách linh hoạt hơn so với chỉ có một operator< trong class. std::accumulate nằm trong <numeric>, không phải <algorithm>.

So với tự viết vòng lặp for, dùng thuật toán có sẵn giúp code nói rõ ý định (“đếm những cuốn trước 2016”) thay vì cách làm (“khởi tạo biến đếm, duyệt, kiểm tra, cộng”), và ít lỗi hơn vì thuật toán đã được kiểm thử kỹ.

Nên dùng container nào?

Nhu cầu	Container
Danh sách có thứ tự, truy cập theo vị trí (mặc định)	`std::vector`
Tra cứu theo khóa, cần duyệt theo thứ tự khóa	`std::map`
Tra cứu theo khóa, chỉ cần nhanh	`std::unordered_map`
Tập không trùng, kiểm tra “đã có chưa”	`std::set` / `std::unordered_set`
Số phần tử cố định lúc biên dịch	`std::array`

Khi không chắc thì dùng std::vector. Nó đơn giản và với dữ liệu vài nghìn phần tử thường nhanh nhất nhờ các phần tử nằm liền nhau trong bộ nhớ.

Bài tập

Dùng std::map<std::string, int> để đếm số lần xuất hiện của mỗi từ trong một câu nhập từ bàn phím.
Cho vector các số nguyên, dùng std::sort với lambda để sắp xếp giảm dần, rồi dùng std::count_if đếm số chẵn.
Dùng std::set<int> loại bỏ các mã thẻ trùng nhau trong một vector mã thẻ, in ra các mã còn lại theo thứ tự.
Từ vector Sach trong ví dụ, tìm cuốn có lượt mượn cao nhất bằng std::max_element, và tính lượt mượn trung bình bằng std::accumulate.

Lời giải sẽ có trong bài tập tổng hợp của chương nhé.

Kết

Thư viện STL trong C++ cung cấp sẵn các container, iterator và thuật toán, giúp các bạn ít phải tự viết cấu trúc dữ liệu và vòng lặp. std::map tra cứu theo khóa, std::set lưu tập không trùng, còn các thuật toán như sort, find_if, count_if kết hợp với lambda cho code ngắn và rõ ý. Nhớ cái bẫy lớn nhất của bài: kiểm tra khóa trong map bằng count hoặc find, không dùng [].

Danh sách đầy đủ các container và thuật toán có trên cppreference: containers và algorithm. Bài tiếp theo chúng ta sẽ học xử lý ngoại lệ trong C++, cách xử lý khi at() hay std::stoi gặp dữ liệu sai. Thấy bài viết có ích thì chia sẻ cho bạn bè nhé.

Rate this post

Lập trình C++

Thư viện STL trong C++: map, set, iterator và các thuật toán