当前位置：首页 > article >正文

标准库简介 - STL容器、算法简介

article 2025/1/8 10:58:23

引言

C++ 标准模板库（Standard Template Library，简称 STL）是 C++ 标准库的一部分，提供了丰富的数据结构和算法。STL 的设计目标是通用性和高效性，它通过模板机制实现了高度的灵活性和复用性。本文将详细介绍 STL 中的容器和算法，并通过实例帮助读者理解其使用方法。

1. STL 容器简介

STL 容器是一组用于存储和管理数据的类模板。根据数据的组织方式，STL 容器可以分为以下几类：

1.1 序列容器

序列容器按照线性顺序存储元素，支持随机访问或顺序访问。常见的序列容器包括：

vector：动态数组，支持快速随机访问，但在中间插入或删除元素时效率较低。
list：双向链表，支持高效的插入和删除操作，但不支持随机访问。
deque：双端队列，支持在两端进行高效的插入和删除操作。

#include <iostream>
#include <vector>
#include <list>
#include <deque>

int main() {
    // 使用 vector
    std::vector<int> vec = {1, 2, 3};
    vec.push_back(4);
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 使用 list
    std::list<int> lst = {1, 2, 3};
    lst.push_back(4);
    for (int i : lst) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 使用 deque
    std::deque<int> deq = {1, 2, 3};
    deq.push_back(4);
    deq.push_front(0);
    for (int i : deq) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

1.2 关联容器

关联容器根据键值对存储元素，并提供高效的查找、插入和删除操作。常见的关联容器包括：

set：存储唯一键值的有序集合。
multiset：允许存储重复键值的有序集合。
map：存储键值对的有序映射。
multimap：允许存储重复键值对的有序映射。

#include <iostream>
#include <set>
#include <map>

int main() {
    // 使用 set
    std::set<int> s = {3, 1, 2};
    for (int i : s) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 使用 map
    std::map<std::string, int> m = {{"apple", 1}, {"banana", 2}};
    m["orange"] = 3;
    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

1.3 无序关联容器

无序关联容器基于哈希表实现，提供平均常数时间复杂度的查找、插入和删除操作。常见的无序关联容器包括：

unordered_set：存储唯一键值的无序集合。
unordered_multiset：允许存储重复键值的无序集合。
unordered_map：存储键值对的无序映射。
unordered_multimap：允许存储重复键值对的无序映射。

#include <iostream>
#include <unordered_set>
#include <unordered_map>

int main() {
    // 使用 unordered_set
    std::unordered_set<int> us = {3, 1, 2};
    for (int i : us) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 使用 unordered_map
    std::unordered_map<std::string, int> um = {{"apple", 1}, {"banana", 2}};
    um["orange"] = 3;
    for (const auto& pair : um) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

2. STL 算法简介

STL 提供了大量的泛型算法，这些算法可以应用于各种容器，而无需关心容器的具体实现细节。常见的 STL 算法包括：

2.1 查找算法

find：在范围内查找指定元素。
find_if：在范围内查找满足条件的元素。
count：统计范围内指定元素的数量。
count_if：统计范围内满足条件的元素数量。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 使用 find
    auto it = std::find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "找到元素 3" << std::endl;
    }

    // 使用 count
    int count = std::count(vec.begin(), vec.end(), 3);
    std::cout << "元素 3 出现了 " << count << " 次" << std::endl;

    return 0;
}

2.2 排序算法

sort：对范围内的元素进行排序。
stable_sort：保持相等元素相对顺序的排序。
partial_sort：对部分元素进行排序。
nth_element：将第 n 个元素放在正确的位置上。

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

int main() {
    std::vector<int> vec = {5, 2, 3, 1, 4};

    // 使用 sort
    std::sort(vec.begin(), vec.end());
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.3 数值算法

accumulate：计算范围内元素的总和。
inner_product：计算两个范围的内积。
adjacent_difference：计算相邻元素的差值。
partial_sum：计算部分和。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 使用 accumulate
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    std::cout << "总和: " << sum << std::endl;

    return 0;
}

2.4 修改算法

copy：将一个范围的元素复制到另一个范围。
replace：将范围内所有等于某个值的元素替换为另一个值。
reverse：反转范围内元素的顺序。
rotate：将范围内元素旋转。

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

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

    // 使用 copy
    std::copy(vec.begin(), vec.end(), vec2.begin());
    for (int i : vec2) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 使用 reverse
    std::reverse(vec.begin(), vec.end());
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}