Thao tác với Container C++: Khám phá các Thuật toán STL

Thư viện mẫu chuẩn (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 với các cấu trúc dữ liệu khác nhau, đặc biệt là các container. Bài viết này đi sâu vào các thuật toán STL, phân loại chúng dựa trên chức năng để dễ dàng tham khảo và sử dụng.

1. Thuật toán không thay đổi tuần tự

Các thuật toán này hoạt động trên các phần tử của container mà không làm thay đổi chúng.

1.1. `find` và `find_if`

find(begin, end, value): Tìm kiếm lần xuất hiện đầu tiên của value trong phạm vi [begin, end). Trả về một iterator tới phần tử đó hoặc end nếu không tìm thấy.
find_if(begin, end, predicate): Tìm kiếm lần xuất hiện đầu tiên của phần tử thỏa mãn điều kiện của predicate.
find_end(begin, end, sub_begin, sub_end): Tìm kiếm lần xuất hiện cuối cùng của một dãy con trong một phạm vi lớn hơn.

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

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

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

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

// Tìm dãy con
std::vector<int> subsequence = {3, 5};
auto it3 = std::find_end(numbers.begin(), numbers.end(), subsequence.begin(), subsequence.end());
if (it3 != numbers.end()) {
    std::cout << "Subsequence found starting at index: " << (it3 - numbers.begin()) << std::endl; // Xuất: 1
}

1.2. `count` và `count_if`

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

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

std::vector<int> data = {1, 2, 3, 2, 4, 2};
int count_of_2 = std::count(data.begin(), data.end(), 2); // Kết quả: 3
int even_count = std::count_if(data.begin(), data.end(), [](int x) {
    return x % 2 == 0;
}); // Kết quả: 4
std::cout << "Count of 2: " << count_of_2 << ", Even count: " << even_count << std::endl;

1.3. `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 <algorithm>
#include <iostream>

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

1.4. `equal` và `mismatch`

equal(b1, e1, b2): Kiểm tra xem hai phạm vi có bằng nhau hay không.
mismatch(b1, e1, b2): Trả về một cặp iterator tới cặp phần tử đầu tiên không khớp nhau giữa hai phạm vi.

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

std::vector<int> first_range = {1, 2, 3};
std::vector<int> second_range = {1, 2, 4};
std::vector<int> third_range = {1, 2, 3, 4};

bool are_equal = std::equal(first_range.begin(), first_range.end(), second_range.begin());
std::cout << "First and second ranges are equal: " << std::boolalpha << are_equal << std::endl; // Xuất: false

auto diff = std::mismatch(first_range.begin(), first_range.end(), third_range.begin());
if (diff.first != first_range.end()) {
    std::cout << "Mismatch found: " << *diff.first << " vs " << *diff.second << std::endl;
} else {
    std::cout << "No mismatch found between first and third ranges." << std::endl; // Xuất: No mismatch...
}

1.5. `all_of`, `any_of`, `none_of`

Các thuật toán này kiểm tra xem tất cả các phần tử, ít nhất một phần tử, hay không có phần tử nào trong phạm vi thỏa mãn một điều kiện nhất định.

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

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

std::cout << "All even: " << std::boolalpha << all_are_even << std::endl;
std::cout << "Any odd: " << std::boolalpha << any_is_odd << std::endl;
std::cout << "None negative: " << std::boolalpha << none_are_negative << std::endl;

2. Thuật toán thay đổi tuần tự

Các thuật toán này sửa đổi các phần tử của container mà chúng hoạt động.

2.1. `copy` và `copy_if`

copy(begin, end, dest): Sao chép các phần tử từ phạm vi [begin, end) sang 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 <algorithm>
#include <iterator> // For std::back_inserter
#include <iostream>

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

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

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

std::cout << "Copied destination: ";
for (int val : destination) std::cout << val << " ";
std::cout << std::endl;

std::cout << "Copied even numbers: ";
for (int val : even_numbers) std::cout << val << " ";
std::cout << std::endl;

Lưu ý: std::back_inserter tự động gọi push_back, không cần cấp phát trước bộ nhớ.

2.2. `transform`

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

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

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

// Chuyển đổi một phạm vi (tính bình phương)
std::transform(nums.begin(), nums.end(), squares.begin(), [](int x) {
    return x * x;
});
// squares: {1, 4, 9}

std::vector<int> vec_a = {1, 2, 3};
std::vector<int> vec_b = {4, 5, 6};
std::vector<int> sum_vec(vec_a.size());

// Chuyển đổi hai phạm vi (cộng các phần tử tương ứng)
std::transform(vec_a.begin(), vec_a.end(), vec_b.begin(), sum_vec.begin(), [](int x, int y) {
    return x + y;
});
// sum_vec: {5, 7, 9}

std::cout << "Squares: ";
for (int val : squares) std::cout << val << " ";
std::cout << std::endl;

std::cout << "Sum vector: ";
for (int val : sum_vec) std::cout << val << " ";
std::cout << std::endl;

2.3. `replace`, `replace_if` và `replace_copy`

replace(begin, end, old_val, new_val): Thay thế tất cả các lần xuất hiện của 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ử, thay thế old_val bằng new_val trong quá trình sao chép. Container gốc không bị thay đổi.

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

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

// Thay thế tất cả giá trị 2 bằng 20
std::replace(items.begin(), items.end(), 2, 20);
// items: {1, 20, 3, 20, 5}

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

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

std::cout << "Items after replacements: ";
for (int val : items) std::cout << val << " ";
std::cout << std::endl;

std::cout << "Replaced copy result: ";
for (int val : replaced_copy_result) std::cout << val << " ";
std::cout << std::endl;

2.4. `remove`, `remove_if` và `erase`

remove(begin, end, value): "Di chuyển" tất cả các phần tử bằng value đến cuối phạm vi và trả về một iterator tới vị trí logic mới của kết thúc. Nó không thực sự xóa các phần tử.
remove_if(begin, end, predicate): Tương tự như remove, nhưng dựa trên một predicate.

Để thực sự xóa các phần tử, bạn cần kết hợp remove hoặc remove_if với phương thức erase của container.

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

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

// Di chuyển tất cả các số 2 đến cuối
auto new_end_iter = std::remove(sequence.begin(), sequence.end(), 2);
// sequence: {1, 3, 4, 2, 2} (vị trí của các phần tử bị "xóa" không xác định)

// Xóa các phần tử không còn cần thiết thực sự
sequence.erase(new_end_iter, sequence.end());
// sequence: {1, 3, 4}

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

std::cout << "Sequence after remove/erase: ";
for (int val : sequence) std::cout << val << " ";
std::cout << std::endl;

2.5. `unique`

Loại bỏ các phần tử trùng lặp liên tiếp trong một phạm vi đã sắp xếp và trả về iterator tới vị trí logic mới của kết thúc. Cũng cần kết hợp với erase để xóa thực sự.

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

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

std::cout << "Unique elements: ";
for (int val : distinct_elements) std::cout << val << " ";
std::cout << std::endl;

2.6. `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<int> list_to_reverse = {1, 2, 3, 4, 5};
std::reverse(list_to_reverse.begin(), list_to_reverse.end());
// list_to_reverse: {5, 4, 3, 2, 1}

std::cout << "Reversed list: ";
for (int val : list_to_reverse) std::cout << val << " ";
std::cout << std::endl;

2.7. `rotate`

Xoay các phần tử trong một phạm vi sao cho một phần tử cụ thể trở thành phần tử đầu tiên.

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

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

std::cout << "Rotated data: ";
for (int val : data_to_rotate) std::cout << val << " ";
std::cout << std::endl;

2.8. `shuffle`

Xáo trộn ngẫu nhiên thứ tự các phần tử trong một phạm vi. Yêu cầu C++11 trở lên.

#include <vector>
#include <algorithm>
#include <random> // For random number generation
#include <iostream>

std::vector<int> unshuffled = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 generator(rd()); // Mersenne Twister engine

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

std::cout << "Shuffled data: ";
for (int val : unshuffled) std::cout << val << " ";
std::cout << std::endl;

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 các phần tử trong phạm vi. Mặc định là tăng dần. 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, nghĩa là các phần tử có giá trị bằng nhau giữ nguyên thứ tự tương đối của chúng.
partial_sort(begin, mid, end): Sắp xếp một phần của phạm vi. Các phần tử trong [begin, mid) sẽ là mid - begin phần tử nhỏ nhất trong toàn bộ phạm vi, và chúng được sắp xếp.

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

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

// Sắp xếp tăng dần mặc định
std::sort(numbers_to_sort.begin(), numbers_to_sort.end());
// numbers_to_sort: {1, 2, 3, 4, 5}

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

// Sắp xếp ổn định (ví dụ với cặp)
std::vector<std::pair<int, int>> pairs = {{1, 5}, {2, 3}, {1, 2}, {2, 1}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // Sắp xếp theo phần tử đầu tiên
});
// pairs có thể là: {{1, 5}, {1, 2}, {2, 3}, {2, 1}} hoặc {{1, 2}, {1, 5}, {2, 1}, {2, 3}}
// Thứ tự tương đối của các cặp có phần tử đầu tiên giống nhau được bảo toàn.

