STL

STL的诞生

长久以来，软件界一直希望建立一种可以重复利用的东西。例如C++的面向对象的编程思想就是在提高复用性。但是，数据结构和算法都未能一套标准，导致要做大量重复的工作。为了建立数据结构算法的一套标准，诞生了STL。

什么是STL

所谓STL，就是Standard Template Library，标准模板库。STL可以分为三部分，容器(container)、算法(algorithm)、迭代器(iterator)。迭代器可以作为容器和算法之间的桥梁，使用起来很像指针。

STL六大组件

STL有六大组件，分别是容器、算法、迭代器、仿函数、适配器、空间配置器。

1. 容器：各种各样的数据结构，如vector、list、map等。
2. 算法：各种常用的算法，如排序(sort)、查找(find)、复制(copy)等。
3. 迭代器：一种用来连接算法和容器的胶合剂。
4. 仿函数：类似于函数，可以为算法提供策略。
5. 适配器：一种用来修饰容器、仿函数或者迭代器接口的东西。
6. 空间配置器：负责空间的配置与管理。

容器、算法、迭代器

• 容器
  容器，顾名思义就是存放东西的容器，可以理解为数组，链表、数之类的数据结构。这些容器分为序列式容器和关联式容器两种：

  1. 序列式容器：强调值的顺序，每个序列式容器容器中元素的位置均有固定的位置。元素放进去是么样，取出来也是什么样。
  2. 关联式容器：树形结构，各个元素之间没有严格的顺序关系。 元素放进去的时候可能是个无序序列，但取出时就变成了有序序列了。

• 算法
  算法就是解决问题的方法 。算法分为质变算法和非质变算法:

  1. 质变算法：运算过程中会更改容器元素的内容算法。如拷贝、删除、替换等等。
  2. 非质变算法：是指运算过程中不会更改容器内容的算法。如查找，遍历，统计等等。

• 迭代器
  提供一种方法，使之能够寻访某个容器中所含的各个元素，而又无需暴露该容器的内部表示方式。每个容器都有自己专属的迭代器。迭代器的使用方法非常类似于指针。

  迭代器的种类：

  种类	功能	支持运算
  输入迭代器	对数据进行访问	只读，支持++、==、!=
  输出迭代器	对数据进行只写访问	只写，支持++
  前向迭代器	读写操作，并且只能向前推进迭代器	读写，支持++、==、!=
  双向迭代器	读写操作，并且能向前和向后推进迭代器	读写，支持++、--
  随机访问迭代器	读写操作，可以跳跃访问任意数据，功能最强的迭代器	读写，支 持++、--、[n]、-n、<、<=、>、>=

  常用的迭代器为双向迭代器和随机访问迭代器。

vector容器

vector容器是STL中最常用的容器，就好像一个数组一样。我们了解了STL的基本概念和思想之后，来完成一个小案例，对vector容器的插入数据、并遍历这个容器的操作，先来体验一把STL。

• vector容器存放内置数据类型
  需要包含头文件<vector>

#include <iostream>
#include <vector>
#include <algorithm>    /*标准算法头文件*/
using namespace std;

//回调函数
void print(int val)
{
    cout << val << " ";
}

int main()
{
    //创建出一个vector容器，数组
    vector<int> v;

    //向容器中插入数据  尾插
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    //第一种遍历方式
    //通过迭代器访问容器中的数据
    vector<int>::iterator itBegain = v.begin(); //起始迭代器 指向容器中第一个位置
    vector<int>::iterator itEnd = v.end(); //结束迭代器 指容器中的第最后一个元素的下一个位置

    while (itBegain != itEnd)
    {
        cout << *itBegain << endl;
        itBegain++;
    }

    //第二种遍历方式
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << endl;
    }

    //第三种遍历方式
    for_each(v.begin(), v.end(), print);

    return 0;
}

