1. Các thuật toán không thay đổi dãy

Các thuật toán này không sửa đổi các phần tử trong container mà chúng hoạt động.

1.1 find và find_if

• find(begin, end, value): Tìm phần tử đầu tiên bằng 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.
• find_end(begin, end, sub_begin, sub_end): Tìm vị trí xuất hiện cuối cùng của dãy con.

std::vector<int> numbers = {2, 4, 6, 8, 10};

// Tìm phần tử có giá trị 6
auto pos = std::find(numbers.begin(), numbers.end(), 6);
if (pos != numbers.end()) {
    std::cout << "Tim thay: " << *pos << std::endl;  // Xuat: 6
}

// Tìm phần tử lớn hơn 7 dau tien
auto pos2 = std::find_if(numbers.begin(), numbers.end(), [](int val) {
    return val > 7;
});
std::cout << "Gia tri lon hon 7: " << *pos2 << std::endl;  // Xuat: 8

// Tim day con
std::vector<int> sub = {4, 6};
auto pos3 = std::find_end(numbers.begin(), numbers.end(), sub.begin(), sub.end());
if (pos3 != numbers.end()) {
    std::cout << "Day con bat dau tai vi tri: " << pos3 - numbers.begin() << std::endl;  // Xuat: 1
}

1.2 count và count_if

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

std::vector<int> data = {1, 3, 3, 5, 3, 7};
int so_lan = std::count(data.begin(), data.end(), 3); // Dem so 3, ket qua la 3
int so_le = std::count_if(data.begin(), data.end(), [](int val) { 
    return val % 2 != 0; 
}); // So le, ket qua la 5

1.3 for_each

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

std::vector<int> data = {1, 2, 3, 4, 5};
std::for_each(data.begin(), data.end(), [](int& val) { 
    val = val * 2; // Nhan doi moi phan tu
});
// Bay gio data tro thanh {2, 4, 6, 8, 10}

1.4 equal và mismatch

• equal(b1, e1, b2): Kiem tra hai dãy [b1,e1) va [b2, b2+(e1-b1)) co bang nhau hay khong.
• mismatch(b1, e1, b2): Tra ve cap iterator den phan tu dau tien khong bang nhau.

std::vector<int> mang_a = {1, 2, 3};
std::vector<int> mang_b = {1, 2, 4};
std::vector<int> mang_c = {1, 2, 3, 4};

// So sanh 3 phan tu dau cua a va b
bool bang_nhau = std::equal(mang_a.begin(), mang_a.end(), mang_b.begin());
std::cout << "a == b? " << std::boolalpha << bang_nhau << std::endl;  // Xuat: false

// Tim phan tu khong khop dau tien giua a va c
auto khong_khop = std::mismatch(mang_a.begin(), mang_a.end(), mang_c.begin());
if (khong_khop.first != mang_a.end()) {
    std::cout << "Khong khop: " << *khong_khop.first << " vs " << *khong_khop.second << std::endl;  
}

1.5 all_of, any_of, none_of

Kiem tra xem tat ca, ton tai, hoac khong co phan tư nao thoa man dieu kien

std::vector<int> data = {2, 4, 6, 8};
bool tat_ca_chan = std::all_of(data.begin(), data.end(), [](int val) { 
    return val % 2 == 0; 
}); // true
bool ton_tai_le = std::any_of(data.begin(), data.end(), [](int val) { 
    return val % 2 != 0; 
}); // false
bool khong_am = std::none_of(data.begin(), data.end(), [](int val) { 
    return val < 0; 
}); // true

2. Các thuật toán thay đổi dãy

Các thuật toán này sẽ sửa đổi các phần tử trong container.

2.1 copy và copy_if

• copy(begin, end, dest): Sao chep cac phan tu tu [begin, end) den vi tri bat dau tu dest.
• copy_if(begin, end, dest, predicate): Sao chep cac phan tu thoa man dieu kien den dest.

std::vector<int> nguon = {1, 2, 3, 4, 5};
std::vector<int> dich(5);  // Can cap phat du dung bo nho

// Sao chep tat ca phan tu
std::copy(nguon.begin(), nguon.end(), dich.begin());  // dich: [1,2,3,4,5]

// Sao chep phan tu chan vao container moi
std::vector<int> so_chan;
std::copy_if(nguon.begin(), nguon.end(), std::back_inserter(so_chan), [](int val) {
    return val % 2 == 0;
});  // so_chan: [2,4]

Luu y: back_inserter(dest) se tu dong goi push_back, khong can cap phat truoc.

