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

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

1.1 find và find_if

• find(begin, end, value): Tìm phần tử đầu tiên bằng với value, trả về iterator (trả về end nếu không tìm thấy).
• find_if(begin, end, predicate): Tìm phần tử đầu tiên thỏa mãn một điều kiện nhất định (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.

std::array danhSachSo = {10, 20, 30, 40, 50};

// Tìm giá trị 30
auto it = std::find(danhSachSo.begin(), danhSachSo.end(), 30);
if (it != danhSachSo.end()) {
    std::cout << "Tìm thấy: " << *it << std::endl; // In ra: 30
}

// Tìm phần tử đầu tiên lớn hơn 25
auto it2 = std::find_if(danhSachSo.begin(), danhSachSo.end(), [](int x) {
    return x > 25;
});
std::cout << "Phần tử đầu tiên >25: " << *it2 << std::endl; // In ra: 30

// Tìm chuỗi con
std::array chuoiCon = {20, 30};
auto it3 = std::find_end(danhSachSo.begin(), danhSachSo.end(), chuoiCon.begin(), chuoiCon.end());
if (it3 != danhSachSo.end()) {
    std::cout << "Chuỗi con bắt đầu tại chỉ số: " << std::distance(danhSachSo.begin(), it3) << std::endl; // In ra: 1
}

1.2 count và count_if

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

std::vector<int> mangSo = {5, 10, 15, 10, 20, 10};
int dem = std::count(mangSo.begin(), mangSo.end(), 10); // Đếm số 10, kết quả là 3
int demChan = std::count_if(mangSo.begin(), mangSo.end(), [](int x) { 
    return x % 2 == 0; 
}); // Đếm số chẵn, kết quả là 3

1.3 for_each

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

std::vector<int> mangSo = {1, 2, 3, 4, 5};
std::for_each(mangSo.begin(), mangSo.end(), [](int& x) { 
    x += 10; // Cộng 10 vào mỗi phần tử
});
// Giờ đây mangSo là {11, 12, 13, 14, 15}

1.4 equal và mismatch

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

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {1, 2, 4};
std::vector<int> c = {1, 2, 3, 4};

// So sánh 3 phần tử đầu của a và b
bool bangNhau = std::equal(a.begin(), a.end(), b.begin());
std::cout << "a == b? " << std::boolalpha << bangNhau << std::endl; // In ra: false

// Tìm phần tử đầu tiên không khớp giữa a và c
auto khacNhau = std::mismatch(a.begin(), a.end(), c.begin());
if (khacNhau.first != a.end()) {
    std::cout << "Phần tử không khớp: " << *khacNhau.first << " so với " << *khacNhau.second << std::endl; // Không có đầu ra (a và c khớp trong 3 phần tử đầu)
}

1.5 all_of, any_of, none_of

Kiểm tra xem tất cả, có ít nhất một, hoặc không có phần tử nào thỏa mãn một điều kiện.

std::vector<int> mangSo = {2, 4, 6, 8};
bool tatCaChan = std::all_of(mangSo.begin(), mangSo.end(), [](int x) { 
    return x % 2 == 0; 
}); // true
bool coSoLe = std::any_of(mangSo.begin(), mangSo.end(), [](int x) { 
    return x % 2 != 0; 
}); // false
bool khongSoAm = std::none_of(mangSo.begin(), mangSo.end(), [](int x) { 
    return x < 0; 
}); // true

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

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

2.1 copy và copy_if

• copy(begin, end, dest): Sao chép các phần tử từ [begin, end) vào 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 vào dest.

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

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

// Sao chép các phần tử lẻ vào một container mới
std::vector<int> le;
std::copy_if(nguon.begin(), nguon.end(), std::back_inserter(le), [](int x) {
    return x % 2 != 0;
});  // le: [1,3,5]

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

2.2 transform

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

std::vector<int> so = {1, 2, 3};
std::vector<int> binhPhuong(3);

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

// Cộng các phần tử của hai vector (chuyển đổi hai tham số)
std::vector<int> a = {10, 20, 30};
std::vector<int> b = {1, 2, 3};
std::vector<int> tong(3);
std::transform(a.begin(), a.end(), b.begin(), tong.begin(), [](int x, int y) {
    return x + y;
});  // tong: [11,22,33]

2.3 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.
• replace_copy(begin, end, dest, old_val, new_val): Sao chép và thay thế phần tử (không sửa đổi container gốc).

std::vector<int> so = {5, 10, 15, 10, 25};

// Thay thế tất cả 10 bằng 100
std::replace(so.begin(), so.end(), 10, 100);  // so: [5,100,15,100,25]

// Thay thế các số lớn hơn 20 bằng 0
std::replace_if(so.begin(), so.end(), [](int x) {
    return x > 20;
}, 0);  // so: [5,0,15,0,0]

// Sao chép và thay thế 15 bằng 150 (container gốc không thay đổi)
std::vector<int> ketQua;
std::replace_copy(so.begin(), so.end(), std::back_inserter(ketQua), 15, 150);  // ketQua: [5,0,150,0,0]

2.4 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 cuối 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.

std::vector<int> so = {5, 10, 15, 10, 20};

// Xóa logic các số 10 (di chuyển về cuối)
auto new_end = std::remove(so.begin(), so.end(), 10); // so: [5,15,20,10,10]

// Xóa vật lý (thực sự xóa phần tử)
so.erase(new_end, so.end()); // so: [5,15,20]

// Kết hợp lambda để xóa các số chia hết cho 5
so = {5, 10, 15, 20, 25};
so.erase(std::remove_if(so.begin(), so.end(), [](int x) {
    return x % 5 == 0;
}), so.end()); // so: []

2.5 unique

Xóa các phần tử trùng lặp liên tiếp trong phạm vi, trả về iterator cuối mới. Thường được kết hợp với erase.

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

2.6 reverse

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

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

2.7 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> vec = {1, 2, 3, 4, 5};
std::rotate(vec.begin(), vec.begin() + 2, vec.end()); // Xoay từ phần tử 3, vec trở thành {3, 4, 5, 1, 2}

2.8 shuffle

Xáo trộn ngẫu nhiên các phần tử trong phạm vi (cần C++11 trở lên).

#include <random>
#include <algorithm>

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

3. Sắp xếp và các thuật toán liên quan

3.1 sort, stable_sort và partial_sort

• sort(begin, end): Sắp xếp các phần tử (không ổn định, độ phức tạp trung bình O(n log n)).
• stable_sort(begin, end): Sắp xếp ổn định (vị trí tương đối của 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) chứa các phần tử nhỏ nhất và được sắp xếp.

std::vector<int> vec = {50, 30, 10, 40, 20};
std::sort(vec.begin(), vec.end()); // Sắp xếp tăng dần, vec trở thành {10, 20, 30, 40, 50}
std::sort(vec.begin(), vec.end(), std::greater<int>()); // Sắp xếp giảm dần, vec trở thành {50, 40, 30, 20, 10}
std::sort(vec.begin(), vec.end(), [](int a, int b) { 
    return a < b; 
}); // Sắp xếp tăng dần, so sánh tùy chỉnh

std::vector> vec = {{2, 1}, {1, 2}, {1, 1}, {2, 2}};
std::stable_sort(vec.begin(), vec.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> vec = {50, 30, 10, 40, 20, 60};
// Sắp xếp một phần, đưa 3 phần tử nhỏ nhất lên đầu
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
// Giờ đây 3 phần tử đầu tiên là 10, 20, 30, các phần tử sau chưa được 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 có giá trị 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> vec = {50, 30, 10, 40, 20, 60};
// Tìm phần tử lớn thứ ba (chỉ số 2)
std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
// Giờ đây vec[2] là 30, các phần tử bên trái <= 30, các phần tử bên phải >= 30

3.3 binary_search, lower_bound, upper_bound

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

• binary_search(begin, end, value): Kiểm tra xem 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.

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

// Kiểm tra 3 có tồn tại không
bool tonTai = std::binary_search(daSapXep.begin(), daSapXep.end(), 3);  // true

// Tìm phần tử đầu tiên >=3
auto lb = std::lower_bound(daSapXep.begin(), daSapXep.end(), 3);
std::cout << "Chỉ số lower_bound: " << std::distance(daSapXep.begin(), lb) << std::endl; // In ra: 1

// Tìm phần tử đầu tiên >3
auto ub = std::upper_bound(daSapXep.begin(), daSapXep.end(), 3);
std::cout << "Chỉ số upper_bound: " << std::distance(daSapXep.begin(), ub) << std::endl; // In ra: 3

3.4 merge

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

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

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

4. Các thuật toán về heap

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

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

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

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

std::sort_heap(vec.begin(), vec.end()); // Sắp xếp heap thành dãy tăng dần, vec 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 trong một danh sách khởi tạo.

int a = 5, b = 3;
int giaTriNho = std::min(a, b); // 3
int giaTriLon = std::max(a, b); // 5

auto nhoNhat = std::min({4, 2, 8, 5, 1}); // 1
auto lonNhat = 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 một phạm vi.

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

5.3 minmax_element (C++11)

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

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

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

6.1 accumulate

Tính tổng tích lũy của các phần tử trong phạm vi (hoặc một phép toán tùy chỉnh).

#include <numeric>

std::vector<int> vec = {1, 2, 3, 4, 5};
int tong = std::accumulate(vec.begin(), vec.end(), 0); // Tổng, giá trị khởi tạo là 0, kết quả là 15
int tich = std::accumulate(vec.begin(), vec.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 một phép toán tùy chỉnh).

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

6.3 iota

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

std::vector<int> vec(5);
std::iota(vec.begin(), vec.end(), 10); // Điền các giá trị 10, 11, 12, 13, 14

6.4 partial_sum

Tính tổng một phần, lưu kết quả vào một 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 tiếp, lưu kết quả vào một 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 một phạm vi bằng cách sử dụng một hàm tạo.

std::vector<int> vec(5);
int n = 0;
std::generate(vec.begin(), vec.end(), [&n]() { 
    return n++; 
}); // Điền các giá trị 0, 1, 2, 3, 4

7.2 generate_n

Điền n phần tử đầu tiên của một phạm vi bằng cách sử dụng một hàm tạo.

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

7.3 includes

Kiểm tra xem 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> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2 = {2, 4};
bool chua = std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end()); // true

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

Thực hiện các phép toán trê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> ketQua;

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

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

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

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

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

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

• sort sử dụng sắp xếp nhanh (thực tế là introsort), không ổn định (vị trí tương đối của các phần tử bằng nhau có thể thay đổi), độ phức tạp trung bình O(n log n).
• stable_sort sử dụng sắp xếp trộn, ổn định (vị trí tương đối của các phần tử bằng nhau không đổi), độ phức tạp O(n log n), nhưng chi phí bộ nhớ cao hơn một chút.

2. Tại sao thuật toán remove cần được kết hợp với erase?

Nguyên tắc của thuật toán 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 về phía trước và trả về iterator cuối mới, nhưng **không thay đổi kích thước thực tế của container**. erase thì xóa thực sự các phần tử thông qua phạm vi iterator, thay đổi kích thước của container. Do đó, cần kết hợp sử dụng: container.erase(remove(...), container.end()).

3. Các thuật toán nào yêu cầu container phải được sắp xếp?

Các thuật toán tìm kiếm nhị phân (như binary_search, lower_bound, upper_bound), các thuật toán trên tập hợp (như set_intersection, set_union), 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 các thao tác hiệu quả (ví dụ: tìm kiếm nhị phân O(log n)).