Thư viện chuẩn C++ (STL) cung cấp một tập hợp phong phú các thuật toán mạnh mẽ, giúp thao tác với các container một cách hiệu quả. Các thuật toán này thường hoạt động trên các phạm vi được xác định bởi các cặp iterator và được phân loại dựa trên tác động của chúng lên dữ liệu. Bài viết này sẽ đi sâu vào các nhóm thuật toán chính, từ những thuật toán không thay đổi dữ liệu gốc đến các thuật toán sắp xếp và số học phức tạp hơn.

1. Các Thuật Toán Không Thay Đổi Dữ Liệu

Nhóm thuật toán này thực hiện các phép đọc hoặc kiểm tra trên các phần tử trong container mà không làm thay đổi giá trị của chúng.

1.1. Tìm kiếm: std::find, std::find_if, std::find_end

• std::find(bat_dau, ket_thuc, gia_tri): Tìm kiếm lần xuất hiện đầu tiên của một gia_tri cụ thể trong phạm vi [bat_dau, ket_thuc). Trả về iterator trỏ đến phần tử tìm thấy, hoặc ket_thuc nếu không tìm thấy.
• std::find_if(bat_dau, ket_thuc, dieu_kien): Tìm phần tử đầu tiên thỏa mãn một dieu_kien (predicate) do người dùng định nghĩa.
• std::find_end(bat_dau_1, ket_thuc_1, bat_dau_2, ket_thuc_2): Tìm lần xuất hiện cuối cùng của một chuỗi con [bat_dau_2, ket_thuc_2) trong chuỗi chính [bat_dau_1, ket_thuc_1).

#include <vector>
#include <algorithm>
#include <iostream>

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

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

// Tìm phần tử đầu tiên lớn hơn 45
auto phanTuLonHon45 = std::find_if(danhSachSo.begin(), danhSachSo.end(), [](int so) {
    return so > 45;
});
if (phanTuLonHon45 != danhSachSo.end()) {
    std::cout << "Phần tử đầu tiên > 45: " << *phanTuLonHon45 << std::endl; // Xuất: 50
}

// Tìm chuỗi con
std::vector<int> chuoiCon = {20, 30};
auto viTriChuoiCon = std::find_end(danhSachSo.begin(), danhSachSo.end(), chuoiCon.begin(), chuoiCon.end());
if (viTriChuoiCon != danhSachSo.end()) {
    std::cout << "Chuỗi con bắt đầu tại chỉ mục: " << viTriChuoiCon - danhSachSo.begin() << std::endl; // Xuất: 1
}

1.2. Đếm số lượng: std::count và std::count_if

• std::count(bat_dau, ket_thuc, gia_tri): Đếm số lần xuất hiện của một gia_tri cụ thể.
• std::count_if(bat_dau, ket_thuc, dieu_kien): Đếm số phần tử thỏa mãn dieu_kien.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> diemSo = {7, 8, 5, 9, 8, 10};
int soLanXuatHien8 = std::count(diemSo.begin(), diemSo.end(), 8); // Đếm số 8, kết quả là 2
std::cout << "Số lần xuất hiện của 8: " << soLanXuatHien8 << std::endl;

int soHocSinhGioi = std::count_if(diemSo.begin(), diemSo.end(), [](int diem) {
    return diem >= 8;
}); // Đếm số học sinh giỏi (điểm >= 8), kết quả là 4
std::cout << "Số học sinh giỏi: " << soHocSinhGioi << std::endl;

1.3. Áp dụng hàm cho mỗi phần tử: std::for_each

Thực hiện một hàm hoặc functor cho từng phần tử trong một phạm vi.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> cacSoGoc = {1, 2, 3, 4, 5};
std::cout << "Các số gốc: ";
for (int so : cacSoGoc) {
    std::cout << so << " ";
}
std::cout << std::endl;

std::for_each(cacSoGoc.begin(), cacSoGoc.end(), [](int& so) {
    so *= 3; // Nhân mỗi phần tử với 3
});
// Bây giờ cacSoGoc trở thành {3, 6, 9, 12, 15}
std::cout << "Các số sau khi nhân 3: ";
for (int so : cacSoGoc) {
    std::cout << so << " ";
}
std::cout << std::endl;

1.4. So sánh phạm vi: std::equal và std::mismatch

• std::equal(b1, e1, b2): Kiểm tra xem hai phạm vi [b1, e1) và [b2, b2+(e1-b1)) có giống nhau hoàn toàn hay không.
• std::mismatch(b1, e1, b2): Trả về một cặp iterator trỏ đến cặp phần tử đầu tiên khác nhau giữa hai phạm vi.