2.2 transform

Ap dung mot ham cho moi phan tu trong dãy va luu ket qua vao dãy khac

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

// Tinh binh phuong (chuyen doi tham so don)
std::transform(input.begin(), input.end(), binh_phuong.begin(), [](int val) {
    return val * val;
});  // binh_phuong: [1,4,9]

// Cong hai container (chuyen doi tham so kep)
std::vector<int> mang_a = {1, 2, 3};
std::vector<int> mang_b = {4, 5, 6};
std::vector<int> ket_qua(3);
std::transform(mang_a.begin(), mang_a.end(), mang_b.begin(), ket_qua.begin(), [](int x, int y) {
    return x + y;
});  // ket_qua: [5,7,9]

2.3 replace, replace_if va replace_copy

• replace(begin, end, gia_cu, gia_moi): Thay tat ca gia_cu thanh gia_moi.
• replace_if(begin, end, predicate, gia_moi): Thay the cac phan tu thoa man dieu kien.
• replace_copy(begin, end, dest, gia_cu, gia_moi): Thay the khi sao chep (khong sua doi container goc).

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

// Thay the tat ca 2 thanh 20
std::replace(numbers.begin(), numbers.end(), 2, 20);  // numbers: [1,20,3,20,5]

// Thay the phan tu lon hon 10 thanh 0
std::replace_if(numbers.begin(), numbers.end(), [](int val) {
    return val > 10;
}, 0);  // numbers: [1,0,3,0,5]

// Thay the 3 thanh 300 khi sao chep (container goc khong doi)
std::vector<int> ket_qua;
std::replace_copy(numbers.begin(), numbers.end(), std::back_inserter(ket_qua), 3, 300);  // ket_qua: [1,0,300,0,5]

2.4 remove, remove_if va erase

• remove(begin, end, value): Di chuyen cac phan tu bang value ve cuoi container, tra ve iterator cuoi logic (khong xoa that su, can ket hop voi erase).
• remove_if(begin, end, predicate): Di chuyen cac phan tu thoa man dieu kien ve cuoi.

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

// Xoa logic tat ca 2 (di ve cuoi)
auto cuoi_moi = std::remove(numbers.begin(), numbers.end(), 2);  // numbers: [1,3,4,2,2]

// Xoa that su (thuc su loai bo phan tu)
numbers.erase(cuoi_moi, numbers.end());  // numbers: [1,3,4]

// Ket hop lambda de xoa so chan
numbers = {1, 2, 3, 4, 5};
numbers.erase(std::remove_if(numbers.begin(), numbers.end(), [](int val) {
    return val % 2 == 0;
}), numbers.end());  // numbers: [1,3,5]

2.5 unique

Loai bo cac phan tu lap lien tiep trong dãy, tra ve iterator cuoi logic. Thuong ket hop voi erase.

std::vector<int> du_lieu = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto vi_tri_cuoi = std::unique(du_lieu.begin(), du_lieu.end());
du_lieu.erase(vi_tri_cuoi, du_lieu.end()); // du_lieu tro thanh {1, 2, 3, 4, 5}

2.6 reverse

Dao nguoc thu tu cac phan tu trong dãy

std::vector<int> du_lieu = {1, 2, 3, 4, 5};
std::reverse(du_lieu.begin(), du_lieu.end()); // du_lieu tro thanh {5, 4, 3, 2, 1}

2.7 rotate

Xoay cac phan tu trong dãy, phan tu giua tro thanh phan tu moi dau tien

std::vector<int> du_lieu = {1, 2, 3, 4, 5};
std::rotate(du_lieu.begin(), du_lieu.begin() + 2, du_lieu.end()); // xoay voi 3 lam diem bat dau, du_lieu tro thanh {3, 4, 5, 1, 2}

2.8 shuffle

Sap xep ngau nhien cac phan tu trong dãy (can C++11 hoac cao hon)

#include <random>
#include <algorithm>

std::vector<int> du_lieu = {1, 2, 3, 4, 5};
std::random_device thiet_bi_ngau_nhien;
std::mt19937 bo_tao(thiet_bi_ngau_nhien());
std::shuffle(du_lieu.begin(), du_lieu.end(), bo_tao); // Xao tron ngau nhien cac phan tu

3. Các thuật toán sắp xếp

3.1 sort, stable_sort va partial_sort

