Thư viện chuẩn C++ (STL) cung cấp một bộ sưu tập phong phú các thuật toán hiệu quả để thao tác trên các dãy dữ liệu. Các thuật toán này được định nghĩa trong các header như <algorithm> và <numeric>, mang lại sự linh hoạt và hiệu suất tối ưu.

1. Thuật toán trên dãy không thay đổi

Các thuật toán này thực hiện các thao tác mà không làm thay đổi nội dung của dãy nguồn.

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

• find(begin, end, value): Trả về một iterator tới phần tử đầu tiên có giá trị bằng value. Nếu không tìm thấy, trả về end.
• find_if(begin, end, predicate): Trả về iterator tới phần tử đầu tiên thỏa mãn điều kiện của predicate (một hàm hoặc lambda).
• find_end(begin, end, sub_begin, sub_end): Tìm vị trí xuất hiện cuối cùng của một dãy con (subsequence) trong dãy nguồn.

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

std::vector<int> data = {10, 30, 50, 70, 90};

// Tìm phần tử có giá trị 50
auto it_find = std::find(data.begin(), data.end(), 50);
if (it_find != data.end()) {
    std::cout << "Found: " << *it_find << std::endl; // Xuất: Found: 50
}

// Tìm phần tử đầu tiên lớn hơn 60
auto it_find_if = std::find_if(data.begin(), data.end(), [](int x) {
    return x > 60;
});
if (it_find_if != data.end()) {
    std::cout << "First element > 60: " << *it_find_if << std::endl; // Xuất: First element > 60: 70
}

// Tìm dãy con
std::vector<int> sub = {30, 50};
auto it_find_end = std::find_end(data.begin(), data.end(), sub.begin(), sub.end());
if (it_find_end != data.end()) {
    std::cout << "Subsequence ends at index: " << (it_find_end - data.begin()) << std::endl; // Xuất: Subsequence ends at index: 2
}

1.2 Đếm: count, count_if

• count(begin, end, value): Đếm số lần xuất hiện của value trong dãy.
• count_if(begin, end, predicate): Đếm số phần tử thỏa mãn điều kiện của predicate.

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

std::vector<int> numbers = {1, 2, 3, 2, 4, 2, 5};
int count_twos = std::count(numbers.begin(), numbers.end(), 2); // Kết quả: 3
int count_odds = std::count_if(numbers.begin(), numbers.end(), [](int x) {
    return x % 2 != 0;
}); // Kết quả: 4

1.3 Lặp và áp dụng hàm: for_each

Áp dụng một hàm (hoặc lambda) cho từng phần tử trong một phạm vi.

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

std::vector<int> values = {1, 2, 3, 4, 5};
std::for_each(values.begin(), values.end(), [](int& val) {
    val *= 10; // Nhân mỗi phần tử với 10
});
// values bây giờ là {10, 20, 30, 40, 50}

1.4 So sánh dãy: equal, mismatch

• equal(b1, e1, b2): Kiểm tra xem hai dãy [b1, e1) và [b2, b2 + (e1 - b1)) có bằng nhau hay không.
• mismatch(b1, e1, b2): Trả về một cặp iterator trỏ tới các phần tử khác nhau đầu tiên của hai dãy.

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

std::vector<int> arr1 = {1, 2, 3};
std::vector<int> arr2 = {1, 2, 4};
std::vector<int> arr3 = {1, 2, 3, 99};

bool are_equal = std::equal(arr1.begin(), arr1.end(), arr2.begin()); // false
auto diff_pair = std::mismatch(arr1.begin(), arr1.end(), arr3.begin());
if (diff_pair.first != arr1.end()) {
    // Không có khác biệt trong phạm vi của arr1
}

1.5 Kiểm tra điều kiện toàn bộ/một phần: all_of, any_of, none_of

• all_of(begin, end, predicate): Trả về true nếu tất cả các phần tử thỏa mãn predicate.
• any_of(begin, end, predicate): Trả về true nếu có ít nhất một phần tử thỏa mãn predicate.
• none_of(begin, end, predicate): Trả về true nếu không có phần tử nào thỏa mãn predicate.

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

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

2. Thuật toán trên dãy có thay đổi

Các thuật toán này thực hiện các thao tác và có thể thay đổi nội dung của dãy nguồn hoặc ghi vào một dãy đích.

2.1 Sao chép: copy, copy_if

