C++ STL 算法使用指南

探索C++标准模板库中的强大算法，提升编程效率与代码质量

概述
非修改序列操作
修改序列操作
排序与相关操作
数值算法
使用示例

STL算法概述

标准模板库(STL)提供了一系列强大的泛型算法，用于处理容器中的数据。这些算法通过迭代器与容器交互，提供高效的数据处理能力。

提示： STL算法通常定义在 <algorithm> 和 <numeric> 头文件中。

算法分类

算法特点

非修改序列操作

这些算法不会修改容器中的元素，主要用于搜索、计数和遍历操作。

find / find_if
非修改

在范围内查找特定元素或满足条件的元素。

find使用示例 
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        std::cout << "找到元素: " << *it << std::endl;
    }
    
    // 使用find_if查找第一个偶数
    auto even = std::find_if(v.begin(), v.end(), 
        [](int n) { return n % 2 == 0; });
    if (even != v.end()) {
        std::cout << "第一个偶数是: " << *even << std::endl;
    }
    return 0;
}
count / count_if
非修改

计算范围内满足特定条件的元素数量。

count使用示例 
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 3, 3};
    int count_three = std::count(v.begin(), v.end(), 3);
    std::cout << "3出现的次数: " << count_three << std::endl;
    
    int count_even = std::count_if(v.begin(), v.end(), 
        [](int n) { return n % 2 == 0; });
    std::cout << "偶数的个数: " << count_even << std::endl;
    return 0;
}

修改序列操作

这些算法会修改容器中的元素，包括复制、替换、填充等操作。

copy / copy_if
修改

将元素从一个范围复制到另一个范围，可选择满足条件的元素。

copy使用示例 
#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dest(5);
    
    // 复制整个范围
    std::copy(src.begin(), src.end(), dest.begin());
    
    // 复制满足条件的元素
    std::vector<int> even_nums;
    std::copy_if(src.begin(), src.end(), std::back_inserter(even_nums),
        [](int n) { return n % 2 == 0; });
    
    std::cout << "复制的偶数: ";
    for (int n : even_nums) std::cout << n << " ";
    return 0;
}
transform
修改

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

transform使用示例 
#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> squared;
    
    // 计算每个元素的平方
    std::transform(v.begin(), v.end(), std::back_inserter(squared),
        [](int n) { return n * n; });
    
    std::cout << "平方值: ";
    for (int n : squared) std::cout << n << " ";
    
    // 两个序列操作
    std::vector<int> v1 = {1,2,3,4,5};
    std::vector<int> v2 = {5,4,3,2,1};
    std::vector<int> result;
    
    std::transform(v1.begin(), v1.end(), v2.begin(), 
        std::back_inserter(result), std::plus<int>());
    
    std::cout << "\n相加结果: ";
    for (int n : result) std::cout << n << " ";
    return 0;
}

排序与相关操作

这些算法用于对容器中的元素进行排序、查找有序范围中的元素以及执行其他与排序相关的操作。

sort / stable_sort
排序

对范围内的元素进行排序，stable_sort 保持相等元素的相对顺序。

时间复杂度
O(n log n)
稳定性
sort: 不稳定
stable_sort: 稳定
sort使用示例 
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {5, 3, 1, 4, 2};
    
    // 默认升序排序
    std::sort(v.begin(), v.end());
    std::cout << "升序排序: ";
    for (int n : v) std::cout << n << " ";
    
    // 自定义排序函数 - 降序
    std::sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;
    });
    std::cout << "\n降序排序: ";
    for (int n : v) std::cout << n << " ";
    
    // 稳定排序
    std::vector<std::pair<int, char>> pairs = 
        {{1, 'a'}, {2, 'b'}, {1, 'c'}, {2, 'd'}};
        
    std::stable_sort(pairs.begin(), pairs.end(), 
        [](const auto& a, const auto& b) {
            return a.first < b.first;
        });
    
    std::cout << "\n稳定排序结果: ";
    for (const auto& p : pairs) 
        std::cout << p.first << p.second << " ";
    
    return 0;
}
binary_search / equal_range
二分查找

在已排序范围内执行二分查找操作，equal_range 返回匹配元素的范围。

