C++

STL Algorithms: The Power of <algorithm>

Nắm vững các thuật toán STL quan trọng nhất — từ tìm kiếm và sắp xếp đến chuyển đổi và tích lũy. Tìm hiểu cách các thuật toán kết hợp với các trình vòng lặp để tạo ra mã hiệu quả và có tính biểu cảm.

The <algorithm> Header

Theheader contains over 100 generic algorithms that operate on iterator ranges. These algorithms embody decades of computer science — battle-tested, optimized, and correct. Using them instead of hand-written loops makes your code shorter, more expressive, and often faster.

Algorithms are organized into categories:

- Non-modifying:find,count,search,all_of/any_of/none_of,equal,mismatch
- Modifying:copy,transform,fill,generate,replace,remove
- Sorting & ordering:sort,stable_sort,partial_sort,nth_element
- Binary search:lower_bound,upper_bound,binary_search,equal_range
- Numeric (in):accumulate,inner_product,partial_sum,iota

Every algorithm takes an iterator range[first, last)as its primary input.

Non-Modifying Algorithms

Non-modifying algorithms inspect elements without changing them. They are the workhorses of querying and validation.

non_modifying.cpp
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

int main() {
    std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5};

    // find — returns iterator to first match (or end)
    auto it = std::find(nums.begin(), nums.end(), 5);
    if (it != nums.end()) {
        std::cout << "Found 5 at index " << std::distance(nums.begin(), it) << '\n';
    }

    // find_if — with a predicate
    auto even = std::find_if(nums.begin(), nums.end(),
                             [](int x) { return x % 2 == 0; });
    std::cout << "First even: " << *even << '\n';  // 4

    // count / count_if
    int fives = std::count(nums.begin(), nums.end(), 5);
    int odds  = std::count_if(nums.begin(), nums.end(),
                              [](int x) { return x % 2 != 0; });
    std::cout << "Fives: " << fives << ", Odds: " << odds << '\n';

    // all_of / any_of / none_of
    bool all_positive = std::all_of(nums.begin(), nums.end(),
                                    [](int x) { return x > 0; });
    bool has_negative = std::any_of(nums.begin(), nums.end(),
                                    [](int x) { return x < 0; });
    std::cout << std::boolalpha;
    std::cout << "All positive: " << all_positive << '\n';  // true
    std::cout << "Has negative: " << has_negative << '\n';  // false

    // equal — compare two ranges
    std::vector<int> nums2 = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    bool same = std::equal(nums.begin(), nums.end(), nums2.begin());
    std::cout << "Equal: " << same << '\n';  // true
}

Modifying Algorithms

Modifying algorithms change element values or rearrange elements within a range.

modifying_algorithms.cpp
#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};

    // transform — apply a function to each element
    std::vector<int> squared;
    std::transform(src.begin(), src.end(), std::back_inserter(squared),
                   [](int x) { return x * x; });
    // squared: {1, 4, 9, 16, 25}

    // transform with two input ranges (binary transform)
    std::vector<int> b = {10, 20, 30, 40, 50};
    std::vector<int> sums;
    std::transform(src.begin(), src.end(), b.begin(),
                   std::back_inserter(sums),
                   [](int a, int b) { return a + b; });
    // sums: {11, 22, 33, 44, 55}

    // fill and generate
    std::vector<int> zeros(10);
    std::fill(zeros.begin(), zeros.end(), 42);  // all 42s

    int counter = 0;
    std::generate(zeros.begin(), zeros.end(),
                  [&counter]() { return counter++; });
    // zeros: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    // remove-erase idiom (pre-C++20)
    std::vector<int> data = {1, 2, 3, 2, 4, 2, 5};
    auto new_end = std::remove(data.begin(), data.end(), 2);
    data.erase(new_end, data.end());  // actually shrinks the vector
    // data: {1, 3, 4, 5}

    // C++20: simpler
    std::erase(data, 3);
    // data: {1, 4, 5}

    // replace
    std::replace(data.begin(), data.end(), 4, 99);
    // data: {1, 99, 5}

    for (int x : data) std::cout << x << ' ';
    std::cout << '\n';
}

Sorting and Ordering Algorithms

The STL provides several sorting algorithms with different trade-offs.std::sortis the general-purpose workhorse (O(n log n) average, introsort), whilepartial_sortandnth_elementare more efficient when you only need partial ordering.

sorting.cpp
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

struct Student {
    std::string name;
    double gpa;
};