• copy(begin, end, dest): Sao chép các phần tử từ [begin, end) tới vị trí bắt đầu bởi dest.
• copy_if(begin, end, dest, predicate): Chỉ sao chép các phần tử thỏa mãn predicate.

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator> // cho back_inserter

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(source.size());

// Sao chép toàn bộ
std::copy(source.begin(), source.end(), destination.begin());
// destination là {1, 2, 3, 4, 5}

std::vector<int> even_numbers;
// Sao chép các số chẵn bằng back_inserter
std::copy_if(source.begin(), source.end(), std::back_inserter(even_numbers), [](int x){
    return x % 2 == 0;
});
// even_numbers là {2, 4}

2.2 Biến đổi: transform

Áp dụng một hàm cho từng phần tử (hoặc cặp phần tử từ hai dãy) và lưu kết quả vào một dãy đích.

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

std::vector<int> original = {1, 2, 3};
std::vector<int> squared(original.size());
std::vector<int> other = {4, 5, 6};
std::vector<int> summed(original.size());

// Biến đổi một dãy (tính bình phương)
std::transform(original.begin(), original.end(), squared.begin(), [](int x){
    return x * x;
});
// squared là {1, 4, 9}

// Biến đổi hai dãy (cộng tương ứng)
std::transform(original.begin(), original.end(), other.begin(), summed.begin(), [](int a, int b){
    return a + b;
});
// summed là {5, 7, 9}

2.3 Thay thế: replace, replace_if, replace_copy

• replace(begin, end, old_val, new_val): Thay thế tất cả các phần tử có giá trị old_val bằng new_val.
• replace_if(begin, end, predicate, new_val): Thay thế các phần tử thỏa mãn predicate bằng new_val.
• replace_copy(begin, end, dest, old_val, new_val): Sao chép các phần tử, đồng thời thực hiện thay thế (không làm thay đổi dãy nguồn).

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

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

// Thay thế tất cả 2 bằng 20
std::replace(data_replace.begin(), data_replace.end(), 2, 20);
// data_replace là {1, 20, 3, 20, 5}

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

std::vector<int> copied_replaced;
// Sao chép và thay thế 3 bằng 300
std::replace_copy(data_replace.begin(), data_replace.end(), std::back_inserter(copied_replaced), 3, 300);
// copied_replaced là {1, 0, 300, 0, 5}

2.4 Xóa logic: remove, remove_if

Các thuật toán này di chuyển các phần tử KHÔNG bị xóa về đầu dãy và trả về một iterator tới vị trí "logic" kết thúc của dãy đã được lọc. Chúng KHÔNG thay đổi kích thước thực tế của container. Cần kết hợp với erase để xóa vật lý.

• remove(begin, end, value): Di chuyển các phần tử KHÔNG bằng value về đầu dãy.
• remove_if(begin, end, predicate): Di chuyển các phần tử KHÔNG thỏa mãn predicate về đầu dãy.

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

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

// Loại bỏ logic các phần tử có giá trị 2
auto new_end_remove = std::remove(data_remove.begin(), data_remove.end(), 2);
// data_remove bây giờ có thể trông giống {1, 3, 4, ?, ?, ?}
// new_end_remove trỏ tới vị trí sau phần tử 4

// Xóa vật lý các phần tử không mong muốn
data_remove.erase(new_end_remove, data_remove.end());
// data_remove cuối cùng là {1, 3, 4}

// Kết hợp remove_if và erase để loại bỏ các số chẵn
std::vector<int> data_remove_if = {1, 2, 3, 4, 5, 6};
data_remove_if.erase(std::remove_if(data_remove_if.begin(), data_remove_if.end(), [](int x){
    return x % 2 == 0;
}), data_remove_if.end());
// data_remove_if cuối cùng là {1, 3, 5}

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

Loại bỏ các phần tử trùng lặp LIÊN TIẾP trong một dãy đã được sắp xếp. Tương tự remove, cần kết hợp với erase.

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

std::vector<int> data_unique = {1, 1, 2, 3, 3, 3, 4, 4};
// Dữ liệu phải được sắp xếp để unique hoạt động hiệu quả với tất cả các phần tử trùng lặp
// std::sort(data_unique.begin(), data_unique.end()); // Nếu chưa sắp xếp

auto last_unique = std::unique(data_unique.begin(), data_unique.end());
data_unique.erase(last_unique, data_unique.end());
// data_unique cuối cùng là {1, 2, 3, 4}

