1. Các thuật toán không thay đổi chuỗi

Đây là các thuật toán không làm thay đổi các phần tử trong container mà chúng thao tác.

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

• find(begin, end, value): Tìm phần tử đầu tiên bằng với value, trả về iterator (nếu không tìm thấy trả về end).
• find_if(begin, end, predicate): Tìm phần tử đầu tiên thỏa mãn điều kiện của predicate.
• find_end(begin, end, sub_begin, sub_end): Tìm vị trí xuất hiện cuối cùng của một chuỗi con.

vector<int> du_lieu = {2, 4, 6, 8, 10};

// Tìm giá trị 6
auto vi_tri = find(du_lieu.begin(), du_lieu.end(), 6);
if (vi_tri != du_lieu.end()) {
    cout << "tim thay: " << *vi_tri << endl;  // Xuất: 6
}

// Tìm phần tử đầu tiên lớn hơn 7
auto vi_tri2 = find_if(du_lieu.begin(), du_lieu.end(), [](int x) {
    return x > 7;
});
cout << "dau tien >7: " << *vi_tri2 << endl;  // Xuất: 8

// Tìm chuỗi con
vector<int> con = {4, 6};
auto vi_tri3 = find_end(du_lieu.begin(), du_lieu.end(), con.begin(), con.end());
if (vi_tri3 != du_lieu.end()) {
    cout << "chuoi con bat dau tai chi so: " << vi_tri3 - du_lieu.begin() << endl;  // Xuất: 1
}

1.2 Đếm với count và count_if

• count(begin, end, value): Đếm số phần tử bằng với value.
• count_if(begin, end, predicate): Đếm số phần tử thỏa mãn điều kiện của predicate.

std::vector<int> mang = {3, 6, 9, 6, 12, 6};
int dem = std::count(mang.begin(), mang.end(), 6); // Đếm số 6, kết quả là 3
int chan_dem = std::count_if(mang.begin(), mang.end(), [](int x) { 
    return x % 2 == 0; 
}); // Đếm số chẵn, kết quả là 4

1.3 Xử lý từng phần tử với for_each

Áp dụng một hàm cho mỗi phần tử trong phạm vi

std::vector<int> mang = {1, 2, 3, 4, 5};
std::for_each(mang.begin(), mang.end(), [](int& x) { 
    x *= 3; // Nhân mỗi phần tử với 3
});
// Giờ mang là {3, 6, 9, 12, 15}

1.4 So sánh với equal và mismatch

• equal(b1, e1, b2): Kiểm tra hai phạm vi [b1,e1) và [b2, b2+(e1-b1)) có bằng nhau không.
• mismatch(b1, e1, b2): Trả về cặp iterator đầu tiên của hai phạm vi không bằng nhau.

vector<int> a = {5, 10, 15};
vector<int> b = {5, 10, 20};
vector<int> c = {5, 10, 15, 20};

// So sánh a và b
bool bang_nhau = equal(a.begin(), a.end(), b.begin());
cout << "a == b? " << boolalpha << bang_nhau << endl;  // Xuất: false

// Tìm phần tử không khớp đầu tiên giữa a và c
auto khac = mismatch(a.begin(), a.end(), c.begin());
if (khac.first != a.end()) {
    cout << "khac nhau: " << *khac.first << " vs " << *khac.second << endl;  // Không xuất (3 phần tử đầu giống nhau)
}

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

Kiểm tra tất cả, có bất kỳ hoặc không có phần tử nào thỏa mãn điều kiện

std::vector<int> mang = {4, 8, 12, 16};
bool chan_het = std::all_of(mang.begin(), mang.end(), [](int x) { 
    return x % 2 == 0; 
}); // true
bool le_batky = std::any_of(mang.begin(), mang.end(), [](int x) { 
    return x % 2 != 0; 
}); // false
bool am = std::none_of(mang.begin(), mang.end(), [](int x) { 
    return x < 0; 
}); // true

2. Các thuật toán thay đổi chuỗi

Đây là các thuật toán sẽ thay đổi các phần tử trong container mà chúng thao tác.

2.1 Sao chép với copy và copy_if

• copy(begin, end, dest): Sao chép các phần tử trong [begin, end) đến vị trí bắt đầu của dest.
• copy_if(begin, end, dest, predicate): Sao chép các phần tử thỏa mãn điều kiện của predicate đến dest.

vector<int> nguon = {1, 2, 3, 4, 5};
vector<int> dich(5);  // Cần cấp phát đủ không gian trước

// Sao chép tất cả
copy(nguon.begin(), nguon.end(), dich.begin());  // dich: [1,2,3,4,5]

// Sao chép số chẵn vào container mới
vector<int> chan;
copy_if(nguon.begin(), nguon.end(), back_inserter(chan), [](int x) {
    return x % 2 == 0;
});  // chan: [2,4]

