算法

ZaynPei Lv6
  2025-10-20 16:00 2025-10-20 16:00 Created   2025-11-08 13:54:24 2025-11-08 13:54:24 Updated      4k Words  17 Mins

算法（Algorithm）是解决特定问题的一系列步骤或规则的集合。在计算机科学中，算法通常用于处理数据、执行计算和解决各种问题。C++ 标准库（STL）提供了丰富的算法支持，涵盖了排序、搜索、修改等多种操作。

std::sort：最常用的排序算法

这是最常使用的排序算法

  • 特点：速度极快，但不保证稳定性。
  • 底层实现：通常是内省排序 (Introsort)，一种混合排序算法。它首先使用快速排序，当递归深度过深时转为堆排序以防止最坏情况，最后对小分区使用插入排序进行优化。
  • 时间复杂度：平均为 O(NlogN)。

它的函数签名如下: 

1
2
3
4
5
template< class RandomIt >
void sort( RandomIt first, RandomIt last );  // RandomIt 必须是随机访问迭代器, 参数是迭代器的范围 [first, last)

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );  // 使用自定义比较函数 comp, 可以是函数指针或函数对象

这里重点介绍第二个版本, 它允许我们传入一个自定义的比较函数 comp, 常常使用lambda表达式来定义排序规则。

这个比较函数接受两个参数, 返回一个布尔值, 用于定义排序的顺序。 例如, 如果我们想要按降序排序一个整数数组, 可以这样写: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <vector>
#include <iostream>

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

    // 使用自定义比较函数进行降序排序
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
        return a > b;
    });

    // 输出排序结果
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    return 0;
}

返回的布尔值表示: 如果 comp(a, b) 返回 true, 则 a 应该排在 b 前面。

std::reverse：反转序列

std::reverse 是 C++ STL 中用于反转一个范围内元素顺序的算法。它定义在 头文件中。使用时只需提供要反转的范围的迭代器。

函数签名如下: 

1
2
template< class BidirIt >
void reverse( BidirIt first, BidirIt last );
- BidirIt: 双向迭代器类型，表示可以向前和向后遍历的迭代器。 - first: 指向要反转范围的起始位置的迭代器（包含该位置）。 - last: 指向要反转范围的结束位置的迭代器（不包含该位置）。

该函数会将 [first, last) 范围内的元素顺序进行反转。例如: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 反转整个向量
    std::reverse(vec.begin(), vec.end());

    // 输出反转后的结果
    for (const auto& elem : vec) {
        std::cout << elem << " "; // 输出: 5 4 3 2 1
    }
    return 0;
}

std::accumulate：累加求和

std::accumulate 是 C++ STL 中用于计算范围内元素累加和的算法。它定义在 头文件中。使用时需要提供要累加的范围的迭代器以及一个初始值。 函数签名如下: 

1
2
template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );
- InputIt: 输入迭代器类型，表示可以读取元素的迭代器。 - first: 指向要累加范围的起始位置的迭代器（包含该位置）。 - last: 指向要累加范围的结束位置的迭代器（不包含该位置）。 - init: 累加的初始值。

该函数会将 [first, last) 范围内的元素与初始值 init 进行累加，并返回最终的结果。例如: 

1
2
3
4
5
6
7
8
9
10
11
12
#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 计算向量元素的累加和，初始值为0
    int sum = std::accumulate(vec.begin(), vec.end(), 0);

    std::cout << "Sum: " << sum << std::endl; // 输出: Sum: 15
    return 0;
}

std::advance：迭代器前进

std::advance 是 C++ STL 中用于将迭代器前进或后退指定步数的算法。它定义在 <iterator> 头文件中。使用时需要提供一个迭代器和一个整数值，表示要前进（正值）或后退（负值）的步数。

函数签名如下: 

