1. Nhóm thuật toán truy vấn (Non-modifying sequence algorithms)

Đây là các thuật toán thực hiện thao tác đọc hoặc kiểm tra trên container mà không làm thay đổi giá trị hay thứ tự của các phần tử.

1.1 Tìm kiếm với find và find_if

• find: Truy vấn vị trí đầu tiên của một giá trị cụ thể.
• find_if: Tìm kiếm dựa trên một điều kiện (predicate).
• find_end: Xác định vị trí xuất hiện cuối cùng của một chuỗi con.

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

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

// Tìm số đầu tiên chia hết cho 11
auto it_cond = std::find_if(values.begin(), values.end(), [](int n) {
    return n % 11 == 0;
});
if (it_cond != values.end()) {
    std::cout << "So chia het cho 11: " << *it_cond << std::endl; // 55
}

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

std::vector<int> data = {1, 3, 2, 3, 4, 3, 5};
int total_threes = std::count(data.begin(), data.end(), 3); // Ket qua: 3

// Dem cac so le
int odd_count = std::count_if(data.begin(), data.end(), [](int n) {
    return n % 2 != 0;
}); // Ket qua: 5

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

std::vector<int> scores = {80, 90, 85, 70};

bool all_passed = std::all_of(scores.begin(), scores.end(), [](int s) { return s >= 50; }); // true
bool has_distinction = std::any_of(scores.begin(), scores.end(), [](int s) { return s > 95; }); // false
bool no_fail = std::none_of(scores.begin(), scores.end(), [](int s) { return s < 40; }); // true

2. Nhóm thuật toán thay đổi dữ liệu (Modifying sequence algorithms)

Các thuật toán này trực tiếp tác động hoặc tạo ra bản sao mới của dữ liệu dựa trên các quy tắc biến đổi.

2.1 Chuyển đổi dữ liệu với transform

transform là công cụ mạnh mẽ để áp dụng một hàm lên toàn bộ dải dữ liệu và lưu kết quả vào một vị trí mới.

std::vector<int> base = {1, 2, 3, 4};
std::vector<int> cubes(base.size());

// Tinh lap phuong
std::transform(base.begin(), base.end(), cubes.begin(), [](int n) {
    return n * n * n;
}); // cubes: {1, 8, 27, 64}

2.2 Kỹ thuật xóa phần tử: remove và erase

Trong C++, std::remove không thực sự xóa phần tử khỏi bộ nhớ mà chỉ dồn chúng về cuối container. Để xóa hoàn toàn, ta cần kết hợp với phương thức erase (Erase-remove idiom).

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

// Loai bo cac so 9
auto new_logical_end = std::remove(numbers.begin(), numbers.end(), 9);
numbers.erase(new_logical_end, numbers.end()); 
// numbers bay gio la: {1, 2, 3, 4}

2.3 Thay thế giá trị

std::vector<int> items = {10, 20, 30, 20, 40};
// Thay the 20 bang 99
std::replace(items.begin(), items.end(), 20, 99); // {10, 99, 30, 99, 40}

3. Sắp xếp và Tìm kiếm nhị phân

3.1 Thuật toán Sort

• sort: Tốc độ trung bình O(n log n), 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ị tương đương.

std::vector<int> arr = {5, 2, 9, 1, 5, 6};
std::sort(arr.begin(), arr.end()); // {1, 2, 5, 5, 6, 9}

// Sap xep giam dan
std::sort(arr.begin(), arr.end(), std::greater<int>());

3.2 Tìm kiếm nhị phân trên dữ liệu đã sắp xếp

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

// Tim kiem su ton tai
bool found = std::binary_search(sorted_vec.begin(), sorted_vec.end(), 20); // true

// lower_bound: Phan tu dau tien >= val
auto lb = std::lower_bound(sorted_vec.begin(), sorted_vec.end(), 20); // Tro vao chi so 1

// upper_bound: Phan tu dau tien > val
auto ub = std::upper_bound(sorted_vec.begin(), sorted_vec.end(), 20); // Tro vao chi so 3

4. Thuật toán số học (Header <numeric>)

#include <numeric>

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

// Tinh tong
int sum = std::accumulate(vals.begin(), vals.end(), 0); // 15

// Dien du lieu tang dan
std::vector<int> range(5);
std::iota(range.begin(), range.end(), 100); // {100, 101, 102, 103, 104}

// Tinh tich vo huong
std::vector<int> v1 = {1, 2};
std::vector<int> v2 = {3, 4};
int dot_product = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0); // 1*3 + 2*4 = 11

5. Các lưu ý quan trọng khi sử dụng

1. Hiệu năng của sort: std::sort thường sử dụng Introsort, là sự kết hợp của QuickSort, HeapSort và InsertionSort để đạt hiệu năng tối ưu nhất.
2. Yêu cầu của Binary Search: Các thuật toán như binary_search, lower_bound, includes chỉ hoạt động chính xác trên các container đã được sắp xếp. Nếu dữ liệu chưa sắp xếp, kết quả trả về sẽ không xác định.
3. Sự khác biệt giữa remove và erase: Đây là lỗi phổ biến nhất của lập trình viên mới. std::remove không làm thay đổi size() của container, chỉ có erase() mới thực sự giải phóng phần dư thừa.