STL算法库的基本知识.doc

《STL算法库的基本知识》

一、STL算法库概述

STL（Standard Template Library，标准模板库）是C++标准库的核心组成部分，提供了一系列通用的模板类和函数，用于高效处理数据结构。其中算法库（Algorithms）是STL的三大组件（容器、迭代器、算法）之一，通过独立于容器的抽象接口，实现了对序列数据的通用操作。算法库的设计遵循"泛型编程"思想，通过迭代器作为容器与算法之间的桥梁，使得同一算法可适用于不同容器（如vector、list、deque等）。

二、算法分类与核心特性

1. 非修改序列操作

这类算法不改变容器内容，仅用于查询或遍历：

#include 
#include 
#include 

int main() {
    std::vector v = {1, 2, 3, 4, 5};
    
    // 遍历输出（C++11起更推荐使用范围for循环）
    std::for_each(v.begin(), v.end(), [](int n) {
        std::cout 

2. 修改序列操作

直接修改容器内容的算法：

#include 
#include 

int main() {
    std::vector v = {5, 3, 1, 4, 2};
    
    // 排序（默认升序）
    std::sort(v.begin(), v.end());
    
    // 反转序列
    std::reverse(v.begin(), v.end());
    
    // 唯一化（需先排序）
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
    
    return 0;
}

3. 排序相关操作

STL提供了多种排序算法：

#include 
#include 
#include  // 用于greater

struct Person {
    std::string name;
    int age;
};

bool compareAge(const Person& a, const Person& b) {
    return a.age  people = {{"Alice", 25}, {"Bob", 20}};
    
    // 默认升序排序
    std::sort(people.begin(), people.end(), compareAge);
    
    // 使用函数对象降序排序
    std::sort(people.begin(), people.end(), 
        std::greater()); // 需重载operator>
    
    // 部分排序（前N个最小元素）
    std::partial_sort(people.begin(), people.begin()+1, people.end());
    
    return 0;
}

4. 数值算法

位于头文件中的数学运算算法：

#include 
#include 

int main() {
    std::vector v = {1, 2, 3, 4, 5};
    
    // 累加
    int sum = std::accumulate(v.begin(), v.end(), 0);
    
    // 内积
    std::vector w = {2, 2, 2, 2, 2};
    int dot = std::inner_product(v.begin(), v.end(), w.begin(), 0);
    
    // 相邻差值
    std::vector diff(v.size());
    std::adjacent_difference(v.begin(), v.end(), diff.begin());
    
    return 0;
}

三、迭代器分类与使用

1. 迭代器类别

• 输入迭代器：只读，单次遍历（如istream_iterator）
• 输出迭代器：只写，单次遍历（如ostream_iterator）
• 前向迭代器：读写，多遍遍历（如forward_list的迭代器）
• 双向迭代器：前向迭代器+反向操作（如list、set的迭代器）
• 随机访问迭代器：双向迭代器+随机访问（如vector、deque的迭代器）

2. 迭代器适配器

#include 
#include 
#include 

int main() {
    std::vector v = {1, 2, 3};
    
    // 反向迭代器
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        std::cout  dest;
    std::copy(v.begin(), v.end(), std::back_inserter(dest));
    
    // 流迭代器
    std::istream_iterator input(std::cin);
    std::ostream_iterator output(std::cout, " ");
    std::copy(input, std::istream_iterator(), output);
    
    return 0;
}

四、算法复杂度保证

STL对算法复杂度有明确规范：

算法	最坏情况复杂度
find	O(n)
sort	O(n log n)
partial_sort	O(n log k)
nth_element	O(n)
merge	O(n+m)

例如std::sort()要求随机访问迭代器，复杂度保证为O(n log n)，而std::list的sort()成员函数使用双向迭代器，实现为O(n log n)的归并排序。

五、自定义操作

1. 谓词（Predicate）

返回bool的一元或二元函数对象：

#include 
#include 

bool isEven(int n) { return n % 2 == 0; }

struct IsOdd {
    bool operator()(int n) const { return n % 2 != 0; }
};

int main() {
    std::vector v = {1, 2, 3, 4, 5};
    
    // 函数指针谓词
    auto even_count = std::count_if(v.begin(), v.end(), isEven);
    
    // 函数对象谓词
    auto odd_count = std::count_if(v.begin(), v.end(), IsOdd());
    
    return 0;
}

2. 绑定器（Binder）

C++11前使用std::bind1st/std::bind2nd，现推荐使用lambda：

#include 
#include 
#include 

bool greaterThan(int a, int b) { return a > b; }

int main() {
    std::vector v = {1, 2, 3, 4, 5};
    
    // C++98风格绑定器（已弃用）
    // auto it = std::find_if(v.begin(), v.end(), 
    //     std::bind1st(std::ptr_fun(greaterThan), 3));
    
    // C++11 lambda表达式
    auto it = std::find_if(v.begin(), v.end(), 
        [](int n) { return n > 3; });
    
    return 0;
}

六、实用算法组合

1. 集合操作

#include 
#include 
#include 

int main() {
    std::vector v1 = {1, 2, 3, 4, 5};
    std::vector v2 = {4, 5, 6, 7, 8};
    std::vector result;
    
    // 并集
    std::set_union(v1.begin(), v1.end(),
                  v2.begin(), v2.end(),
                  std::back_inserter(result));
    
    // 交集
    result.clear();
    std::set_intersection(v1.begin(), v1.end(),
                        v2.begin(), v2.end(),
                        std::back_inserter(result));
    
    return 0;
}

2. 堆操作

#include 
#include 

int main() {
    std::vector v = {3, 1, 4, 1, 5, 9};
    
    // 建堆
    std::make_heap(v.begin(), v.end());
    
    // 添加元素
    v.push_back(6);
    std::push_heap(v.begin(), v.end());
    
    // 弹出最大元素
    std::pop_heap(v.begin(), v.end());
    int max = v.back();
    v.pop_back();
    
    return 0;
}

七、性能优化技巧

1. 预分配内存

对于可能多次扩容的操作，预先分配足够空间：

std::vector v;
v.reserve(1000); // 避免多次realloc

2. 选择合适迭代器

随机访问迭代器比双向迭代器效率高：

// 高效方式（vector的随机访问迭代器）
std::nth_element(v.begin(), v.begin()+v.size()/2, v.end());

// 低效方式（list的双向迭代器）
std::list l;
// l.sort(); // 必须使用成员函数sort()

3. 避免不必要的拷贝

使用移动语义或引用：

#include 
#include 

void process(std::vector&& data) {
    std::sort(std::make_move_iterator(data.begin()),
              std::make_move_iterator(data.end()));
}

int main() {
    std::vector v = {5, 3, 1, 4, 2};
    process(std::move(v));
    return 0;
}

八、C++11后的改进

1. 范围循环

std::vector v = {1, 2, 3};
for (auto& n : v) {
    n *= 2; // 直接修改元素
}

2. 新算法

#include 
#include 

int main() {
    std::array a = {1, 2, 3, 4, 5};
    
    // C++11新增的is_sorted
    bool sorted = std::is_sorted(a.begin(), a.end());
    
    // C++17的sample算法
    std::vector sample(3);
    std::sample(a.begin(), a.end(), sample.begin(),
               3, std::mt19937{std::random_device{}()});
    
    return 0;
}

九、常见误区与解决方案

1. 迭代器失效

// 错误示例：在删除元素后继续使用失效迭代器
std::vector v = {1, 2, 3};
auto it = v.begin();
v.erase(it);
++it; // 未定义行为！

解决方案：使用返回新迭代器的erase版本：

it = v.erase(it); // 正确方式

2. 算法前提条件

std::unique()要求序列已排序，否则结果不可预测：

std::vector v = {1, 2, 2, 1, 3};
// 错误：未排序直接unique
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end()); // 结果可能不符合预期

十、完整示例：学生成绩处理

#include 
#include 
#include 
#include 
#include 

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector students = {
        {"Alice", 85}, {"Bob", 92}, {"Charlie", 78},
        {"David", 92}, {"Eve", 88}
    };
    
    // 1. 按分数排序
    std::sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.score > b.score;
        });
    
    // 2. 计算平均分
    double avg = std::accumulate(students.begin(), students.end(), 0.0,
        [](double sum, const Student& s) {
            return sum + s.score;
        }) / students.size();
    
    // 3. 找出最高分学生
    auto max_it = std::max_element(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.score = 60; });
    
    // 输出结果
    std::cout name score 

关键词：STL算法库、迭代器、泛型编程、排序算法、数值计算、C++标准库、谓词、性能优化、容器操作

简介：本文系统介绍了C++ STL算法库的核心知识，涵盖算法分类、迭代器使用、复杂度保证、自定义操作、实用组合及性能优化技巧。通过代码示例展示了排序、查找、集合操作等典型应用场景，并分析了C++11后的改进和常见误区，最后通过学生成绩处理完整案例演示算法库的实际应用。

《STL算法库的基本知识.doc》

将本文以doc文档格式下载到电脑，方便收藏和打印

推荐度：

点击下载文档