std::vector<int> partial_sort_data = {5, 3, 1, 4, 2, 6};
// Sắp xếp 3 phần tử nhỏ nhất vào đầu
std::partial_sort(partial_sort_data.begin(), partial_sort_data.begin() + 3, partial_sort_data.end());
// partial_sort_data: {1, 2, 3, ?, ?, ?} (các phần tử sau 3 không được đảm bảo thứ tự)

std::cout << "Sorted (ascending): ";
for (int val : numbers_to_sort) std::cout << val << " ";
std::cout << std::endl;

std::cout << "Sorted (descending): ";
for (int val : another_set) std::cout << val << " ";
std::cout << std::endl;

std::cout << "Partially sorted: ";
for (int val : partial_sort_data) std::cout << val << " ";
std::cout << std::endl;

3.2. `nth_element`

Tái sắp xếp phạm vi sao cho phần tử tại vị trí thứ n là phần tử sẽ đứng ở vị trí đó 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í đó đều nhỏ hơn hoặc bằng nó, và tất cả các phần tử sau đó đều lớn hơn hoặc bằng nó.

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

std::vector<int> nth_element_data = {5, 3, 1, 4, 2, 6};
// Đặt phần tử thứ 3 (chỉ số 2) vào đúng vị trí của nó nếu được sắp xếp
std::nth_element(nth_element_data.begin(), nth_element_data.begin() + 2, nth_element_data.end());
// nth_element_data[2] sẽ là 3. Các phần tử trước nó <= 3, các phần tử sau nó >= 3.
// Ví dụ kết quả: {1, 2, 3, 5, 4, 6} (thứ tự của các phần tử khác có thể thay đổi)