2.6 Đảo ngược: reverse

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

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

std::vector<int> data_reverse = {1, 2, 3, 4, 5};
std::reverse(data_reverse.begin(), data_reverse.end());
// data_reverse là {5, 4, 3, 2, 1}

2.7 Xoay vòng: rotate

Xoay các phần tử sao cho phần tử tại một vị trí nhất định trở thành phần tử đầu tiên.

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

std::vector<int> data_rotate = {1, 2, 3, 4, 5};
// Xoay sao cho phần tử thứ 3 (giá trị 3) là phần tử đầu tiên
std::rotate(data_rotate.begin(), data_rotate.begin() + 2, data_rotate.end());
// data_rotate là {3, 4, 5, 1, 2}

2.8 Tráo trộn: shuffle (C++11 trở lên)

Hoán vị ngẫu nhiên các phần tử trong một phạm vi.

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

std::vector<int> data_shuffle = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 generator(rd()); // Sử dụng Mersenne Twister engine

std::shuffle(data_shuffle.begin(), data_shuffle.end(), generator);
// data_shuffle chứa các phần tử được xáo trộn ngẫu nhiên

3. Thuật toán sắp xếp và liên quan

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

• sort(begin, end): Sắp xếp dãy theo thứ tự mặc định (thường là tăng dần). Không đảm bảo thứ tự tương đối của các phần tử bằng nhau.
• stable_sort(begin, end): Sắp xếp ổn định, giữ nguyên thứ tự tương đối của các phần tử bằng nhau.
• partial_sort(begin, mid, end): Sắp xếp một phần của dãy, đảm bảo rằng các phần tử trong phạm vi [begin, mid) là các phần tử nhỏ nhất trong toàn bộ dãy và chúng được sắp xếp.

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

std::vector<int> data_sort = {5, 3, 1, 4, 2};
std::sort(data_sort.begin(), data_sort.end()); // Sắp xếp tăng dần: {1, 2, 3, 4, 5}
std::sort(data_sort.begin(), data_sort.end(), std::greater<int>()); // Sắp xếp giảm dần: {5, 4, 3, 2, 1}

std::vector<std::pair<int, char>> data_stable = {{2, 'b'}, {1, 'a'}, {2, 'c'}, {1, 'd'}};
// Sắp xếp ổn định theo first element
std::stable_sort(data_stable.begin(), data_stable.end(), [](const auto& p1, const auto& p2){
    return p1.first < p2.first;
});
// data_stable: {{1, 'a'}, {1, 'd'}, {2, 'b'}, {2, 'c'}}

std::vector<int> data_partial = {9, 3, 7, 1, 5, 2, 8, 4, 6};
// Sắp xếp 3 phần tử nhỏ nhất vào đầu
std::partial_sort(data_partial.begin(), data_partial.begin() + 3, data_partial.end());
// data_partial có thể là {1, 2, 3, 9, 5, 7, 8, 4, 6} (3 phần tử đầu tiên đã sắp xếp)

3.2 Định vị phần tử thứ N: nth_element

Sắp xếp lại dãy sao cho phần tử tại vị trí nth là phần tử sẽ đứng ở vị trí đó nếu toàn bộ dãy được sắp xếp. Các phần tử trước nth nhỏ hơn hoặc bằng nó, các phần tử sau lớn hơn hoặc bằng nó.

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

std::vector<int> data_nth = {5, 3, 1, 4, 2, 6};
// Tìm phần tử thứ 3 (chỉ số 2) trong dãy đã sắp xếp
std::nth_element(data_nth.begin(), data_nth.begin() + 2, data_nth.end());
// data_nth[2] sẽ là 3. Các phần tử trước nó <= 3, sau nó >= 3.
// Ví dụ: {1, 2, 3, 6, 5, 4}

3.3 Tìm kiếm nhị phân (trên dãy đã sắp xếp): binary_search, lower_bound, upper_bound

Các thuật toán này yêu cầu dãy nguồn phải được sắp xếp.

• binary_search(begin, end, value): Kiểm tra xem value có tồn tại trong dãy hay không (trả về bool).
• lower_bound(begin, end, value): Trả về iterator tới phần tử đầu tiên không nhỏ hơn value (>=).
• upper_bound(begin, end, value): Trả về iterator tới phần tử đầu tiên lớn hơn value (>).

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

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

bool found = std::binary_search(sorted_data.begin(), sorted_data.end(), 3); // true