Lưu ý: back_inserter(dich) sẽ tự động gọi push_back, không cần cấp phát trước.

2.2 Biến đổi dữ liệu với transform

Áp dụng một hàm cho mỗi phần tử trong phạm vi và lưu kết quả vào một phạm vi khác

vector<int> so = {1, 2, 3};
vector<int> binh_phuong(3);

// Tính bình phương (biến đổi một tham số)
transform(so.begin(), so.end(), binh_phuong.begin(), [](int x) {
    return x * x;
});  // binh_phuong: [1,4,9]

// Cộng hai mảng (biến đổi hai tham số)
vector<int> a = {10, 20, 30};
vector<int> b = {1, 2, 3};
vector<int> tong(3);
transform(a.begin(), a.end(), b.begin(), tong.begin(), [](int x, int y) {
    return x + y;
});  // tong: [11,22,33]

2.3 Thay thế với replace, replace_if và replace_copy

• replace(begin, end, old_val, new_val): Thay thế tất cả old_val bằng new_val.
• replace_if(begin, end, predicate, new_val): Thay thế các phần tử thỏa mãn điều kiện của predicate.
• replace_copy(begin, end, dest, old_val, new_val): Sao chép và thay thế phần tử (không thay đổi container gốc).

vector<int> so = {1, 2, 3, 2, 5};

// Thay thế tất cả 2 thành 20
replace(so.begin(), so.end(), 2, 20);  // so: [1,20,3,20,5]

// Thay thế số lớn hơn 10 thành 0
replace_if(so.begin(), so.end(), [](int x) {
    return x > 10;
}, 0);  // so: [1,0,3,0,5]

// Sao chép và thay thế 3 thành 300 (không thay đổi mảng gốc)
vector<int> ket_qua;
replace_copy(so.begin(), so.end(), back_inserter(ket_qua), 3, 300);  // ket_qua: [1,0,300,0,5]

2.4 Loại bỏ với remove, remove_if và erase

• remove(begin, end, value): "Di chuyển" các phần tử bằng value về cuối container, trả về iterator logic mới (không thực sự xóa phần tử, cần kết hợp với erase).
• remove_if(begin, end, predicate): Di chuyển các phần tử thỏa mãn điều kiện về cuối.

vector<int> so = {1, 2, 3, 2, 4};

// Xóa logic tất cả 2 (di chuyển về cuối)
auto cuoi_moi = remove(so.begin(), so.end(), 2);  // so: [1,3,4,2,2]

// Xóa thực tế (thực sự loại bỏ phần tử)
so.erase(cuoi_moi, so.end());  // so: [1,3,4]

// Kết hợp lambda xóa số chẵn
so = {1, 2, 3, 4, 5};
so.erase(remove_if(so.begin(), so.end(), [](int x) {
    return x % 2 == 0;
}), so.end());  // so: [1,3,5]

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

Loại bỏ các phần tử trùng lặp liên tiếp trong phạm vi, trả về iterator logic mới. Thường kết hợp với erase.

std::vector<int> mang = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto cuoi = std::unique(mang.begin(), mang.end());
mang.erase(cuoi, mang.end()); // mang trở thành {1, 2, 3, 4, 5}

2.6 Đảo ngược với reverse

Đảo ngược thứ tự các phần tử trong phạm vi

std::vector<int> mang = {1, 2, 3, 4, 5};
std::reverse(mang.begin(), mang.end()); // mang trở thành {5, 4, 3, 2, 1}

2.7 Xoay với rotate

Xoay các phần tử trong phạm vi, làm cho phần tử ở giữa trở thành phần tử đầu tiên

std::vector<int> mang = {1, 2, 3, 4, 5};
std::rotate(mang.begin(), mang.begin() + 2, mang.end()); // Xoay với 3 làm điểm bắt đầu, mang trở thành {3, 4, 5, 1, 2}

2.8 Xáo trộn với shuffle

Xáo trộn ngẫu nhiên các phần tử trong phạm vi (cần C++11 hoặc cao hơn)

#include <random>
#include <algorithm>

std::vector<int> mang = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(mang.begin(), mang.end(), g); // Xáo trộn ngẫu nhiên các phần tử trong mang

3. Thuật toán sắp xếp và liên quan

3.1 sort, stable_sort và partial_sort

• sort(begin, end): Sắp xếp các phần tử bằng quick sort (không ổn định, độ phức tạp thời gian trung bình O(n log n)).
• stable_sort(begin, end): Sắp xếp ổn định (vị trí tương đối các phần tử bằng nhau không đổi).
• partial_sort(begin, mid, end): Sắp xếp một phần, làm cho [begin, mid) là các phần tử nhỏ nhất trong phạm vi và được sắp xếp.