std::cout << "After nth_element (at index 2): ";
for (int val : nth_element_data) std::cout << val << " ";
std::cout << std::endl;

3.3. `binary_search`, `lower_bound`, `upper_bound`

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

binary_search(begin, end, value): Kiểm tra xem value có tồn tại trong phạm vi đã sắp xếp 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 (lớn hơn hoặc bằng) 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 <algorithm>
#include <iostream>

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

bool found = std::binary_search(sorted_list.begin(), sorted_list.end(), 3);
std::cout << "Binary search for 3: " << std::boolalpha << found << std::endl; // Xuất: true

auto lower = std::lower_bound(sorted_list.begin(), sorted_list.end(), 3);
std::cout << "Lower bound for 3 is at index: " << (lower - sorted_list.begin()) << std::endl; // Xuất: 1

auto upper = std::upper_bound(sorted_list.begin(), sorted_list.end(), 3);
std::cout << "Upper bound for 3 is at index: " << (upper - sorted_list.begin()) << std::endl; // Xuất: 3

3.4. `merge`

Hợp nhất hai phạm vi đã sắp xếp thành một phạm vi đích, cũng được sắp xếp.

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

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: {1, 2, 3, 4, 5, 6}

std::cout << "Merged list: ";
for (int val : merged_list) std::cout << val << " ";
std::cout << std::endl;

