Trong phần này, chúng ta sẽ tìm hiểu về các thuật toán không sửa đổi và sửa đổi chuỗi, cũng như các thuật toán sắp xếp và các thuật toán khác trong thư viện chuẩn C++.

1. Thuật toán không sửa đổi chuỗi

Các thuật toán này không thay đổi các phần tử của vùng nhớ mà chúng hoạt động.

1.1 find và find_if

• find(bắt_đầu, kết_thúc, giá_trị): Tìm phần tử đầu tiên bằng giá_trị, trả về iterator (trả về kết_thúc nếu không tìm thấy).
• find_if(bắt_đầu, kết_thúc, điều_kiện): Tìm phần tử đầu tiên thỏa mãn điều kiện.
• find_end(bắt_đầu, kết_thúc, bắt_đầu_con, kết_thúc_con): Tìm vị trí cuối cùng của chuỗi con.

vector<int> số = {1, 3, 5, 7, 9};

// Tìm giá trị 5
auto it = find(số.begin(), số.end(), 5);
if (it != số.end()) {
    cout << "tìm thấy: " << *it << endl;  // Kết quả: 5
}

// Tìm phần tử đầu tiên lớn hơn 6
auto it2 = find_if(số.begin(), số.end(), [](int x) {
    return x > 6;
});
cout << "phần tử đầu tiên >6: " << *it2 << endl;  // Kết quả: 7

// Tìm chuỗi con
vector<int> con = {3, 5};
auto it3 = find_end(số.begin(), số.end(), con.begin(), con.end());
if (it3 != số.end()) {
    cout << "chuỗi con bắt đầu tại chỉ mục: " << it3 - số.begin() << endl;  // Kết quả: 1
}

1.2 count và count_if

• count(bắt_đầu, kết_thúc, giá_trị): Đếm số lượng phần tử bằng giá_trị.
• count_if(bắt_đầu, kết_thúc, điều_kiện): Đếm số lượng phần tử thỏa mãn điều kiện.

vector<int> vec = {1, 2, 3, 2, 4, 2};
int đếm = count(vec.begin(), vec.end(), 2); // Đếm số lượng 2, kết quả là 3
int đếm_chẵn = count_if(vec.begin(), vec.end(), [](int x) { 
    return x % 2 == 0; 
}); // Số lượng chẵn, kết quả là 3

1.3 for_each

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

vector<int> vec = {1, 2, 3, 4, 5};
for_each(vec.begin(), vec.end(), [](int& x) { 
    x *= 2; // Nhân mỗi phần tử với 2
});
// Bây giờ vec là {2, 4, 6, 8, 10}

1.4 equal và mismatch

• equal(b1, e1, b2): So sánh hai phạm vi [b1,e1) và [b2, b2+(e1-b1)) xem chúng có bằng nhau hay không.
• mismatch(b1, e1, b2): Trả về cặp iterator đến phần tử đầu tiên không bằng nhau giữa hai phạm vi.

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

// So sánh a và b trong 3 phần tử đầu tiên
bool bằng_nhau = equal(a.begin(), a.end(), b.begin());
cout << "a == b? " << boolalpha << bằng_nhau << endl;  // Kết quả: false

// Tìm phần tử đầu tiên không khớp giữa a và c
auto không_khop = mismatch(a.begin(), a.end(), c.begin());
if (không_khop.first != a.end()) {
    cout << "khoảng cách: " << *không_khop.first << " so với " << *không_khop.second << endl;  // Không có kết quả (a và c 3 phần tử đầu tiên bằng nhau)
}

1.5 all_of, any_of, none_of

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

vector<int> vec = {2, 4, 6, 8};
bool tất_cả_chẵn = all_of(vec.begin(), vec.end(), [](int x) { 
    return x % 2 == 0; 
}); // true
bool bất_kỳ_lẻ = any_of(vec.begin(), vec.end(), [](int x) { 
    return x % 2 != 0; 
}); // false
bool không_phản_bất = none_of(vec.begin(), vec.end(), [](int x) { 
    return x < 0; 
}); // true

2. Thuật toán sửa đổi chuỗi

Các thuật toán này thay đổi các phần tử của vùng nhớ mà chúng hoạt động.

2.1 copy và copy_if

• copy(bắt_đầu, kết_thúc, đích): Sao chép các phần tử từ [bắt_đầu, kết_thúc) vào vị trí bắt đầu từ đích.
• copy_if(bắt_đầu, kết_thúc, đích, điều_kiện): Sao chép các phần tử thỏa mãn điều kiện vào đích.

vector<int> nguồn = {1, 2, 3, 4, 5};
vector<int> đích(5);  // Cần phân bổ trước đủ không gian

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

// Sao chép các phần tử chẵn vào một vùng nhớ mới
vector<int> chẵn;
copy_if(nguồn.begin(), nguồn.end(), back_inserter(chẵn), [](int x) {
    return x % 2 == 0;
});  // chẵn: [2,4]

