C++ STD algorithm举例

作者: zxlele_c763 | 来源:发表于2025-03-11 09:48 被阅读0次

2019-01-28 [HDU-2067]
2019-02-09
C++常用类型转换备忘
c/c++学习笔记6-std标准库学习
C++字符串处理小结
C++ 经典算法集锦一
2018-10-23 step
{ 1 }CPP_线程管理的基础
c++ algorithm
C++ algorithm

C++ 标准模板库 (STL) 提供了丰富的算法，这些算法操作容器中的元素，执行各种常见的任务，例如搜索、排序、转换等。使用 STL 算法可以提高代码的可读性、可维护性和性能。

下面是一些常用的 C++ STL 算法的示例，并附有详细的说明：

1. 排序算法:

std::sort: 对指定范围内的元素进行排序 (默认升序)。
std::stable_sort: 对指定范围内的元素进行排序，保持相等元素的相对顺序。
std::partial_sort: 对指定范围内的元素进行部分排序，将最小/最大的 k 个元素排到容器的前面。
std::nth_element: 找到指定范围内的第 n 个元素 (排序后)，并将小于该元素的元素放在它的前面，大于该元素的元素放在它的后面。

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

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

  // 使用 std::sort 排序
  std::sort(numbers.begin(), numbers.end());
  std::cout << "Sorted: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出: Sorted: 1 2 4 5 8 9

  // 使用 std::stable_sort
  std::vector<std::pair<int, char>> data = {{3, 'c'}, {1, 'a'}, {3, 'b'}, {2, 'd'}};
  std::stable_sort(data.begin(), data.end());
  std::cout << "Stable Sorted: ";
  for (const auto& pair : data) {
    std::cout << "(" << pair.first << ", " << pair.second << ") ";
  }
  std::cout << std::endl; // 输出: Stable Sorted: (1, a) (2, d) (3, c) (3, b)  (注意相等元素 'c' 和 'b' 的顺序保持不变)

  // 使用 std::partial_sort
  std::vector<int> unsorted = {5, 2, 8, 1, 9, 4};
  std::partial_sort(unsorted.begin(), unsorted.begin() + 3, unsorted.end());
  std::cout << "Partial Sorted (first 3 elements): ";
  for (int num : unsorted) {
      std::cout << num << " ";
  }
  std::cout << std::endl; // 输出类似: Partial Sorted (first 3 elements): 1 2 4 5 9 8 (前三个元素是最小的 3 个，但不保证后面的元素是有序的)

  //使用 std::nth_element
  std::vector<int> unsorted2 = {5, 2, 8, 1, 9, 4};
  std::nth_element(unsorted2.begin(), unsorted2.begin() + 2, unsorted2.end()); // 找到第三小的元素
  std::cout << "nth_element (3rd smallest): ";
  for (int num : unsorted2) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出类似: nth_element (3rd smallest): 2 1 4 5 9 8  (4 是第三小的，并且 2, 1 都小于 4， 5, 9, 8 都大于 4)
  std::cout << "The 3rd smallest element is: " << unsorted2[2] << std::endl; // 输出: The 3rd smallest element is: 4
  return 0;
}

2. 搜索算法:

std::find: 在指定范围内查找第一个与给定值相等的元素。
std::find_if: 在指定范围内查找第一个满足给定谓词（函数对象或 lambda 表达式）的元素。
std::binary_search: 在已排序的指定范围内查找是否存在与给定值相等的元素 (二分查找)。
std::lower_bound: 在已排序的指定范围内查找第一个不小于给定值的元素的位置。
std::upper_bound: 在已排序的指定范围内查找第一个大于给定值的元素的位置。
std::equal_range: 在已排序的指定范围内查找与给定值相等的元素的范围（返回一个包含 lower_bound 和 upper_bound 的 pair）。

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

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

  // 使用 std::find 查找
  auto it = std::find(numbers.begin(), numbers.end(), 5);
  if (it != numbers.end()) {
    std::cout << "Found 5 at position: " << std::distance(numbers.begin(), it) << std::endl; // 输出: Found 5 at position: 2
  } else {
    std::cout << "5 not found" << std::endl;
  }

  // 使用 std::find_if 查找第一个偶数
  auto it2 = std::find_if(numbers.begin(), numbers.end(), [](int n){ return n % 2 == 0; });
  if (it2 != numbers.end()) {
    std::cout << "Found first even number: " << *it2 << std::endl;
  } else {
    std::cout << "No even numbers found" << std::endl; //输出: No even numbers found
  }

  // 使用 std::binary_search (需要先排序)
  bool found = std::binary_search(numbers.begin(), numbers.end(), 5);
  if (found) {
    std::cout << "5 found using binary_search" << std::endl; // 输出: 5 found using binary_search
  } else {
    std::cout << "5 not found using binary_search" << std::endl;
  }

  //使用 std::lower_bound 和 upper_bound
    std::vector<int> sorted_nums = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5};

    auto lower = std::lower_bound(sorted_nums.begin(), sorted_nums.end(), 3);
    auto upper = std::upper_bound(sorted_nums.begin(), sorted_nums.end(), 3);

    std::cout << "Lower bound of 3: " << std::distance(sorted_nums.begin(), lower) << std::endl; // 输出: Lower bound of 3: 3
    std::cout << "Upper bound of 3: " << std::distance(sorted_nums.begin(), upper) << std::endl; // 输出: Upper bound of 3: 6
    std::cout << "Number of occurrences of 3: " << std::distance(lower, upper) << std::endl;    // 输出: Number of occurrences of 3: 3

    //使用 std::equal_range
    auto range = std::equal_range(sorted_nums.begin(), sorted_nums.end(), 4);
    std::cout << "Equal range for 4: [" << std::distance(sorted_nums.begin(), range.first) << ", "
              << std::distance(sorted_nums.begin(), range.second) << ")" << std::endl; // Equal range for 4: [6, 10)
    std::cout << "Number of occurrences of 4: " << std::distance(range.first, range.second) << std::endl; //Number of occurrences of 4: 4

  return 0;
}

3. 复制和移动算法:

std::copy: 将指定范围内的元素复制到另一个位置。
std::copy_if: 将指定范围内满足给定谓词的元素复制到另一个位置。
std::copy_n: 从指定范围复制指定数量的元素到另一个位置。
std::move: 将指定范围内的元素移动到另一个位置（移动语义）。
std::move_backward: 将指定范围内的元素反向移动到另一个位置（移动语义）。
std::transform: 对指定范围内的元素应用一个函数对象，并将结果存储到另一个位置。

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