4. Thuật toán Heap

STL cung cấp các thuật toán để xử lý các phạm vi dưới dạng cấu trúc dữ liệu heap (mặc định là max-heap).

make_heap: Xây dựng một heap từ một phạm vi.
push_heap: Thêm một phần tử mới vào heap.
pop_heap: Di chuyển phần tử gốc của heap (phần tử lớn nhất đối với max-heap) đến cuối phạm vi.
sort_heap: Sắp xếp một heap thành một dãy tăng dần.

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

std::vector<int> heap_data = {4, 1, 3, 2, 5};
std::make_heap(heap_data.begin(), heap_data.end());
// heap_data: {5, 4, 3, 2, 1} (Cấu trúc heap, phần tử lớn nhất ở gốc)

heap_data.push_back(6); // Thêm phần tử mới
std::push_heap(heap_data.begin(), heap_data.end());
// heap_data: {6, 4, 5, 2, 1, 3} (Cấu trúc heap được cập nhật)

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

std::sort_heap(heap_data.begin(), heap_data.end());
// heap_data: {1, 2, 3, 4, 5} (Đã sắp xếp)

std::cout << "Heap sort result: ";
for (int val : heap_data) std::cout << val << " ";
std::cout << std::endl;

5. Thuật toán Min/Max

5.1. `min` và `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>
#include <iostream>

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

auto min_in_list = std::min({4, 2, 8, 5, 1}); // 1
auto max_in_list = std::max({4, 2, 8, 5, 1}); // 8

std::cout << "Min of " << a << ", " << b << ": " << min_val << std::endl;
std::cout << "Max of {4, 2, 8, 5, 1}: " << max_in_list << std::endl;

5.2. `min_element` và `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>
#include <iostream>

std::vector<int> values_for_minmax = {3, 1, 4, 2, 5};
auto min_it = std::min_element(values_for_minmax.begin(), values_for_minmax.end());
auto max_it = std::max_element(values_for_minmax.begin(), values_for_minmax.end());

std::cout << "Min element: " << *min_it << std::endl; // 1
std::cout << "Max element: " << *max_it << std::endl; // 5

5.3. `minmax_element` (C++11)

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

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

std::vector<int> values_for_minmax2 = {3, 1, 4, 2, 5};
auto minmax_pair = std::minmax_element(values_for_minmax2.begin(), values_for_minmax2.end());

std::cout << "Min element (pair): " << *(minmax_pair.first) << std::endl;  // 1
std::cout << "Max element (pair): " << *(minmax_pair.second) << std::endl; // 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 một phạm vi, có thể với một toán tử tùy chỉnh.

#include <vector>
#include <numeric> // Required for accumulate
#include <functional> // For std::multiplies
#include <iostream>

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

// Tính tổng
int sum = std::accumulate(sequence_nums.begin(), sequence_nums.end(), 0); // 0 là giá trị khởi tạo
// sum: 15

// Tính tích
int product = std::accumulate(sequence_nums.begin(), sequence_nums.end(), 1, std::multiplies<int>());
// product: 120

std::cout << "Accumulated sum: " << sum << std::endl;
std::cout << "Accumulated product: " << product << std::endl;

6.2. `inner_product`

Tính tích vô hướng của hai phạm vi, với các toán tử tùy chỉnh có thể được chỉ định.

#include <vector>
#include <numeric>
#include <iostream>

std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = {4, 5, 6};

// Tích vô hướng: (1*4) + (2*5) + (3*6)
int dot_product = std::inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
// dot_product: 32

std::cout << "Inner product: " << dot_product << std::endl;

6.3. `iota`

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

#include <vector>
#include <numeric>
#include <iostream>

std::vector<int> fill_sequence(5);
// Điền từ 10, 11, 12, 13, 14
std::iota(fill_sequence.begin(), fill_sequence.end(), 10);

std::cout << "Iota filled sequence: ";
for (int val : fill_sequence) std::cout << val << " ";
std::cout << std::endl;

