C++ STL 常用容器、算法和迭代器组件

STL概述

C++标准模板库（Standard Template Library，STL）是C++标准库的重要组成部分，它提供了一套通用的模板类和函数，用于处理各种数据结构和算法。STL主要由三个核心组件构成：容器（Containers）、算法（Algorithms）和迭代器（Iterators）。

常用容器

容器是用来存储和管理数据的对象，STL提供了多种容器，每种容器都有其特定的用途和性能特征。主要分为序列容器、关联容器、无序关联容器和容器适配器。

序列容器

序列容器按照线性顺序存储元素，元素的位置取决于插入时机和位置。

关联容器

关联容器按照特定的排序准则存储元素，通常使用平衡二叉树实现。

无序关联容器

无序关联容器使用哈希表实现，不保证元素的顺序。

容器适配器

容器适配器是基于其他容器实现的，提供了特定的接口。

常用算法

STL提供了大量算法，用于处理容器中的数据。这些算法通常通过迭代器操作容器中的元素，不依赖于具体的容器类型。

非修改序列算法

这些算法不修改容器中的元素。

• for_each: 对指定范围内的每个元素执行指定的操作
• find: 在指定范围内查找等于特定值的第一个元素
• find_if: 在指定范围内查找满足特定条件的第一个元素
• count: 计算指定范围内等于特定值的元素数量
• count_if: 计算指定范围内满足特定条件的元素数量
• all_of/any_of/none_of: 检查指定范围内是否所有/任何/没有元素满足特定条件

修改序列算法

这些算法会修改容器中的元素。

• copy: 将一个范围内的元素复制到另一个范围
• move: 将一个范围内的元素移动到另一个范围
• fill: 用特定值填充指定范围
• transform: 对指定范围内的每个元素应用指定的操作，并将结果存储在另一个范围中
• generate: 用生成函数的结果填充指定范围
• remove/remove_if: 移除等于特定值或满足特定条件的元素
• replace/replace_if: 将等于特定值或满足特定条件的元素替换为新值
• reverse: 反转指定范围内的元素顺序
• unique: 移除连续的重复元素
• shuffle: 随机打乱指定范围内的元素顺序

排序算法

这些算法用于对容器中的元素进行排序。

• sort: 对指定范围内的元素进行排序
• stable_sort: 对指定范围内的元素进行稳定排序
• partial_sort: 对指定范围内的部分元素进行排序
• nth_element: 将第n个元素放到它应该在的位置
• is_sorted: 检查指定范围内的元素是否已排序

二分查找算法

这些算法用于在已排序的范围内进行查找。

• binary_search: 检查指定范围内是否存在等于特定值的元素
• lower_bound: 返回指向第一个不小于特定值的元素的迭代器
• upper_bound: 返回指向第一个大于特定值的元素的迭代器
• equal_range: 返回等于特定值的元素范围

集合算法

这些算法用于对已排序的范围执行集合操作。

• merge: 合并两个已排序的范围
• set_union: 计算两个已排序范围的并集
• set_intersection: 计算两个已排序范围的交集
• set_difference: 计算两个已排序范围的差集
• set_symmetric_difference: 计算两个已排序范围的对称差集
• includes: 检查一个已排序范围是否包含另一个已排序范围

堆算法

这些算法用于操作堆数据结构。

• make_heap: 将指定范围内的元素转换为堆
• push_heap: 将元素添加到堆中
• pop_heap: 从堆中移除最大元素
• sort_heap: 对堆进行排序
• is_heap: 检查指定范围内的元素是否构成堆

最值算法

这些算法用于查找最小值和最大值。

• min/max: 返回两个值或范围中的最小值/最大值
• min_element/max_element: 返回指向范围中最小值/最大值的迭代器
• minmax: 返回两个值或范围中的最小值和最大值
• minmax_element: 返回指向范围中最小值和最大值的迭代器对

数值算法

这些算法用于执行数值计算。

• accumulate: 计算指定范围内元素的和或自定义的累积结果
• inner_product: 计算两个范围的内积
• partial_sum: 计算指定范围内元素的部分和
• adjacent_difference: 计算指定范围内相邻元素的差
• iota: 用递增的值填充指定范围

