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

Các 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, 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 predicate.
• 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.

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

// Tìm phần tử có giá trị 5
auto it = find(numbers.begin(), numbers.end(), 5);
if (it != numbers.end()) {
    cout << "Đã tìm thấy: " << *it << endl;  // Kết quả: 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 >6: " << *it2 << endl;  // Kết quả: 7

// Tìm dãy con
vector<int> subsequence = {3, 5};
auto it3 = find_end(numbers.begin(), numbers.end(), subsequence.begin(), subsequence.end());
if (it3 != numbers.end()) {
    cout << "Dãy con bắt đầu tại chỉ số: " << it3 - numbers.begin() << endl;  // Kết quả: 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 predicate.

std::vector<int> data = {1, 2, 3, 2, 4, 2};
int count_two = std::count(data.begin(), data.end(), 2); // Đếm số lần xuất hiện của 2, kết quả là 3
int even_count = std::count_if(data.begin(), data.end(), [](int x) { 
    return x % 2 == 0; 
}); // Đếm số chẵn, kết quả là 4

1.3 for_each

Áp dụng một hàm lên mỗi phần tử trong một phạm vi.

std::vector<int> items = {1, 2, 3, 4, 5};
std::for_each(items.begin(), items.end(), [](int& x) { 
    x *= 2; // Nhân đôi mỗi phần tử
});
// items bây giờ là {2, 4, 6, 8, 10}

1.4 equal và mismatch

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

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

// So sánh 3 phần tử đầu của arr1 và arr2
bool are_equal = equal(arr1.begin(), arr1.end(), arr2.begin());
cout << "arr1 == arr2? " << boolalpha << are_equal << endl;  // Kết quả: false

// Tìm điểm khác biệt đầu tiên giữa arr1 và arr3
auto diff = mismatch(arr1.begin(), arr1.end(), arr3.begin());
if (diff.first != arr1.end()) {
    cout << "Khác biệt: " << *diff.first << " vs " << *diff.second << endl;  // Không có kết quả (3 phần tử đầu của arr1 và arr3 bằng nhau)
}

1.5 all_of, any_of, none_of

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

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

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

Các thuật toán này sẽ thay đổi các phần tử trong container mà chúng thao tác.

2.1 copy và copy_if

• copy(begin, end, dest): Sao chép các 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 predicate vào dest.

vector<int> source = {1, 2, 3, 4, 5};
vector<int> destination(5);  // Cần cấp phát đủ dung lượng trước

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

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

Lưu ý: back_inserter(dest) sẽ tự động gọi push_back, không cần cấp phát dung lượng trước.

2.2 transform

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

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

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

// Cộng các phần tử của hai container (biến đổi hai tham số)
vector<int> list_a = {1, 2, 3};
vector<int> list_b = {4, 5, 6};
vector<int> sums(3);
transform(list_a.begin(), list_a.end(), list_b.begin(), sums.begin(), [](int x, int y) {
    return x + y;
});  // sums: [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ế các phần tử thỏa mãn predicate.
• replace_copy(begin, end, dest, old_val, new_val): Sao chép và thay thế (không sửa đổi container gốc).

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

// Thay thế tất cả 2 bằng 20
replace(data.begin(), data.end(), 2, 20);  // data: [1,20,3,20,5]

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

// Sao chép và thay thế 3 bằng 300 (container gốc không đổi)
vector<int> result;
replace_copy(data.begin(), data.end(), back_inserter(result), 3, 300);  // result: [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 về cuối container, trả về iterator logic mới ( không thực sự xóa phần tử, cần kết hợp với erase).
• remove_if(begin, end, predicate): Di chuyển các phần tử thỏa mãn predicate về cuối.

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

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

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

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

2.5 unique

Loại bỏ các phần tử trùng lặp liền kề trong phạm vi, trả về iterator kết thúc logic mới. Thường được kết hợp với erase.

std::vector<int> sequence = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto last = std::unique(sequence.begin(), sequence.end());
sequence.erase(last, sequence.end()); // sequence trở thành {1, 2, 3, 4, 5}

2.6 reverse

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

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

2.7 rotate

Xoay các phần tử trong phạm vi, làm cho phần tử ở vị trí middle trở thành phần tử đầu tiên mới.

std::vector<int> items = {1, 2, 3, 4, 5};
std::rotate(items.begin(), items.begin() + 2, items.end()); // Xoay với 3 làm điểm bắt đầu, items trở thành {3, 4, 5, 1, 2}

2.8 shuffle

Sắp xếp lại các phần tử trong phạm vi một cách ngẫu nhiên (yêu cầu C++11 trở lên).

#include <random>
#include <algorithm>

std::vector<int> items = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(items.begin(), items.end(), g); // Trộn ngẫu nhiên các phần tử trong items

3. Sắp xếp và các thuật toán liên quan

3.1 sort, stable_sort và partial_sort

• sort(begin, end): Sắp xếp các phần tử (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 (vị trí tương đối của các phần tử bằng nhau được giữ nguyên).
• partial_sort(begin, mid, end): Sắp xếp một phần, làm cho [begin, mid) là các phần tử nhỏ nhất trong toàn bộ phạm vi và được sắp xếp.

std::vector<int> data = {5, 3, 1, 4, 2};
std::sort(data.begin(), data.end()); // Mặc định tăng dần, data trở thành {1, 2, 3, 4, 5}
std::sort(data.begin(), data.end(), std::greater<int>()); // Giảm dần, data trở thành {5, 4, 3, 2, 1}
std::sort(data.begin(), data.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>> data_pairs = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(data_pairs.begin(), data_pairs.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // Sắp xếp theo first, giữ nguyên thứ tự tương đối của các phần tử bằng nhau
});

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

3.2 nth_element

Sắp xếp lại phạm vi sao cho phần tử ở vị trí được chỉ định bằng phần tử sau khi sắp xếp, và các phần tử bên trái không lớn hơn nó, các phần tử bên phải không nhỏ hơn nó.

std::vector<int> values = {5, 3, 1, 4, 2, 6};
// Tìm phần tử nhỏ thứ ba (chỉ số 2)
std::nth_element(values.begin(), values.begin() + 2, values.end());
// Bây giờ values[2] là 3, các phần tử bên trái <=3, các phần tử bên phải >=3

3.3 binary_search, lower_bound, upper_bound

Phải được sử dụng trên các 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_list = {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_list.begin(), sorted_list.end(), 3);  // true

// Tìm phần tử đầu tiên >=3
auto lb = lower_bound(sorted_list.begin(), sorted_list.end(), 3);
cout << "lower_bound index: " << lb - sorted_list.begin() << endl;  // Kết quả: 1

// Tìm phần tử đầu tiên >3
auto ub = upper_bound(sorted_list.begin(), sorted_list.end(), 3);
cout << "upper_bound index: " << ub - sorted_list.begin() << endl;  // Kết quả: 3

3.4 merge

Hợp nhất hai phạm vi đã được sắp xếp vào một container mới (giữ nguyên trật tự sắp xếp).

vector<int> sorted_a = {1, 3, 5};
vector<int> sorted_b = {2, 4, 6};
vector<int> merged_list(sorted_a.size() + sorted_b.size());

// Hợp nhất sorted_a và sorted_b (cả hai đều cần được sắp xếp)
merge(sorted_a.begin(), sorted_a.end(), sorted_b.begin(), sorted_b.end(), merged_list.begin());  // merged_list: [1,2,3,4,5,6]

4. Thuật toán Heap

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

std::vector<int> heap_data = {4, 1, 3, 2, 5};
std::make_heap(heap_data.begin(), heap_data.end()); // Xây dựng max-heap, heap_data trở thành {5, 4, 3, 2, 1}

heap_data.push_back(6);
std::push_heap(heap_data.begin(), heap_data.end()); // Thêm phần tử mới vào heap, heap_data trở thành {6, 4, 5, 2, 1, 3}

std::pop_heap(heap_data.begin(), heap_data.end()); // Di chuyển phần tử lớn nhất về cuối, heap_data trở thành {5, 4, 3, 2, 1, 6}
int max_value = heap_data.back(); // Lấy phần tử lớn nhất là 6
heap_data.pop_back(); // Xóa phần tử lớn nhất

std::sort_heap(heap_data.begin(), heap_data.end()); // Sắp xếp heap thành dãy tăng dần, heap_data trở thành {1, 2, 3, 4, 5}

5. Thuật toán tìm Min/Max

5.1 min và max

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

int x = 5, y = 3;
int min_val = std::min(x, y); // 3
int max_val = std::max(x, y); // 5

auto min_from_list = std::min({4, 2, 8, 5, 1}); // 1
auto max_from_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> dataset = {3, 1, 4, 2, 5};
auto min_it = std::min_element(dataset.begin(), dataset.end()); // Trỏ đến 1
auto max_it = std::max_element(dataset.begin(), dataset.end()); // Trỏ đến 5

5.3 minmax_element (C++11)

Trả về đồng thời iterator của phần tử nhỏ nhất và lớn nhất trong phạm vi.

std::vector<int> dataset = {3, 1, 4, 2, 5};
auto minmax = std::minmax_element(dataset.begin(), dataset.end());
// minmax.first trỏ đến 1, minmax.second trỏ đến 5

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

6.1 accumulate

Tính tổng tích lũy của các phần tử trong phạm vi (hoặc một phép toán tùy chỉnh).

#include <numeric>

std::vector<int> values = {1, 2, 3, 4, 5};
int sum = std::accumulate(values.begin(), values.end(), 0); // Tổng, giá trị ban đầu là 0, kết quả là 15
int product = std::accumulate(values.begin(), values.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 một phép toán tùy chỉnh).

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

6.3 iota

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

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

6.4 partial_sum

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

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(source.size());
std::partial_sum(source.begin(), source.end(), destination.begin()); // destination trở thành {1, 3, 6, 10, 15}

6.5 adjacent_difference

Tính hiệu số giữa các phần tử liền kề và lưu kết quả vào phạm vi đích.

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

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

7.1 generate

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

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

7.2 generate_n

Điền vào n phần tử đầu tiên của phạm vi bằng một hàm sinh.

std::vector<int> target(5);
int start_val = 10;
std::generate_n(target.begin(), 3, [&start_val]() { 
    return start_val++; 
}); // Ba phần tử đầu là 10, 11, 12, hai phần tử sau giữ nguyên

7.3 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.

std::vector<int> big_set = {1, 2, 3, 4, 5};
std::vector<int> small_set = {2, 4};
bool includes = std::includes(big_set.begin(), big_set.end(), small_set.begin(), small_set.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> set1 = {1, 2, 3, 4, 5};
std::vector<int> set2 = {3, 4, 5, 6, 7};
std::vector<int> output;

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

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

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

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

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

1. sort và stable_sort khác nhau thế nào?

   • sort sử dụng sắp xếp nhanh (thực tế là thuật toán introsort), 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 trung bình O (n log n).
   • stable_sort sử dụng sắp xếp trộn (merge sort), ổn định (vị trí tương đối của các phần tử bằng nhau được giữ nguyên), độ phức tạp O (n log n), nhưng tốn thêm một chút bộ nhớ.

2. Tại sao thuật toán remove cần được sử dụng kết hợp với erase?
   Nguyên lý của thuật toán remove là "ghi đè" lên các phần tử cần xóa, di chuyển các phần tử được giữ lại lên phía trước, và trả về iterator kết thúc logic mới, nhưng không thay đổi kích thước thực tế của container. erase thực sự xóa các phần tử thông qua một phạm vi iterator và thay đổi kích thước container. Do đó 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 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_intersection, set_union, v.v.), merge, v.v. Các thuật toán này phụ thuộc vào tính có thứ tự để đạt được hiệu quả cao (ví dụ: tìm kiếm nhị phân O (log n)).