6.4. `partial_sum`

Tính tổng từng phần 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>
#include <iostream>

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

std::partial_sum(source_sums.begin(), source_sums.end(), destination_sums.begin());
// destination_sums: {1, 3, 6, 10, 15} (1, 1+2, 1+2+3, ...)

std::cout << "Partial sum: ";
for (int val : destination_sums) std::cout << val << " ";
std::cout << std::endl;

6.5. `adjacent_difference`

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

#include <vector>
#include <numeric>
#include <iostream>

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

std::adjacent_difference(source_diff.begin(), source_diff.end(), destination_diff.begin());
// destination_diff: {1, 1, 1, 1, 1} (1, 2-1, 3-2, 4-3, 5-4)

std::cout << "Adjacent difference: ";
for (int val : destination_diff) std::cout << val << " ";
std::cout << std::endl;

7. Khác

7.1. `generate`

Điền một phạm vi bằng cách gọi một hàm tạo giá trị cho mỗi phần tử.

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

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

std::cout << "Generated values: ";
for (int val : generated_values) std::cout << val << " ";
std::cout << std::endl;

7.2. `generate_n`

Tương tự như generate, nhưng chỉ điền n phần tử đầu tiên bắt đầu từ một vị trí nhất định.

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

std::vector<int> generate_n_target(5, 99); // Khởi tạo với giá trị mặc định
int start_num = 10;
// Điền 3 phần tử đầu tiên với các giá trị tăng dần từ 10
std::generate_n(generate_n_target.begin(), 3, [&start_num]() {
    return start_num++; // Tạo 10, 11, 12
});

std::cout << "generate_n result: ";
for (int val : generate_n_target) std::cout << val << " ";
std::cout << std::endl; // Xuất: 10 11 12 99 99

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.

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

std::vector<int> main_range = {1, 2, 3, 4, 5};
std::vector<int> sub_range = {2, 4};

bool contains_all = std::includes(main_range.begin(), main_range.end(),
                                  sub_range.begin(), sub_range.end());
std::cout << "main_range includes sub_range: " << std::boolalpha << contains_all << std::endl; // Xuất: true

7.4. `set_union`, `set_intersection`, `set_difference`, `set_symmetric_difference`

Các thuật toán này thực hiện các phép toán tập hợp trên hai phạm vi đã sắp xếp.

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

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

// Phép hợp (Union)
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}

// Phép giao (Intersection)
result_set.clear();
std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result_set));
// result_set: {3, 4, 5}

// Phép hiệu (Difference: 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}

// Phép hiệu đối xứng (Symmetric Difference)
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}

// Hàm trợ giúp để in kết quả
auto print_set = [](const std::string& op_name, const std::vector<int>& s) {
    std::cout << op_name << ": {";
    for (size_t i = 0; i < s.size(); ++i) {
        std::cout << s[i] << (i == s.size() - 1 ? "" : ", ");
    }
    std::cout << "}" << std::endl;
};

print_set("Union", result_set); // Sẽ in kết quả của phép toán cuối cùng (symmetric_difference)
// Để xem các kết quả khác, cần chạy từng lệnh và in ra

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

