当前位置：首页 > article >正文

C++ STL算法总结

article 2025/2/11 12:49:40

C++ 标准库的 <algorithm> 提供了大量通用的算法, 用于操作容器, 范围和迭代器. 这些算法可以归纳为几大类, 涵盖排序, 搜索, 修改, 统计等功能.

以下是 <algorithm> 中算法的分类和常用方法的总结:

批处理操作

for_each, ranges::for_each: 对范围内的每一个元素执行操作
for_each_n, ranges::for_each_n (C++17): 对一个序列的前 N 个元素执行操作

样例代码

// for_each
std::for_each(v.begin(), v.end(), [](int& n) { n *= 2; });
fmt::println("{}", v);  // [2, 4, 6, 8, 10]

// ranges::for_each (C++20)
std::ranges::for_each(v, [](int& n) { n = 1; });
fmt::println("{}", v); // [1, 1, 1, 1, 1]

// for_each_n (C++17)
std::for_each_n(v.begin(), 3, [](int& n) { n = 2; });
fmt::println("{}", v); // [2, 2, 2, 1, 1]

// ranges::for_each_n (C++20)
std::ranges::for_each_n(v.begin(), 2, [](int& n) { n = 3; });
fmt::println("{}", v); // [3, 3, 2, 1, 1]

搜索操作

这些算法不会修改容器中的元素，主要用于查询、统计和范围操作。

检查元素

all_of, ranges::all_of (C++20): 检查范围内所有元素是否满足条件。
any_of, ranges::any_of (C++20): 检查范围内是否存在满足条件的元素。
none_of, ranges::none_of (C++20): 检查范围内所有元素是否都不满足条件。

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

// all_of
fmt::println("All elements greater than 0: {}",
              std::all_of(v.begin(), v.end(), [](int n) { return n > 0; }));
// ranges::all_of (C++20)
fmt::println("All elements greater than 1: {}",
              std::ranges::all_of(v, [](int n) { return n > 1; }));

// any_of
fmt::println("Any element greater than 4: {}",
              std::any_of(v.begin(), v.end(), [](int n) { return n > 4; }));
// ranges::any_of (C++20)
fmt::println("Any element greater than 6: {}",
              std::ranges::any_of(v, [](int n) { return n > 6; }));

// none_of
fmt::println("None of the elements greater than 6: {}",
              std::none_of(v.begin(), v.end(), [](int n) { return n > 6; }));
// ranges::none_of (C++20)
fmt::println("None of the elements greater than 2: {}",
              std::ranges::none_of(v, [](int n) { return n > 2; }));

查找

ranges::contains (C++23): 检查范围是否包含指定值。
ranges::contains_subrange (C++23): 检查范围是否包含指定子范围。
find, ranges::find: 查找第一个等于指定值的元素。
find_if, ranges::find_if: 查找第一个满足条件的元素。
find_if_not, ranges::find_if_not: 查找第一个不满足条件的元素。
ranges::find_last (C++23):查找最后一个等于指定值的元素。
ranges::find_last_if (C++23): 查找最后一个满足条件的元素。
ranges::find_last_if_not (C++23): 查找最后一个不满足条件的元素。
find_end, ranges::find_end: 查找某个子范围在另一个范围中最后一次出现的位置。
find_first_of, ranges::find_first_of: 查找两个范围中第一个匹配的元素。
adjacent_find, ranges::adjacent_find: 查找范围内相邻且相等的元素。

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

// ranges::contains (C++23)
fmt::print("Vector contains 3: {}\n", std::ranges::contains(v, 3));
// Vector contains 3: true

// ranges::contains_subrange (C++23)
fmt::print("Vector contains sub - range {{3, 4}}: {}\n",
            std::ranges::contains_subrange(v, sub_v));
// Vector contains sub - range {3, 4}: true