1
2
template< class InputIt, class Distance >
void advance( InputIt& it, Distance n );
- InputIt: 迭代器类型，表示可以读取元素的迭代器。 - it: 要前进或后退的迭代器引用。 - n: 要前进（正值）或后退（负值）的步数。 该函数会将迭代器 it 前进或后退 n 步。例如: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iterator>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};
    auto it = vec.begin();

    // 将迭代器前进2步
    std::advance(it, 2);
    std::cout << "Element after advancing 2 steps: " << *it << std::endl; // 输出: 30

    // 将迭代器后退1步
    std::advance(it, -1);
    std::cout << "Element after retreating 1 step: " << *it << std::endl; // 输出: 20

    return 0;
}

std::count：计数元素出现次数

std::count 是 C++ STL 中用于计算范围内某个特定值出现次数的算法。它定义在 头文件中。使用时需要提供要搜索的范围的迭代器以及要计数的值。

函数签名如下: 

1
2
3
template< class InputIt, class T >
typename std::iterator_traits<InputIt>::difference_type
count( InputIt first, InputIt last, const T& value );
- InputIt: 输入迭代器类型，表示可以读取元素的迭代器。 - first: 指向要搜索范围的起始位置的迭代器（包含该位置）。 - last: 指向要搜索范围的结束位置的迭代器（不包含该位置）。 - value: 要计数的特定值。 - 返回值: 范围内等于 value 的元素数量。

该函数会计算并返回 [first, last) 范围内等于 value 的元素数量。例如: 

1
2
3
4
5
6
7
8
9
10
11
12
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};

    // 计算数字2在向量中出现的次数
    int count_of_2 = std::count(vec.begin(), vec.end(), 2);

    std::cout << "Count of 2: " << count_of_2 << std::endl; // 输出: Count of 2: 3
    return 0;
}

std::find：查找元素

std::find 是 C++ STL 中用于在范围内查找特定值的算法。它定义在 头文件中。使用时需要提供要搜索的范围的迭代器以及要查找的值。

函数签名如下: 

1
2
template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );
- InputIt: 输入迭代器类型，表示可以读取元素的迭代器。 - first: 指向要搜索范围的起始位置的迭代器（包含该位置）。 - last: 指向要搜索范围的结束位置的迭代器（不包含该位置）。 - value: 要查找的特定值。 - 返回值: 指向第一个等于 value 的元素的迭代器；如果未找到，则返回 last。 该函数会在 [first, last) 范围内查找第一个等于 value 的元素，并返回其迭代器。例如: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // 查找数字30在向量中的位置
    auto it = std::find(vec.begin(), vec.end(), 30);

    if (it != vec.end()) {
        std::cout << "Found 30 at position: " << std::distance(vec.begin(), it) << std::endl; // 输出: Found 30 at position: 2
    } else {
        std::cout << "30 not found in the vector." << std::endl;
    }
    return 0;
}

std::transform：转换元素

std::transform 是 C++ STL 中用于对范围内的元素应用指定操作并将结果存储到另一个范围的算法。它定义在 头文件中。使用时需要提供要转换的范围的迭代器、目标范围的起始迭代器以及一个函数或函数对象。

函数签名如下: 

1
2
3
template< class InputIt, class OutputIt, class UnaryOperation >
OutputIt transform( InputIt first1, InputIt last1,
                      OutputIt d_first, UnaryOperation unary_op );
- InputIt: 输入迭代器类型，表示可以读取元素的迭代器。 - OutputIt: 输出迭代器类型，表示可以写入元素的迭代器。 - UnaryOperation: 一元操作函数或函数对象类型。 - first1: 指向要转换范围的起始位置的迭代器（包含该位置）。 - last1: 指向要转换范围的结束位置的迭代器（不包含该位置）。 - d_first: 指向目标范围起始位置的迭代器。 - unary_op: 应用于每个元素的一元操作函数或函数对象。

该函数会对 [first1, last1) 范围内的每个元素应用 unary_op，并将结果存储到从 d_first 开始的目标范围中。例如: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> result(vec.size());

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

    // 输出转换后的结果
    for (const auto& elem : result) {
        std::cout << elem << " "; // 输出: 2 4 6 8 10
    }
    return 0;
}