int main() {
  std::vector<int> source = {1, 2, 3, 4, 5};
  std::vector<int> destination(5);  // 确保 destination 容器有足够的空间

  // 使用 std::copy 复制
  std::copy(source.begin(), source.end(), destination.begin());
  std::cout << "Copied: ";
  for (int num : destination) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出: Copied: 1 2 3 4 5

    //使用 std::copy_if
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> even_numbers;
    std::copy_if(numbers.begin(), numbers.end(), std::back_inserter(even_numbers), [](int n){ return n % 2 == 0; }); // back_inserter 用于动态增长容器

    std::cout << "Even numbers: ";
    for (int num : even_numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl; //输出：Even numbers: 2 4 6 8 10

  // 使用 std::transform 将每个元素乘以 2
  std::vector<int> transformed(source.size());
  std::transform(source.begin(), source.end(), transformed.begin(), [](int n){ return n * 2; });
  std::cout << "Transformed: ";
  for (int num : transformed) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出: Transformed: 2 4 6 8 10

  return 0;
}

4. 修改算法:

std::fill: 用给定的值填充指定范围内的元素。
std::generate: 用函数对象生成的值填充指定范围内的元素。
std::replace: 将指定范围内所有等于给定值的元素替换为另一个值。
std::remove: 从指定范围内移除所有等于给定值的元素（实际上是将不等于给定值的元素移动到范围的前面，并返回指向新范围末尾的迭代器）。需要配合 erase 使用才能真正删除。
std::unique: 从指定范围内移除相邻的重复元素（实际上是将不重复的元素移动到范围的前面，并返回指向新范围末尾的迭代器）。需要配合 erase 使用才能真正删除。

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

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

  // 使用 std::fill 填充
  std::fill(numbers.begin(), numbers.end(), 0);
  std::cout << "Filled: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出: Filled: 0 0 0 0 0

  // 使用 std::generate 生成随机数
  std::vector<int> randomNumbers(5);
  std::generate(randomNumbers.begin(), randomNumbers.end(), [](){ return std::rand() % 100; }); // 生成 0-99 之间的随机数
  std::cout << "Generated: ";
  for (int num : randomNumbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出类似: Generated: 41 18 46 79 2

  // 使用 std::replace 替换
  std::vector<int> data = {1, 2, 3, 2, 4, 2, 5};
  std::replace(data.begin(), data.end(), 2, 0);
  std::cout << "Replaced: ";
  for (int num : data) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出: Replaced: 1 0 3 0 4 0 5

  // 使用 std::remove 移除 (注意需要配合 erase)
  std::vector<int> data2 = {1, 2, 3, 2, 4, 2, 5};
  data2.erase(std::remove(data2.begin(), data2.end(), 2), data2.end());
  std::cout << "Removed: ";
  for (int num : data2) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出: Removed: 1 3 4 5

    //使用 std::unique 移除相邻重复元素(注意需要先排序，并且需要配合 erase)
    std::vector<int> numbers_unique = {1, 1, 2, 2, 2, 3, 4, 4, 5};
    auto last = std::unique(numbers_unique.begin(), numbers_unique.end());
    numbers_unique.erase(last, numbers_unique.end());

    std::cout << "Unique elements: ";
    for (int num : numbers_unique) {
        std::cout << num << " ";
    }
    std::cout << std::endl; // 输出: Unique elements: 1 2 3 4 5
  return 0;
}

5. 数值算法:

std::accumulate: 对指定范围内的元素求和。
std::inner_product: 计算两个序列的内积。
std::adjacent_difference: 计算序列中相邻元素的差值。
std::partial_sum: 计算序列的部分和。

#include <iostream>
#include <vector>
#include <numeric> // 包含数值算法

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

  // 使用 std::accumulate 求和
  int sum = std::accumulate(numbers.begin(), numbers.end(), 0); // 0 是初始值
  std::cout << "Sum: " << sum << std::endl; // 输出: Sum: 15

  //使用 std::inner_product 计算内积
  std::vector<int> a = {1, 2, 3};
  std::vector<int> b = {4, 5, 6};
  int inner_product = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 0 是初始值
  std::cout << "Inner product: " << inner_product << std::endl; // 输出: Inner product: 32  (1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32)

  return 0;
}

6. 集合算法:

std::set_union: 求两个已排序集合的并集。
std::set_intersection: 求两个已排序集合的交集。
std::set_difference: 求两个已排序集合的差集。
std::set_symmetric_difference: 求两个已排序集合的对称差集 (只属于一个集合的元素)。

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

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

  std::vector<int> union_set;
  std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(union_set));
  std::cout << "Union: ";
  for (int num : union_set) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出: Union: 1 2 3 4 5 6 7

  std::vector<int> intersection_set;
  std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(intersection_set));
  std::cout << "Intersection: ";
  for (int num : intersection_set) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出: Intersection: 3 4 5

  return 0;
}

7. 堆算法:

std::make_heap: 将指定范围内的元素转换为堆。
std::push_heap: 将一个元素添加到堆中。
std::pop_heap: 从堆中移除最大的元素（将其移动到范围的末尾）。
std::sort_heap: 对堆进行排序。

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

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

  // 创建堆
  std::make_heap(numbers.begin(), numbers.end());
  std::cout << "Heap: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出类似: Heap: 9 5 8 1 2 4

  // 添加元素到堆
  numbers.push_back(7);
  std::push_heap(numbers.begin(), numbers.end());
  std::cout << "Heap after push: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出类似: Heap after push: 9 7 8 1 2 4 5

  // 移除最大元素
  std::pop_heap(numbers.begin(), numbers.end());
  int maxElement = numbers.back();
  numbers.pop_back();
  std::cout << "Heap after pop: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出类似: Heap after pop: 8 7 5 1 2 4
  std::cout << "Max element: " << maxElement << std::endl; // 输出: Max element: 9

  // 排序堆
  std::sort_heap(numbers.begin(), numbers.end());
  std::cout << "Sorted Heap: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl; // 输出: Sorted Heap: 1 2 4 5 7 8
  return 0;
}

8. std::for_each:

对指定范围内的每个元素执行一个函数对象。

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

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

    std::cout << "Numbers multiplied by 2: ";
    std::for_each(numbers.begin(), numbers.end(), [](int& n){ n *= 2; std::cout << n << " "; });
    std::cout << std::endl; //输出：Numbers multiplied by 2: 2 4 6 8 10
    return 0;
}

关键点和注意事项:

迭代器 (Iterators): 大部分 STL 算法都使用迭代器作为输入，而不是直接使用容器。这使得算法可以与不同类型的容器一起工作，并可以对容器的一部分进行操作。
函数对象 (Function Objects) 和 Lambda 表达式: 许多算法接受函数对象或 lambda 表达式作为参数，以便自定义算法的行为。
谓词 (Predicates): 谓词是一种返回 bool 值的函数对象或 lambda 表达式，通常用于 find_if, remove_if, copy_if 等算法中。
复杂度: 了解每个算法的时间复杂度和空间复杂度非常重要，以便选择最适合特定任务的算法。例如，std::sort 通常是 O(N log N), std::find 在最坏情况下是 O(N), std::binary_search 是 O(log N)。
已排序范围的要求: std::binary_search, std::lower_bound, std::upper_bound, std::set_union, std::set_intersection 等算法要求输入范围已经排序。如果范围未排序，算法的行为是未定义的。
返回值: 仔细阅读每个算法的文档，了解其返回值。返回值可能是一个迭代器，指向特定位置，或是一个布尔值，表示是否找到了某个元素。
std::back_inserter: 当你向一个空容器或容量不足的容器复制元素时，可以使用 std::back_inserter 创建一个插入迭代器，该迭代器会调用容器的 push_back 方法，自动增加容器的大小。
remove 和 erase 的配合使用: std::remove 并不真正删除元素，而是将不等于给定值的元素移动到范围的前面，并返回指向新范围末尾的迭代器。要真正删除元素，你需要使用 容器.erase(std::remove(...), 容器.end())。
unique 和 erase 的配合使用: std::unique 类似 std::remove，需要和 erase 配合使用。而且 unique 只能移除相邻的重复元素，所以通常需要先 sort 再 unique。

如何选择合适的算法:

明确任务: 清楚地了解你需要完成的任务，例如搜索、排序、转换等。
分析数据: 了解数据的特征，例如是否已排序，是否需要保持相等元素的相对顺序等。
查看 STL 文档: 仔细阅读 STL 算法的文档，了解每个算法的功能、参数、返回值和复杂度。 https://en.cppreference.com/w/cpp/algorithm 是一个很好的参考。
选择最合适的算法: 根据任务、数据特征和算法复杂度，选择最合适的算法。
测试和优化: 编写测试用例来验证算法的正确性，并根据需要进行优化。