1、Thuật Toán Không Sửa Đổi Dãy

Những 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 value và 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 đ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.

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

// Tìm phần tử có giá trị là 5
auto it = find(numbers.begin(), numbers.end(), 5);
if (it != numbers.end()) {
    cout << "tìm thấy: " << *it << endl;  // Xuất ra: 5
}

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

// Tìm dãy con
vector<int> sub = {3, 5};
auto it3 = find_end(numbers.begin(), numbers.end(), sub.begin(), sub.end());
if (it3 != numbers.end()) {
    cout << "dãy con bắt đầu tại chỉ mục: " << it3 - numbers.begin() << endl;  // Xuất ra: 1
}

1.2 count và count_if

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

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

1.3 for_each

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

std::vector<int> vec = {1, 2, 3, 4, 5};
std::for_each(vec.begin(), vec.end(), [](int& x) { 
    x *= 2; // Nhân mỗi phần tử với 2
});
// Bây giờ vec trở thành {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)) có giống nhau không.
• mismatch(b1, e1, b2)：Trả về cặp iterator của phần tử đầu tiên không trùng nhau trong 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 ba phần tử đầu tiên của a và b
bool is_equal = equal(a.begin(), a.end(), b.begin());
cout << "a == b? " << boolalpha << is_equal << endl;  // Xuất ra: false

// Tìm phần tử đầu tiên không khớp giữa a và c
auto mis = mismatch(a.begin(), a.end(), c.begin());
if (mis.first != a.end()) {
    cout << "không khớp: " << *mis.first << " vs " << *mis.second << endl;  // Không xuất gì (ba phần tử đầu tiên của a và c giống nhau)
}

1.5 all_of, any_of, none_of

Kiểm tra các phần tử trong phạm vi có thỏa mãn điều kiện không

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

2、Thuật Toán Thay Đổi Dãy

Những thuật toán này sửa đổi nội dung của container mà chúng xử lý.

2.1 copy và copy_if

• copy(begin, end, dest)：Sao chép phần tử từ [begin, end) vào vị trí bắt đầu từ 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.

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

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

// Sao chép phần tử chẵn vào container mới
vector<int> evens;
copy_if(source.begin(), source.end(), back_inserter(evens), [](int x) {
    return x % 2 == 0;
});  // evens: [2,4]

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

2.2 transform

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

vector<int> nums = {1, 2, 3};
vector<int> squares(3);

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

// Cộng hai container (chuyển đổi đôi tham số)
vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
vector<int> sum(3);
transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y) {
    return x + y;
});  // sum: [5,7,9]

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ế 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 làm thay đổi container gốc).

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

// Thay thế tất cả 2 thành 20
replace(nums.begin(), nums.end(), 2, 20);  // nums: [1,20,3,20,5]

// Thay thế phần tử lớn hơn 10 thành 0
replace_if(nums.begin(), nums.end(), [](int x) {
    return x > 10;
}, 0);  // nums: [1,0,3,0,5]

// Sao chép và thay thế 3 thành 300 (container gốc không đổi)
vector<int> res;
replace_copy(nums.begin(), nums.end(), back_inserter(res), 3, 300);  // res: [1,0,300,0,5]

2.4 remove, remove_if và erase

• remove(begin, end, value)：Di chuyển các phần tử bằng value đến cuối container, trả về iterator cuối logic (không xóa thực tế, cần dùng erase).
• remove_if(begin, end, predicate)：Di chuyển các phần tử thỏa mãn điều kiện đến cuối.

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

// Xóa logic tất cả 2 (di chuyển về cuối)
auto new_end = remove(nums.begin(), nums.end(), 2);  // nums: [1,3,4,2,2]

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

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

2.5 unique

Loại bỏ các phần tử trùng lặp liên tiếp trong phạm vi, trả về iterator cuối logic. Thường 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ự 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 sao 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

Ngẫu nhiên sắp xếp lại các phần tử trong phạm vi (yêu cầu 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); // Trộn ngẫu nhiên các phần tử trong vec

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

3.1 sort, stable_sort và partial_sort

