Thư viện C++ STL cung cấp nhiều thuật toán mạnh mẽ, được phân loại thành các nhóm chức năng khác nhau. Dưới đây là tổng quan chi tiết kèm ví dụ minh họa.

1. Thuật toán không thay đổi (Non-modifying sequence operations)

Các thuật toán này không làm thay đổi nội dung của container.

1.1 Tìm kiếm: find và find_if

find trả về iterator tới phần tử đầu tiên có giá trị cụ thể. find_if trả về iterator tới phần tử đầu tiên thỏa mãn điều kiện (predicate).

std::vector<int> numbers = {10, 20, 30, 40, 50};

// Tìm giá trị 30
auto it = std::find(numbers.begin(), numbers.end(), 30);
if (it != numbers.end()) {
    std::cout << "Đã tìm thấy: " << *it << "\n";
}

// Tìm số đầu tiên lớn hơn 25
auto it2 = std::find_if(numbers.begin(), numbers.end(),
                        [](int val) { return val > 25; });
if (it2 != numbers.end()) {
    std::cout << "Số đầu tiên >25: " << *it2 << "\n";
}

1.2 Đếm: count và count_if

Đếm số lần xuất hiện của một giá trị hoặc số phần tử thỏa mãn điều kiện.

std::vector<int> data = {1, 2, 3, 2, 4, 2, 5};
int countTwo = std::count(data.begin(), data.end(), 2); // Kết quả: 3

int evenCount = std::count_if(data.begin(), data.end(),
                              [](int x) { return x % 2 == 0; }); // Kết quả: 4

1.3 Áp dụng hàm: for_each

Áp dụng một hàm (hoặc lambda) cho mọi phần tử trong dãy. Có thể thay đổi giá trị nếu truyền tham chiếu.

std::vector<int> vals = {1, 2, 3, 4, 5};
std::for_each(vals.begin(), vals.end(), [](int &x) {
    x = x * x; // Bình phương mỗi phần tử
});
// vals bây giờ là {1, 4, 9, 16, 25}

1.4 So sánh: equal và mismatch

equal kiểm tra hai dãy có bằng nhau không. mismatch tìm vị trí khác nhau đầu tiên.

std::vector<int> first = {1, 2, 3};
std::vector<int> second = {1, 2, 4};

bool isEqual = std::equal(first.begin(), first.end(), second.begin());
// isEqual = false

auto diff = std::mismatch(first.begin(), first.end(), second.begin());
if (diff.first != first.end()) {
    std::cout << "Khác nhau tại: " << *diff.first << " vs " << *diff.second << "\n";
}

1.5 Kiểm tra điều kiện: all_of, any_of, none_of

std::vector<int> numbers = {2, 4, 6, 8};

bool allEven = std::all_of(numbers.begin(), numbers.end(),
                           [](int x) { return x % 2 == 0; }); // true

bool anyOdd = std::any_of(numbers.begin(), numbers.end(),
                          [](int x) { return x % 2 != 0; }); // false

bool noneNegative = std::none_of(numbers.begin(), numbers.end(),
                                 [](int x) { return x < 0; }); // true

2. Thuật toán thay đổi (Modifying sequence operations)

Các thuật toán này có thể thay đổi giá trị của các phần tử trong container.

2.1 Sao chép: copy và copy_if

copy sao chép toàn bộ dãy. copy_if chỉ sao chép các phần tử thỏa mãn điều kiện.

std::vector<int> source = {5, 10, 15, 20, 25};
std::vector<int> destination(5);

std::copy(source.begin(), source.end(), destination.begin());

std::vector<int> evens;
std::copy_if(source.begin(), source.end(),
             std::back_inserter(evens),
             [](int x) { return x % 2 == 0; });
// evens = {10, 20}

2.2 Biến đổi: transform

Áp dụng hàm lên từng phần tử và lưu kết quả vào dãy đích. Có thể dùng với một hoặc hai dãy nguồn.

std::vector<int> input = {1, 2, 3, 4, 5};
std::vector<int> output(input.size());

// Tính bình phương (một dãy nguồn)
std::transform(input.begin(), input.end(), output.begin(),
               [](int x) { return x * x; });
// output = {1, 4, 9, 16, 25}

// Cộng hai vector (hai dãy nguồn)
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {10, 20, 30};
std::vector<int> sum(3);
std::transform(a.begin(), a.end(), b.begin(), sum.begin(),
               std::plus<int>());
// sum = {11, 22, 33}

2.3 Thay thế: replace, replace_if, replace_copy

Thay thế giá trị cũ bằng giá trị mới, có thể kèm điều kiện hoặc sao chép sang container khác.

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

// Thay tất cả số 2 bằng 99
std::replace(data.begin(), data.end(), 2, 99);
// data = {1, 99, 3, 99, 4}

// Thay các số chẵn bằng 0
std::replace_if(data.begin(), data.end(),
                [](int x) { return x % 2 == 0; }, 0);