std::vector<int> mang = {5, 3, 1, 4, 2};
std::sort(mang.begin(), mang.end()); // Mặc định tăng dần, mang trở thành {1, 2, 3, 4, 5}
std::sort(mang.begin(), mang.end(), std::greater<int>()); // Giảm dần, mang trở thành {5, 4, 3, 2, 1}
std::sort(mang.begin(), mang.end(), [](int a, int b) { 
    return a < b; 
}); // Tăng dần, so sánh tùy chỉnh

std::vector<std::pair<int, int>> cap = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(cap.begin(), cap.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // Sắp xếp theo first, giữ nguyên thứ tự các phần tử bằng nhau
});

std::vector<int> mang = {5, 3, 1, 4, 2, 6};
// Đưa 3 phần tử nhỏ nhất về phía trước và sắp xếp
std::partial_sort(mang.begin(), mang.begin() + 3, mang.end());
// Giờ 3 phần tử đầu của mang là 1, 2, 3, các phần tử sau là 4, 5, 6 chưa sắp xếp

3.2 nth_element

Sắp xếp lại phạm vi sao cho phần tử ở vị trí chỉ định bằng với phần tử đã sắp xếp, và các phần tử bên trái không lớn hơn nó, các phần tử bên phải không nhỏ hơn nó

std::vector<int> mang = {5, 3, 1, 4, 2, 6};
// Tìm phần tử thứ 3 nhỏ nhất (chỉ số 2)
std::nth_element(mang.begin(), mang.begin() + 2, mang.end());
// Giờ mang[2] là 3, các phần tử bên trái <= 3, các phần tử bên phải >= 3

3.3 binary_search, lower_bound, upper_bound

Cần sử dụng trên container đã được sắp xếp

• binary_search(begin, end, value): Kiểm tra value có tồn tại không (trả về bool).
• lower_bound(begin, end, value): Trả về iterator của phần tử đầu tiên không nhỏ hơn value.
• upper_bound(begin, end, value): Trả về iterator của phần tử đầu tiên lớn hơn value.

vector<int> da_sap_xep = {1, 3, 3, 5, 7};  // Phải được sắp xếp trước

// Kiểm tra 3 có tồn tại
bool ton_tai = binary_search(da_sap_xep.begin(), da_sap_xep.end(), 3);  // true

// Tìm phần tử đầu tiên >=3
auto lb = lower_bound(da_sap_xep.begin(), da_sap_xep.end(), 3);
cout << "chi so lower_bound: " << lb - da_sap_xep.begin() << endl;  // Xuất: 1

// Tìm phần tử đầu tiên >3
auto ub = upper_bound(da_sap_xep.begin(), da_sap_xep.end(), 3);
cout << "chi so upper_bound: " << ub - da_sap_xep.begin() << endl;  // Xuất: 3

3.4 merge

Hai phạm vi đã sắp xếp được hợp nhất vào một container mới (giữ thứ tự sắp xếp)

vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> hop_nhat(a.size() + b.size());

// Hợp nhất a và b (cả hai đều phải được sắp xếp)
merge(a.begin(), a.end(), b.begin(), b.end(), hop_nhat.begin());  // hop_nhat: [1,2,3,4,5,6]

4. Thuật toán heap

STL cung cấp các thuật toán để thao tác với phạm vi như heap, bao gồm make_heap, push_heap, pop_heap, sort_heap, v.v.

std::vector<int> mang = {4, 1, 3, 2, 5};
std::make_heap(mang.begin(), mang.end()); // Xây dựng heap lớn nhất, mang trở thành {5, 4, 3, 2, 1}

mang.push_back(6);
std::push_heap(mang.begin(), mang.end()); // Thêm phần tử mới vào heap, mang trở thành {6, 4, 5, 2, 1, 3}

std::pop_heap(mang.begin(), mang.end()); // Di chuyển phần tử lớn nhất về cuối, mang trở thành {5, 4, 3, 2, 1, 6}
int gia_tri_lon_nhat = mang.back(); // Lấy phần tử lớn nhất 6
mang.pop_back(); // Loại bỏ phần tử lớn nhất

std::sort_heap(mang.begin(), mang.end()); // Sắp xếp heap thành dãy tăng dần, mang trở thành {1, 2, 3, 4, 5}

5. Thuật toán tìm giá trị nhỏ/lớn nhất

5.1 min và max

Trả về giá trị nhỏ nhất/lớn nhất giữa hai giá trị hoặc danh sách khởi tạo

int x = 10, y = 7;
int gia_tri_nho = std::min(x, y); // 7
int gia_lon_nhat = std::max(x, y); // 10

auto nho_nhat_danh_sach = std::min({4, 2, 8, 5, 1}); // 1
auto lon_nhat_danh_sach = std::max({4, 2, 8, 5, 1}); // 8

5.2 min_element và max_element

Trả về iterator của phần tử nhỏ nhất/lớn nhất trong phạm vi