• sort(begin, end): Sap xep nhanh (khong on dinh, do phuc tap trung binh O(n log n)).
• stable_sort(begin, end): Sap xep on dinh (cac phan tu bang nhau giu nguyen vi tri).
• partial_sort(begin, mid, end): Sap xep mot phan, [begin, mid) chua cac phan tu nho nhat va da duoc sap xep.

std::vector<int> du_lieu = {5, 3, 1, 4, 2};
std::sort(du_lieu.begin(), du_lieu.end()); // Mac dinh tang, du_lieu tro thanh {1, 2, 3, 4, 5}
std::sort(du_lieu.begin(), du_lieu.end(), std::greater<int>()); // Giam, du_lieu tro thanh {5, 4, 3, 2, 1}
std::sort(du_lieu.begin(), du_lieu.end(), [](int a, int b) { 
    return a < b; 
}); // Tang, so sanh tuy chinh

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; // Sap xep theo first, giu nguyen thu tu tuong doi cua phan tu bang nhau
});

std::vector<int> du_lieu = {5, 3, 1, 4, 2, 6};
// Dua 3 phan tu nho nhat len truoc va sap xep
std::partial_sort(du_lieu.begin(), du_lieu.begin() + 3, du_lieu.end());
// Bay gio 3 phan tu dau tien la 1, 2, 3, sau la 4, 5, 6 chua sap xep

3.2 nth_element

Sap xep lai dãy de phan tu o vi tri chi dinh bang voi phan tu sau khi sap xep, cac phan tu ben trai khong lon hon no, ben phai khong nho hon no

std::vector<int> du_lieu = {5, 3, 1, 4, 2, 6};
// Tim phan tu nho thu 3 (chi so 2)
std::nth_element(du_lieu.begin(), du_lieu.begin() + 2, du_lieu.end());
// Bay gio du_lieu[2] la 3, phan tu ben trai <= 3, ben pha >= 3

3.3 binary_search, lower_bound, upper_bound

Can tren container da sap xep

• binary_search(begin, end, value): Kiem tra value co ton tai hay khong (tra ve bool).
• lower_bound(begin, end, value): Tra ve iterator phan tu khong nho hon value.
• upper_bound(begin, end, value): Tra ve iterator phan tu lon hon value.

std::vector<int> da_sap_xep = {1, 3, 3, 5, 7};  // Phai sap xep truoc

// Kiem tra 3 co ton tai khong
bool ton_tai = std::binary_search(da_sap_xep.begin(), da_sap_xep.end(), 3);  // true

// Tim phan tu dau tien >= 3
auto lb = std::lower_bound(da_sap_xep.begin(), da_sap_xep.end(), 3);
std::cout << "Chi so lower_bound: " << lb - da_sap_xep.begin() << std::endl;  // Xuat: 1

// Tim phan tu dau tien > 3
auto ub = std::upper_bound(da_sap_xep.begin(), da_sap_xep.end(), 3);
std::cout << "Chi so upper_bound: " << ub - da_sap_xep.begin() << std::endl;  // Xuat: 3

3.4 merge

Gop hai dãy da sap xep vao container moi (giu nguyen thu tu)

std::vector<int> mang_a = {1, 3, 5};
std::vector<int> mang_b = {2, 4, 6};
std::vector<int> ket_hop(da_sap_xep.size() + b.size());

// Gop a va b (deu phai duoc sap xep)
std::merge(mang_a.begin(), mang_a.end(), mang_b.begin(), mang_b.end(), ket_hop.begin());  // ket_hop: [1,2,3,4,5,6]

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

STL cung cap cac thuat toan de xu li dãy nhu heap, bao gom make_heap, push_heap, pop_heap, sort_heap.

std::vector<int> du_lieu = {4, 1, 3, 2, 5};
std::make_heap(du_lieu.begin(), du_lieu.end()); // Xay dung max heap, du_lieu tro thanh {5, 4, 3, 2, 1}

du_lieu.push_back(6);
std::push_heap(du_lieu.begin(), du_lieu.end()); // Them phan tu moi vao heap, du_lieu tro thanh {6, 4, 5, 2, 1, 3}

std::pop_heap(du_lieu.begin(), du_lieu.end()); // Chuyen phan tu lon nhat ve cuoi, du_lieu tro thanh {5, 4, 3, 2, 1, 6}
int gia_tri_lon_nhat = du_lieu.back(); // Lay phan tu lon nhat 6
du_lieu.pop_back(); // Loai bo phan tu lon nhat

std::sort_heap(du_lieu.begin(), du_lieu.end()); // Sap xep heap thanh day tang, du_lieu tro thanh {1, 2, 3, 4, 5}

