C++标准模板库（STL）容器、算法、迭代器

陈一男学习网站[ ChenYinan.com ] - CCF - NOI - 菜鸟教程 - 编程题库 - C++语言 - API

一. STL（标准模板库）的概述

定义：STL（Standard Template Library）是C++标准库的一部分，它提供了一系列通用的模板类和函数，用于处理常见的编程任务，如数据存储、排序、搜索等，旨在提高代码的复用性和效率。

组成部分：STL主要由容器（Containers）、算法（Algorithms）和迭代器（Iterators）三大组件构成，此外还包括函数对象（Function objects）、适配器（Adapters）和分配器（Allocators）等辅助组件。

二. 容器（Containers）

1. 顺序容器 vector：

vector是一个动态大小的数组，可以在末尾快速插入和删除元素。它在内存中是连续存储的，这使得随机访问元素非常高效（时间复杂度为$O(1)$），但在中间插入或删除元素可能会比较慢（平均时间复杂度为$O(n)$，其中$n$是容器中的元素个数）。

#include <vector>
#include <iostream>
int main() {
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    for (size_t i = 0; i < v.size(); i++) {
        std::cout << v[i] << " ";
    }
    return 0;
}

2. 顺序容器 list：

list是一个双向链表，它的每个节点包含一个元素和指向前一个节点和后一个节点的指针。在list中任意位置插入和删除元素都非常快（时间复杂度为$O(1)$），但随机访问元素比较慢（时间复杂度为$O(n)$）。

#include <list>
#include <iostream>
int main() {
    std::list<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    for (auto it = l.begin(); it!= l.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

3. 顺序容器 deque（双端队列）：

deque（发音为“deck”）是一种双端队列，它类似于vector，但在两端插入和删除元素都非常高效（时间复杂度为$O(1)$）。deque内部的存储结构可能不是连续的，而是由多个固定大小的块组成。

#include <deque>
#include <iostream>
int main() {
    std::deque<int> d;
    d.push_back(1);
    d.push_front(0);
    for (size_t i = 0; i < d.size(); i++) {
        std::cout << d[i] << " ";
    }
    return 0;
}

4. 关联容器 set：

set是一个有序的集合，其中的元素是唯一的。它基于红黑树实现，插入、删除和查找操作的时间复杂度都是$O(\log n)$。set会自动对元素进行排序。

#include <set>
#include <iostream>
int main() {
    std::set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(2);
    for (auto it = s.begin(); it!= s.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

5. 关联容器 map：

map是一个键 - 值对的有序集合，每个键在map中是唯一的。它基于红黑树实现，插入、删除和查找操作的时间复杂度都是$O(\log n)$。可以通过键快速查找对应的值。

#include <map>
#include <iostream>
int main() {
    std::map<int, int> m;
    m.insert(std::make_pair(1, 10));
    m.insert(std::make_pair(2, 20));
    m.insert(std::make_pair(3, 30));
    for (auto it = m.begin(); it!= m.end(); ++it) {
        std::cout << it->first << " " << it->second << " ";
    }
    return 0;
}

6. 关联容器 unordered_set、关联容器 unordered_map（C++11及以上）：

这两个容器分别是set和map的无序版本，它们基于哈希表实现。插入、删除和查找操作在平均情况下的时间复杂度为$O(1)$，但在最坏情况下可能为$O(n)$。由于是无序的，所以不会对元素进行自动排序。

#include <unordered_set>
#include <unordered_map>
#include <iostream>
int main() {
    std::unordered_set<int> us;
    us.insert(3);
    us.insert(1);
    us.insert(2);
    for (auto it = us.begin(); it!= us.end(); ++it) {
        std::cout << *it << " ";
    }
    std::unordered_map<int, int> um;
    um.insert(std::make_pair(1, 10));
    um.insert(std::make_pair(2, 20));
    um.insert(std::make_pair(3, 30));
    for (auto it = um.begin(); it!= um.end(); ++it) {
        std::cout << it->first << " " << it->second << " ";
    }
    return 0;
}

三. 算法（Algorithms）

1. 排序算法 std::sort：

对给定范围内的元素进行排序。它是一个快速排序的实现，平均时间复杂度为$O(n\log n)$，最坏情况下为$O(n^{2})$，但在实际应用中通常表现良好。

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {3, 1, 2};
    std::sort(v.begin(), v.end());
    for (auto num : v) {
        std::cout << num << " ";
    }
    return 0;
}

2. 查找算法 std::find：

功能：在给定范围内查找指定元素，如果找到则返回指向该元素的迭代器，否则返回范围末尾的迭代器。

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3};
    auto it = std::find(v.begin(), v.end(), 2);
    if (it!= v.end()) {
        std::cout << "Element found";
    } else {
        std::cout << "Element not found";
    }
    return 0;
}

四. 迭代器（Iterators）

定义与功能：迭代器是一种类似于指针的对象，用于遍历容器中的元素。不同类型的容器提供不同类型的迭代器，但它们都遵循一定的规范，使得可以使用相同的算法来操作不同类型的容器。

分类：

输入迭代器：可以从容器中读取元素，支持++（向前移动）操作和*（解引用）操作，但不支持多次解引用同一元素，也不支持--（向后移动）操作。

输出迭代器：用于向容器中写入元素，支持++操作和*操作，但解引用操作只能用于赋值，不能读取元素。

前向迭代器：兼具输入迭代器和输出迭代器的功能，并且支持多次解引用同一元素。

双向迭代器：在前向迭代器的基础上，支持--操作，可以双向遍历容器。

随机访问迭代器：除了双向迭代器的功能外，还支持随机访问元素，如it + n、it - n等操作，像vector容器提供的迭代器就是随机访问迭代器。

五. 函数对象（Function objects）、适配器（Adapters）和分配器（Allocators）

函数对象（Function objects）：也称为仿函数，是一个类，其重载了()运算符，使得类的对象可以像函数一样被调用。例如：

class Add {
    public:
        int operator()(int a, int b) {
            return a + b;
        }
};
int main() {
    Add add;
    int result = add(1, 2);
    std::cout << result << " ";
    return 0;
}

适配器（Adapters）：用于修改或组合其他组件的行为。例如，std::bind是一个函数适配器，它可以绑定函数的部分参数，创建一个新的可调用对象。

分配器（Allocators）：负责为容器分配和回收内存。默认的分配器std::allocator在大多数情况下能够满足需求，但在一些特殊场景下，如需要定制内存分配策略时，可以创建自己的分配器。