时间复杂度
O(log n)
前提条件
范围必须已排序
二分查找示例 
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7};
    
    // 检查元素是否存在
    bool found = std::binary_search(v.begin(), v.end(), 4);
    std::cout << "4是否在数组中: " << std::boolalpha << found;
    
    // 查找元素范围
    auto range = std::equal_range(v.begin(), v.end(), 4);
    std::cout << "\n4的位置: [" 
              << range.first - v.begin() << ", "
              << range.second - v.begin() << ")";
    
    // 查找第一个不小于3的元素
    auto low = std::lower_bound(v.begin(), v.end(), 3);
    std::cout << "\n第一个不小于3的元素: " << *low;
    
    // 查找第一个大于4的元素
    auto up = std::upper_bound(v.begin(), v.end(), 4);
    std::cout << "\n第一个大于4的元素: " << *up;
    
    return 0;
}
partial_sort / nth_element
部分排序

partial_sort 对范围的前N个元素排序，nth_element 重新排列元素使第n个元素处于正确位置。

时间复杂度
平均O(n log k)
典型用途
Top N元素/中位数查找
部分排序示例 
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {9, 5, 2, 7, 1, 8, 3, 6, 4};
    
    // 获取前3个最小元素
    std::partial_sort(v.begin(), v.begin() + 3, v.end());
    std::cout << "前3个最小元素: ";
    for (int i = 0; i < 3; ++i) 
        std::cout << v[i] << " ";
    
    // 获取第5个元素（中位数）
    auto mid = v.begin() + v.size()/2;
    std::nth_element(v.begin(), mid, v.end());
    std::cout << "\n中位数: " << *mid;
    
    // 划分前5个最大元素
    std::partial_sort(v.begin(), v.begin() + 5, v.end(),
        [](int a, int b) { return a > b; });
    
    std::cout << "\n前5个最大元素: ";
    for (int i = 0; i < 5; ++i) 
        std::cout << v[i] << " ";
    
    return 0;
}
partition / stable_partition
划分

根据谓词将元素分为两组，stable_partition 保持元素相对顺序。

提示： partition 常用于快速排序算法和按条件分组数据。

划分示例 
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // 将偶数移到前面
    auto it = std::partition(v.begin(), v.end(),
        [](int n) { return n % 2 == 0; });
    
    std::cout << "划分结果: ";
    std::cout << "\n偶数: ";
    for (auto i = v.begin(); i != it; ++i) 
        std::cout << *i << " ";
    
    std::cout << "\n奇数: ";
    for (auto i = it; i != v.end(); ++i) 
        std::cout << *i << " ";
    
    // 稳定划分 - 保持相对顺序
    std::vector<int> v2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto it2 = std::stable_partition(v2.begin(), v2.end(),
        [](int n) { return n > 5; });
    
    std::cout << "\n稳定划分(>5): ";
    for (int n : v2) std::cout << n << " ";
    
    return 0;
}

数值算法

这些算法用于执行数值计算操作，包括累加、内积、部分和等。

accumulate
数值

计算范围内元素的累加值或自定义二元操作的累积结果。

时间复杂度
O(n)
头文件
<numeric>
accumulate使用示例 
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 基本求和
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "元素总和: " << sum;
    
    // 自定义操作 - 乘积
    int product = std::accumulate(v.begin(), v.end(), 1, 
        [](int a, int b) { return a * b; });
    std::cout << "\n元素乘积: " << product;
    
    // 字符串连接
    std::vector<std::string> words = {"Hello", " ", "World", "!"};
    std::string sentence = std::accumulate(words.begin(), words.end(), 
        std::string(""));
    std::cout << "\n连接结果: " << sentence;
    
    // 计算平均值
    double avg = std::accumulate(v.begin(), v.end(), 0.0) / v.size();
    std::cout << "\n平均值: " << avg;
    
    return 0;
}
inner_product
数值

计算两个范围的內积（点积）或自定义二元操作的累积结果。

提示： 除了数学应用，inner_product 还可用于计算两组数据的相关性。

inner_product使用示例 
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::vector<int> b = {5, 4, 3, 2, 1};
    
    // 基本点积
    int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);
    std::cout << "点积: " << dot;
    
    // 自定义操作 - 计算曼哈顿距离
    int manhattan = std::inner_product(a.begin(), a.end(), b.begin(), 0,
        std::plus<int>(), 
        [](int x, int y) { return std::abs(x - y); });
    std::cout << "\n曼哈顿距离: " << manhattan;
    
    // 计算欧几里得距离平方
    int euclidean_sq = std::inner_product(a.begin(), a.end(), b.begin(), 0,
        std::plus<int>(), 
        [](int x, int y) { 
            int diff = x - y; 
            return diff * diff; 
        });
    std::cout << "\n欧几里得距离平方: " << euclidean_sq;
    
    return 0;
}
partial_sum / adjacent_difference
数值