int main() {
    std::vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    // sort — O(n log n), not stable
    std::sort(nums.begin(), nums.end());
    // nums: {1, 2, 3, 4, 5, 6, 7, 8, 9}

    // sort descending with comparator
    std::sort(nums.begin(), nums.end(), std::greater<int>{});
    // nums: {9, 8, 7, 6, 5, 4, 3, 2, 1}

    // stable_sort — preserves relative order of equal elements
    std::vector<Student> students = {
        {"Alice", 3.8}, {"Bob", 3.5}, {"Charlie", 3.8}, {"Diana", 3.5}
    };
    std::stable_sort(students.begin(), students.end(),
                     [](const Student& a, const Student& b) {
                         return a.gpa > b.gpa;  // descending GPA
                     });
    // Alice before Charlie (both 3.8) — relative order preserved

    // partial_sort — sort only the first k elements
    std::vector<int> data = {5, 2, 8, 1, 9, 3};
    std::partial_sort(data.begin(), data.begin() + 3, data.end());
    // First 3 are sorted: {1, 2, 3, ...rest unspecified}

    // nth_element — partition so the nth element is in its sorted position
    std::vector<int> vals = {5, 2, 8, 1, 9, 3, 7};
    std::nth_element(vals.begin(), vals.begin() + 3, vals.end());
    // vals[3] == 5 (the median), left side <= 5, right side >= 5

    // lower_bound / upper_bound — binary search on sorted data
    std::vector<int> sorted = {1, 2, 4, 4, 4, 7, 9};
    auto lo = std::lower_bound(sorted.begin(), sorted.end(), 4);  // first 4
    auto hi = std::upper_bound(sorted.begin(), sorted.end(), 4);  // past last 4
    std::cout << "Count of 4s: " << std::distance(lo, hi) << '\n';  // 3
}

Thuật toán số (<số>)

Theheader provides algorithms for mathematical computations on ranges.

numeric_algorithms.cpp
#include <numeric>
#include <vector>
#include <iostream>
#include <functional>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};

    // accumulate — fold/reduce with initial value
    int sum = std::accumulate(nums.begin(), nums.end(), 0);
    std::cout << "Sum: " << sum << '\n';  // 15

    // accumulate with custom operation (product)
    int product = std::accumulate(nums.begin(), nums.end(), 1,
                                  std::multiplies<int>{});
    std::cout << "Product: " << product << '\n';  // 120

    // inner_product — dot product
    std::vector<int> weights = {2, 3, 1, 4, 2};
    int dot = std::inner_product(nums.begin(), nums.end(),
                                 weights.begin(), 0);
    std::cout << "Dot product: " << dot << '\n';  // 1*2 + 2*3 + 3*1 + 4*4 + 5*2 = 37

    // partial_sum — running total
    std::vector<int> running;
    std::partial_sum(nums.begin(), nums.end(), std::back_inserter(running));
    // running: {1, 3, 6, 10, 15}

    // iota — fill with incrementing values
    std::vector<int> seq(10);
    std::iota(seq.begin(), seq.end(), 1);  // {1, 2, 3, ..., 10}

    // C++17: reduce (parallel-friendly version of accumulate)
    // int sum2 = std::reduce(nums.begin(), nums.end());  // same as accumulate for +

    for (int x : running) std::cout << x << ' ';
    std::cout << '\n';
}
Lỗi thường gặp

std::removedoes not actually remove elements from a container. It moves the "kept" elements to the front and returns an iterator to the new logical end. The container's actual size is unchanged — you must callerase()to physically remove the trailing elements:

std::vector<int> v = {1, 2, 3, 2, 4};
auto new_end = std::remove(v.begin(), v.end(), 2);
// v is now: {1, 3, 4, ?, ?} with size still 5
v.erase(new_end, v.end()); // NOW size is 3

In C++20, std::erase(container, value) and std::erase_if(container, predicate) handle this idiom in one call. Prefer these when available.

Thực hành tốt

Algorithms shine when composed. Instead of complex loops, chain algorithms together:

// Get sorted unique elements
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

// Copy only even numbers, squared, to output
std::vector<int> result;
std::copy_if(v.begin(), v.end(), std::back_inserter(result),
             [](int x) { return x % 2 == 0; });
std::transform(result.begin(), result.end(), result.begin(),
               [](int x) { return x * x; });

This style is clear, correct, and often outperforms hand-written loops because library implementations use SIMD, branch-free code, and other micro-optimizations.

Điểm chính
  • Theheader provides 100+ generic algorithms that work on any iterator range
  • std::sortis O(n log n) introsort;std::stable_sortpreserves equal-element order
  • std::transformis the functional "map" — applies a function to every element
  • std::removedoes not erase — use the remove-erase idiom, or C++20std::erase_if
  • std::accumulate(from) is the general fold/reduce operation
  • Prefer algorithms over hand-written loops — they are clearer, safer, and often faster

Câu đố — Kiểm tra kiến thức

(20 XP)

1. What does`std::remove`return?

2. Bạn sẽ sử dụng thuật toán nào để kiểm tra xem TẤT CẢ các phần tử trong một phạm vi có thỏa mãn một vị từ hay không?

3. Độ phức tạp về thời gian của`std::nth_element`là bao nhiêu?

Trước
Iterators: The STL Glue
Tiếp
Lambdas & Lập trình chức năng