// Sao chép và thay thế (không sửa đổi dãy gốc)
std::vector<int> copied;
std::replace_copy(data.begin(), data.end(),
                  std::back_inserter(copied), 3, 300);

2.4 Xóa logic: remove, remove_if và erase

remove di chuyển các phần tử cần giữ lại lên đầu, trả về iterator tới phần tử "rác" đầu tiên. Cần kết hợp với erase để thực sự xóa.

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

// Xóa logic các số 2
auto newEnd = std::remove(items.begin(), items.end(), 2);
// items lúc này: {1, 3, 4, 5, ?, ?, ?}

// Thực sự xóa
items.erase(newEnd, items.end());
// items = {1, 3, 4, 5}

// Kết hợp trong một dòng (remove-erase idiom)
items = {1, 2, 3, 4, 5, 6};
items.erase(
    std::remove_if(items.begin(), items.end(),
                   [](int x) { return x % 2 == 0; }),
    items.end()
);
// items = {1, 3, 5}

2.5 Loại bỏ trùng lặp: unique

Loại bỏ các phần tử trùng lặp liên tiếp, cần kết hợp erase.

std::vector<int> values = {1, 1, 2, 3, 3, 3, 4, 5, 5};
auto last = std::unique(values.begin(), values.end());
values.erase(last, values.end());
// values = {1, 2, 3, 4, 5}

2.6 Đảo ngược: reverse

std::vector<int> arr = {1, 2, 3, 4, 5};
std::reverse(arr.begin(), arr.end());
// arr = {5, 4, 3, 2, 1}

2.7 Xoay vòng: rotate

std::vector<int> arr = {1, 2, 3, 4, 5};
std::rotate(arr.begin(), arr.begin() + 2, arr.end());
// arr = {3, 4, 5, 1, 2}

2.8 Xáo trộn: shuffle

#include <random>

std::vector<int> deck = {1, 2, 3, 4, 5, 6};
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(deck.begin(), deck.end(), gen);
// deck bị xáo trộn ngẫu nhiên

3. Thuật toán sắp xếp (Sorting and related operations)

3.1 sort, stable_sort, partial_sort

sort (nhanh, không ổn định), stable_sort (giữ nguyên thứ tự các phần tử bằng nhau), partial_sort (sắp xếp một phần).

std::vector<int> vec = {5, 3, 1, 4, 2};
std::sort(vec.begin(), vec.end()); // {1, 2, 3, 4, 5}

// Ổn định
std::vector<std::pair<int, char>> pairs = {{2, 'b'}, {1, 'a'}, {2, 'c'}};
std::stable_sort(pairs.begin(), pairs.end(),
                 [](auto &a, auto &b) { return a.first < b.first; });
// Giữ nguyên thứ tự (b, c) cho first=2

// Sắp xếp một phần
std::vector<int> big = {9, 3, 7, 1, 5, 8, 2};
std::partial_sort(big.begin(), big.begin() + 3, big.end());
// 3 phần tử đầu là {1, 2, 3}

3.2 nth_element

Đặt phần tử thứ n vào đúng vị trí như khi sắp xếp. Các phần tử bên trái nhỏ hơn nó, bên phải lớn hơn.

std::vector<int> scores = {90, 70, 80, 60, 100};
std::nth_element(scores.begin(), scores.begin() + 2, scores.end());
// scores[2] là 80 (phần tử lớn thứ 3)

3.3 Tìm kiếm nhị phân: binary_search, lower_bound, upper_bound

Yêu cầu dãy đã được sắp xếp.

std::vector<int> sorted = {1, 3, 5, 7, 9, 11};

bool found = std::binary_search(sorted.begin(), sorted.end(), 7); // true

auto lower = std::lower_bound(sorted.begin(), sorted.end(), 5);
// Iterator trỏ tới phần tử đầu tiên >= 5 (giá trị 5)

auto upper = std::upper_bound(sorted.begin(), sorted.end(), 5);
// Iterator trỏ tới phần tử đầu tiên > 5 (giá trị 7)

3.4 Trộn: merge

Kết hợp hai dãy đã sắp xếp thành một dãy đã sắp xếp.

std::vector<int> left = {1, 4, 7};
std::vector<int> right = {2, 5, 8};
std::vector<int> result(left.size() + right.size());

std::merge(left.begin(), left.end(),
           right.begin(), right.end(),
           result.begin());
// result = {1, 2, 4, 5, 7, 8}

4. Thuật toán Heap

Các thao tác với cấu trúc dữ liệu heap (max-heap mặc định).

std::vector<int> heap = {3, 1, 4, 1, 5, 9};

// Xây dựng heap
std::make_heap(heap.begin(), heap.end());
// heap = {9, 5, 4, 1, 1, 3}

// Thêm phần tử
heap.push_back(10);
std::push_heap(heap.begin(), heap.end());
// heap = {10, 5, 9, 1, 1, 3, 4}

