C++ STL 算法

概述

STL算法库提供了丰富的通用算法，这些算法可以作用于不同的容器和数据结构。算法通过迭代器与容器解耦，实现了高度的可重用性。本章介绍查找、排序、修改、数值算法等常用STL算法。

🔍 查找算法

基础查找

cpp

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

class SearchAlgorithms {
public:
    static void basicSearch() {
        std::cout << "=== 基础查找算法 ===" << std::endl;
        
        std::vector<int> vec{1, 3, 5, 7, 9, 11, 13, 15};
        
        // find - 查找元素
        auto it = std::find(vec.begin(), vec.end(), 7);
        if (it != vec.end()) {
            std::cout << "找到7，位置: " << std::distance(vec.begin(), it) << std::endl;
        }
        
        // find_if - 条件查找
        auto it2 = std::find_if(vec.begin(), vec.end(), [](int x) {
            return x > 10;
        });
        if (it2 != vec.end()) {
            std::cout << "第一个大于10的数: " << *it2 << std::endl;
        }
        
        // count - 计数
        std::vector<int> vec2{1, 2, 3, 2, 4, 2, 5};
        int count = std::count(vec2.begin(), vec2.end(), 2);
        std::cout << "数字2出现次数: " << count << std::endl;
        
        // count_if - 条件计数
        int even_count = std::count_if(vec2.begin(), vec2.end(), [](int x) {
            return x % 2 == 0;
        });
        std::cout << "偶数个数: " << even_count << std::endl;
    }
    
    static void binarySearch() {
        std::cout << "\n=== 二分查找算法 ===" << std::endl;
        
        std::vector<int> sorted_vec{1, 3, 5, 7, 9, 11, 13, 15};
        
        // binary_search - 二分查找存在性
        bool found = std::binary_search(sorted_vec.begin(), sorted_vec.end(), 7);
        std::cout << "7是否存在: " << (found ? "是" : "否") << std::endl;
        
        // lower_bound - 查找第一个不小于目标的元素
        auto lb = std::lower_bound(sorted_vec.begin(), sorted_vec.end(), 7);
        std::cout << "lower_bound(7): " << *lb << std::endl;
        
        // upper_bound - 查找第一个大于目标的元素
        auto ub = std::upper_bound(sorted_vec.begin(), sorted_vec.end(), 7);
        std::cout << "upper_bound(7): " << *ub << std::endl;
        
        // equal_range - 获取相等元素的范围
        auto range = std::equal_range(sorted_vec.begin(), sorted_vec.end(), 7);
        std::cout << "equal_range(7): [" << *range.first << ", " << *range.second << ")" << std::endl;
    }
    
    static void searchPatterns() {
        std::cout << "\n=== 模式查找 ===" << std::endl;
        
        std::vector<int> haystack{1, 2, 3, 4, 5, 6, 7, 8, 9};
        std::vector<int> needle{4, 5, 6};
        
        // search - 查找子序列
        auto it = std::search(haystack.begin(), haystack.end(), 
                             needle.begin(), needle.end());
        if (it != haystack.end()) {
            std::cout << "找到子序列，起始位置: " << std::distance(haystack.begin(), it) << std::endl;
        }
        
        // search_n - 查找连续n个相同元素
        std::vector<int> vec{1, 1, 2, 2, 2, 3, 3};
        auto it2 = std::search_n(vec.begin(), vec.end(), 3, 2);
        if (it2 != vec.end()) {
            std::cout << "找到连续3个2，起始位置: " << std::distance(vec.begin(), it2) << std::endl;
        }
        
        // adjacent_find - 查找相邻重复元素
        auto it3 = std::adjacent_find(vec.begin(), vec.end());
        if (it3 != vec.end()) {
            std::cout << "第一个重复元素: " << *it3 << std::endl;
        }
    }
};

int main() {
    SearchAlgorithms::basicSearch();
    SearchAlgorithms::binarySearch();
    SearchAlgorithms::searchPatterns();
    
    return 0;
}

🔄 排序算法

排序和分区

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

