目录

概述：

🔧容器(Container)

1️⃣序列式容器 (Sequence container)

2️⃣关联式容器 (Associative container)

3️⃣无序容器 (Unordered (associative) container)

🔧迭代器(Iterator)

🔧算法(Algorithm)

STL (standard template library, 标准模板库) 是 C++ 标准库的核心，它深刻影响了标准库

的整体结构。STL 是一个泛型 (generic) 程序库，提供一系列软件方案，利用先进、高效的

算法来管理数据。

概述：

STL包括六大组件，分别为容器、算法、迭代器、仿函数、适配器、分配器

以下是各组件的概念

1. 容器（Containers）用于存储和管理数据的类模板，提供了多种数据结构（如数组、链表、树、栈、队列等），方便我们直接使用。容器分为序列式容器、关联式容器和无序容器。
2. 算法（Algorithms）用于操作容器中数据的函数模板，涵盖排序、查找、遍历、修改、数值计算等常见操作（如 sort、find、for_each）。算法独立于容器，通过迭代器访问容器元素，具有通用性。
3. 迭代器（Iterators）连接容器和算法的桥梁，提供了类似于指针的接口，用于遍历容器中的元素。迭代器将不同容器的内部结构抽象化，使算法能统一操作各种容器，常见类型有输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器。
4. 仿函数（Functors）重载了 operator() 的类或结构体，行为类似函数，可作为算法的参数（比如自定义排序规则）。仿函数能保存状态，比普通函数更灵活，STL 中提供了算术运算、逻辑运算等基础仿函数（如 plus、greater）。
5. 适配器（Adapters）用于转换容器、迭代器或仿函数的接口，使其满足特定需求。常见类型：容器适配器（如 stack、queue，基于其他容器实现特定功能）、迭代器适配器（如 reverse_iterator，反转迭代方向）。
6. 分配器（Allocators）负责容器的内存管理，包括内存的分配、释放、对象的构造和析构。默认情况下，STL 容器使用 std::allocator，开发者也可自定义分配器以优化内存使用（如针对特定场景减少内存碎片）。

其中最关键的是容器、算法和迭代器

STL 的基本观念就是将数据和操作分离。数据由容器类加以管理，操作则由可定制的算法定义之。迭代器在两者之间充当黏合剂利，使任何算法都可以和任何容器交互运作

🔧容器(Container)

总的来说，容器可分为三大类:

1️⃣序列式容器 (Sequence container)

这是一种有序 (ordered 集合，其内每个元素均有确切的位置 -- 取决于插入时机和地点，与元素值无关。如果你以追加方式对一个集合置入 6 个元素，它们的排列次序将和置入次序一致。STL 提供了 5 个定好的序列式容器:array, vector, deque, list 和 forward_list.

该容器底层实现为数组或者链表

2️⃣关联式容器 (Associative container)

这是一种已排序 (sorted) 集合，元素位置取决于其 value (或 key-- 如果元素是个 key/value pair) 和给定的某个捐非序准则。如果将 6个元素置入这样的集合中，它们的值将决定它们的次序，和插入次序无关。STL 提供了4 个关联式容器:set、multiset、map 和 multimap。

该容器底层实现为二叉树

3️⃣无序容器 (Unordered (associative) container)

这是一种无序集合 (unordered collection), 其内每个元素的位置无关紧要，唯一重要的是某特定元素是否位于此集合内。元素值或其安插顺序，都不影响

该容器底层实现为哈希表，也叫做散列表

🔧迭代器(Iterator)

自 C++11 起，我们可以使用一个范围for循环来处理所有元素，然而如果只是要找出某元素，并不需要处理所有元素。我们应该选代所有元素，直到找到目标。

就比如，你在容器里找到了某个元素后，可能想记住它在哪儿，方便后面接着往下遍历，或者做点别的操作。这时候就需要一个东西能 “标记” 这个位置 —— 这东西就是迭代器。

你可以把迭代器理解成一个 “指针”（虽然不完全一样，但意思差不多），它指着容器里某个元素的位置。有了它，你就知道 “刚才找到的东西在这儿”，后面想从这儿继续往后走，或者直接操作这个位置的元素，都能用它来搞定。

所以迭代器的核心作用就是：帮你记住容器里元素的位置，让你能方便地移动、访问或者操作这些元素。

迭代器是一个 "可遍历 STL 容器全部或部分元素" 的对象。迭代器用来表现容器中的某一个位置。基本操作如下:

Operator * 返回当前位置上的元素值。如果该元素拥有成员，你可以通过迭代器直接以操作符 -> 取用它们。

Operator++ 令迭代器前进至下一元素。大多数迭代器还可使用 perator--- 退至前一元素。Operators== 和！= 判断两个迭代器是否指向同一位置。

Operator = 对迭代器赋值 (也就是指明迭代器所指向的元素的立置)

这些操作和 C/C++"运用 pointer 操作寻常的 array 元素" 时的接口一致。差别在于，迭代器是所谓的 smart pointer, 具有遍历复杂数据结构的能力，其内部运作机制取决于其所追历的数据结构。因此，每一种容器都必须提供自己的迭代器。虽然各种迭代器的接口虽然相同，类型却各自不同。

所有容器类都提供一些基本的成员函数,使我们得以取得选代器并以之遍历所有元素。

而这些函数中最重要的是:

begin()返回一个迭代器,指向容器起点,也就是第一元素(如果有的话)的位置。

end()返回一个迭代器,指向容器终点。终点位于最末元素的下一位置,这样的迭代器又

称作"逾尾(past-the-end)"迭代器。

于是,begin()和end()形成了一个半开区间(half-openrange),从第一元素开始,到最末元素的下一位置结束。

半开区间有两个优点:

1.为"遍历元素时的结束时机"提供一个简单的判断依据。只要尚未到达end(),就可以继续进行。

2.不必对空区间采取特殊处理手法。空区间的begin()就等于end()。

比如你用范围 for 循环（就是那种 “for (auto x : 容器)” 的写法），看着简单，其实它内部偷偷用了迭代器：先拿到容器第一个元素的迭代器，然后一步步往后挪，直到容器末尾，这样就把所有元素遍历完了。

for(auto elem : containers) {...}
// 会被解释为
for(auto pos = containers.begin(); pos != containers.end(); ++pos) {
    auto elem = *pos;
    ...
}

🔧算法(Algorithm)

为了处理容器内的元素,STL提供了一些标准算法,包括查找、排序、拷贝、重新排序、修

改、数值运算等基本而普遍的算法。

算法并非容器类的成员函数,而是一种搭配选代器使用的全局函数。

这么做有一个重要优势:所有算法只需实现一份,就可以对所有容器运作,不必为每一种容器量身定制。

算法甚至可以操作不同类型(type)之容器内的元素,也可以与)用户自定义的容器搭配。这个概念大幅降低了代码量,提高了程序库的能力和弹性。

