Thuật toán STL trong C++: hướng dẫn thực hành có ví dụ

Những vòng lặp bạn không cần tự viết

Ở trang trước, bạn đã thấy mọi container đều cung cấp iterator: những con trỏ vị trí gọn nhẹ với begin() và end(). Lớp trừu tượng đó chính là lý do các thuật toán (algorithm) chuẩn tồn tại. Thay vì viết một vòng for thô mỗi lần muốn tìm kiếm, đếm hay biến đổi dữ liệu, bạn gọi một hàm có tên sẵn trong <algorithm> và truyền cho nó một range.

Một range chỉ là hai iterator: chỗ bắt đầu và vị trí ngay sau chỗ kết thúc. Vì mọi thuật toán đều nói chung một ngôn ngữ iterator, cùng một hàm find dùng được cho vector, string hay một mảng thường.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 8, 15, 16, 23, 42};

    // Is 16 in the range [begin, end)?
    auto it = find(v.begin(), v.end(), 16);

    if (it != v.end())
        cout << "found " << *it << " at index " << (it - v.begin()) << "\n";
    else
        cout << "not found\n";
    return 0;
}

Khuôn mẫu cần ghi nhớ: thuật toán tìm kiếm trả về iterator end() để báo "không tìm thấy". Luôn so sánh với end() trước khi dereference kết quả, vì dereference end() là undefined behavior.

Đếm và kiểm tra bằng predicate

Nhiều thuật toán nhận một predicate: một hàm (thường là lambda) trả về bool cho từng phần tử. count_if đếm số phần tử khớp; all_of, any_of và none_of trả lời các câu hỏi có hoặc không về toàn bộ range.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {42, 88, 17, 95, 63, 71};

    int passed = count_if(scores.begin(), scores.end(),
                          [](int s) { return s >= 60; });

    bool allPositive = all_of(scores.begin(), scores.end(),
                              [](int s) { return s > 0; });

    bool anyPerfect = any_of(scores.begin(), scores.end(),
                             [](int s) { return s == 100; });

    cout << passed << " passed\n";          // 4 passed
    cout << "all positive? " << allPositive << "\n";  // 1
    cout << "any perfect? " << anyPerfect << "\n";    // 0
    return 0;
}

std::count (không có _if) là phiên bản đơn giản hơn, đếm một giá trị cụ thể thay vì một điều kiện. Hãy chuyển sang các phiên bản dùng predicate ngay khi phép kiểm tra của bạn là "bất cứ thứ gì khớp một quy tắc" chứ không phải "đúng giá trị này".

Biến đổi và rút gọn một range

Hai công cụ chủ lực đảm nhận phần lớn việc xử lý dữ liệu: std::transform đưa từng phần tử qua một hàm, còn std::accumulate (trong <numeric>, không phải <algorithm>) gộp cả range lại thành một giá trị duy nhất.

transform ghi kết quả qua một output iterator. Một lỗi phổ biến và nguy hiểm là trỏ đầu ra vào một vector rỗng: thuật toán mặc định là đã có sẵn chỗ và ghi vượt quá cuối vector. Hãy đặt kích thước cho vùng đích trước, hoặc dùng back_inserter để mỗi kết quả được push_back vào.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> squares;   // empty - no room yet

    // back_inserter grows `squares` as results arrive
    transform(nums.begin(), nums.end(), back_inserter(squares),
              [](int n) { return n * n; });

    for (int s : squares) cout << s << " ";  // 1 4 9 16
    cout << "\n";
    return 0;
}

accumulate bắt đầu từ một giá trị khởi đầu và kết hợp các phần tử từ trái sang phải. Kiểu của giá trị khởi đầu rất quan trọng: truyền 0 (một int) thì tổng được tính bằng int, có thể bị tràn số hoặc mất phần thập phân tùy theo kiểu dữ liệu của phần tử.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<double> prices = {9.99, 4.50, 19.95};

    // Start with 0.0 (double) so the running total stays a double.
    double total = accumulate(prices.begin(), prices.end(), 0.0);

    cout << "total: " << total << "\n";  // total: 34.44
    return 0;
}

Nếu bạn viết accumulate(prices.begin(), prices.end(), 0) với giá trị khởi đầu kiểu int, mỗi phép cộng sẽ diễn ra trong int và phần xu lẻ biến mất. Kiểu của giá trị khởi đầu âm thầm quyết định kiểu của kết quả.

Erase-remove idiom

Đây là cái bẫy khiến ai cũng bất ngờ. std::remove không xóa gì khỏi container cả. Thuật toán chỉ có iterator, nên không thể thay đổi kích thước container; chúng thậm chí không biết có container ở đó. Việc remove thật sự làm là dồn mọi phần tử được giữ lại lên đầu, để phần đuôi ở trạng thái không xác định, rồi trả về một iterator trỏ tới điểm kết thúc logic mới.

// remove alone leaves the size unchanged - this is the bug:
remove(v.begin(), v.end(), 0);  // returns an iterator you ignored
// v still has its original size; the tail is garbage

Để thật sự xóa các phần tử, bạn ghép remove với erase của container, và đó là lý do nó được gọi là erase-remove idiom:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 0, 7, 0, 1, 0, 9};

    // 1. remove shuffles non-zeros forward, returns new end
    // 2. erase chops off everything from there to the real end
    v.erase(remove(v.begin(), v.end(), 0), v.end());

    for (int n : v) cout << n << " ";  // 3 7 1 9
    cout << "\n";
    return 0;
}

Dùng remove_if khi cần predicate thay vì một giá trị cụ thể. Trong C++20, bạn có thể bỏ qua cả màn này bằng hàm tự do std::erase / std::erase_if, làm cả hai bước giúp bạn: erase(v, 0);.

Dùng iterator đã hết hiệu lực là tự chuốc rủi ro

Vì thuật toán trả về iterator, các iterator đó cũng tuân theo quy tắc vô hiệu hóa mà bạn đã gặp ở trang trước. Lưu một iterator rồi sửa đổi container, như một lần push_back gây cấp phát lại hay một lần erase, có thể khiến iterator đã lưu bị treo (dangling), và dùng nó là undefined behavior.

auto it = find(v.begin(), v.end(), 16);
v.push_back(99);   // may reallocate v's storage
cout << *it;       // BUG: `it` may now point at freed memory

Thói quen an toàn: dùng iterator mà thuật toán trả về ngay lập tức, trước mọi thao tác có thể thay đổi kích thước hoặc cấp phát lại container. Nếu cần sửa container dựa trên kết quả, hãy lưu chỉ số (it - v.begin()), vì chỉ số vẫn đúng sau khi cấp phát lại.

Tiếp theo: sắp xếp

Bạn đã thấy tìm kiếm, đếm, biến đổi và rút gọn, nhưng có một thuật toán quan trọng đến mức xứng đáng có trang riêng. std::sort sắp xếp lại một range ngay tại chỗ, và khi dữ liệu đã được sắp xếp, cả một nhóm thuật toán nhanh hơn chỉ dành cho dữ liệu đã sắp xếp (binary_search, lower_bound, equal_range) sẽ mở ra. Tiếp theo, chúng ta sẽ đi sâu vào sắp xếp: cách truyền một hàm so sánh tùy chỉnh, khác biệt giữa sort và stable_sort, và những quy tắc mà hàm so sánh phải tuân theo để tránh undefined behavior.