C++ STL中常用算法怎么使用

# C++ STL中常用算法怎么使用

## 1. 概述

标准模板库(STL)是C++中最重要的组成部分之一，它提供了丰富的容器、算法和迭代器。STL算法主要定义在`<algorithm>`头文件中，这些算法可以对容器中的元素进行各种操作，如排序、查找、遍历等。STL算法的优势在于：

1. **高度通用性**：通过迭代器与各种容器配合工作
2. **高效实现**：底层经过充分优化
3. **减少代码量**：避免重复编写常见操作

## 2. 常用算法分类

### 2.1 非修改序列算法

不改变容器内容的算法：

```cpp
#include <algorithm>
#include <vector>

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

// 查找算法
auto it = std::find(v.begin(), v.end(), 3);  // 查找值为3的元素

// 计数算法
int cnt = std::count(v.begin(), v.end(), 2);  // 统计值为2的元素个数

// 遍历算法
std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
});

2.2 修改序列算法

会改变容器内容的算法：

// 填充算法
std::fill(v.begin(), v.end(), 0);  // 将所有元素设为0

// 复制算法
std::vector<int> dest(v.size());
std::copy(v.begin(), v.end(), dest.begin());

// 移除算法
auto new_end = std::remove(v.begin(), v.end(), 3);  // 移除所有3
v.erase(new_end, v.end());  // 实际删除元素

2.3 排序和相关算法

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

// 排序算法
std::sort(nums.begin(), nums.end());  // 默认升序

// 二分查找
bool found = std::binary_search(nums.begin(), nums.end(), 3);

// 合并两个有序序列
std::vector<int> nums2 = {6, 7, 8};
std::vector<int> merged(nums.size() + nums2.size());
std::merge(nums.begin(), nums.end(), 
           nums2.begin(), nums2.end(),
           merged.begin());

2.4 数值算法

#include <numeric>

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

// 累加
int sum = std::accumulate(v.begin(), v.end(), 0);

// 内积
std::vector<int> v2 = {2, 3, 4, 5, 6};
int product = std::inner_product(v.begin(), v.end(), v2.begin(), 0);

// 部分和
std::vector<int> partial(v.size());
std::partial_sum(v.begin(), v.end(), partial.begin());

3. 核心算法详解

3.1 std::sort

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

// 默认升序排序
std::sort(v.begin(), v.end());

// 自定义排序规则
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;  // 降序排序
});

// 对结构体排序
struct Person {
    std::string name;
    int age;
};
std::vector<Person> people = {{"Alice", 25}, {"Bob", 20}};
std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age < b.age;
});

3.2 std::find和std::find_if

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

// 查找特定值
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {
    std::cout << "Found: " << *it << std::endl;
}

// 使用谓词查找
auto even = std::find_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});
if (even != v.end()) {
    std::cout << "First even: " << *even << std::endl;
}

3.3 std::transform

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

// 对每个元素进行转换
std::transform(v.begin(), v.end(), squared.begin(), [](int x) {
    return x * x;
});

// 两个序列操作
std::vector<int> v2 = {2, 3, 4, 5, 6};
std::vector<int> result(v.size());
std::transform(v.begin(), v.end(), v2.begin(), result.begin(), 
    [](int a, int b) { return a + b; });

3.4 std::accumulate

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

// 基本求和
int sum = std::accumulate(v.begin(), v.end(), 0);

// 自定义操作
int product = std::accumulate(v.begin(), v.end(), 1, 
    [](int a, int b) { return a * b; });

// 字符串连接
std::vector<std::string> words = {"Hello", " ", "World"};
std::string sentence = std::accumulate(words.begin(), words.end(), 
    std::string());

4. 算法使用技巧

4.1 使用lambda表达式

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

// 使用lambda作为谓词
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;
});

// 捕获外部变量
int threshold = 3;
auto count = std::count_if(v.begin(), v.end(), [threshold](int x) {
    return x > threshold;
});

4.2 算法组合使用

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

// 先排序再去重
std::sort(v.begin(), v.end());
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end());

// 查找并处理
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {
    *it = 30;  // 修改找到的元素
}

4.3 自定义比较函数

struct Point {
    int x, y;
};

std::vector<Point> points = {{1, 2}, {3, 1}, {2, 3}};

// 按x坐标排序
std::sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
    return a.x < b.x;
});

// 多条件排序
std::sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
});

5. 性能考虑

1. 算法复杂度：

   • std::sort: O(N log N)
   • std::find: O(N)
   • std::binary_search: O(log N)

2. 内存局部性：连续存储容器(如vector)通常比链表(list)性能更好

3. 避免不必要的拷贝： “`cpp // 不佳的实现 std::vector copy = original; std::sort(copy.begin(), copy.end());

// 更好的实现(原地排序) std::sort(original.begin(), original.end());

## 6. 实际应用示例

### 6.1 统计文本词频

```cpp
std::vector<std::string> words = {"apple", "banana", "apple", "cherry"};
std::map<std::string, int> word_count;

std::for_each(words.begin(), words.end(), [&](const std::string& word) {
    word_count[word]++;
});

6.2 过滤容器元素

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

std::copy_if(numbers.begin(), numbers.end(), 
             std::back_inserter(evens),
             [](int x) { return x % 2 == 0; });

6.3 并行算法(C++17)

#include <execution>

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

// 并行排序
std::sort(std::execution::par, v.begin(), v.end());

// 并行遍历
std::for_each(std::execution::par, v.begin(), v.end(), [](int& x) {
    x *= 2;
});

7. 总结

STL算法是C++编程中不可或缺的工具，掌握它们可以显著提高开发效率和代码质量。关键点包括：

1. 理解迭代器概念和算法适用范围
2. 熟练使用lambda表达式自定义算法行为
3. 了解不同算法的复杂度特性
4. 合理组合算法完成复杂任务
5. 在C++17及以上版本中考虑使用并行算法

通过实践这些算法，你将能够编写出更简洁、高效和可维护的C++代码。

8. 进一步学习资源

1. 《Effective STL》 by Scott Meyers
2. 《The C++ Standard Library》 by Nicolai Josuttis
3. C++官方文档：https://en.cppreference.com/w/cpp/algorithm
4. C++ Core Guidelines：https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines

”`