class SortingAlgorithms {
public:
    static void basicSorting() {
        std::cout << "=== 基础排序算法 ===" << std::endl;
        
        std::vector<int> vec{64, 34, 25, 12, 22, 11, 90};
        
        std::cout << "原始数据: ";
        printVector(vec);
        
        // sort - 快速排序
        std::vector<int> vec1 = vec;
        std::sort(vec1.begin(), vec1.end());
        std::cout << "sort结果: ";
        printVector(vec1);
        
        // stable_sort - 稳定排序
        std::vector<std::pair<int, char>> pairs{
            {3, 'a'}, {1, 'b'}, {3, 'c'}, {2, 'd'}
        };
        
        std::stable_sort(pairs.begin(), pairs.end(), 
            [](const auto& a, const auto& b) {
                return a.first < b.first;
            });
        
        std::cout << "stable_sort结果: ";
        for (const auto& p : pairs) {
            std::cout << "(" << p.first << "," << p.second << ") ";
        }
        std::cout << std::endl;
        
        // partial_sort - 部分排序
        std::vector<int> vec2 = vec;
        std::partial_sort(vec2.begin(), vec2.begin() + 3, vec2.end());
        std::cout << "partial_sort前3个: ";
        printVector(vec2);
    }
    
    static void customSorting() {
        std::cout << "\n=== 自定义排序 ===" << std::endl;
        
        struct Student {
            std::string name;
            int age;
            double gpa;
        };
        
        std::vector<Student> students{
            {"Alice", 20, 3.8},
            {"Bob", 19, 3.9},
            {"Charlie", 21, 3.7},
            {"David", 20, 3.85}
        };
        
        // 按年龄排序
        std::sort(students.begin(), students.end(), 
            [](const Student& a, const Student& b) {
                return a.age < b.age;
            });
        
        std::cout << "按年龄排序:" << std::endl;
        for (const auto& s : students) {
            std::cout << s.name << " (" << s.age << ") ";
        }
        std::cout << std::endl;
        
        // 多条件排序
        std::sort(students.begin(), students.end(), 
            [](const Student& a, const Student& b) {
                if (a.age != b.age) return a.age < b.age;
                return a.gpa > b.gpa;  // 年龄相同时按GPA降序
            });
        
        std::cout << "多条件排序:" << std::endl;
        for (const auto& s : students) {
            std::cout << s.name << " (" << s.age << ", " << s.gpa << ") ";
        }
        std::cout << std::endl;
    }
    