// find
if (auto it = std::find(v.begin(), v.end(), 3); it != v.end()) {
  fmt::print("Found 3 at position: {}\n", std::distance(v.begin(), it));
  // Found 3 at position: 2
}

// ranges::find
if (auto rit = std::ranges::find(v, 3); rit != v.end()) {
  fmt::print("Found 3 at position (ranges): {}\n",
              std::distance(v.begin(), rit));
  // Found 3 at position (ranges): 2
}

// find_if
// 查找第一个大于 3 的元素，第一个大于 3 的元素是 4，其位置索引是 3
if (auto it_if =
        std::find_if(v.begin(), v.end(), [](int n) { return n > 3; });
    it_if != v.end()) {
  fmt::print("Found element greater than 3 at position: {}\n",
              std::distance(v.begin(), it_if));
  // Found element greater than 3 at position: 3
}

// ranges::find_if
// 使用 ranges 版本查找第一个大于 3 的元素，结果位置索引同样是 3
if (auto rit_if = std::ranges::find_if(v, [](int n) { return n > 3; });
    rit_if != v.end()) {
  fmt::print("Found element greater than 3 at position (ranges): {}\n",
              std::distance(v.begin(), rit_if));
  // Found element greater than 3 at position (ranges): 3
}

// find_if_not
// 查找第一个不大于 3 的元素，也就是第一个小于等于 3 的元素，是 1，位置索引是0
if (auto it_if_not =
        std::find_if_not(v.begin(), v.end(), [](int n) { return n > 3; });
    it_if_not != v.end()) {
  fmt::print("Found element not greater than 3 at position: {}\n",
              std::distance(v.begin(), it_if_not));
  // Found element not greater than 3 at position: 0
}

// ranges::find_if_not
// 使用 ranges 版本查找第一个不大于 3 的元素，结果位置索引还是 0
if (auto rit_if_not =
        std::ranges::find_if_not(v, [](int n) { return n > 3; });
    rit_if_not != v.end()) {
  fmt::print("Found element not greater than 3 at position (ranges): {}\n",
              std::distance(v.begin(), rit_if_not));
  // Found element not greater than 3 at position (ranges): 0
}

// adjacent_find
// 查找相邻且相等的元素，向量中没有相邻且相等的元素，所以此条件不满足，不会有输出
if (auto it_adj = std::adjacent_find(v.begin(), v.end()); it_adj != v.end()) {
  fmt::print("Found adjacent equal elements at position: {}\n",
              std::distance(v.begin(), it_adj));
}

// ranges::adjacent_find
// 使用 ranges 版本查找相邻且相等的元素，同样不会有输出
if (auto rit_adj = std::ranges::adjacent_find(v); rit_adj != v.end()) {
  fmt::print("Found adjacent equal elements at position (ranges): {}\n",
              std::distance(v.begin(), rit_adj));
}

计数

count, ranges::count: 统计等于指定值的元素个数。
count_if, ranges::count_if: 统计满足条件的元素个数。

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

// count
fmt::print("Count of 3: {}\n", std::count(v.begin(), v.end(), 3));
// Count of 3: 2

// ranges::count
fmt::print("Count of 3 (ranges): {}\n", std::ranges::count(v, 3));
// Count of 3 (ranges): 2

// count_if
fmt::print("Count of elements greater than 3: {}\n",
            std::count_if(v.begin(), v.end(), [](int n) { return n > 3; }));
// Count of elements greater than 3: 2

// ranges::count_if
fmt::print("Count of elements greater than 3 (ranges): {}\n",
            std::ranges::count_if(v, [](int n) { return n > 3; }));
// Count of elements greater than 3 (ranges): 2

比较

mismatch, ranges::mismatch: 找到两个范围中第一个不匹配的元素。
equal, ranges::equal: 比较两个范围是否相等。
search, ranges::search: 在一个范围中查找另一个范围第一次出现的位置。
search_n, ranges::search_n: 在一个范围中查找连续 n 个等于指定值的元素。
ranges::starts_with: 检查一个范围是否以另一个范围开头。
ranges::ends_with: 检查一个范围是否以另一个范围结尾。