std::unique：移除重复元素

std::unique 是 C++ STL 中用于移除范围内连续重复元素的算法。它定义在 头文件中。使用时需要提供要处理的范围的迭代器。 函数签名如下: 

1
2
template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );
- ForwardIt: 前向迭代器类型，表示可以向前遍历的迭代器。 - first: 指向要处理范围的起始位置的迭代器（包含该位置）。 - last: 指向要处理范围的结束位置的迭代器（不包含该位置）。 - 返回值: 指向新范围结束位置的迭代器。 该函数会移除 [first, last) 范围内的连续重复元素，并返回新范围的结束位置。例如: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 4, 5};

    // 移除连续重复元素
    auto new_end = std::unique(vec.begin(), vec.end());

    // 输出处理后的结果
    for (auto it = vec.begin(); it != new_end; ++it) {
        std::cout << *it << " "; // 输出: 1 2 3 4 5
    }
    return 0;
}
如果要对整个容器进行去重，通常会先对容器进行排序，然后再调用 std::unique，最后使用容器的 erase 方法删除多余的元素。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {4, 2, 1, 3, 2, 4, 5, 1};

    // 先排序
    std::sort(vec.begin(), vec.end());

    // 移除重复元素
    auto new_end = std::unique(vec.begin(), vec.end());

    // 删除多余的元素
    vec.erase(new_end, vec.end());

    // 输出去重后的结果
    for (const auto& elem : vec) {
        std::cout << elem << " "; // 输出: 1 2 3 4 5
    }
    return 0;
}

std::lower_bound 和 std::upper_bound

std::lower_bound 和 std::upper_bound 是 C++ STL 中用于在有序范围内查找元素位置的算法。它们定义在 头文件中。使用时需要提供要搜索的范围的迭代器以及要查找的值。 函数签名如下: 

1
2
3
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
- ForwardIt: 前向迭代器类型，表示可以向前遍历的迭代器。 - first: 指向要搜索范围的起始位置的迭代器（包含该位置）。 - last: 指向要搜索范围的结束位置的迭代器（不包含该位置）。 - value: 要查找的特定值。 - 返回值: - lower_bound 返回指向第一个大于等于 value 的元素的迭代器。 - upper_bound 返回指向第一个大于 value 的元素的迭代器。 - 如果未找到符合条件的元素，则返回 last。

它们的名字看上去都“往上找”，但为什么一个叫 lower（下界）、一个叫 upper（上界） 呢？ 这个名字来源于数学中的“上下确界”概念: - lower_bound 找到的是“下确界”（greatest lower bound），即第一个大于等于给定值的元素位置。 - upper_bound 找到的是“上确界”（least upper bound），即第一个大于给定值的元素位置。 例如: v = {1, 3, 3, 5, 7} - 对于 value = 3, lower_bound 返回指向第一个 3 的迭代器, 即索引1的位置(3的下边界) - 假如你要插入value, lower_bound 找到的是可以放下 value 的最早位置（lower edge） - 而 upper_bound 返回指向第一个大于3的元素5的迭代器, 即索引3的位置(3的上边界, 不包含3本身) - 假如你要插入value, upper_bound 找到的是 value “延伸结束”的上边界（upper edge）

这两个函数通常用于有序范围内的二分查找。例如: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5, 6, 8};

    int value = 4;

    // 查找 lower_bound
    auto lower = std::lower_bound(vec.begin(), vec.end(), value);
    std::cout << "Lower bound of " << value << " is at position: " 
              << std::distance(vec.begin(), lower) << std::endl; // 输出: 2(索引位置), 即第一个4的位置

    // 查找 upper_bound
    auto upper = std::upper_bound(vec.begin(), vec.end(), value);
    std::cout << "Upper bound of " << value << " is at position: " 
              << std::distance(vec.begin(), upper) << std::endl; // 输出: 4(索引位置), 即第一个大于4的元素的位置

    return 0;
}