#include <vector>
#include <algorithm>
#include <iostream>
#include <utility> // Cho std::pair

std::vector<int> dayA = {10, 20, 30};
std::vector<int> dayB = {10, 20, 40};
std::vector<int> dayC = {10, 20, 30, 50};

// So sánh dayA và dayB
bool dayASamaDayB = std::equal(dayA.begin(), dayA.end(), dayB.begin());
std::cout << "dayA có bằng dayB không? " << std::boolalpha << dayASamaDayB << std::endl; // Xuất: false

// Tìm điểm khác biệt đầu tiên giữa dayA và dayC
auto ketQuaSaiLech = std::mismatch(dayA.begin(), dayA.end(), dayC.begin());
if (ketQuaSaiLech.first != dayA.end()) {
    std::cout << "Sai lệch tại: " << *ketQuaSaiLech.first << " (dayA) vs " << *ketQuaSaiLech.second << " (dayC)" << std::endl; // Không xuất gì vì dayA là tiền tố của dayC
} else {
    std::cout << "Hai chuỗi giống nhau trong phạm vi ngắn hơn." << std::endl; // Xuất dòng này
}

1.5. Kiểm tra điều kiện tổng thể: std::all_of, std::any_of, std::none_of (C++11)

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

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> chuoiChan = {2, 4, 6, 8};
bool tatCaChan = std::all_of(chuoiChan.begin(), chuoiChan.end(), [](int so) {
    return so % 2 == 0;
}); // true
std::cout << "Tất cả đều chẵn: " << std::boolalpha << tatCaChan << std::endl;

bool coLeNaoKhong = std::any_of(chuoiChan.begin(), chuoiChan.end(), [](int so) {
    return so % 2 != 0;
}); // false
std::cout << "Có số lẻ nào không: " << std::boolalpha << coLeNaoKhong << std::endl;

bool khongCoAm = std::none_of(chuoiChan.begin(), chuoiChan.end(), [](int so) {
    return so < 0;
}); // true
std::cout << "Không có số âm: " << std::boolalpha << khongCoAm << std::endl;

2. Các Thuật Toán Thay Đổi Dữ Liệu

Những thuật toán này sẽ làm thay đổi giá trị hoặc vị trí của các phần tử bên trong container.

2.1. Sao chép: std::copy và std::copy_if

• std::copy(bat_dau, ket_thuc, diem_den): Sao chép các phần tử từ phạm vi nguồn [bat_dau, ket_thuc) sang vị trí bắt đầu từ diem_den. Đích đến phải có đủ không gian.
• std::copy_if(bat_dau, ket_thuc, diem_den, dieu_kien): Chỉ sao chép các phần tử thỏa mãn dieu_kien.

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator> // Cho std::back_inserter

std::vector<int> nguonDuLieu = {1, 2, 3, 4, 5, 6};
std::vector<int> dichSaoChep(nguonDuLieu.size()); // Cần cấp phát đủ không gian

// Sao chép tất cả phần tử
std::copy(nguonDuLieu.begin(), nguonDuLieu.end(), dichSaoChep.begin());
// dichSaoChep: {1, 2, 3, 4, 5, 6}
std::cout << "Dữ liệu đã sao chép: ";
for (int so : dichSaoChep) {
    std::cout << so << " ";
}
std::cout << std::endl;

// Sao chép chỉ các số chẵn vào một vector mới
std::vector<int> cacSoChan;
std::copy_if(nguonDuLieu.begin(), nguonDuLieu.end(), std::back_inserter(cacSoChan), [](int so) {
    return so % 2 == 0;
});
// cacSoChan: {2, 4, 6}
std::cout << "Các số chẵn đã sao chép: ";
for (int so : cacSoChan) {
    std::cout << so << " ";
}
std::cout << std::endl;
// Lưu ý: std::back_inserter sẽ tự động thêm phần tử, không cần cấp phát trước.

2.2. Biến đổi: std::transform

Áp dụng một hàm biến đổi cho từng phần tử trong một hoặc hai phạm vi, lưu kết quả vào một phạm vi đích.

#include <vector>
#include <algorithm>
#include <iostream>

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

// Tính bình phương của từng số (biến đổi đơn tham số)
std::transform(giaTriGoc.begin(), giaTriGoc.end(), ketQuaBinhPhuong.begin(), [](int so) {
    return so * so;
});
// ketQuaBinhPhuong: {1, 4, 9, 16}
std::cout << "Bình phương các số: ";
for (int so : ketQuaBinhPhuong) {
    std::cout << so << " ";
}
std::cout << std::endl;