这个例子的第一种遍历方式和第二种方式本质上没什么区别，跟指针操作数组的道理一样。第三种遍历方式使用了标准算法的for_each遍历算法。需要包含头文件<algorithm>。三个参数分别为起始迭代器，终止迭代器，回调函数。这里要注意，回调函数的参数列表一定是T val型的，因为for_each底层在执行回调的时候是有一个参数的。

• vector存放自定义数据类型
  我们已经知道了如何使用vector容器存放内置数据类型，下面我们来演示一下vector容器存放自定义数据类型。

//vector容器存放自定义数据类型
class Person
{
public:
    Person(string name,int age)
    {
        this->name = name;
        this->age = age;
    }
    string name;
    int age;
};

void print(const Person &p)
{
    cout << "姓名：" << p.name << " 年龄：" << p.age << endl;
}

int main()
{
    //创建出一个vector容器，数组
    vector<Person> v;
    Person p1("张三", 10);
    Person p2("李四", 20);
    Person p3("王五", 30);
    Person p4("赵六", 40);

    //向容器中插入数据
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);

    //通过迭代器访问容器中的数据 
    vector<Person>::iterator itBegain = v.begin(); //起始迭代器 指向容器中第一个位置
    vector<Person>::iterator itEnd = v.end(); //结束迭代器 指容器中的第最后一个元素的下一个位置

    while (itBegain != itEnd)
    {
        cout << "姓名：" << itBegain->name << " 年龄：" << itBegain->age << endl;
        itBegain++;
    }

    //第二种遍历方式  这里有一个技巧<>内部是什么，*it就是什么。
    for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << "姓名：" << it->name << " 年龄：" << (*it).age << endl;
    }

    //第三种遍历方式
    for_each(v.begin(), v.end(), print);

    return 0;
}

把迭代器看做指针，所以我在里面有 it->name，还有(*it).age的写法。以上vector存放Person数据类型，如果存放的是一个Person*数据类型呢？

存放Person*数据类型

//vector容器存放自定义数据类型
class Person
{
public:
    Person(string name,int age)
    {
        this->name = name;
        this->age = age;
    }
    string name;
    int age;
};

int main()
{
    //创建出一个vector容器，数组
    vector<Person*> v;
    Person p1("张三", 10);
    Person p2("李四", 20);
    Person p3("王五", 30);
    Person p4("赵六", 40);

    //向容器中插入数据
    v.push_back(&p1);
    v.push_back(&p2);
    v.push_back(&p3);
    v.push_back(&p4);

    //尖括号内是什么数据类型，*it就是什么数据类型
    for (vector<Person*>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << "姓名：" << (*it)->name << " 年龄：" << (*it)->age << endl;
    }

    return 0;
}

这次存入的vaetor容器的是一个Person*类型的指针，所以注意到输出的时候*it成了一个指针，才有了(*it)->name的写法。这里有一个技巧：尖括号里面是什么数据类型，*it就是什么数据类型。

• vector容器嵌套容器

//容器嵌套容器
void test01()
{
    vector<vector<int>> v;

    //创建小容器
    vector<int> v1;
    vector<int> v2;
    vector<int> v3;
    vector<int> v4;

    //向每一个容器添加元素
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i + 1);  //1~10
        v2.push_back(i + 11); //11~20
        v3.push_back(i + 21); //21~30
        v4.push_back(i + 31); //31~40
    }

    //把小容器放入大容器中去
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);
    v.push_back(v4);

    //通过大容器把所有的小容器的数据都遍历一遍
    for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++)
    {
        //*it---容器
        for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++)
        {
            cout << *vit << " ";
        }
        cout << endl;
    }
}

这里主要说一下双重循环的这部分代码。外层循环是在遍历每一个小容器，这里的*it表示的每一个小容器v1，v2，v3，v4。在找到每一个小容器的基础之上对每一个小容器进行的内容进行遍历输出。跟遍历二维数组的过程很像。