1. Các thuật toán không làm thay đổi dữ liệu (Non-modifying)

Nhóm thuật toán này thực hiện việc đọc hoặc kiểm tra các phần tử trong container mà không làm biến đổi giá trị của chúng.

1.1. Truy vấn vị trí với find, find_if và find_end

• find: Trả về iterator đến phần tử đầu tiên khớp với giá trị cần tìm.
• find_if: Tìm kiếm dựa trên một điều kiện (predicate) tùy chỉnh.
• find_end: Tìm kiếm vị trí xuất hiện cuối cùng của một chuỗi con.

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

std::vector<int> data_set = {10, 25, 40, 55, 70, 25, 85};

// Tìm giá trị 40
auto it = std::find(data_set.begin(), data_set.end(), 40);
if (it != data_set.end()) {
    std::cout << "Tim thay: " << *it << std::endl;
}

// Tìm số đầu tiên lớn hơn 50
auto it_gt = std::find_if(data_set.begin(), data_set.end(), [](int val) {
    return val > 50;
});
std::cout << "So dau tien > 50 la: " << *it_gt << std::endl;

// Tìm chuỗi con {25, 40}
std::vector<int> pattern = {25, 40};
auto it_sub = std::find_end(data_set.begin(), data_set.end(), pattern.begin(), pattern.end());

1.2. Thống kê với count và count_if

std::vector<int> scores = {8, 7, 10, 8, 9, 8};
// Đếm số lượng điểm 8
int count_8 = std::count(scores.begin(), scores.end(), 8); // Kết quả: 3

// Đếm số lượng điểm đạt (>= 8)
int pass_count = std::count_if(scores.begin(), scores.end(), [](int s) {
    return s >= 8;
});

1.3. Kiểm tra logic: all_of, any_of, none_of

std::vector<int> ages = {20, 25, 30};
bool is_adult = std::all_of(ages.begin(), ages.end(), [](int a) { return a >= 18; });
bool has_senior = std::any_of(ages.begin(), ages.end(), [](int a) { return a > 60; });

2. Các thuật toán làm thay đổi dữ liệu (Modifying)

Nhóm này trực tiếp can thiệp vào giá trị hoặc cấu trúc sắp xếp của các phần tử trong container.

2.1. Copy và Transform

transform cho phép áp dụng một hàm lên từng phần tử và lưu kết quả vào container đích.

std::vector<int> inputs = {1, 2, 3, 4};
std::vector<int> outputs(4);

// Nhân đôi giá trị các phần tử
std::transform(inputs.begin(), inputs.end(), outputs.begin(), [](int x) {
    return x * 2;
}); 
// outputs: {2, 4, 6, 8}

2.2. Kỹ thuật Erase-Remove

Trong STL, remove không thực sự xóa phần tử khỏi bộ nhớ mà chỉ dồn các phần tử cần giữ lại lên phía trước. Để xóa hoàn toàn, ta cần kết hợp với phương thức erase của container.

std::vector<int> vals = {1, 0, 2, 0, 3};

// Loại bỏ tất cả số 0
vals.erase(std::remove(vals.begin(), vals.end(), 0), vals.end());
// vals hiện tại: {1, 2, 3}

2.3. Sắp xếp và Đảo ngược

std::reverse(vals.begin(), vals.end()); // Đảo ngược thứ tự
std::rotate(vals.begin(), vals.begin() + 1, vals.end()); // Dịch chuyển xoay vòng

3. Thuật toán sắp xếp và Tìm kiếm nhị phân

Để tối ưu hiệu suất, các thuật toán tìm kiếm nhị phân yêu cầu dữ liệu phải được sắp xếp trước.

3.1. Sắp xếp nâng cao

• sort: Tốc độ nhanh (O(N log N)), nhưng không bảo toàn thứ tự các phần tử bằng nhau.
• stable_sort: Bảo toàn thứ tự ban đầu của các phần tử có giá trị bằng nhau.
• partial_sort: Chỉ sắp xếp một nhóm nhỏ phần tử đầu tiên (ví dụ: tìm Top 3).

std::vector<int> collection = {9, 1, 5, 3, 7};
std::sort(collection.begin(), collection.end()); // {1, 3, 5, 7, 9}

// Tìm kiếm nhị phân
bool found = std::binary_search(collection.begin(), collection.end(), 5);

// Xác định biên
auto lb = std::lower_bound(collection.begin(), collection.end(), 4); // Vị trí đầu tiên >= 4

4. Thao tác trên Heap

C++ cung cấp các hàm để biến một vector thành cấu trúc Max-Heap nhanh chóng.

std::vector<int> heap_data = {10, 20, 5, 30};
std::make_heap(heap_data.begin(), heap_data.end()); // Tạo cấu trúc Heap

heap_data.push_back(40);
std::push_heap(heap_data.begin(), heap_data.end()); // Cập nhật sau khi thêm phần tử

5. Thuật toán số học (Numeric)

Nằm trong thư viện <numeric>, các hàm này hữu ích cho việc tính toán tổng hợp.

#include <numeric>

std::vector<int> nums = {1, 2, 3, 4, 5};
// Tính tổng
int total = std::accumulate(nums.begin(), nums.end(), 0);

// Tạo dãy số tịnh tiến
std::iota(nums.begin(), nums.end(), 100); // {100, 101, 102, 103, 104}

6. Phân tích các vấn đề thường gặp

1. Khi nào nên dùng stable_sort?
Sử dụng stable_sort khi bạn cần sắp xếp dữ liệu theo nhiều tiêu chí. Ví dụ: Sắp xếp danh sách sinh viên theo tên, sau đó sắp xếp theo lớp mà vẫn giữ nguyên thứ tự tên đã sắp xếp trước đó.

2. Tại sao binary_search chỉ trả về bool?
Vì binary_search chỉ nhằm mục đích kiểm tra sự tồn tại. Nếu bạn cần lấy iterator của phần tử đó, hãy sử dụng std::lower_bound hoặc std::equal_range.

3. Hiệu suất của std::unique?
std::unique chỉ loại bỏ các phần tử trùng lặp nằm cạnh nhau. Do đó, thông thường ta phải gọi std::sort trước khi gọi std::unique để đạt được kết quả tập hợp các phần tử duy nhất.