std:: min_element 和 std:: max_element

std::min_element 和 std::max_element 是 C++ STL 中用于查找范围内最小和最大元素的算法, 返回最值对应的迭代器。它们定义在 头文件中。使用时需要提供要搜索的范围的迭代器。其内部使用线性搜索算法来查找最小和最大元素, 复杂度为 O(N)。

函数签名如下: 

1
2
3
template< class ForwardIt >
ForwardIt min_element( ForwardIt first, ForwardIt last );
ForwardIt max_element( ForwardIt first, ForwardIt last );
- ForwardIt: 前向迭代器类型，表示可以向前遍历的迭代器。 - first: 指向要搜索范围的起始位置的迭代器（包含该位置）。 - last: 指向要搜索范围的结束位置的迭代器（不包含该位置）。 - 返回值: - min_element 返回指向范围内最小元素的迭代器。 - max_element 返回指向范围内最大元素的迭代器。 - 如果范围为空，则返回 last。

例如: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {5, 2, 8, 1, 3};

    // 查找最小元素
    auto min_it = std::min_element(vec.begin(), vec.end());
    if (min_it != vec.end()) {
        std::cout << "Minimum element: " << *min_it << std::endl; // 输出: 1
    }

    // 查找最大元素
    auto max_it = std::max_element(vec.begin(), vec.end());
    if (max_it != vec.end()) {
        std::cout << "Maximum element: " << *max_it << std::endl; // 输出: 8
    }

    return 0;
}

std::min和 std::max

std::min和std::max已经是耳熟能详的函数, 不过需要注意的是, 他们不仅可以比较两个值, 还可以接受一个初始化列表, 用于比较多个值: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <iostream>
int main() {
    int a = 10, b = 20, c = 5;

    // 比较两个值
    int min_val = std::min(a, b);
    int max_val = std::max(a, b);
    std::cout << "Min of " << a << " and " << b << " is: " << min_val << std::endl; // 输出: 10
    std::cout << "Max of " << a << " and " << b << " is: " << max_val << std::endl; // 输出: 20

    // 比较多个值
    int min_of_three = std::min({a, b, c});
    int max_of_three = std::max({a, b, c});
    std::cout << "Min of " << a << ", " << b << ", and " << c << " is: " << min_of_three << std::endl; // 输出: 5
    std::cout << "Max of " << a << ", " << b << ", and " << c << " is: " << max_of_three << std::endl; // 输出: 20

    return 0;
}

std::count

std::count 是 C++ STL 中用于计算范围内特定元素出现次数的算法。它定义在 头文件中。使用时需要提供要搜索的范围的迭代器以及要查找的值。 函数签名如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template< class InputIt, class T >
typename std::iterator_traits<InputIt>::difference_type
count( InputIt first, InputIt last, const T& value );
- InputIt: 输入迭代器类型，表示可以读取元素的迭代器。
- first: 指向要搜索范围的起始位置的迭代器（包含该位置）。
- last: 指向要搜索范围的结束位置的迭代器（不包含该位置）。
- value: 要查找的特定值。
- 返回值: 范围内等于 `value` 的元素数量。
该函数会计算并返回 `[first, last)` 范围内等于 `value` 的元素数量。例如:
```cpp
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};

    // 计算数字2在向量中出现的次数
    int count_of_2 = std::count(vec.begin(), vec.end(), 2);

    std::cout << "Count of 2: " << count_of_2 << std::endl; // 输出: Count of 2: 3
    return 0;
}

On this page
算法
  1. std::sort：最常用的排序算法
  2. std::reverse：反转序列
  3. std::accumulate：累加求和
  4. std::advance：迭代器前进
  5. std::count：计数元素出现次数
  6. std::find：查找元素
  7. std::transform：转换元素
  8. std::unique：移除重复元素
  9. std::lower_bound 和 std::upper_bound
  10. std:: min_element 和 std:: max_element
    1. std::min和 std::max
  11. std::count