std::vector<int> mang = {3, 1, 4, 2, 5};
auto min_it = std::min_element(mang.begin(), mang.end()); // Trỏ đến 1
auto max_it = std::max_element(mang.begin(), mang.end()); // Trỏ đến 5

5.3 minmax_element (C++11)

Trả về iterator của phần tử nhỏ nhất và lớn nhất trong phạm vi cùng lúc

std::vector<int> mang = {3, 1, 4, 2, 5};
auto minmax = std::minmax_element(mang.begin(), mang.end());
// minmax.first trỏ đến 1, minmax.second trỏ đến 5

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

6.1 accumulate

Tính tổng các phần tử trong phạm vi (hoặc thao tác tùy chỉnh)

#include <numeric>

std::vector<int> mang = {1, 2, 3, 4, 5};
int tong = std::accumulate(mang.begin(), mang.end(), 0); // Tổng, giá trị khởi tạo là 0, kết quả là 15
int tich = std::accumulate(mang.begin(), mang.end(), 1, std::multiplies<int>()); // Tích, giá trị khởi tạo là 1, kết quả là 120

6.2 inner_product

Tính tích vô hướng của hai phạm vi (hoặc thao tác tùy chỉnh)

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

6.3 iota

Điền phạm vi với các giá trị tăng dần liên tiếp

std::vector<int> mang(5);
std::iota(mang.begin(), mang.end(), 10); // Điền với 10, 11, 12, 13, 14

6.4 partial_sum

Tính tổng từng phần, lưu kết quả vào phạm vi đích

std::vector<int> nguon = {1, 2, 3, 4, 5};
std::vector<int> dich(nguon.size());
std::partial_sum(nguon.begin(), nguon.end(), dich.begin()); // dich trở thành {1, 3, 6, 10, 15}

6.5 adjacent_difference

Tính hiệu của các phần tử liền kề, lưu kết quả vào phạm vi đích

std::vector<int> nguon = {1, 2, 3, 4, 5};
std::vector<int> dich(nguon.size());
std::adjacent_difference(nguon.begin(), nguon.end(), dich.begin()); // dich trở thành {1, 1, 1, 1, 1}

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

7.1 generate

Điền phạm vi với một hàm tạo

std::vector<int> mang(5);
int n = 0;
std::generate(mang.begin(), mang.end(), [&n]() { 
    return n++; 
}); // Điền với 0, 1, 2, 3, 4

7.2 generate_n

Điền n phần tử đầu tiên của phạm vi với một hàm tạo

std::vector<int> mang(5);
int n = 10;
std::generate_n(mang.begin(), 3, [&n]() { 
    return n++; 
}); // 3 phần tử đầu là 10, 11, 12, 2 phần tử sau không đổi

7.3 includes

Kiểm tra một phạm vi đã sắp xếp có chứa tất cả các phần tử của một phạm vi đã sắp xếp khác không

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

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

Thực hiện các phép toán tập hợp: hợp, giao, hiệu và hiệu đối xứng

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> ket_qua;

// Hợp
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(ket_qua));
// ket_qua là {1, 2, 3, 4, 5, 6, 7}

// Giao
ket_qua.clear();
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(ket_qua));
// ket_qua là {3, 4, 5}

// Hiệu (v1 - v2)
ket_qua.clear();
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(ket_qua));
// ket_qua là {1, 2}

// Hiệu đối xứng (v1 ∪ v2 - v1 ∩ v2)
ket_qua.clear();
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(ket_qua));
// ket_qua là {1, 2, 6, 7}

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

1. Sự khác biệt giữa sort và stable_sort?

• sort sử dụng quick sort (thực tế là introsort), không ổn định (vị trí tương đối các phần tử bằng nhau có thể thay đổi), độ phức tạp thời gian trung bình O(n log n).
• stable_sort sử dụng merge sort, ổn định (vị trí tương đối các phần tử bằng nhau không đổi), độ phức tạp thời gian O(n log n), nhưng tốn bộ nhớ hơi nhiều hơn.

2. Tại sao thuật toán remove cần kết hợp với erase? Nguyên lý của remove là "che đậy" các phần tử cần xóa, di chuyển các phần tử còn lại lên phía trước, trả về iterator logic mới, nhưng không thay đổi kích thước thực của container. erase thì xóa các phần tử thông qua phạm vi iterator, thay đổi kích thước container. Vì vậy cần kết hợp: container.erase(remove(...), container.end()).
3. Các thuật toán nào cần container đã được sắp xếp? Các thuật toán tìm kiếm nhị phân (binary_search, lower_bound, upper_bound), các thuật toán tập hợp (set_intersection, set_union, v.v.), merge, v.v. Các thuật toán này phụ thuộc vào tính sắp xếp để thực hiện thao tác hiệu quả (như tìm kiếm nhị phân O(log n)).