partial_sum 计算部分和，adjacent_difference 计算相邻元素的差。

时间复杂度
O(n)
应用场景
时间序列分析/数据压缩
部分和与差分示例 
#include <numeric>
#include <vector>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> v = {2, 3, 5, 7, 11};
    std::vector<int> result;
    
    // 计算部分和
    std::partial_sum(v.begin(), v.end(), 
        std::back_inserter(result));
    std::cout << "部分和: ";
    for (int n : result) std::cout << n << " ";
    
    // 重置结果向量
    result.clear();
    
    // 计算相邻差
    std::adjacent_difference(v.begin(), v.end(), 
        std::back_inserter(result));
    std::cout << "\n相邻差: ";
    for (int n : result) std::cout << n << " ";
    
    // 自定义操作 - 计算斐波那契数列
    std::vector<int> fib(10, 1);
    std::adjacent_difference(fib.begin(), fib.end()-1, 
        fib.begin()+1, std::plus<int>());
    std::cout << "\n斐波那契数列: ";
    for (int n : fib) std::cout << n << " ";
    
    return 0;
}
iota
数值

用连续递增的值填充范围，从指定值开始。

iota使用示例 
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v(10);
    
    // 填充1到10
    std::iota(v.begin(), v.end(), 1);
    std::cout << "1到10: ";
    for (int n : v) std::cout << n << " ";
    
    // 创建索引序列
    std::vector<size_t> indices(5);
    std::iota(indices.begin(), indices.end(), 0);
    std::cout << "\n索引序列: ";
    for (size_t i : indices) std::cout << i << " ";
    
    // 生成字母序列
    std::vector<char> letters(26);
    std::iota(letters.begin(), letters.end(), 'A');
    std::cout << "\n大写字母: ";
    for (char c : letters) std::cout << c << " ";
    
    return 0;
}

算法使用示例

实际应用场景中算法的综合使用案例。

数据处理流程

数据处理示例 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    // 1. 创建数据集
    std::vector<int> data = {7, 3, 5, 1, 9, 2, 8, 4, 6};
    
    // 2. 排序数据
    std::sort(data.begin(), data.end());
    std::cout << "排序后: ";
    for (int n : data) std::cout << n << " ";
    
    // 3. 查找中位数
    auto mid = data.begin() + data.size()/2;
    std::nth_element(data.begin(), mid, data.end());
    std::cout << "\n中位数: " << *mid;
    
    // 4. 移除小于5的元素
    auto new_end = std::remove_if(data.begin(), data.end(),
                                [](int n) { return n < 5; });
    data.erase(new_end, data.end());
    
    std::cout << "\n大于等于5的元素: ";
    for (int n : data) std::cout << n << " ";
    
    // 5. 计算平均值
    double avg = std::accumulate(data.begin(), data.end(), 0.0) / data.size();
    std::cout << "\n平均值: " << avg;
    
    // 6. 查找最大值和最小值
    auto minmax = std::minmax_element(data.begin(), data.end());
    std::cout << "\n最小值: " << *minmax.first;
    std::cout << "\n最大值: " << *minmax.second;
    
    return 0;
}

自定义对象处理

自定义对象示例 
#include <iostream>
#include <vector>
#include <algorithm>

struct Student {
    std::string name;
    int score;
    
    Student(std::string n, int s) : name(n), score(s) {}
    
    bool operator<(const Student& other) const {
        return score < other.score;
    }
};

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 76},
        {"Charlie", 92},
        {"David", 68}
    };
    
    // 按分数排序
    std::sort(students.begin(), students.end());
    
    std::cout << "按分数排序:\n";
    for (const auto& s : students) {
        std::cout << s.name << ": " << s.score << "\n";
    }
    
    // 查找分数大于80的学生
    auto it = std::find_if(students.begin(), students.end(),
                          [](const Student& s) { return s.score > 80; });
    
    std::cout << "\n分数大于80的学生:\n";
    while (it != students.end()) {
        std::cout << it->name << ": " << it->score << "\n";
        it = std::find_if(std::next(it), students.end(),
                         [](const Student& s) { return s.score > 80; });
    }
    
    // 计算平均分
    int total = std::accumulate(students.begin(), students.end(), 0,
                               [](int sum, const Student& s) { 
                                   return sum + s.score; 
                               });
    double average = static_cast<double>(total) / students.size();
    std::cout << "\n平均分: " << average;
    
    return 0;
}

C++ STL 算法使用指南 © 2023 | 提供高效、现代的C++编程解决方案

返回顶部 返回主页