// Cộng các phần tử từ hai vector (biến đổi đa tham số)
std::vector<int> daySo1 = {10, 20, 30};
std::vector<int> daySo2 = {1, 2, 3};
std::vector<int> tongCacPhanTu(daySo1.size());
std::transform(daySo1.begin(), daySo1.end(), daySo2.begin(), tongCacPhanTu.begin(), [](int x, int y) {
    return x + y;
});
// tongCacPhanTu: {11, 22, 33}
std::cout << "Tổng các phần tử từ 2 vector: ";
for (int so : tongCacPhanTu) {
    std::cout << so << " ";
}
std::cout << std::endl;

2.3. Thay thế: std::replace, std::replace_if, std::replace_copy

• std::replace(bat_dau, ket_thuc, gia_tri_cu, gia_tri_moi): Thay thế tất cả gia_tri_cu bằng gia_tri_moi.
• std::replace_if(bat_dau, ket_thuc, dieu_kien, gia_tri_moi): Thay thế các phần tử thỏa mãn dieu_kien.
• std::replace_copy(bat_dau, ket_thuc, diem_den, gia_tri_cu, gia_tri_moi): Sao chép phạm vi và thay thế các phần tử trên đường đi (không thay đổi container gốc).

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator> // Cho std::back_inserter

std::vector<int> duLieuBanDau = {1, 5, 3, 5, 7, 5};

// Thay thế tất cả số 5 thành 55
std::replace(duLieuBanDau.begin(), duLieuBanDau.end(), 5, 55);
// duLieuBanDau: {1, 55, 3, 55, 7, 55}
std::cout << "Sau khi thay 5 bằng 55: ";
for (int so : duLieuBanDau) {
    std::cout << so << " ";
}
std::cout << std::endl;

// Thay thế các số lớn hơn 50 bằng 0
std::replace_if(duLieuBanDau.begin(), duLieuBanDau.end(), [](int so) {
    return so > 50;
}, 0);
// duLieuBanDau: {1, 0, 3, 0, 7, 0}
std::cout << "Sau khi thay > 50 bằng 0: ";
for (int so : duLieuBanDau) {
    std::cout << so << " ";
}
std::cout << std::endl;

// Sao chép và thay thế 3 bằng 300 (vector gốc không đổi)
std::vector<int> ketQuaThayTheCopy;
std::replace_copy(duLieuBanDau.begin(), duLieuBanDau.end(), std::back_inserter(ketQuaThayTheCopy), 3, 300);
// ketQuaThayTheCopy: {1, 0, 300, 0, 7, 0}
std::cout << "Kết quả của replace_copy: ";
for (int so : ketQuaThayTheCopy) {
    std::cout << so << " ";
}
std::cout << std::endl;

2.4. Xóa phần tử (logic và vật lý): std::remove, std::remove_if, std::erase

• std::remove(bat_dau, ket_thuc, gia_tri): Di chuyển các phần tử không cần xóa về phía đầu container, trả về iterator trỏ đến vị trí logic cuối mới. **Không thay đổi kích thước container**.
• std::remove_if(bat_dau, ket_thuc, dieu_kien): Tương tự remove nhưng dựa trên dieu_kien.
• Để xóa phần tử vật lý, cần kết hợp với phương thức erase của container.

#include <vector>
#include <algorithm>
#include <iostream>

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