Sự khác biệt giữa sort và stable_sort?
- sort: Thường sử dụng thuật toán Introsort (kết hợp QuickSort, HeapSort, InsertionSort). Không ổn định (thứ tự 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: Thường sử dụng MergeSort. Ổn định (thứ tự tương đối của các phần tử bằng nhau được bảo toàn). Độ phức tạp O(N log N), nhưng thường tốn thêm bộ nhớ.
Tại sao remove cần đi kèm với erase?
remove chỉ di chuyển các phần tử cần giữ lại về phía trước và trả về một iterator tới vị trí "kết thúc logic" mới. Nó không thay đổi kích thước thực tế của container. erase mới là hàm thực sự loại bỏ các phần tử khỏi container dựa trên một phạm vi iterator, làm thay đổi kích thước container. Do đó, mẫu phổ biến là container.erase(std::remove(container.begin(), container.end(), value), container.end());.
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 phép toán tập hợp (set_intersection, set_union, v.v.) và merge yêu cầu dữ liệu đầu vào phải được sắp xếp để hoạt động hiệu quả và chính xác (ví dụ: tìm kiếm nhị phân có độ phức tạp O(log N)).

Thẻ: C++ STL thuật toán container sắp xếp

Đăng vào ngày 12 tháng 11 lúc 14:32

Thành phố Cuồng loạn

Thao tác với Container C++: Khám phá các Thuật toán STL

1. Thuật toán không thay đổi tuần tự

1.1. `find` và `find_if`

1.2. `count` và `count_if`

1.3. `for_each`

1.4. `equal` và `mismatch`

1.5. `all_of`, `any_of`, `none_of`

2. Thuật toán thay đổi tuần tự

2.1. `copy` và `copy_if`

2.2. `transform`

2.3. `replace`, `replace_if` và `replace_copy`

2.4. `remove`, `remove_if` và `erase`

2.5. `unique`

2.6. `reverse`

2.7. `rotate`

2.8. `shuffle`

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

3.1. `sort`, `stable_sort` và `partial_sort`

3.2. `nth_element`

3.3. `binary_search`, `lower_bound`, `upper_bound`

3.4. `merge`

4. Thuật toán Heap

5. Thuật toán Min/Max

5.1. `min` và `max`

5.2. `min_element` và `max_element`

5.3. `minmax_element` (C++11)

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

6.1. `accumulate`

6.2. `inner_product`

6.3. `iota`

6.4. `partial_sum`

6.5. `adjacent_difference`

7. Khác

7.1. `generate`

7.2. `generate_n`

7.3. `includes`

7.4. `set_union`, `set_intersection`, `set_difference`, `set_symmetric_difference`

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

Thẻ Phổ Biến

Thành phố Cuồng loạn

Thao tác với Container C++: Khám phá các Thuật toán STL

1. Thuật toán không thay đổi tuần tự

1.1. find và find_if

1.2. count và count_if

1.3. for_each

1.4. equal và mismatch

1.5. all_of, any_of, none_of

2. Thuật toán thay đổi tuần tự

2.1. copy và copy_if

2.2. transform

2.3. replace, replace_if và replace_copy

2.4. remove, remove_if và erase

2.5. unique

2.6. reverse

2.7. rotate

2.8. shuffle

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

3.1. sort, stable_sort và partial_sort

3.2. nth_element

3.3. binary_search, lower_bound, upper_bound

3.4. merge

4. Thuật toán Heap

5. Thuật toán Min/Max

5.1. min và max

5.2. min_element và max_element

5.3. minmax_element (C++11)

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

6.1. accumulate

6.2. inner_product

6.3. iota

6.4. partial_sum

6.5. adjacent_difference

7. Khác

7.1. generate

7.2. generate_n

7.3. includes

7.4. set_union, set_intersection, set_difference, set_symmetric_difference

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

Thẻ Phổ Biến

1.1. `find` và `find_if`

1.2. `count` và `count_if`

1.3. `for_each`

1.4. `equal` và `mismatch`

1.5. `all_of`, `any_of`, `none_of`

2.1. `copy` và `copy_if`

2.2. `transform`

2.3. `replace`, `replace_if` và `replace_copy`

2.4. `remove`, `remove_if` và `erase`

2.5. `unique`

2.6. `reverse`

2.7. `rotate`

2.8. `shuffle`

3.1. `sort`, `stable_sort` và `partial_sort`

3.2. `nth_element`

3.3. `binary_search`, `lower_bound`, `upper_bound`

3.4. `merge`

5.1. `min` và `max`

5.2. `min_element` và `max_element`

5.3. `minmax_element` (C++11)

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

6.1. `accumulate`

6.2. `inner_product`

6.3. `iota`

6.4. `partial_sum`

6.5. `adjacent_difference`

7.1. `generate`

7.2. `generate_n`

7.3. `includes`

7.4. `set_union`, `set_intersection`, `set_difference`, `set_symmetric_difference`