5. Các thuật toán tìm min/max

5.1 min va max

Tra ve gia tri nho nhat/lon nhat trong hai gia tri hoac danh sach khoi tao

int x = 5, y = 3;
int gia_tri_min = std::min(x, y); // 3
int gia_tri_max = std::max(x, y); // 5

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

5.2 min_element va max_element

Tra ve iterator den phan tu nho nhat/lon nhat trong dãy

std::vector<int> du_lieu = {3, 1, 4, 2, 5};
auto it_min = std::min_element(du_lieu.begin(), du_lieu.end()); // Tro den 1
auto it_max = std::max_element(du_lieu.begin(), du_lieu.end()); // Tro den 5

5.3 minmax_element (C++11)

Tra ve dong thoi iterator den phan tu nho nhat va lon nhat trong dãy

std::vector<int> du_lieu = {3, 1, 4, 2, 5};
auto minmax = std::minmax_element(du_lieu.begin(), du_lieu.end());
// minmax.first tro den 1, minmax.second tro den 5

6. Các thuật toán số (trong )

6.1 accumulate

Tinh tong tich luy cua cac phan tu trong dãy (hoac phep toan tuy chinh)

#include <numeric>

std::vector<int> du_lieu = {1, 2, 3, 4, 5};
int tong = std::accumulate(du_lieu.begin(), du_lieu.end(), 0); // Tong, gia tri ban dau 0, ket qua 15
int tich = std::accumulate(du_lieu.begin(), du_lieu.end(), 1, std::multiplies<int>()); // Tich, gia tri ban dau 1, ket qua 120

6.2 inner_product

Tinh tich trong cua hai dãy (hoac phep toan tuy chinh)

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

6.3 iota

Dien day voi cac gia tri tang dan lien tiep

std::vector<int> du_lieu(5);
std::iota(du_lieu.begin(), du_lieu.end(), 10); // Dien: 10, 11, 12, 13, 14

6.4 partial_sum

Tinh tong tong, luu ket qua vao dãy dich

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 tro thanh {1, 3, 6, 10, 15}

6.5 adjacent_difference

Tinh hieu giua cac phan tu lien ke, luu ket qua vao dãy dich

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 tro thanh {1, 1, 1, 1, 1}

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

7.1 generate

Dien day voi ham tao

std::vector<int> du_lieu(5);
int n = 0;
std::generate(du_lieu.begin(), du_lieu.end(), [&n]() { 
    return n++; 
}); // Dien: 0, 1, 2, 3, 4

7.2 generate_n

Dien n phan tu dau tien cua dãy voi ham tao

std::vector<int> du_lieu(5);
int n = 10;
std::generate_n(du_lieu.begin(), 3, [&n]() { 
    return n++; 
}); // Ba phan tu dau la 10, 11, 12, hai phan tu cuoi giu nguyen

7.3 includes

Kiem tra mot dãy da sap xep co chua tat ca phan tu cua dãy da sap xep khac hay khong

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

Thuc hien cac phep toan tap hop: hop, giao, hieu, va hieu doi xung

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

// Hop
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(ket_qua));
// ket_qua: {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: {3, 4, 5}

// Hieu (v1 - v2)
ket_qua.clear();
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(ket_qua));
// ket_qua: {1, 2}

// Hieu doi xung (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: {1, 2, 6, 7}

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

1. Su khac biet giua sort va stable_sort?

• sort su dung thuat toan quick sort (thuc chat la introsort), khong on dinh (vi tri tuong doi cua phan tu bang nhau co the thay doi), do phuc tap trung binh O(n log n).
• stable_sort su dung merge sort, on dinh (vi tri tuong doi cua phan tu bang nhau khong doi), do phuc tap O(n log n), nhung ton them bo nho.

2. Tai sao thuat toan remove can ket hop voi erase? Nguyen ly cua thuat toan remove la "ghi de" cac phan tu can xoa, di chuyen cac phan tu giu lai ve phia truoc, tra ve iterator cuoi logic nhung khong thay doi kich thuc that cua container. erase thuc su xoa phan tu qua iterator, thay doi kich thuc container. Can ket hop: container.erase(remove(...), container.end()).

3. Thuật toán nào cần container đã sắp xếp? Cac thuat toan tim kiem nhi phan (binary_search, lower_bound, upper_bound), cac thuat toan tap hop (set_intersection, set_union, ...), merge, ... cac thuat toan nay phu thuoc vao tinh sap xep de thuc hien hieu qua (nhu tim kiem nhi phan O(log n)).