// Xóa logic tất cả số 20 (chỉ di chuyển các phần tử còn lại về phía trước)
auto new_logical_end = std::remove(mangSo.begin(), mangSo.end(), 20);
// mangSo có thể trông như {10, 30, 40, 50, 20, 20} (phần tử cuối không xác định nhưng không quan trọng)
std::cout << "Sau remove (logic): ";
for (auto it = mangSo.begin(); it != new_logical_end; ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

// Xóa vật lý các phần tử bị đánh dấu
mangSo.erase(new_logical_end, mangSo.end());
// mangSo: {10, 30, 40, 50}
std::cout << "Sau erase (vật lý): ";
for (int so : mangSo) {
    std::cout << so << " ";
}
std::cout << std::endl;

// Kết hợp remove_if và erase để xóa các số lẻ
mangSo = {11, 22, 33, 44, 55};
mangSo.erase(std::remove_if(mangSo.begin(), mangSo.end(), [](int so) {
    return so % 2 != 0; // Điều kiện xóa số lẻ
}), mangSo.end());
// mangSo: {22, 44}
std::cout << "Sau khi xóa số lẻ: ";
for (int so : mangSo) {
    std::cout << so << " ";
}
std::cout << std::endl;

2.5. Loại bỏ phần tử trùng lặp liên tiếp: std::unique

Di chuyển các phần tử trùng lặp liên tiếp về phía cuối, trả về iterator trỏ đến vị trí logic cuối mới. Cần sắp xếp trước nếu muốn loại bỏ tất cả các bản sao trùng lặp.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> danhSachTrungLap = {1, 1, 2, 2, 2, 3, 4, 4, 5};
auto cuoiLogich = std::unique(danhSachTrungLap.begin(), danhSachTrungLap.end());
// danhSachTrungLap có thể trông như {1, 2, 3, 4, 5, 4, 4, 5, 5}
danhSachTrungLap.erase(cuoiLogich, danhSachTrungLap.end());
// danhSachTrungLap trở thành {1, 2, 3, 4, 5}
std::cout << "Sau unique và erase: ";
for (int so : danhSachTrungLap) {
    std::cout << so << " ";
}
std::cout << std::endl;

2.6. Đảo ngược thứ tự: std::reverse

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

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<char> chuCai = {'a', 'b', 'c', 'd', 'e'};
std::reverse(chuCai.begin(), chuCai.end());
// chuCai trở thành {'e', 'd', 'c', 'b', 'a'}
std::cout << "Sau reverse: ";
for (char ch : chuCai) {
    std::cout << ch << " ";
}
std::cout << std::endl;

2.7. Xoay vòng: std::rotate

Xoay vòng các phần tử trong một phạm vi sao cho phần tử tại giua trở thành phần tử đầu tiên mới.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> chuoiGiaTri = {10, 20, 30, 40, 50};
// Xoay vòng để 30 (ở vị trí index 2) trở thành phần tử đầu tiên
std::rotate(chuoiGiaTri.begin(), chuoiGiaTri.begin() + 2, chuoiGiaTri.end());
// chuoiGiaTri trở thành {30, 40, 50, 10, 20}
std::cout << "Sau rotate: ";
for (int so : chuoiGiaTri) {
    std::cout << so << " ";
}
std::cout << std::endl;

2.8. Xáo trộn ngẫu nhiên: std::shuffle (C++11)

Sắp xếp lại các phần tử trong phạm vi một cách ngẫu nhiên, sử dụng một bộ sinh số ngẫu nhiên được cung cấp.

#include <vector>
#include <algorithm>
#include <iostream>
#include <random> // Cho std::random_device và std::mt19937

std::vector<int> daySoNgauNhien = {1, 2, 3, 4, 5, 6, 7, 8, 9};
std::random_device rd; // Thiết bị tạo số ngẫu nhiên
std::mt19937 boTaoNgauNhien(rd()); // Bộ tạo số ngẫu nhiên Mersenne Twister

std::shuffle(daySoNgauNhien.begin(), daySoNgauNhien.end(), boTaoNgauNhien); // Xáo trộn ngẫu nhiên
std::cout << "Sau shuffle: ";
for (int so : daySoNgauNhien) {
    std::cout << so << " ";
}
std::cout << std::endl;

3. Các Thuật Toán Sắp Xếp và Liên Quan

3.1. Sắp xếp: std::sort, std::stable_sort, std::partial_sort

• std::sort(bat_dau, ket_thuc): Sắp xếp các phần tử (mặc định tăng dần) sử dụng thuật toán introsort (kết hợp quicksort, heapsort và insertion sort). 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 thời gian trung bình O(n log n).
• std::stable_sort(bat_dau, ket_thuc): Sắp xếp ổn định (giữ nguyên thứ tự tương đối của các phần tử bằng nhau), thường dùng mergesort. Độ phức tạp thời gian O(n log n), có thể tốn thêm không gian.
• std::partial_sort(bat_dau, giua, ket_thuc): Sắp xếp một phần của phạm vi, đảm bảo rằng các phần tử trong [bat_dau, giua) là những phần tử nhỏ nhất của toàn bộ phạm vi và chúng được sắp xếp.

#include <vector>
#include <algorithm>
#include <iostream>
#include <functional> // Cho std::greater

std::vector<int> cacGiaTri = {5, 2, 8, 1, 9, 3};
std::sort(cacGiaTri.begin(), cacGiaTri.end()); // Sắp xếp tăng dần: {1, 2, 3, 5, 8, 9}
std::cout << "Sau sort tăng dần: ";
for (int val : cacGiaTri) {
    std::cout << val << " ";
}
std::cout << std::endl;

std::sort(cacGiaTri.begin(), cacGiaTri.end(), std::greater<int>()); // Sắp xếp giảm dần: {9, 8, 5, 3, 2, 1}
std::cout << "Sau sort giảm dần: ";
for (int val : cacGiaTri) {
    std::cout << val << " ";
}
std::cout << std::endl;

// stable_sort ví dụ (giữ nguyên thứ tự tương đối)
std::vector<std::pair<int, char>> danhSachDoi = {{1, 'b'}, {2, 'a'}, {1, 'a'}, {2, 'b'}};
std::stable_sort(danhSachDoi.begin(), danhSachDoi.end(), [](const auto& p1, const auto& p2) {
    return p1.first < p2.first; // Sắp xếp theo phần tử đầu tiên
});
// Kết quả: {{1, 'b'}, {1, 'a'}, {2, 'a'}, {2, 'b'}} - thứ tự 'b' trước 'a' với first=1 vẫn được giữ
// (Nếu dùng sort, có thể là {{1, 'a'}, {1, 'b'}, {2, 'a'}, {2, 'b'}})
std::cout << "Sau stable_sort: ";
for (const auto& p : danhSachDoi) {
    std::cout << "{" << p.first << "," << p.second << "} ";
}
std::cout << std::endl;

// partial_sort ví dụ
std::vector<int> duLieuHonHop = {7, 1, 5, 3, 9, 2, 8};
// Sắp xếp 3 phần tử nhỏ nhất và đưa chúng lên đầu
std::partial_sort(duLieuHonHop.begin(), duLieuHonHop.begin() + 3, duLieuHonHop.end());
// duLieuHonHop: {1, 2, 3, 7, 9, 5, 8} (3 phần tử đầu là 3 số nhỏ nhất và đã được sắp xếp)
std::cout << "Sau partial_sort (3 phần tử nhỏ nhất): ";
for (int val : duLieuHonHop) {
    std::cout << val << " ";
}
std::cout << std::endl;

3.2. Tìm phần tử thứ n: std::nth_element

Sắp xếp lại phạm vi sao cho phần tử tại vị trí `n` bằng với phần tử đó nếu toàn bộ phạm vi được sắp xếp. Tất cả các phần tử trước vị trí `n` sẽ không lớn hơn nó, và tất cả các phần tử sau vị trí `n` sẽ không nhỏ hơn nó.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> daySo = {5, 3, 1, 8, 2, 9, 4, 7, 6};
// Tìm phần tử thứ 4 nhỏ nhất (tại index 3)
std::nth_element(daySo.begin(), daySo.begin() + 3, daySo.end());
// daySo[3] sẽ là 4. Các phần tử bên trái <= 4, bên phải >= 4.
// Ví dụ: {3, 2, 1, 4, 9, 8, 7, 5, 6} (thứ tự bên trái/phải 4 có thể khác)
std::cout << "Sau nth_element (phần tử thứ 4 nhỏ nhất): ";
for (int val : daySo) {
    std::cout << val << " ";
}
std::cout << std::endl;
std::cout << "Phần tử tại index 3: " << daySo[3] << std::endl;

3.3. Tìm kiếm nhị phân: std::binary_search, std::lower_bound, std::upper_bound

Các thuật toán này yêu cầu container phải được **sắp xếp** để hoạt động hiệu quả.

• std::binary_search(bat_dau, ket_thuc, gia_tri): Kiểm tra xem gia_tri có tồn tại trong phạm vi hay không (trả về bool).
• std::lower_bound(bat_dau, ket_thuc, gia_tri): Trả về iterator trỏ đến phần tử đầu tiên **không nhỏ hơn** gia_tri.
• std::upper_bound(bat_dau, ket_thuc, gia_tri): Trả về iterator trỏ đến phần tử đầu tiên **lớn hơn** gia_tri.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> dayDaSapXep = {10, 20, 20, 30, 40, 50}; // Phải được sắp xếp

// Kiểm tra sự tồn tại của 30
bool timThay30 = std::binary_search(dayDaSapXep.begin(), dayDaSapXep.end(), 30); // true
std::cout << "Có 30 trong danh sách không? " << std::boolalpha << timThay30 << std::endl;

// Tìm phần tử đầu tiên >= 20
auto viTriLower = std::lower_bound(dayDaSapXep.begin(), dayDaSapXep.end(), 20);
std::cout << "Index của phần tử đầu tiên >= 20: " << viTriLower - dayDaSapXep.begin() << std::endl; // Xuất: 1

// Tìm phần tử đầu tiên > 20
auto viTriUpper = std::upper_bound(dayDaSapXep.begin(), dayDaSapXep.end(), 20);
std::cout << "Index của phần tử đầu tiên > 20: " << viTriUpper - dayDaSapXep.begin() << std::endl; // Xuất: 3

3.4. Gộp hai phạm vi: std::merge

Kết hợp hai phạm vi đã được sắp xếp vào một phạm vi đích mới, vẫn giữ nguyên thứ tự sắp xếp.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> day1 = {1, 3, 5, 7};
std::vector<int> day2 = {2, 4, 6, 8};
std::vector<int> ketQuaGop(day1.size() + day2.size());

// Gộp day1 và day2 (cả hai đều phải được sắp xếp)
std::merge(day1.begin(), day1.end(), day2.begin(), day2.end(), ketQuaGop.begin());
// ketQuaGop: {1, 2, 3, 4, 5, 6, 7, 8}
std::cout << "Sau merge: ";
for (int val : ketQuaGop) {
    std::cout << val << " ";
}
std::cout << std::endl;

4. Các Thuật Toán Heap

STL cung cấp các thuật toán để coi một phạm vi như một cấu trúc dữ liệu heap (ưu tiên), bao gồm make_heap, push_heap, pop_heap, và sort_heap.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> daySoHeap = {4, 1, 7, 2, 5, 8};
std::make_heap(daySoHeap.begin(), daySoHeap.end()); // Biến đổi thành max-heap. Ví dụ: {8, 5, 7, 2, 1, 4}
std::cout << "Sau make_heap: ";
for (int val : daySoHeap) {
    std::cout << val << " ";
}
std::cout << std::endl;

daySoHeap.push_back(10); // Thêm phần tử mới vào cuối
std::push_heap(daySoHeap.begin(), daySoHeap.end()); // Điều chỉnh heap sau khi thêm. Ví dụ: {10, 8, 7, 2, 5, 4, 1}
std::cout << "Sau push_heap (thêm 10): ";
for (int val : daySoHeap) {
    std::cout << val << " ";
}
std::cout << std::endl;

std::pop_heap(daySoHeap.begin(), daySoHeap.end()); // Đưa phần tử lớn nhất về cuối, điều chỉnh heap.
// Ví dụ: {8, 5, 7, 2, 1, 4, 10}
int maxVal = daySoHeap.back(); // Phần tử lớn nhất là 10
daySoHeap.pop_back(); // Xóa phần tử lớn nhất khỏi heap
std::cout << "Sau pop_heap (lấy 10): ";
for (int val : daySoHeap) {
    std::cout << val << " ";
}
std::cout << std::endl;

std::sort_heap(daySoHeap.begin(), daySoHeap.end()); // Sắp xếp heap thành dãy tăng dần: {1, 2, 4, 5, 7, 8}
std::cout << "Sau sort_heap: ";
for (int val : daySoHeap) {
    std::cout << val << " ";
}
std::cout << std::endl;

5. Các Thuật Toán Tìm Giá Trị Nhỏ Nhất/Lớn Nhất

5.1. Giá trị nhỏ nhất/lớn nhất: std::min và std::max

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

#include <algorithm>
#include <iostream>
#include <initializer_list> // Cho std::initializer_list

int so1 = 15, so2 = 7;
int giaTriMin = std::min(so1, so2); // 7
int giaTriMax = std::max(so1, so2); // 15
std::cout << "Min của 15 và 7: " << giaTriMin << std::endl;
std::cout << "Max của 15 và 7: " << giaTriMax << std::endl;

int minTrongList = std::min({12, 5, 20, 8, 3}); // 3
int maxTrongList = std::max({12, 5, 20, 8, 3}); // 20
std::cout << "Min trong danh sách: " << minTrongList << std::endl;
std::cout << "Max trong danh sách: " << maxTrongList << std::endl;

5.2. Phần tử nhỏ nhất/lớn nhất: std::min_element và std::max_element

Trả về iterator trỏ đến phần tử nhỏ nhất hoặc lớn nhất trong một phạm vi.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<double> nhietDo = {25.5, 22.1, 28.0, 23.9, 26.7};
auto itMin = std::min_element(nhietDo.begin(), nhietDo.end()); // Trỏ đến 22.1
auto itMax = std::max_element(nhietDo.begin(), nhietDo.end()); // Trỏ đến 28.0
std::cout << "Nhiệt độ thấp nhất: " << *itMin << std::endl;
std::cout << "Nhiệt độ cao nhất: " << *itMax << std::endl;

5.3. Cả nhỏ nhất và lớn nhất: std::minmax_element (C++11)

Trả về một cặp iterator (pair), trỏ đến phần tử nhỏ nhất và lớn nhất trong phạm vi.

#include <vector>
#include <algorithm>
#include <iostream>
#include <utility> // Cho std::pair

std::vector<int> cacDiem = {80, 65, 95, 70, 88};
auto capMinMax = std::minmax_element(cacDiem.begin(), cacDiem.end());
// capMinMax.first trỏ đến 65, capMinMax.second trỏ đến 95
std::cout << "Điểm thấp nhất: " << *capMinMax.first << std::endl;
std::cout << "Điểm cao nhất: " << *capMinMax.second << std::endl;

6. Các Thuật Toán Số Học (trong <numeric>)

Thư viện <numeric> cung cấp các thuật toán thực hiện các phép toán số học trên các phạm vi.

6.1. Tích lũy: std::accumulate

Tính tổng tích lũy của các phần tử trong một phạm vi, với một giá trị khởi tạo và một phép toán tùy chỉnh tùy chọn.

#include <vector>
#include <numeric> // Cho std::accumulate
#include <iostream>
#include <functional> // Cho std::multiplies

std::vector<int> daySoNguyen = {1, 2, 3, 4, 5};
int tong = std::accumulate(daySoNguyen.begin(), daySoNguyen.end(), 0); // Tính tổng, khởi tạo 0. Kết quả: 15
std::cout << "Tổng các số: " << tong << std::endl;

int tich = std::accumulate(daySoNguyen.begin(), daySoNguyen.end(), 1, std::multiplies<int>()); // Tính tích, khởi tạo 1. Kết quả: 120
std::cout << "Tích các số: " << tich << std::endl;

6.2. Tích vô hướng: std::inner_product

Tính tích vô hướng của hai phạm vi, hoặc một phép toán nhị phân tùy chỉnh.

#include <vector>
#include <numeric> // Cho std::inner_product
#include <iostream>

std::vector<int> vectorA = {1, 2, 3};
std::vector<int> vectorB = {4, 5, 6};
int tichVoHuong = std::inner_product(vectorA.begin(), vectorA.end(), vectorB.begin(), 0); // (1*4) + (2*5) + (3*6) = 4 + 10 + 18 = 32
std::cout << "Tích vô hướng: " << tichVoHuong << std::endl;

6.3. Điền giá trị tăng dần: std::iota (C++11)

Điền một phạm vi với các giá trị liên tiếp, bắt đầu từ một giá trị được chỉ định.

#include <vector>
#include <numeric> // Cho std::iota
#include <iostream>

std::vector<int> dayTuDong(7);
std::iota(dayTuDong.begin(), dayTuDong.end(), 100); // Điền từ 100, 101, ..., 106
std::cout << "Sau iota: ";
for (int val : dayTuDong) {
    std::cout << val << " ";
}
std::cout << std::endl;

6.4. Tổng tiền tố (Partial Sum): std::partial_sum

Tính tổng tiền tố (prefix sum) của một phạm vi và lưu kết quả vào một phạm vi đích.

#include <vector>
#include <numeric> // Cho std::partial_sum
#include <iostream>

std::vector<int> nguon = {1, 2, 3, 4, 5};
std::vector<int> dichTongPhan(nguon.size());
std::partial_sum(nguon.begin(), nguon.end(), dichTongPhan.begin()); // dichTongPhan: {1, 3, 6, 10, 15}
std::cout << "Tổng tiền tố: ";
for (int val : dichTongPhan) {
    std::cout << val << " ";
}
std::cout << std::endl;

6.5. Hiệu giữa các phần tử liền kề: std::adjacent_difference

Tính hiệu giữa các phần tử liền kề và lưu kết quả vào một phạm vi đích. Phần tử đầu tiên được sao chép nguyên trạng.

#include <vector>
#include <numeric> // Cho std::adjacent_difference
#include <iostream>

std::vector<int> dayGoc = {10, 11, 13, 16, 20};
std::vector<int> dayHieu(dayGoc.size());
std::adjacent_difference(dayGoc.begin(), dayGoc.end(), dayHieu.begin()); // dayHieu: {10, 1, 2, 3, 4}
std::cout << "Hiệu liền kề: ";
for (int val : dayHieu) {
    std::cout << val << " ";
}
std::cout << std::endl;

7. Các Thuật Toán Khác

7.1. Tạo phần tử theo hàm: std::generate

Điền một phạm vi với các giá trị được tạo ra bởi một hàm sinh (generator function).

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> dayDuLieu(5);
int bienDem = 10;
std::generate(dayDuLieu.begin(), dayDuLieu.end(), [&bienDem]() {
    return bienDem++;
}); // Điền với 10, 11, 12, 13, 14
std::cout << "Sau generate: ";
for (int val : dayDuLieu) {
    std::cout << val << " ";
}
std::cout << std::endl;

7.2. Tạo n phần tử theo hàm: std::generate_n

Điền n phần tử đầu tiên của một phạm vi với các giá trị được tạo ra bởi một hàm sinh.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> dayPartial(5, 99); // Khởi tạo với 5 phần tử giá trị 99
int index = 0;
// Điền 3 phần tử đầu tiên với 0, 1, 2
std::generate_n(dayPartial.begin(), 3, [&index]() {
    return index++;
}); // dayPartial: {0, 1, 2, 99, 99}
std::cout << "Sau generate_n: ";
for (int val : dayPartial) {
    std::cout << val << " ";
}
std::cout << std::endl;

7.3. Kiểm tra bao gồm: std::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 hay không.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> tapHopLon = {10, 20, 30, 40, 50};
std::vector<int> tapHopNho = {20, 40};
bool coBaoGomKhong = std::includes(tapHopLon.begin(), tapHopLon.end(), tapHopNho.begin(), tapHopNho.end()); // true
std::cout << "TapHopLon có bao gồm TapHopNho không? " << std::boolalpha << coBaoGomKhong << std::endl;

7.4. Các phép toán tập hợp: std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference

Thực hiện các phép toán hợp, giao, hiệu và hiệu đối xứng trên hai phạm vi đã được sắp xếp.

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator> // Cho std::back_inserter

std::vector<int> bo1 = {1, 2, 3, 4, 5};
std::vector<int> bo2 = {3, 4, 5, 6, 7};
std::vector<int> ketQuaTapHop;

// Hợp (Union)
std::set_union(bo1.begin(), bo1.end(), bo2.begin(), bo2.end(), std::back_inserter(ketQuaTapHop));
// ketQuaTapHop: {1, 2, 3, 4, 5, 6, 7}
std::cout << "Hợp: ";
for (int val : ketQuaTapHop) {
    std::cout << val << " ";
}
std::cout << std::endl;

// Giao (Intersection)
ketQuaTapHop.clear();
std::set_intersection(bo1.begin(), bo1.end(), bo2.begin(), bo2.end(), std::back_inserter(ketQuaTapHop));
// ketQuaTapHop: {3, 4, 5}
std::cout << "Giao: ";
for (int val : ketQuaTapHop) {
    std::cout << val << " ";
}
std::cout << std::endl;

// Hiệu (Difference) (bo1 - bo2)
ketQuaTapHop.clear();
std::set_difference(bo1.begin(), bo1.end(), bo2.begin(), bo2.end(), std::back_inserter(ketQuaTapHop));
// ketQuaTapHop: {1, 2}
std::cout << "Hiệu (bo1 - bo2): ";
for (int val : ketQuaTapHop) {
    std::cout << val << " ";
}
std::cout << std::endl;

// Hiệu đối xứng (Symmetric Difference)
ketQuaTapHop.clear();
std::set_symmetric_difference(bo1.begin(), bo1.end(), bo2.begin(), bo2.end(), std::back_inserter(ketQuaTapHop));
// ketQuaTapHop: {1, 2, 6, 7}
std::cout << "Hiệu đối xứng: ";
for (int val : ketQuaTapHop) {
    std::cout << val << " ";
}
std::cout << std::endl;

8. Các Câu Hỏi Thường Gặp

1. Sự khác biệt giữa std::sort và std::stable_sort là gì?

• std::sort là thuật toán không ổn định, nghĩa là nó không đảm bảo giữ nguyên thứ tự tương đối của các phần tử bằng nhau. Nó thường sử dụng introsort, có độ phức tạp thời gian trung bình O(n log n).
• std::stable_sort là thuật toán ổn định, đảm bảo rằng thứ tự tương đối của các phần tử bằng nhau được giữ nguyên. Nó thường sử dụng mergesort, cũng có độ phức tạp thời gian O(n log n) nhưng có thể yêu cầu thêm không gian bộ nhớ.

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

Thuật toán std::remove (và std::remove_if) thực hiện việc "xóa logic" các phần tử. Nó di chuyển tất cả các phần tử không bị xóa về phía đầu của container và trả về một iterator trỏ đến vị trí "kết thúc mới" của chuỗi hợp lệ. Tuy nhiên, nó không thay đổi kích thước vật lý của container. Để thực sự loại bỏ các phần tử và thu nhỏ container, bạn cần sử dụng phương thức erase của container với phạm vi từ iterator trả về bởi remove đến container.end().

3. Những thuật toán nào yêu cầu container phải được sắp xếp trước khi sử dụng?

Các thuật toán liên quan đến tìm kiếm nhị phân như std::binary_search, std::lower_bound, std::upper_bound, cũng như các thuật toán tập hợp như std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference và std::merge, đều yêu cầu các phạm vi đầu vào phải được sắp xếp. Điều này là do chúng dựa vào tính chất có thứ tự của dữ liệu để đạt được hiệu suất cao (ví dụ, O(log n) cho tìm kiếm nhị phân).