auto lb = std::lower_bound(sorted_data.begin(), sorted_data.end(), 3);
// lb trỏ tới phần tử 3 đầu tiên (chỉ số 1)

auto ub = std::upper_bound(sorted_data.begin(), sorted_data.end(), 3);
// ub trỏ tới phần tử 5 (chỉ số 3)

3.4 Trộn hai dãy đã sắp xếp: merge

Trộn hai dãy đã sắp xếp thành một dãy đích mới, giữ nguyên tính sắp xếp.

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

std::vector<int> list1 = {1, 3, 5};
std::vector<int> list2 = {2, 4, 6};
std::vector<int> merged_list(list1.size() + list2.size());

std::merge(list1.begin(), list1.end(), list2.begin(), list2.end(), merged_list.begin());
// merged_list là {1, 2, 3, 4, 5, 6}

4. Thuật toán Heap

STL cung cấp các hàm để thao tác trên cấu trúc dữ liệu heap (thường là max-heap theo mặc định).

• make_heap: Biến đổi một phạm vi thành một heap.
• push_heap: Thêm một phần tử vào heap.
• pop_heap: Di chuyển phần tử lớn nhất (root) ra cuối phạm vi và sắp xếp lại phần còn lại thành heap.
• sort_heap: Sắp xếp heap thành một dãy được sắp xếp.

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

std::vector<int> data_heap = {4, 1, 3, 2, 5};
std::make_heap(data_heap.begin(), data_heap.end());
// data_heap là {5, 4, 3, 2, 1} (cấu trúc max-heap)

data_heap.push_back(6);
std::push_heap(data_heap.begin(), data_heap.end());
// data_heap sau khi thêm 6 và push_heap: {6, 4, 5, 2, 1, 3}

std::pop_heap(data_heap.begin(), data_heap.end());
// Phần tử lớn nhất (6) được chuyển ra cuối: {5, 4, 3, 2, 1, 6}
int max_val = data_heap.back(); // max_val = 6
data_heap.pop_back(); // Loại bỏ 6

std::sort_heap(data_heap.begin(), data_heap.end());
// data_heap được sắp xếp: {1, 2, 3, 4, 5}

5. Thuật toán Tìm giá trị Cực tiểu/Cực đại

5.1 min, max

Trả về giá trị nhỏ nhất hoặc lớn nhất giữa hai hoặc nhiều giá trị.

#include <algorithm>
#include <initializer_list>

int val1 = 5, val2 = 3;
int minimum = std::min(val1, val2); // 3
int maximum = std::max(val1, val2); // 5

int min_from_list = std::min({4, 2, 8, 1, 5}); // 1
int max_from_list = std::max({4, 2, 8, 1, 5}); // 8

5.2 min_element, max_element

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

#include <vector>
#include <algorithm>

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

5.3 minmax_element (C++11 trở lên)

Trả về một cặp iterator, một trỏ tới phần tử nhỏ nhất và một trỏ tới phần tử lớn nhất.

#include <vector>
#include <algorithm>

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

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

6.1 accumulate

Tính tổng (hoặc áp dụng một phép toán tùy chỉnh) các phần tử trong một phạm vi, bắt đầu từ một giá trị ban đầu.

#include <vector>
#include <numeric>
#include <functional>

std::vector<int> values_accum = {1, 2, 3, 4, 5};
int sum = std::accumulate(values_accum.begin(), values_accum.end(), 0); // Tính tổng, kết quả là 15
int product = std::accumulate(values_accum.begin(), values_accum.end(), 1, std::multiplies<int>()); // Tính tích, kết quả là 120

6.2 inner_product

Tính tích vô hướng của hai dãy.

#include <vector>
#include <numeric>

std::vector<int> vec_a = {1, 2, 3};
std::vector<int> vec_b = {4, 5, 6};
// Tính (1*4) + (2*5) + (3*6)
int dot_product = std::inner_product(vec_a.begin(), vec_a.end(), vec_b.begin(), 0); // Kết quả là 32

6.3 iota

Điền vào một phạm vi các giá trị tăng dần liên tiếp.

#include <vector>
#include <numeric>

std::vector<int> data_iota(5);
std::iota(data_iota.begin(), data_iota.end(), 10); // data_iota là {10, 11, 12, 13, 14}

6.4 partial_sum

Tính tổng từng phần của một dãy và lưu vào một dãy đích.

#include <vector>
#include <numeric>