2.2 transform

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

vector<int> số = {1, 2, 3};
vector<int> bình_phương(3);

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

// Cộng hai phần tử từ hai vùng nhớ (chuyển đổi hai tham số)
vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
vector<int> tổng(3);
transform(a.begin(), a.end(), b.begin(), tổng.begin(), [](int x, int y) {
    return x + y;
});  // tổng: [5,7,9]

2.3 replace, replace_if và replace_copy

• replace(bắt_đầu, kết_thúc, giá_trị_cũ, giá_trị_mới): Thay thế tất cả các phần tử bằng giá_trị_cũ bằng giá_trị_mới.
• replace_if(bắt_đầu, kết_thúc, điều_kiện, giá_trị_mới): Thay thế các phần tử thỏa mãn điều kiện bằng giá_trị_mới.
• replace_copy(bắt_đầu, kết_thúc, đích, giá_trị_cũ, giá_trị_mới): Sao chép và thay thế phần tử (không thay đổi vùng nhớ gốc).

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

// Thay thế tất cả 2 bằng 20
replace(số.begin(), số.end(), 2, 20);  // số: [1,20,3,20,5]

// Thay thế các phần tử lớn hơn 10 bằng 0
replace_if(số.begin(), số.end(), [](int x) {
    return x > 10;
}, 0);  // số: [1,0,3,0,5]

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

2.4 remove, remove_if và erase

• remove(bắt_đầu, kết_thúc, giá_trị): Di chuyển các phần tử bằng giá_trị đến cuối vùng nhớ, trả về iterator mới (không thực sự xóa phần tử, cần kết hợp với erase).
• remove_if(bắt_đầu, kết_thúc, điều_kiện): Di chuyển các phần tử thỏa mãn điều kiện đến cuối vùng nhớ.

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

// Xóa logic tất cả 2 (di chuyển đến cuối)
auto cuối_mới = remove(số.begin(), số.end(), 2);  // số: [1,3,4,2,2]

// Xóa vật lý (thực sự loại bỏ phần tử)
số.erase(cuối_mới, số.end());  // số: [1,3,4]

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

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 mới. Thường được sử dụng kết hợp với erase.

vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto cuối = unique(vec.begin(), vec.end());
vec.erase(cuối, 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.

vector<int> vec = {1, 2, 3, 4, 5};
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ử trung tâm trở thành phần tử đầu tiên.

vector<int> vec = {1, 2, 3, 4, 5};
rotate(vec.begin(), vec.begin() + 2, vec.end()); // Xoay từ 3 trở đi, vec trở thành {3, 4, 5, 1, 2}

2.8 shuffle

Sắp xếp ngẫu nhiên các phần tử trong phạm vi (yêu cầu C++11 trở lên).

#include <random>
#include <algorithm>

vector<int> vec = {1, 2, 3, 4, 5};
random_device rd;
mt19937 gen(rd());
shuffle(vec.begin(), vec.end(), gen); // Sắp xếp 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(bắt_đầu, kết_thúc): Sắp xếp các phần tử bằng thuật toán nhanh (không ổn định, độ phức tạp trung bình O(n log n)).
• stable_sort(bắt_đầu, kết_thúc): Sắp xếp ổn định (thứ tự tương đối của các phần tử bằng nhau giữ nguyên).
• partial_sort(bắt_đầu, giữa, kết_thúc): Sắp xếp một phần, khiến [bắt_đầu, giữa) chứa các phần tử nhỏ nhất trong toàn bộ phạm vi và sắp xếp chúng.

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

vector<pair<int, int>> vec = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
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ự tương đối của các phần tử bằng nhau
});

vector<int> vec = {5, 3, 1, 4, 2, 6};
// Đặt 3 phần tử nhỏ nhất ở đầu và sắp xếp chúng
partial_sort(vec.begin(), vec.begin() + 3, vec.end());
// Bây giờ 3 phần tử đầu tiên của vec là 1, 2, 3, phần còn lại chưa được sắp xếp

3.2 nth_element

Tái sắp xếp phạm vi sao cho phần tử tại vị trí chỉ định bằng 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ó.

vector<int> vec = {5, 3, 1, 4, 2, 6};
// Tìm phần tử nhỏ thứ 3 (chỉ số 2)
nth_element(vec.begin(), vec.begin() + 2, vec.end());
// Bây giờ vec[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 các vùng nhớ đã được sắp xếp.

• binary_search(bắt_đầu, kết_thúc, giá_trị): Kiểm tra xem giá_trị có tồn tại hay không (trả về bool).
• lower_bound(bắt_đầu, kết_thúc, giá_trị): Trả về iterator đến phần tử đầu tiên không nhỏ hơn giá_trị.
• upper_bound(bắt_đầu, kết_thúc, giá_trị): Trả về iterator đến phần tử đầu tiên lớn hơn giá_trị.