Fold operations (C++23)

ranges::fold_left(C++23): 从左到右折叠范围中的元素。
ranges::fold_left_first(C++23): 从左到右折叠范围中的元素，初始值为范围的第一个元素。
ranges::fold_right(C++23): 从右到左折叠范围中的元素。
ranges::fold_right_last(C++23): 从右到左折叠范围中的元素，初始值为范围的最后一个元素。
ranges::fold_left_with_iter(C++23): 从左到右折叠范围中的元素，并返回迭代器。
ranges::fold_left_first_with_iter(C++23): 从左到右折叠范围中的元素，初始值为范围的第一个元素，并返回迭代器。

修改序列

这些算法会修改容器或范围中的元素.

拷贝和移动

copy, ranges::copy: 将一个范围的元素拷贝到另一个范围。
copy_if, ranges::copy_if: 拷贝满足条件的元素。
copy_n, ranges::copy_n: 拷贝指定个数的元素。
copy_backward, ranges::copy_backward: 从后往前拷贝元素。
move, ranges::move: 将元素从一个范围移动到另一个范围。
move_backward, ranges::move_backward: 从后往前移动元素。

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

// copy
std::copy(src.begin(), src.end(), dst.begin());
fmt::println("After std::copy: {}", dst);
// output: After std::copy: [1, 2, 3, 4, 5]

// ranges::copy
std::ranges::copy(src, dst.begin());
fmt::println("After std::ranges::copy: {}", dst);
// output: After std::ranges::copy: [1, 2, 3, 4, 5]

// copy_if
dst.clear();
dst.resize(src.size());
auto it = std::copy_if(src.begin(), src.end(), dst.begin(),
                        [](int num) { return num % 2 == 0; });
dst.erase(it, dst.end());
fmt::println("After std::copy_if (even numbers): {}", dst);
// output: After std::copy_if (even numbers): [2, 4]

// ranges::copy_if
dst.clear();
dst.resize(src.size());
auto result = std::ranges::copy_if(src, dst.begin(),
                                    [](int num) { return num % 2 == 0; });
dst.erase(result.out, dst.end());
fmt::println("After std::ranges::copy_if (even numbers): {}", dst);
// output: After std::ranges::copy_if (even numbers): [2, 4]

// copy_n
dst.clear();
dst.resize(3);
std::copy_n(src.begin(), 3, dst.begin());
fmt::println("After std::copy_n (first 3 elements): {}", dst);
// output: After std::copy_n (first 3 elements): [1, 2, 3]

// ranges::copy_n
dst.clear();
dst.resize(3);
std::ranges::copy_n(src.begin(), 3, dst.begin());
fmt::println("After std::ranges::copy_n (first 3 elements): {}", dst);
// output: After std::ranges::copy_n (first 3 elements): [1, 2, 3]

// copy_backward
dst.clear();
dst.resize(src.size());
std::copy_backward(src.begin(), src.end(), dst.end());
fmt::println("After std::copy_backward: {}", dst);
// output: After std::copy_backward: [1, 2, 3, 4, 5]

// ranges::copy_backward
dst.clear();
dst.resize(src.size());
std::ranges::copy_backward(src, dst.end());
fmt::println("After std::ranges::copy_backward: {}", dst);
// output: After std::ranges::copy_backward: [1, 2, 3, 4, 5]

// move
std::vector<int> move_dst(5);
std::move(src.begin(), src.end(), move_dst.begin());
fmt::println("After std::move: {}", move_dst);
// output: After std::move: [1, 2, 3, 4, 5]

// ranges::move
std::vector<int> ranges_move_dst(5);
std::ranges::move(src, ranges_move_dst.begin());
fmt::println("After std::ranges::move: {}", ranges_move_dst);
// output: After std::ranges::move: [1, 2, 3, 4, 5]