• sort(begin, end)：Sắp xếp nhanh (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 (thứ tự tương đối của phần tử bằng nhau không đổi).
• partial_sort(begin, mid, end)：Sắp xếp một phần, đưa [begin, mid) về các phần tử nhỏ nhất trong toàn bộ phạm vi.

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

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

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

3.2 nth_element

Sắp xếp lại phạm vi để phần tử tại vị trí chỉ định là phần tử nhỏ nhất trong dãy đã sắp xếp, các phần tử bên trái nhỏ hơn hoặc bằng, bên phải lớn hơn hoặc bằng

std::vector<int> vec = {5, 3, 1, 4, 2, 6};
// Tìm phần tử thứ ba nhỏ nhất (chỉ mục 2)
std::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, bên phải >= 3

3.3 binary_search, lower_bound, upper_bound

Phải được sử dụng trên 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.

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

// Kiểm tra xem 3 có tồn tại không
bool exists = binary_search(sorted.begin(), sorted.end(), 3);  // true

// Tìm phần tử đầu tiên >= 3
auto lb = lower_bound(sorted.begin(), sorted.end(), 3);
cout << "chỉ mục lower_bound: " << lb - sorted.begin() << endl;  // Xuất ra: 1

// Tìm phần tử đầu tiên > 3
auto ub = upper_bound(sorted.begin(), sorted.end(), 3);
cout << "chỉ mục upper_bound: " << ub - sorted.begin() << endl;  // Xuất ra: 3

3.4 merge

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

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

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

4、Thuật Toán Heap

STL cung cấp các thuật toán để xử lý phạm vi như heap, bao gồm make_heap, push_heap, pop_heap, sort_heap.

std::vector<int> vec = {4, 1, 3, 2, 5};
std::make_heap(vec.begin(), vec.end()); // Tạo heap tối đa, 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 max_val = vec.back(); // Lấy giá trị lớn nhất 6
vec.pop_back(); // Loại bỏ phần tử lớn nhất

std::sort_heap(vec.begin(), vec.end()); // Sắp xếp heap thành chuỗi 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

int a = 5, b = 3;
int min_val = std::min(a, b); // 3
int max_val = std::max(a, b); // 5

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

std::vector<int> vec = {3, 1, 4, 2, 5};
auto min_it = std::min_element(vec.begin(), vec.end()); // Trỏ tới 1
auto max_it = std::max_element(vec.begin(), vec.end()); // Trỏ tới 5

5.3 minmax_element (C++11)

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

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

6、Thuật Toán Số Học (trong <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>

std::vector<int> vec = {1, 2, 3, 4, 5};
int sum = std::accumulate(vec.begin(), vec.end(), 0); // Tổng, giá trị ban đầu là 0, kết quả là 15
int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>()); // Tích, giá trị ban đầu 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)

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

6.3 iota

Điền vào phạm vi với các giá trị tăng dần liên tục

std::vector<int> vec(5);
std::iota(vec.begin(), vec.end(), 10); // Điền thành 10, 11, 12, 13, 14

6.4 partial_sum

Tính tổng từng phần, lưu kết quả vào phạm vi đích

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(src.size());
std::partial_sum(src.begin(), src.end(), dst.begin()); // dst 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

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

7、Khác

7.1 generate

Điền vào phạm vi bằng hàm tạo

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

7.2 generate_n

Điền vào n phần tử đầu tiên trong phạm vi bằng 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 giữ nguyên

7.3 includes

Kiểm tra một phạm vi đã sắp xếp có chứa tất cả phần tử của phạm vi khác không

std::vector<int> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2 = {2, 4};
bool includes = 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 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> result;

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

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

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

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

8、Vấn Đề Thường Gặp

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

• sort sử dụng thuật toán sắp xếp nhanh (thực tế là introsort), không ổn định (thứ tự tương đối của 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 thuật toán sắp xếp trộn, ổn định (thứ tự tương đối của phần tử bằng nhau không đổi), độ phức tạp O(n log n), nhưng tiêu tốn thêm không gian.

2. Tại sao thuật toán remove cần kết hợp với erase? Nguyên tắc của remove là "ghi đè" phần tử cần xóa, di chuyển các phần tử còn lại về phía trước, trả về iterator cuối logic, nhưng không thay đổi kích thước thực tế của container. erase sẽ thực sự xóa phần tử bằng cách sử dụng iterator, thay đổi kích thước container. Vì vậy cần kết hợp: container.erase(remove(...), container.end()).
3. Những thuật toán nào yêu cầu container đã được sắp xếp? Các thuật toán tìm kiếm nhị phân (binary_search, lower_bound, upper_bound), thuật toán tập hợp (set_intersection, set_union, v.v.), merge, v.v., những thuật toán này phụ thuộc vào tính sắp xếp để hoạt động hiệu quả (ví dụ như tìm kiếm nhị phân O(log n)).