下面从一个简单的例子入手

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

using namespace std;
int main() {

    vector<int> coll = { 2, 5, 4, 1, 6, 3 };

    auto minpos = min_element(coll.begin(),coll.end());
    cout << "min: " << *minpos << endl;
    auto maxpos = max_element(coll.begin(),coll.end());
    cout << "max: " << *maxpos << endl;

    sort(coll.begin(), coll.end());


    auto pos3 = find (coll.begin(), coll.end(), 3);
    reverse (pos3, coll.end());
    for (auto elem : coll) {
        cout << elem << " ";
    }
    return 0;
}

输出：

min: 1
max: 6
1 2 6 5 4 3  

为了能够调用算法,首先必须包含头文件<algorithm>(某些)算法需要特别的头文件

⏩最先出现的算法是min_element()和max_element()。调用它们时必须传入两个实参,定

义出欲处理的元素范围。如果想处理容器内所有元素,可使用cbegin()和cend(),或

begin()和end()。两个算法都返回一个迭代器,分别指向最小或最大元素。

算法min_element()返回最小元素的位置(如果最小元素不止一个,则返回第一个的

位置)。以下语句打印出该元素:

cout << "min:"<<*minpos << endl;

当然,你也可以把上述两个动作合并于单一语句:

cout << *min_element(coll.begin(),coll.end()) << endl;

⏩接下来出现的算法是sort()。顾名思义,它将"由两个实参指出来"的区间内的所有元素

加以排序。你可以(选择性地)传入一个排序准则,默认使用operato<。因此,本例容器

内的所有元素以递增方式排列。

sort (coll.begin(), coll.end());

排序后的容器元素次序如下:

123456

⏩再来便是算法find()。它在给定范围内查找某值。本例在整个容器内寻找数值为3的

第一个元素。

auto pos3 = find (coll.begin(), coll.end(), 3);

如果find()成功,返回一个迭代器指向目标元素。如果失!败,返回第二实参所指示的区间

末端,本例是coll的逾尾(past-the-end)迭代器。本例在第三个元素位置上发现数值3,

因此完成后pos3指向coll的第三个元素，返回其元素下标。

⏩本例所展示的最后一个算法是reverse(),将区间内的元素反转放置:

reverse (pos3, coll.end());

这个动作会将第三元素至最末元素的排列次序逆转。

好的，这期我们只是简单的了解了一下容器、迭代器还有算法的基本概念，下一期的话，我们就要深入到容器中。

谢谢大家💖💖💖