// move_backward
std::vector<int> move_backward_dst(5);
std::move_backward(src.begin(), src.end(), move_backward_dst.end());
fmt::println("After std::move_backward: {}", move_backward_dst);
// output: After std::move_backward: [1, 2, 3, 4, 5]

// ranges::move_backward
std::vector<int> ranges_move_backward_dst(5);
std::ranges::move_backward(src, ranges_move_backward_dst.end());
fmt::println("After std::ranges::move_backward: {}",
              // output: After std::ranges::move_backward: [1, 2, 3, 4, 5]
              ranges_move_backward_dst);

交换操作

swap: 交换两个值。
swap_ranges, ranges::swap_ranges: 交换两个范围的元素。
iter_swap: 交换两个迭代器所指向的元素。

// swap
int a = 10;
int b = 20;
fmt::println("Before std::swap: a = {}, b = {}", a,
              b);  // 预期输出：Before std::swap: a = 10, b = 20
std::swap(a, b);
fmt::println("After std::swap: a = {}, b = {}", a,
              b);  // 预期输出：After std::swap: a = 20, b = 10

// swap_ranges 和 ranges::swap_ranges
std::vector<int> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2 = {6, 7, 8, 9, 10};

fmt::println("Before std::swap_ranges:");
fmt::println("vec1 = {}", vec1);  // 预期输出：vec1 = [1, 2, 3, 4, 5]
fmt::println("vec2 = {}", vec2);  // 预期输出：vec2 = [6, 7, 8, 9, 10]

std::swap_ranges(vec1.begin(), vec1.end(), vec2.begin());
fmt::println("After std::swap_ranges:");
fmt::println("vec1 = {}", vec1);  // 预期输出：vec1 = [6, 7, 8, 9, 10]
fmt::println("vec2 = {}", vec2);  // 预期输出：vec2 = [1, 2, 3, 4, 5]

// 恢复 vec1 和 vec2 以便测试 ranges::swap_ranges
vec1 = {1, 2, 3, 4, 5};
vec2 = {6, 7, 8, 9, 10};

fmt::println("Before std::ranges::swap_ranges:");
fmt::println("vec1 = {}", vec1);  // 预期输出：vec1 = [1, 2, 3, 4, 5]
fmt::println("vec2 = {}", vec2);  // 预期输出：vec2 = [6, 7, 8, 9, 10]

std::ranges::swap_ranges(vec1, vec2);
fmt::println("After std::ranges::swap_ranges:");
fmt::println("vec1 = {}", vec1);  // 预期输出：vec1 = [6, 7, 8, 9, 10]
fmt::println("vec2 = {}", vec2);  // 预期输出：vec2 = [1, 2, 3, 4, 5]

// iter_swap
std::vector<int> vec3 = {100, 200};
fmt::println("Before std::iter_swap: vec3 = {}",
              vec3);  // 预期输出：Before std::iter_swap: vec3 = [100, 200]
std::iter_swap(vec3.begin(), std::next(vec3.begin()));
fmt::println("After std::iter_swap: vec3 = {}",
              vec3);  // 预期输出：After std::iter_swap: vec3 = [200, 100]

变换操作

变换

transform, ranges::transform: 对范围内的每个元素应用函数，并将结果存储到另一个范围。

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

// 使用 transform 将每个元素乘以 2 并存储到 result 中
std::transform(numbers.begin(), numbers.end(), result.begin(),
                [](int num) { return num * 2; });

// 使用 ranges::transform 做同样的操作
std::vector<int> resultRanges(numbers.size());
std::ranges::transform(numbers, resultRanges.begin(),
                        [](int num) { return num * 2; });

// 输出 transform 的结果
fmt::print("transform 结果: {}\n", result);

// 输出 ranges::transform 的结果
fmt::print("ranges::transform 结果: {}\n", resultRanges);