1. Thuật toán không thay đổi cấu trúc dãy

Các thuật toán trong nhóm này duyệt qua dữ liệu mà không làm thay đổi thứ tự hay giá trị của các phần tử trong container.

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

• find(begin, end, value): Trả về con trỏ lặp đến lần xuất hiện đầu tiên của value, nếu không thấy thì trả về end.
• find_if(begin, end, pred): Tìm phần tử đầu tiên thỏa mãn điều kiện hàm vị từ pred.
• find_end(begin, end, sub_begin, sub_end): Xác định vị trí cuối cùng xuất hiện một dãy con.

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

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

// Tìm giá trị 5
auto pos = std::find(data.begin(), data.end(), 5);
if (pos != data.end()) {
    std::cout << "Tìm thấy: " << *pos << "\n"; // In ra: 5
}

// Tìm số đầu tiên lớn hơn 6
auto large = std::find_if(data.begin(), data.end(), [](int x) {
    return x > 6;
});
std::cout << "Số đầu tiên >6: " << *large << "\n"; // In ra: 7

// Tìm dãy con {3, 5}
std::vector<int> subseq = {3, 5};
auto match = std::find_end(data.begin(), data.end(), subseq.begin(), subseq.end());
if (match != data.end()) {
    std::cout << "Dãy con bắt đầu tại: " << match - data.begin() << "\n"; // Vị trí 1
}

1.2 Đếm phần tử – count và count_if

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

std::vector<int> values = {1, 2, 3, 2, 4, 2};
int count_2 = std::count(values.begin(), values.end(), 2); // Kết quả: 3
int even_count = std::count_if(values.begin(), values.end(), [](int n) {
    return n % 2 == 0;
}); // Số chẵn: 4

1.3 Duyệt từng phần tử – for_each

Áp dụng một hành động lên từng phần tử trong khoảng.

std::vector<int> arr = {1, 2, 3, 4, 5};
std::for_each(arr.begin(), arr.end(), [](int& item) {
    item *= 2;
});
// arr trở thành: {2, 4, 6, 8, 10}

1.4 So sánh dãy – equal và mismatch

• equal(b1, e1, b2): Kiểm tra hai dãy có giống nhau từ b1 đến e1 và tương ứng từ b2 không.
• mismatch(b1, e1, b2): Trả về cặp con trỏ đến vị trí đầu tiên khác nhau.

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

bool same = std::equal(a.begin(), a.end(), b.begin());
std::cout << "a == b? " << std::boolalpha << same << "\n"; // false

auto diff = std::mismatch(a.begin(), a.end(), c.begin());
if (diff.first != a.end()) {
    std::cout << "Khác biệt: " << *(diff.first) << " vs " << *(diff.second) << "\n";
} // Không in gì vì 3 phần tử đầu giống nhau

1.5 Kiểm tra điều kiện hàng loạt – all_of, any_of, none_of

Dùng để xác minh tính chất trên toàn bộ tập hợp.

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

2. Thuật toán thay đổi dãy

Nhóm này thực hiện thao tác trực tiếp lên dữ liệu: sao chép, biến đổi, sắp xếp lại.

2.1 Sao chép chọn lọc – copy và copy_if

• copy(src_begin, src_end, dest): Chép toàn bộ dãy.
• copy_if(src_begin, src_end, dest, pred): Chỉ chép những phần tử thỏa mãn.

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> target(5);
std::copy(source.begin(), source.end(), target.begin()); // target = [1,2,3,4,5]

std::vector<int> evens;
std::copy_if(source.begin(), source.end(), std::back_inserter(evens), [](int x) {
    return x % 2 == 0;
}); // evens = [2,4]

Lưu ý: back_inserter cho phép vector tự mở rộng khi thêm phần tử.

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

Chuyển đổi mỗi phần tử theo một hàm, có thể dùng một hoặc hai dãy đầu vào.

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

// Bình phương từng phần tử
std::transform(input.begin(), input.end(), output.begin(), [](int x) {
    return x * x;
}); // output = [1,4,9]

// Cộng song song hai dãy
std::vector<int> a = {1, 2, 3}, b = {4, 5, 6}, sum(3);
std::transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y) {
    return x + y;
}); // sum = [5,7,9]