迭代器

迭代器是STL的核心组件，它提供了访问容器中元素的通用方法。迭代器类似于指针，可以用于遍历容器中的元素。

迭代器的分类

根据功能的不同，迭代器分为五类，功能依次增强：

迭代器适配器

迭代器适配器是特殊的迭代器，它们修改或扩展了其他迭代器的功能。

• 反向迭代器（Reverse Iterator）: 反向遍历容器
• 插入迭代器（Insert Iterator）: 用于向容器插入元素，而不是覆盖现有元素
  • back_inserter: 在末尾插入
  • front_inserter: 在开头插入
  • inserter: 在指定位置插入
• 流迭代器（Stream Iterator）: 用于与输入输出流交互
  • istream_iterator: 从输入流读取
  • ostream_iterator: 写入输出流
• 移动迭代器（Move Iterator）: 用于移动元素而不是复制元素

迭代器辅助函数

STL提供了一些辅助函数，用于操作迭代器。

• advance: 将迭代器前进或后退指定的距离
• distance: 计算两个迭代器之间的距离
• next/prev: 返回迭代器前进或后退指定位置后的副本
• begin/end: 返回容器的开始和结束迭代器
• cbegin/cend: 返回容器的常量开始和结束迭代器
• rbegin/rend: 返回容器的反向开始和结束迭代器
• crbegin/crend: 返回容器的常量反向开始和结束迭代器

容器、算法和迭代器的关系

容器、算法和迭代器是STL的三个核心组件，它们之间有着密切的关系：

1. 容器存储数据：容器用于存储和管理数据，提供了不同的数据结构和访问方式。
2. 迭代器访问数据：迭代器提供了访问容器中元素的通用接口，使得算法可以不依赖于具体的容器类型。
3. 算法操作数据：算法通过迭代器操作容器中的元素，实现了各种数据处理功能。

这种设计模式被称为"泛型编程"，它使得STL具有高度的灵活性和可重用性。算法可以应用于任何提供了相应迭代器的容器，而不需要为每种容器类型都实现一套算法。

实际应用示例

下面是一个使用STL容器、算法和迭代器的实际应用示例：

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

using namespace std;

// 打印容器的辅助函数
template <typename T>
void printContainer(const T& container) {
    for (const auto& elem : container) {
        cout << elem << " ";
    }
    cout << endl;
}

int main() {
    // 使用vector容器存储字符串
    vector<string> words = {"hello", "world", "c++", "stl", "algorithm"};
    
    // 使用迭代器遍历容器
    cout << "Original words: ";
    printContainer(words);
    
    // 使用sort算法对容器进行排序
    sort(words.begin(), words.end());
    cout << "Sorted words: ";
    printContainer(words);
    
    // 使用find_if算法查找长度大于3的单词
    auto it = find_if(words.begin(), words.end(), [](const string& s) {
        return s.length() > 3;
    });
    if (it != words.end()) {
        cout << "First word with length > 3: " << *it << endl;
    }
    
    // 使用transform算法将所有单词转换为大写
    transform(words.begin(), words.end(), words.begin(), [](string s) {
        for (char& c : s) {
            c = toupper(c);
        }
        return s;
    });
    cout << "Uppercase words: ";
    printContainer(words);
    
    // 使用copy算法将vector中的元素复制到另一个vector
    vector<string> copy_words;
    copy(words.begin(), words.end(), back_inserter(copy_words));
    cout << "Copied words: ";
    printContainer(copy_words);
    
    // 使用unique算法移除连续的重复元素
    auto last = unique(copy_words.begin(), copy_words.end());
    copy_words.erase(last, copy_words.end());
    cout << "Unique words: ";
    printContainer(copy_words);
    
    // 使用accumulate算法计算所有单词的总长度
    int total_length = accumulate(copy_words.begin(), copy_words.end(), 0,
        [](int sum, const string& s) {
            return sum + s.length();
        });
    cout << "Total length of unique words: " << total_length << endl;
    
    return 0;
}

参考文档

1. C++ Reference - Containers
2. C++ Reference - Algorithms
3. C++ Reference - Iterators
4. GeeksforGeeks - C++ STL
5. Microsoft Docs - C++ Standard Library