std::vector<int> source_sum = {1, 2, 3, 4, 5};
std::vector<int> dest_sum(source_sum.size());
std::partial_sum(source_sum.begin(), source_sum.end(), dest_sum.begin());
// dest_sum là {1, 3, 6, 10, 15}

6.5 adjacent_difference

Tính hiệu của các phần tử liền kề trong một dãy và lưu vào một dãy đích.

#include <vector>
#include <numeric>

std::vector<int> source_diff = {1, 2, 3, 4, 5};
std::vector<int> dest_diff(source_diff.size());
std::adjacent_difference(source_diff.begin(), source_diff.end(), dest_diff.begin());
// dest_diff là {1, 1, 1, 1, 1} (hiệu của các phần tử liên tiếp)

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

7.1 generate

Điền vào một phạm vi bằng các giá trị được tạo ra bởi một hàm sinh.

#include <vector>
#include <algorithm>

std::vector<int> data_generate(5);
int counter = 0;
std::generate(data_generate.begin(), data_generate.end(), [&counter]() {
    return counter++; // Tạo giá trị 0, 1, 2, 3, 4
});

7.2 generate_n

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

#include <vector>
#include <algorithm>
#include <iterator>

std::vector<int> data_gen_n(5);
int start_val = 10;
// Chỉ điền 3 phần tử đầu tiên
std::generate_n(data_gen_n.begin(), 3, [&start_val]() {
    return start_val++; // Tạo giá trị 10, 11, 12
});
// data_gen_n là {10, 11, 12, 0, 0} (giả sử các phần tử còn lại là 0)

7.3 includes

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

#include <vector>
#include <algorithm>

std::vector<int> main_set = {1, 2, 3, 4, 5, 6};
std::vector<int> sub_set = {2, 4};
bool is_included = std::includes(main_set.begin(), main_set.end(), sub_set.begin(), sub_set.end()); // true

7.4 Các thuật toán tập hợp (trên dãy đã sắp xếp): set_union, set_intersection, set_difference, set_symmetric_difference

• set_union: Tính hợp của hai tập hợp.
• set_intersection: Tính giao của hai tập hợp.
• set_difference: Tính hiệu của hai tập hợp (phần tử có trong tập thứ nhất nhưng không có trong tập thứ hai).
• set_symmetric_difference: Tính hiệu đối xứng (phần tử có trong một trong hai tập hợp nhưng không có trong cả hai).

#include <vector>
#include <algorithm>
#include <iterator>

std::vector<int> set1 = {1, 2, 3, 4, 5};
std::vector<int> set2 = {3, 4, 5, 6, 7};
std::vector<int> result_set;

// Hợp
result_set.clear();
std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result_set));
// result_set: {1, 2, 3, 4, 5, 6, 7}

// Giao
result_set.clear();
std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result_set));
// result_set: {3, 4, 5}

// Hiệu (set1 - set2)
result_set.clear();
std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result_set));
// result_set: {1, 2}

// Hiệu đối xứng
result_set.clear();
std::set_symmetric_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result_set));
// result_set: {1, 2, 6, 7}

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

1. Sự khác biệt giữa sort và stable_sort?
   sort thường sử dụng IntroSort (kết hợp QuickSort, HeapSort, InsertionSort) với độ phức tạp trung bình O(N log N) nhưng không ổn định. stable_sort sử dụng MergeSort hoặc tương tự, đảm bảo thứ tự tương đối của các phần tử bằng nhau, với độ phức tạp O(N log N) hoặc O(N log^2 N) tùy thuộc vào việc cấp phát bộ nhớ.
2. Tại sao remove cần đi kèm erase?
   remove chỉ di chuyển các phần tử cần giữ về đầu dãy và trả về một iterator trỏ tới "kết thúc logic". Nó không thực sự thay đổi kích thước container. erase mới là hàm thực hiện việc xóa các phần tử khỏi container, thay đổi kích thước. Do đó, cần gọi container.erase(remove(...), container.end()) để loại bỏ hoàn toàn các phần tử không mong muốn.
3. Những thuật toán nào yêu cầu dãy nguồn phải được sắp xếp?
   Các thuật toán tìm kiếm nhị phân (binary_search, lower_bound, upper_bound), các thuật toán tập hợp (set_union, set_intersection, v.v.), và merge đều yêu cầu dãy nguồn phải được sắp xếp để hoạt động chính xác và hiệu quả.