2.3 Thay thế giá trị – replace, replace_if, replace_copy

• replace(..., old_val, new_val): Đổi tất cả old_val thành new_val.
• replace_if(..., pred, new_val): Đổi những phần tử thỏa mãn điều kiện.
• replace_copy: Tạo bản sao đã thay thế, giữ nguyên dãy gốc.

std::vector<int> seq = {1, 2, 3, 2, 5};
std::replace(seq.begin(), seq.end(), 2, 20); // seq = [1,20,3,20,5]

std::replace_if(seq.begin(), seq.end(), [](int x) { return x > 10; }, 0); // [1,0,3,0,5]

std::vector<int> result;
std::replace_copy(seq.begin(), seq.end(), std::back_inserter(result), 3, 300); // result = [1,0,300,0,5]

2.4 Xóa phần tử – remove và erase

Thuật toán remove chỉ dồn các phần tử cần giữ lên đầu, còn erase mới thực sự thu nhỏ container.

std::vector<int> list = {1, 2, 3, 2, 4};
auto new_end = std::remove(list.begin(), list.end(), 2); // Dồn phần tử khác 2 lên đầu
list.erase(new_end, list.end()); // Xóa thật sự phần dư → list = [1,3,4]

// Xóa số chẵn
list = {1, 2, 3, 4, 5};
list.erase(std::remove_if(list.begin(), list.end(), [](int x) { return x % 2 == 0; }), list.end());
// list = [1,3,5]

2.5 Loại bỏ trùng liên tiếp – unique

Chỉ loại bỏ các phần tử giống nhau đứng kề nhau. Cần sắp xếp trước nếu muốn loại bỏ mọi bản sao.

std::vector<int> data = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto it = std::unique(data.begin(), data.end());
data.erase(it, data.end()); // data = [1,2,3,4,5]

2.6 Đảo ngược và xoay vòng

• reverse(begin, end): Đảo ngược thứ tự.
• rotate(begin, mid, end): Xoay sao cho phần tử tại mid trở thành đầu.

std::vector<int> v = {1, 2, 3, 4, 5};
std::reverse(v.begin(), v.end()); // v = [5,4,3,2,1]
std::rotate(v.begin(), v.begin() + 2, v.end()); // v = [3,4,5,1,2] (xoay từ vị trí 2)

2.7 Xáo ngẫu nhiên – shuffle

Sắp xếp lại các phần tử theo thứ tự ngẫu nhiên.

#include <random>
std::vector<int> items = {1, 2, 3, 4, 5};
std::shuffle(items.begin(), items.end(), std::mt19937{std::random_device{}()});

3. Sắp xếp và tìm kiếm nhị phân

3.1 sort, stable_sort, partial_sort

• sort: Sắp nhanh, hiệu suất cao nhưng không ổn định.
• stable_sort: Giữ thứ tự tương đối của phần tử bằng nhau.
• partial_sort: Sắp một đoạn đầu với các phần tử nhỏ nhất.

std::vector<int> vec = {5, 3, 1, 4, 2};
std::sort(vec.begin(), vec.end()); // [1,2,3,4,5]

std::vector<std::pair<int, int>> pairs = {{1,2},{2,1},{1,1},{2,2}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
    return a.first < b.first;
});

std::partial_sort(vec.begin(), vec.begin() + 3, vec.end()); // 3 phần tử nhỏ nhất ở đầu

3.2 nth_element

Đưa phần tử thứ n về đúng vị trí như khi sắp xếp, chia mảng thành hai phần: bên trái ≤ nó, bên phải ≥ nó.

std::vector<int> v = {5, 3, 1, 4, 2, 6};
std::nth_element(v.begin(), v.begin() + 2, v.end()); // v[2] là phần tử nhỏ thứ 3 (giá trị 3)

3.3 Tìm kiếm nhị phân

Các hàm sau yêu cầu dãy đã được sắp xếp:

• binary_search(begin, end, val): Kiểm tra sự tồn tại.
• lower_bound(begin, end, val): Trả về vị trí đầu tiên ≥ val.
• upper_bound(begin, end, val): Trả về vị trí đầu tiên > val.