    static void partitioning() {
        std::cout << "\n=== 分区算法 ===" << std::endl;
        
        std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        
        // partition - 分区
        auto pivot = std::partition(vec.begin(), vec.end(), [](int x) {
            return x % 2 == 0;  // 偶数在前
        });
        
        std::cout << "partition结果: ";
        printVector(vec);
        std::cout << "分界点: " << std::distance(vec.begin(), pivot) << std::endl;
        
        // stable_partition - 稳定分区
        std::vector<int> vec2{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        auto pivot2 = std::stable_partition(vec2.begin(), vec2.end(), [](int x) {
            return x % 2 == 0;
        });
        
        std::cout << "stable_partition结果: ";
        printVector(vec2);
        
        // nth_element - 第n个元素
        std::vector<int> vec3{64, 34, 25, 12, 22, 11, 90};
        std::nth_element(vec3.begin(), vec3.begin() + 3, vec3.end());
        std::cout << "第4小的元素: " << vec3[3] << std::endl;
    }
    
private:
    static void printVector(const std::vector<int>& vec) {
        for (int n : vec) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
};

🔧 修改算法

变换和生成

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>

class ModifyingAlgorithms {
public:
    static void transformation() {
        std::cout << "=== 变换算法 ===" << std::endl;
        
        std::vector<int> src{1, 2, 3, 4, 5};
        std::vector<int> dest(src.size());
        
        // transform - 变换
        std::transform(src.begin(), src.end(), dest.begin(), [](int x) {
            return x * x;
        });
        
        std::cout << "平方变换: ";
        for (int n : dest) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // transform 二元操作
        std::vector<int> src2{10, 20, 30, 40, 50};
        std::transform(src.begin(), src.end(), src2.begin(), dest.begin(), 
            [](int a, int b) {
                return a + b;
            });
        
        std::cout << "加法变换: ";
        for (int n : dest) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
    
    static void copying() {
        std::cout << "\n=== 复制算法 ===" << std::endl;
        
        std::vector<int> src{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        std::vector<int> dest;
        
        // copy_if - 条件复制
        std::copy_if(src.begin(), src.end(), std::back_inserter(dest), [](int x) {
            return x % 2 == 0;
        });
        
        std::cout << "偶数复制: ";
        for (int n : dest) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // unique_copy - 去重复制
        std::vector<int> src2{1, 1, 2, 2, 2, 3, 3, 4, 5, 5};
        std::vector<int> unique_dest;
        
        std::unique_copy(src2.begin(), src2.end(), std::back_inserter(unique_dest));
        
        std::cout << "去重复制: ";
        for (int n : unique_dest) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
    
    static void generation() {
        std::cout << "\n=== 生成算法 ===" << std::endl;
        
        // fill - 填充
        std::vector<int> vec(10);
        std::fill(vec.begin(), vec.end(), 42);
        
        std::cout << "fill填充: ";
        for (int n : vec) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // generate - 生成
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(1, 100);
        
        std::generate(vec.begin(), vec.end(), [&]() {
            return dis(gen);
        });
        
        std::cout << "generate生成: ";
        for (int n : vec) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // iota - 递增序列
        std::vector<int> seq(10);
        std::iota(seq.begin(), seq.end(), 1);
        
        std::cout << "iota序列: ";
        for (int n : seq) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
    
    static void removal() {
        std::cout << "\n=== 删除算法 ===" << std::endl;
        
        std::vector<int> vec{1, 2, 3, 2, 4, 2, 5};
        
        std::cout << "原始: ";
        for (int n : vec) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // remove - 移除元素
        auto new_end = std::remove(vec.begin(), vec.end(), 2);
        vec.erase(new_end, vec.end());
        
        std::cout << "移除2后: ";
        for (int n : vec) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // remove_if - 条件移除
        std::vector<int> vec2{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        auto new_end2 = std::remove_if(vec2.begin(), vec2.end(), [](int x) {
            return x % 2 == 0;
        });
        vec2.erase(new_end2, vec2.end());
        
        std::cout << "移除偶数后: ";
        for (int n : vec2) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
};

🔢 数值算法

累积和数值操作

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <functional>

class NumericAlgorithms {
public:
    static void accumulation() {
        std::cout << "=== 累积算法 ===" << std::endl;
        
        std::vector<int> vec{1, 2, 3, 4, 5};
        
        // accumulate - 累积
        int sum = std::accumulate(vec.begin(), vec.end(), 0);
        std::cout << "累加和: " << sum << std::endl;
        
        // 自定义操作
        int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>());
        std::cout << "累积: " << product << std::endl;
        
        // 字符串连接
        std::vector<std::string> words{"Hello", " ", "World", "!"};
        std::string sentence = std::accumulate(words.begin(), words.end(), std::string(""));
        std::cout << "字符串连接: " << sentence << std::endl;
        
        // reduce (C++17) - 并行累积
        #ifdef __cpp_lib_parallel_algorithm
        int parallel_sum = std::reduce(vec.begin(), vec.end(), 0);
        std::cout << "并行累积: " << parallel_sum << std::endl;
        #endif
    }
    
    static void partialSums() {
        std::cout << "\n=== 部分和算法 ===" << std::endl;
        
        std::vector<int> vec{1, 2, 3, 4, 5};
        std::vector<int> result(vec.size());
        
        // partial_sum - 部分和
        std::partial_sum(vec.begin(), vec.end(), result.begin());
        
        std::cout << "原始: ";
        for (int n : vec) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        std::cout << "部分和: ";
        for (int n : result) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 自定义操作的部分和
        std::partial_sum(vec.begin(), vec.end(), result.begin(), std::multiplies<int>());
        
        std::cout << "部分积: ";
        for (int n : result) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // adjacent_difference - 相邻差
        std::vector<int> diff_result(vec.size());
        std::adjacent_difference(vec.begin(), vec.end(), diff_result.begin());
        
        std::cout << "相邻差: ";
        for (int n : diff_result) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
    
    static void innerProduct() {
        std::cout << "\n=== 内积算法 ===" << std::endl;
        
        std::vector<int> vec1{1, 2, 3, 4, 5};
        std::vector<int> vec2{2, 3, 4, 5, 6};
        
        // inner_product - 内积
        int dot_product = std::inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
        std::cout << "内积: " << dot_product << std::endl;
        
        // 自定义操作
        int custom = std::inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0,
            std::plus<int>(), [](int a, int b) {
                return a * b * 2;  // 每个乘积再乘以2
            });
        std::cout << "自定义内积: " << custom << std::endl;
    }
    
    static void gcdLcm() {
        std::cout << "\n=== 最大公约数和最小公倍数 ===" << std::endl;
        
        // gcd, lcm (C++17)
        #ifdef __cpp_lib_gcd_lcm
        int a = 48, b = 18;
        std::cout << "gcd(" << a << ", " << b << ") = " << std::gcd(a, b) << std::endl;
        std::cout << "lcm(" << a << ", " << b << ") = " << std::lcm(a, b) << std::endl;
        #endif
    }
};

🔀 排列和集合算法

排列组合

cpp

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

class PermutationAlgorithms {
public:
    static void permutations() {
        std::cout << "=== 排列算法 ===" << std::endl;
        
        std::vector<int> vec{1, 2, 3};
        
        std::cout << "所有排列:" << std::endl;
        do {
            for (int n : vec) {
                std::cout << n << " ";
            }
            std::cout << std::endl;
        } while (std::next_permutation(vec.begin(), vec.end()));
        
        // 重置到最小排列
        std::sort(vec.begin(), vec.end());
        
        std::cout << "\n逆序排列:" << std::endl;
        do {
            for (int n : vec) {
                std::cout << n << " ";
            }
            std::cout << std::endl;
        } while (std::prev_permutation(vec.begin(), vec.end()));
    }
    
    static void setOperations() {
        std::cout << "\n=== 集合算法 ===" << std::endl;
        
        std::vector<int> set1{1, 2, 3, 4, 5};
        std::vector<int> set2{3, 4, 5, 6, 7};
        std::vector<int> result;
        
        // set_union - 并集
        std::set_union(set1.begin(), set1.end(), 
                      set2.begin(), set2.end(), 
                      std::back_inserter(result));
        
        std::cout << "并集: ";
        for (int n : result) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // set_intersection - 交集
        result.clear();
        std::set_intersection(set1.begin(), set1.end(), 
                             set2.begin(), set2.end(), 
                             std::back_inserter(result));
        
        std::cout << "交集: ";
        for (int n : result) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // set_difference - 差集
        result.clear();
        std::set_difference(set1.begin(), set1.end(), 
                           set2.begin(), set2.end(), 
                           std::back_inserter(result));
        
        std::cout << "差集: ";
        for (int n : result) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // set_symmetric_difference - 对称差集
        result.clear();
        std::set_symmetric_difference(set1.begin(), set1.end(), 
                                     set2.begin(), set2.end(), 
                                     std::back_inserter(result));
        
        std::cout << "对称差集: ";
        for (int n : result) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    SearchAlgorithms::basicSearch();
    SearchAlgorithms::binarySearch();
    SearchAlgorithms::searchPatterns();
    
    SortingAlgorithms::basicSorting();
    SortingAlgorithms::customSorting();
    SortingAlgorithms::partitioning();
    
    ModifyingAlgorithms::transformation();
    ModifyingAlgorithms::copying();
    ModifyingAlgorithms::generation();
    ModifyingAlgorithms::removal();
    
    NumericAlgorithms::accumulation();
    NumericAlgorithms::partialSums();
    NumericAlgorithms::innerProduct();
    NumericAlgorithms::gcdLcm();
    
    PermutationAlgorithms::permutations();
    PermutationAlgorithms::setOperations();
    
    return 0;
}

总结

STL算法库提供了丰富的通用算法，显著提高了开发效率：

算法分类

查找算法: find, search, binary_search
排序算法: sort, stable_sort, partial_sort
修改算法: transform, copy, remove
数值算法: accumulate, partial_sum, inner_product
排列算法: next_permutation, set operations

性能特点

算法类型	时间复杂度	适用场景
线性查找	O(n)	无序数据
二分查找	O(log n)	有序数据
排序	O(n log n)	数据整理
线性变换	O(n)	数据处理

设计原则

迭代器抽象: 算法与容器解耦
函数对象: 自定义操作逻辑
策略模式: 算法行为可配置
泛型编程: 类型无关实现

最佳实践

选择合适的算法复杂度
利用STL避免重复造轮子
结合lambda表达式简化代码
注意算法的前置条件
使用范围算法(C++20)

STL算法是C++高效编程的重要工具，掌握它们能大幅提升代码质量和开发速度。

C++ STL 算法 ​

概述 ​

🔍 查找算法 ​

基础查找 ​

🔄 排序算法 ​

排序和分区 ​

🔧 修改算法 ​

变换和生成 ​

🔢 数值算法 ​

累积和数值操作 ​

🔀 排列和集合算法 ​

排列组合 ​

总结 ​

算法分类 ​

性能特点 ​

设计原则 ​

最佳实践 ​

C++ STL 算法

概述

🔍 查找算法

基础查找

🔄 排序算法

排序和分区

🔧 修改算法

变换和生成

🔢 数值算法

累积和数值操作

🔀 排列和集合算法

排列组合

总结

算法分类

性能特点

设计原则

最佳实践