vector<int> đã_sắp_xếp = {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 tồn_tại = binary_search(đã_sắp_xếp.begin(), đã_sắp_xếp.end(), 3);  // true

// Tìm phần tử đầu tiên ≥ 3
auto lb = lower_bound(đã_sắp_xếp.begin(), đã_sắp_xếp.end(), 3);
cout << "chỉ số lower_bound: " << lb - đã_sắp_xếp.begin() << endl;  // Kết quả: 1

// Tìm phần tử đầu tiên > 3
auto ub = upper_bound(đã_sắp_xếp.begin(), đã_sắp_xếp.end(), 3);
cout << "chỉ số upper_bound: " << ub - đã_sắp_xếp.begin() << endl;  // Kết quả: 3

3.4 merge

Hợp nhất hai vùng nhớ đã được sắp xếp vào vùng nhớ mới (giữ nguyên thứ tự).

vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> hợp_chập(a.size() + b.size());

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

4. Thuật toán heap

Thư viện chuẩn C++ cung cấp các thuật toán để thao tác với phạm vi dưới dạng heap, bao gồm make_heap, push_heap, pop_heap, sort_heap v.v.

vector<int> vec = {4, 1, 3, 2, 5};
make_heap(vec.begin(), vec.end()); // Xây dựng heap tối đa, vec trở thành {5, 4, 3, 2, 1}

vec.push_back(6);
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}

pop_heap(vec.begin(), vec.end()); // Di chuyển phần tử tối đa đến cuối, vec trở thành {5, 4, 3, 2, 1, 6}
int giá_trị_tối_đa = vec.back(); // Lấy phần tử tối đa 6
vec.pop_back(); // Loại bỏ phần tử tối đa

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 giá trị nhỏ nhất/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 a = 5, b = 3;
int giá_trị_nhỏ_nhat = min(a, b); // 3
int giá_trị_lớn_nhat = max(a, b); // 5

auto giá_trị_nhỏ_nhat_trong_danh_sách = min({4, 2, 8, 5, 1}); // 1
auto giá_trị_lớn_nhat_trong_danh_sách = max({4, 2, 8, 5, 1}); // 8

5.2 min_element và max_element

Trả về iterator đến phần tử nhỏ nhất/lớn nhất trong phạm vi.

vector<int> vec = {3, 1, 4, 2, 5};
auto min_it = min_element(vec.begin(), vec.end()); // Chỉ đến 1
auto max_it = max_element(vec.begin(), vec.end()); // Chỉ đến 5

5.3 minmax_element (C++11)

Cùng lúc trả về iterator đến phần tử nhỏ nhất và lớn nhất trong phạm vi.

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

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

6.1 accumulate

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

#include <numeric>

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

vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
int tích_vô_hướng = inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32

6.3 iota

Nhập các giá trị liên tục tăng vào phạm vi.

vector<int> vec(5);
iota(vec.begin(), vec.end(), 10); // Nhập vào 10, 11, 12, 13, 14

6.4 partial_sum

Tính tổng riêng lẻ, lưu kết quả vào phạm vi đích.

vector<int> nguồn = {1, 2, 3, 4, 5};
vector<int> đích(nhân_giữa.size());
partial_sum(nhân_giữa.begin(), nguồn.end(), đích.begin()); // đích trở thành {1, 3, 6, 10, 15}

6.5 adjacent_difference

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

vector<int> nguồn = {1, 2, 3, 4, 5};
vector<int> đích(nhân_giữa.size());
adjacent_difference(nhân_giữa.begin(), nguồn.end(), đích.begin()); // đích trở thành {1, 1, 1, 1, 1}

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

7.1 generate

Nhập các phần tử vào phạm vi bằng hàm tạo.

vector<int> vec(5);
int n = 0;
generate(vec.begin(), vec.end(), [&n]() { 
    return n++; 
}); // Nhập vào 0, 1, 2, 3, 4

7.2 generate_n

Nhập các phần tử vào n phần tử đầu tiên của phạm vi bằng hàm tạo.

vector<int> vec(5);
int n = 10;
generate_n(vec.begin(), 3, [&n]() { 
    return n++; 
}); // Ba phần tử đầu tiên là 10, 11, 12, hai phần tử còn lại giữ nguyên

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 hay không.

vector<int> vec1 = {1, 2, 3, 4, 5};
vector<int> vec2 = {2, 4};
bool chứa = 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 tập hợp: hợp, giao, hiệu và hiệu đối xứng.

vector<int> v1 = {1, 2, 3, 4, 5};
vector<int> v2 = {3, 4, 5, 6, 7};
vector<int> kết_quả;

// Hợp
set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(kết_quả));
// kết_quả là {1, 2, 3, 4, 5, 6, 7}

// Giao
kết_quả.clear();
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(kết_quả));
// kết_quả là {3, 4, 5}

// Hiệu (v1 - v2)
kết_quả.clear();
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(kết_quả));
// kết_quả là {1, 2}

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