std::vector<int> sorted = {1, 3, 3, 5, 7};
bool found = std::binary_search(sorted.begin(), sorted.end(), 3); // true
auto low = std::lower_bound(sorted.begin(), sorted.end(), 3);     // chỉ đến index 1
auto high = std::upper_bound(sorted.begin(), sorted.end(), 3);    // chỉ đến index 3

3.4 merge – Trộn hai dãy đã sắp

Kết hợp hai dãy đã sắp thành một dãy mới vẫn duy trì thứ tự.

std::vector<int> A = {1, 3, 5}, B = {2, 4, 6};
std::vector<int> merged(A.size() + B.size());
std::merge(A.begin(), A.end(), B.begin(), B.end(), merged.begin());
// merged = [1,2,3,4,5,6]

4. Cấu trúc đống (heap)

STL hỗ trợ thao tác trên vùng nhớ như một đống nhị phân.

std::vector<int> heap_data = {4, 1, 3, 2, 5};
std::make_heap(heap_data.begin(), heap_data.end()); // Xây max-heap

heap_data.push_back(6);
std::push_heap(heap_data.begin(), heap_data.end()); // Đưa 6 vào heap

std::pop_heap(heap_data.begin(), heap_data.end()); // Đưa phần tử lớn nhất ra cuối
int top = heap_data.back();
heap_data.pop_back();

std::sort_heap(heap_data.begin(), heap_data.end()); // Sắp xếp toàn bộ theo heap

5. Tìm cực trị

• min(a, b), max(a, b): Giá trị nhỏ/lớn hơn giữa hai số.
• min_element(begin, end), max_element(begin, end): Trả về con trỏ lặp đến phần tử nhỏ/nhỏ nhất.
• minmax_element: Trả về cả hai cùng lúc.

std::vector<int> vals = {3, 1, 4, 2, 5};
auto min_it = std::min_element(vals.begin(), vals.end()); // → 1
auto max_it = std::max_element(vals.begin(), vals.end()); // → 5
auto mm = std::minmax_element(vals.begin(), vals.end()); // first→1, second→5

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

6.1 accumulate – Tổng hóa dãy

Tính tổng hoặc tích tùy theo toán tử.

#include <numeric>
std::vector<int> series = {1, 2, 3, 4, 5};
int total = std::accumulate(series.begin(), series.end(), 0); // 15
int product = std::accumulate(series.begin(), series.end(), 1, std::multiplies<int>{}); // 120

6.2 inner_product – Tích vô hướng

std::vector<int> u = {1, 2, 3}, v = {4, 5, 6};
int dot_product = std::inner_product(u.begin(), u.end(), v.begin(), 0); // 32

6.3 iota – Gán giá trị tăng dần

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

6.4 partial_sum và adjacent_difference

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> psum(src.size()), diff(src.size());
std::partial_sum(src.begin(), src.end(), psum.begin());       // [1,3,6,10,15]
std::adjacent_difference(src.begin(), src.end(), diff.begin()); // [1,1,1,1,1]

7. Các hàm tiện ích khác

7.1 generate và generate_n

Dùng hàm sinh để điền dữ liệu.

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

std::generate_n(vec.begin(), 3, [&counter]() { return counter++; }); // 3 phần tử đầu: [5,6,7]

7.2 includes – Kiểm tra tập con

Kiểm tra một dãy đã sắp có chứa toàn bộ phần tử của dãy đã sắp khác không.

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

7.3 Các phép toán tập hợp

std::vector<int> A = {1,2,3,4,5}, B = {3,4,5,6,7}, res;

std::set_union(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(res));        // [1..7]
res.clear();
std::set_intersection(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(res)); // [3,4,5]
res.clear();
std::set_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(res));   // [1,2]
res.clear();
std::set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(res)); // [1,2,6,7]

8. Một số lưu ý quan trọng

• sort vs stable_sort: sort nhanh hơn nhưng không bảo toàn thứ tự tương đối của phần tử bằng nhau; stable_sort chậm hơn chút do dùng thêm bộ nhớ.
• remove cần erase: Vì remove chỉ dồn dữ liệu, còn erase mới thay đổi kích thước thật sự.
• Yêu cầu sắp xếp: Các hàm như binary_search, lower_bound, merge, và các phép toán tập hợp đều yêu cầu dãy đầu vào phải đã được sắp thứ tự.