STL概述

长久以来，软件界一直希望建立一种可重复利用的东西，以及一种得以制造出“可重复运用的东西”的方法,让程序员的心血不止于随时间的迁移，人事异动而烟消云散，从函数(functions)、类别(classes)、函数库(function libraries)、类别库(class libraries)、各种组件，从模块化设计，到面向对象(object oriented )，为的就是复用性的提升。

复用性必须建立在某种标准之上。但是在许多环境下，就连软件开发最基本的数据结构(data structures) 和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作，竟然是为了完成前人已经完成但自己手上并未拥有的程序代码，这不仅是人力资源的浪费，也是挫折与痛苦的来源。

为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹性、交互操作性(相互合作性 interoperability)诞生了STL。

STL(Standard Template Library，标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要出现在 C++中，但是在引入 C++之前该技术已经存在很长时间了。

STL基本概念

，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准库中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。与之前学到的编程思想面向对象编程不一样，STL采用的是一种新的编程模式：。它允许程序员编写通用的代码，即可适用于不同的数据类型，而不必为每种类型编写不同的代码。这种编程方法的基本思想是将数据类型抽象化，使用泛型来表示数据类型，并在编写代码时使用泛型来代替具体的数据类型。STL是很庞大复杂的系统，单单就STL就可写出厚达千页的技术书籍，所以，本章不可能做到面面俱到，重点在于介绍泛型编程的思想和本质，介绍一些常用的方法，为初学者学习STL提供一些感性认识，起到抛砖引玉的作用。

STL 从广义上分为: 容器(container)、算法(algorithm)、迭代器(iterator)，容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。STL(Standard Template Library)标准模板库在我们 C++标准程序库中隶属于 STL 的占到了 80%以上。

虽然STL的内容繁多，但是可以总结为六大组件：容器、迭代器、算法、适配器、函数对象、空间配置器。六大组件彼此之间可以组合套用，下面对六大组件的功能做一个概述。

容器：是一种数据结构。这里可以按照类别分为序列式容器（比如：vector、list）、关联式容器（比如：set、map）、无序关联式容器（比如：unordered_set、unordered_map）三类。从实现角度来看，STL容器是一种类模版（class template）。
迭代器：是一种抽象的数据类型，可用于访问容器中的元素，行为类似于C语言中的指针一样，这里可以将其称为泛型指针。扮演了容器与算法之间的胶合剂，共有五种类型。所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。从实现角度来看，迭代器是一种将operator* , operator->，operator++，operator--等指针相关操作予以重载的类模板(class template)。
算法：它是用于对容器中的元素进行操作的函数模板。STL中提供了大量的常用算法，包括：查找、排序、合并、去重、集合操作、取最值、数值计算等。从实现的角度来看，STL算法是一种函数模板（function tempalte）。
适配器：一种用来修饰容器或者访函数或者迭代器接口的东西。是使一种事物的行为类似于另外一种事物行为的一种机制，类似于生活中的转接器功能。
函数对象：也称为仿函数，可作为算法的某种策略。是一种封装了函数或函数指针的对象，它可以像函数一样被调用，也可以像对象一样被赋值或传递给其他函数，STL中的函数对象是做定制化操作的。行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的类(class)或者类模板(class template)。
空间配置器：管理内存分配和释放，负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的类模板(class tempalte)。

STL六大组件的交互关系：容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数。

STL优点

STL是C++的一部分，因此不用额外安装什么，它被内建在你的编译器之内。
STL的一个重要特性是将数据和操作分离。数据由容器类别加以管理，操作则由可定制的算法定义。迭代器在两者之间充当“粘合剂”，以使算法可以和容器交互运作。
程序员可以不用思考STL具体的实现过程，只要能够熟练使用STL就OK了。这样他们就可以把精力放在程序开发的别的方面。
STL具有高可重用性，高性能，高移植性，跨平台的优点。
- 高可重用性：STL中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。关于模板的知识，已经给大家介绍了。
- 高性能：如map可以高效地从十万条记录里面查找出指定的记录，因为map是采用红黑树的变体实现的。
- 高移植性：如在项目A上用STL编写的模块，可以直接移植到项目B上。

STL三大组件

容器

容器就是用来存放数据的，也就是数据结构，这是STL中最基础、最重要的部分。STL中的容器可以分为三类：序列式容器、关联式容器、无序关联式容器，这里我们需要具体学习各个容器的用法。

研究数据的特定排列方式，以利于搜索或排序或其他特殊目的，这一门学科我们称为数据结构。大学信息类相关专业里面，与编程最有直接关系的学科，首推数据结构与算法。几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。STL容器就是将运用最广泛的一些数据结构实现出来。

常用的数据结构：数组(array)、链表(list)、tree(树)、栈(stack)、队列(queue)、集合(set)、映射表(map)，根据数据在容器中的排列特性，这些数据分为序列式容器和关联式容器两种。

容器中要掌握的内容

序列式容器：强调值的排序，序列式容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。具体容器有
- array：（静态数组）
- vector：（动态数组）
- deque：（双端队列）
- forward_list：（单向链表）
- list：（双向链表）
关联式容器：是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是：在值中选择一个值作为关键字key，这个关键字对值起到索引的作用，方便查找。关联容器主要有两种类型，集合set和映射表map。其中集合set只存储key，映射表存储成对的[key, value]。基于这两种类型又细分为有序的、无序的关联容器；有序无序中又细分单重和多重，单重就是不允许key重复，多重就是允许key重复。这些关联容器提供的API接口基本是一致的，它们的区别在于底层数据结构的实现有所不同。
- 有序关联容器：底层基于红黑树实现，增删查时间复杂度近似于O(log2n)，2是底数。具体容器有
  - set：（单重无序集合容器）
  - multiset：（多重无序集合容器）
  - map：（单重无序映射表容器）
  - multimap：（多重无序映射表容器）
- 无序关联容器：底层基于链式哈希表实现，增删查时间复杂度近似于O(1)。具体容器有
  - unordered_set：（单重无序集合容器）
  - unordered_multiset：（多重无序集合容器）
  - unordered_map：（单重无序映射表容器）
  - unordered_multimap：（多重无序映射表容器）

容器适配器：是一种对容器的封装，它可以将一个容器的接口转换为另一个容器的接口，从而使得容器的接口更加通用。容器适配器主要有三种：

stack:(栈)
queue:(队列)
priority_queue:(优先级队列)。

近容器：可以理解为近似容器但没有纳入标准容器。

array：（数组）
string：（字符串）
bitset：（位容器，专门处理位运算）

算法

以有限的步骤，解决逻辑或数学上的问题，这一门学科我们叫做算法(Algorithms)。

广义而言，我们所编写的每个程序都是一个算法，其中的每个函数也都是一个算法，毕竟它们都是用来解决或大或小的逻辑问题或数学问题。STL收录的算法经过了数学上的效能分析与证明，是极具复用价值的，包括常用的排序，查找等等。特定的算法往往搭配特定的数据结构，算法与数据结构相辅相成。

算法分为：质变算法和非质变算法。

：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

再好的编程技巧，也无法让一个笨拙的算法起死回生。

算法中要掌握的内容

sort：排序
find：查找
find_if：条件查找
binary_search：二分查找
for_each：遍历

迭代器

迭代器(iterator)是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。在《Design Patterns》一书中提供了23中设计模式的完整描述，其中iterator模式定义如下：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

迭代器的设计思维——STL的关键所在，STL的中心思想在于将容器(container)和算法(algorithms)分开，彼此独立设计，最后再一贴胶着剂将他们撮合在一起。从技术角度来看，容器和算法的泛型化并不困难，C++的类模板class template和函数模板function template可分别达到目标，如果设计出两这个之间的良好的胶着剂，才是大难题。

输入迭代器	提供对数据的只读访问	只读，支持`++`、`==`、`！=`
输出迭代器	提供对数据的只写访问	只写，支持`++`
前向迭代器	提供读写操作，并能向前推进迭代器	读写，支持`++`、`==`、`！=`
双向迭代器	提供读写操作，并能向前和向后操作	读写，支持`++`、`--`
随机访问迭代器	提供读写操作，并能以跳跃的方式访问容器的任意数据，是功能最强的迭代器	读写，支持`++`、`--`、`[n]`、`-n`、`<`、`<=`、`>`、`>=`

迭代器中要掌握的内容

支持修改元素的
- iterator：普通正向迭代器
- reverse_iterator：普通反向迭代器
不支持修改元素的
- const_iterator：常量正向迭代器
- const_reverse_iterator：常量反向迭代器

案例

cpp

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

//STL 中的容器 算法 迭代器
void test01() {
    vector<int> v; //STL 中的标准容器之一 ：动态数组
    v.push_back(1);//vector 容器提供的插入数据的方法
    v.push_back(5);
    v.push_back(3);
    v.push_back(7);
    //迭代器
    vector<int>::iterator pStart = v.begin();//vector 容器提供了 begin()方法 返回指向第一个元素的迭代器
    vector<int>::iterator pEnd = v.end();    //vector 容器提供了 end()方法 返回指向最后一个元素下一个位置的迭代器
    //通过迭代器遍历
    while (pStart != pEnd) {
        cout << *pStart << " ";
        pStart++;
    }
    cout << endl;
}
//STL 容器不单单可以存储基础数据类型，也可以存储类对象
class Teacher {
public:
    Teacher(int age) : age(age){};
    ~Teacher(){};

public:
    int age;
};
void test02() {
    vector<Teacher> v;//存储 Teacher 类型数据的容器
    Teacher t1(10), t2(20), t3(30);
    v.push_back(t1);
    v.push_back(t2);
    v.push_back(t3);
    vector<Teacher>::iterator pStart = v.begin();
    vector<Teacher>::iterator pEnd = v.end();
    //通过迭代器遍历
    while (pStart != pEnd) {
        cout << pStart->age << " ";
        pStart++;
    }
    cout << endl;
}
//存储 Teacher 类型指针
void test03() {
    vector<Teacher *> v;//存储 Teacher 类型指针
    Teacher *t1 = new Teacher(10);
    Teacher *t2 = new Teacher(20);
    Teacher *t3 = new Teacher(30);
    v.push_back(t1);
    v.push_back(t2);
    v.push_back(t3);
    //拿到容器迭代器
    vector<Teacher *>::iterator pStart = v.begin();
    vector<Teacher *>::iterator pEnd = v.end();
    //通过迭代器遍历
    while (pStart != pEnd) {
        cout << (*pStart)->age << " ";
        pStart++;
    }
    cout << endl;
}
//容器嵌套容器 难点(不理解，可以跳过)
void test04() {
    vector<vector<int>> v;
    vector<int> v1;
    vector<int> v2;
    vector<int> v3;

    for (int i = 0; i < 5; i++) {
        v1.push_back(i);
        v2.push_back(i * 10);
        v3.push_back(i * 100);
    }
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);

    for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) {
        for (vector<int>::iterator subIt = (*it).begin(); subIt != (*it).end(); subIt++) {
            cout << *subIt << " ";
        }
        cout << endl;
    }
}
int main(void) {
    //test01();
    //test02();
    //test03();
    test04();
    
    return 0;
}

log4cpp

C++11智能指针

C++11线程库

C++11其他新特性

C++20协程

workflow

STL概述

STL基本概念

STL优点

STL三大组件

容器

算法

迭代器

案例

STL概述 ​

STL基本概念 ​

STL优点 ​

STL三大组件 ​

容器 ​

算法 ​

迭代器 ​

案例 ​

STL概述

STL基本概念

STL优点

STL三大组件

容器

算法

迭代器

案例