// Lấy phần tử lớn nhất
std::pop_heap(heap.begin(), heap.end());
int maxVal = heap.back(); // 10
heap.pop_back();

// Sắp xếp heap thành dãy tăng dần
std::sort_heap(heap.begin(), heap.end());

5. Thuật toán tìm min/max

5.1 min và max

int smallest = std::min(10, 20); // 10
int largest = std::max(10, 20);  // 20

auto minList = std::min({5, 2, 8, 1, 9}); // 1
auto maxList = std::max({5, 2, 8, 1, 9}); // 9

5.2 min_element và max_element

std::vector<int> data = {3, 7, 1, 9, 4};
auto minPos = std::min_element(data.begin(), data.end());
auto maxPos = std::max_element(data.begin(), data.end());
// *minPos = 1, *maxPos = 9

5.3 minmax_element (C++11)

auto both = std::minmax_element(data.begin(), data.end());
// both.first trỏ tới 1, both.second trỏ tới 9

6. Thuật toán số (Header <numeric>)

6.1 accumulate

Tính tổng (hoặc tích, với toán tử tùy chỉnh).

#include <numeric>

std::vector<int> vals = {1, 2, 3, 4, 5};
int total = std::accumulate(vals.begin(), vals.end(), 0); // 15
int product = std::accumulate(vals.begin(), vals.end(), 1, std::multiplies<int>()); // 120

6.2 inner_product

Tính tích vô hướng (dot product).

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};
int dot = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
// 1*4 + 2*5 + 3*6 = 32

6.3 iota

Gán giá trị tăng dần cho dãy.

std::vector<int> range(5);
std::iota(range.begin(), range.end(), 10);
// range = {10, 11, 12, 13, 14}

6.4 partial_sum

Tính tổng tích lũy (prefix sum).

std::vector<int> input = {1, 2, 3, 4};
std::vector<int> output(input.size());
std::partial_sum(input.begin(), input.end(), output.begin());
// output = {1, 3, 6, 10}

6.5 adjacent_difference

Tính hiệu giữa các phần tử liền kề.

std::vector<int> input = {1, 3, 6, 10};
std::vector<int> diff(input.size());
std::adjacent_difference(input.begin(), input.end(), diff.begin());
// diff = {1, 2, 3, 4}

7. Các thuật toán khác

7.1 generate và generate_n

Điền dãy bằng cách gọi một hàm sinh.

std::vector<int> seq(5);
int counter = 0;
std::generate(seq.begin(), seq.end(), [&counter]() { return ++counter; });
// seq = {1, 2, 3, 4, 5}

std::vector<int> part(10);
std::generate_n(part.begin(), 3, []() { return 42; });
// 3 phần tử đầu = 42

7.2 includes

Kiểm tra dãy A có chứa tất cả phần tử của dãy B không (cả hai phải được sắp xếp).

std::vector<int> setA = {1, 2, 3, 4, 5};
std::vector<int> setB = {2, 4};
bool result = std::includes(setA.begin(), setA.end(),
                            setB.begin(), setB.end()); // true

7.3 Các phép toán tập hợp

std::vector<int> s1 = {1, 2, 3, 4, 5};
std::vector<int> s2 = {3, 4, 5, 6, 7};
std::vector<int> output;

// Hợp
std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
               std::back_inserter(output));
// output = {1, 2, 3, 4, 5, 6, 7}

// Giao
output.clear();
std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
                      std::back_inserter(output));
// output = {3, 4, 5}

// Hiệu (s1 - s2)
output.clear();
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
                    std::back_inserter(output));
// output = {1, 2}

// Hiệu đối xứng
output.clear();
std::set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
                              std::back_inserter(output));
// output = {1, 2, 6, 7}

8. Câu hỏi thường gặp

1. Phân biệt sort và stable_sort?
   sort dùng Introsort (kết hợp QuickSort, HeapSort), không đảm bảo thứ tự các phần tử bằng nhau. stable_sort dùng MergeSort, giữ nguyên thứ tự tương đối của các phần tử bằng nhau, nhưng tốn thêm bộ nhớ.
2. Tại sao remove phải đi với erase?
   remove chỉ di chuyển các phần tử "cần giữ" lên đầu và trả về iterator tới vùng "rác". Nó không thay đổi kích thước container. erase mới thực sự xóa vùng rác và thu nhỏ container. Đây là kỹ thuật erase-remove idiom.
3. Thuật toán nào yêu cầu dãy đã được sắp xếp?
   Tất cả các thuật toán tìm kiếm nhị phân (binary_search, lower_bound, upper_bound), các phép toán tập hợp (set_union, set_intersection, ...), includes, merge, và unique (để loại bỏ tất cả trùng lặp). Các thuật toán này tận dụng tính chất sắp xếp để đạt độ phức tạp O(log n) hoặc O(n).