STL的六种基本组件

STL（Standard Template Library）是支持C++泛型的标准模板库，为用户提供了一些常用的数据结构及算法，包括链表、队列、集合等。STL包括六种基本组件：容器、迭代器、仿函数（也称函数对象）、算法、适配器以及分配器。

个人理解上不妨把STL的种种概念看成将一堆文件放到一个抽屉柜中。抽屉柜（容器）有着各种款式，每种款式的抽屉格（迭代器）的排列顺序、大小都不一样（向量、链表、映射、集合等）。我们需要将一堆文件（程序运行中需要处理的数据），放入到抽屉格（迭代器）中。同时为了让文件更加有序，我们还需要对不同抽屉格中的文件的一些信息进行比较，然后按要求排列好顺序（算法）。

容器 Container

容器提供了各种数据结构，决定了数据之间的存储关系。容器分为序列容器（Sequence Container）和关联容器（Associative Container）两类，序列容器包含向量（vector）、链表(list)、数组（array）、队列(queue)、栈(stack)等，关联容器主要包含集合(set)、映射(map)等。使用容器可以帮助更好地标准化管理组织抽象的数据。

序列容器（Sequence Container）

通过元素在容器中的位置顺序进行查找
序列容器在内存中是连续的
遵循一定顺序的元素通常使用序列容器

关联容器（Associative Container）

通过键存储、读取元素
元素没有强制的序列顺序
更容易查找
一般使用树结构进行存储，常用于映射和集合关系

迭代器 Iterator

迭代器可以看作一个泛化的指针，指向泛型数据。不同种类的迭代器就是指重载了哪些运算符（加减、前缀递增递减/后缀递增递减、等于等等）。以vector的迭代器为例，其重载了 +、-、++/–（前缀递增递减及后缀递增递减）、*、->、+=、-=、[]等运算符，是一个随机访问迭代器。如果说容器是不同形式的抽屉柜，那么迭代器就是一个抽屉，用户可以在抽屉里放入任何同种类型的数据。

迭代器提供了通用的访问容器中数据的途径，其作用是用来遍历容器。因为泛型算法是针对多种容器实现的通用算法，所以需要一种统一的方式遍历访问容器元素，迭代器的作用就作为连接容器和算法的桥梁起到为算法提供访问数据接口的作用。

迭代器共有五种，分别是输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器，分别实现了不同运算符的重载。
（注：输入、输出不是相对于迭代器而言的，是相对于使用者而言的。就是说输入迭代器是只读的，输出迭代器是只写的）

输入迭代器

输入迭代器支持读取迭代器内容。（可以记为从迭代器获取输入）

输出迭代器

输出迭代器支持向迭代器中写入内容。（可以记为向迭代器输出）

前向迭代器

前向迭代器是功能最少的迭代器种类，一般包含输入、输出迭代器，即前向迭代器一般支持读写。
此外支持++向前推进迭代器，以及!=、==两个运算符。

双向迭代器

双向迭代器在前向迭代器的基础上添加了向后推进迭代器的功能，即重载了–运算符。

随机访问迭代器

随机访问迭代器在双向迭代器的基础上重载了[]、+=、-=等运算符，以支持任意访问迭代器内容。

迭代器种类关系示意图

不同容器的迭代器种类
注：这里的stack和queue没有迭代器是因为两个容器都是deque的适配器。

仿函数（函数对象 Function Object）

函数对象指重载了函数调用操作符（函数调用操作符为“（）”）的类。称该行为称为函数对象或仿函数。

函数对象的本质是一个类，而非函数。

常与算法部分结合使用

#include <iostram>

class MyPrint{
    void operator () MyaPrint(const int& a){
        std::cout<<a<<" ">>
    }
}

int main(){
    std::vector v1 = {2,1,10,9,6,4};
    for_each(v1.begin(),v1.end(),Myprint(a));
}

算法 Algorithm

C++提供的内置通用算法，可以用于不同容器。大部分算法集中在头文件中。其他算法在、中。

不同容器的常见STL算法请见这篇文章：
C++ STL常用算法

适配器 Adaptor

适配器将一个类的接口转化为另一个类的接口。STL中的适配器将不同的容器、迭代器和函数对象进行二次封装以实现对旧组件的利用。
适配器分为容器适配器、迭代适配器、函数适配器三种。具体内容可见下面这篇博客:
STL适配器详解

分配器 Allocator

由于使用new关键字创建指针的底层是调用malloc函数，而malloc函数常常会申请多余的空间，造成内存的浪费。为了高效的运行，需要对申请空间的过程进行修改，同时也需要让算法识别迭代器类型以达到高效的运行效率。
具体的分配器内容可见下面这篇博客：
C++STL学习笔记(4) 分配器(Allocator)

常用容器及其优缺点

向量 vector

vector是基于倍增思想的内存连续的顺序容器，可以实现高效的随机存取、尾部加入或删除新元素等操作。

for(int i = 0;i<v2.size();i++)
{
    std::cout<<&(v2[i])<<" ";
}
std::cout<<std::endl;

输出：

1	000001E512AAE500 000001E512AAE504 000001E512AAE508 000001E512AAE50C

在元素个数超出容量时，vector将自动分配更多的空间，这一分配过程将当前vector的容量翻倍分配。

#include <iostream>
#include <vector>
#include <string>

int main(int argc, char* argv[])
{
    //vector的创建
    std::vector<int> v1;//空的vector
    std::vector<int> v2{0,3,10,2};//
    std::vector<int> v3(3,10);//创建含有3个10的vector
    
    std::cout<<"--------vector容量的重新分配--------"<<std::endl;
    std::cout<<"v3 original address:"<< &v3 <<std::endl;
    std::cout<<"v3 element address:"<< &(v3[2]) <<std::endl;
    std::cout<<"v3 original size:"<< v3.size() <<std::endl;
    std::cout<<"v3 original capacity:"<< v3.capacity() <<std::endl;
    v3.push_back(1);
    v3.push_back(4);
    std::cout<<"after reserve v3, it's address:"<< &v3 <<std::endl;
    std::cout<<"after reserve v3, v3 element address:"<< &(v3[2]) <<std::endl;
    std::cout<<"v3 size:"<< v3.size() <<std::endl;
    std::cout<<"v3 capacity:"<< v3.capacity() <<std::endl;

    return 0;
}

输出：

--------vector容量的重新分配--------
v3 original address:000000331533F518
v3 element address:000001995C508918
v3 original size:3
v3 original capacity:3

after reserve v3, it's address:000000331533F518
after reserve v3, v3 element address:000001995C50A238
v3 size:5
v3 capacity:6

可以看到重新分配内存后，vector的地址没有变化，但容器中的元素已经被重新分配了内存，同时内存的分配是成倍的。

此外，调用reserve()方法也会使得容器中的元素被重新分配地址。

#include <iostream>
#include <vector>

int main(int argc, char* argv[])
{
    //vector的创建
    std::vector<int> v1;//空的vector
    std::vector<int> v2{0,3,10,2};//
    std::vector<int> v3(3,10);//创建含有3个10的vector
    
    std::cout<<"--------vector.reserve()--------"<<std::endl;
    std::cout<<"v2 original address:"<< &v2 <<std::endl;
    std::cout<<"v2 element address:"<< &(v2[2]) <<std::endl;
    std::cout<<"v2 original size:"<< v2.size() <<std::endl;
    std::cout<<"v2 original capacity:"<< v2.capacity() <<std::endl;
    v2.reserve(7);
    std::cout<<"after reserve v2, it's address:"<< &v2 <<std::endl;
    std::cout<<"after reserve v2, v2 element address:"<< &(v2[2]) <<std::endl;
    std::cout<<"v2 original size:"<< v2.size() <<std::endl;
    std::cout<<"v2 original capacity:"<< v2.capacity() <<std::endl;
        
    return 0;
}

输出：

--------vector.reserve()--------
v2 original address:000000233F54F648
v2 element address:000001E512AB4EE8
v2 original size:4
v2 original capacity:4
after reserve v2, it's address:000000233F54F648
after reserve v2, v2 element address:000001E512AAE508
v2 original size:4
v2 original capacity:7

常用操作的时间复杂度

push_back() / pop_back()
时间复杂度： O(1)
insert() / erase()
时间复杂度： O(n) 与靠近头部复杂度越高，因为插入的目标位置后的元素均需要重新分配地址，随之带来的问题就是插入位置之前（或之后）的迭代器的引用、指针失效。
find()
时间复杂度：O(n)

优点

支持随机访问；
长度可拓展

缺点

多次插入数据或插入大量数据时会有多次拓展vector内存的风险，造成时间上的浪费。（可以在插入前先计算好插入后的长度，使用reserve()函数重新分配内存。）

应用场景

适用于经常随机访问容器元素，在中间插入次数少、插入数据量较小的情况。

迭代器失效

#include <iostream>
#include <vector>

int main(int argc, char* argv[])
{
    //vector的创建
    std::vector<int> v1;//空的vector
    
    std::cout<<"-----------------------vector迭代器的失效------------------------"<<std::endl;
    v1.push_back(2);
    auto iterator = v1.begin();
    std::cout<<*iterator<<std::endl;
    v1.reserve(6);
    std::cout<<*iterator<<std::endl;    //触发断点 can't dereference incalidated vector iterator

    return 0;
}

链表 list

list是一个双向链表。虽然与vector均为顺序容器，但不同的是list不支持随机存取，只能从头部或尾部一次顺序访问。插入和删除操作只会导致被删除元素的迭代器失效。

#include <iostream>
#include <list>

int main(int argc, char* argv[])
{
    //list的创建
    std::list<int> l1;
    std::list<int> l2{3,1,4,1,5,9};
    std::list<int> l3(3,5);

    std::cout<<"-----------------------list添加元素------------------------"<<std::endl;
    l1.push_back(2);
    l1.push_back(3);
    l1.insert(l1.begin(),10);
    l1.push_front(9);
    std::cout<<"---l1---"<<std::endl;
    for(const auto & item : l1)
    {
        std::cout<<item<<" ";
    }
    std::cout<<std::endl;
    
    std::cout<<"-----------------------list删除元素------------------------"<<std::endl;

    std::cout<<"---l2---"<<std::endl;
    for(const auto & item : l2)
    {
        std::cout<<item<<" ";
    }
    std::cout<<std::endl;
    
    l2.erase(l2.begin());
    l2.pop_back();
    l2.pop_front();
    std::cout<<"-----------------------list查找元素------------------------"<<std::endl;
    l2.front(); //返回第一个元素
    l2.rbegin(); //列表第一个元素的逆向迭代器
    l2.begin(); //列表第一个元素的迭代器
    l2.end(); //列表最后一个元素的迭代器
    l2.rend(); //列表最后一个元素的迭代器
    l2.cend(); //列表最后一个元素的常量迭代器
    std::cout<<"-----------------------list遍历------------------------"<<std::endl;
    std::cout<<"---l2---"<<std::endl;
    for(const auto & item : l2)
    {
        std::cout<<item<<" ";
    }
    std::cout<<std::endl;

    std::cout<<"---l3---"<<std::endl;
    for(auto i = l3.begin();i!=l3.end();i++)
    {
        std::cout<<*i<<" ";
    }
    std::cout<<std::endl;
    
    std::cout<<"-----------------------list迭代器失效------------------------"<<std::endl;
    //list的插入和删除不会引发像vector一样的迭代器失效
    l3.push_front(2);
    auto iterator = l3.begin();
    std::cout<<*iterator<<std::endl;
    l3.insert(l3.begin(),1);
    l3.resize(10);
    //l3.erase(l3.begin());
    std::cout<<*iterator<<std::endl;
    
    return 0;
}

list的迭代器失效。

std::cout<<"-----------------------list迭代器失效------------------------"<<std::endl;
   //list的插入一般不会引发迭代器失效
   l3.push_front(2);
   auto iterator = l3.begin();
   std::cout<<*iterator<<std::endl;
   //l3.insert(l3.begin(),1);
   //l3.resize(10);
   l3.erase(l3.begin());
   std::cout<<*iterator<<std::endl;

std::cout<<"-----------------------遍历list+删除导致的迭代器失效------------------------"<<std::endl;
    std::list<int>::iterator iterator = l2.begin();
    while(iterator != l2.end())
    {
        if(*iterator % 2 == 0)
        {
            l2.erase(iterator);  
        }
        else
        {
            ++iterator;
        }
    }

此时会触发断言，这是因为已经将iterator erase掉了，迭代器就不能++了。
所以，需要这样写避免断言：

std::cout<<"-----------------------遍历list+删除导致的迭代器失效------------------------"<<std::endl;
    std::list<int>::iterator iterator = l2.begin();
    while(iterator != l2.end())
    {
        if(*iterator % 2 == 0)
        {
            iterator = l2.erase(iterator);  
        }
        else
        {
            ++iterator;
        }
    }

常用操作的时间复杂度

push_back() / push_front() / pop_back() / pop_front()
时间复杂度： O(1)
insert() / erase()
时间复杂度： O(1)
与靠近头部复杂度越高，因为插入的目标位置后的元素均需要重新分配地址，随之带来的问题就是插入位置之前（或之后）的迭代器的引用、指针失效。
遍历or访问某一元素
时间复杂度O(n)

优点

插入、删除元素速度快
插入删除操作不会复制其他元素，改变元素地址，从一定程度上避免了迭代器失效。

缺点

内存不连续，空间利用率较低
当面对大量的元素时，遍历list会变得耗时。

应用场景

list适合经常插入、删除数据，数据量不大或不需要查找、遍历的情况。

映射 map

map是基于红黑树的二元关联容器，类似C#的字典，前一个模板类用于存储键值，后一个模板类用于存储值类型。map会按键值自动排序。

每个键只出现一次，若插入元素的键已经存在，则原元素会被新插入的元素替换。

当通过访问不存在的键查找值时，map会自动创建一个新的pair元素，其键是用户给定的查找值，值将通过默认的构造函数创建，一个新的变量。

#include <iostream>
#include <string>
#include <map>

struct Vector3f
{
    float x,y,z;
    Vector3f():x(0),y(0),z(0){}
    Vector3f(float a, float b,float c):x(a),y(b),z(c){}
};

struct GameObject
{
public:
    Vector3f Position;
    GameObject():Position(Vector3f()){}
    GameObject(float a, float b,float c):Position(a,b,c){}
    friend std::ostream& operator << (std::ostream &out,const GameObject &obj)
    {
        out<<"("<<obj.Position.x<<","<<obj.Position.y<<","<<obj.Position.z<<")";
        return out;
    }
};

int main(int argc, char* argv[])
{
    //create map
    std::map<std::string,GameObject> m1;
    //insert element
    GameObject obj1(10.f,2.f,1.f);
    m1.insert(std::pair<std::string,GameObject>("s1",obj1));
    m1["s2"] = GameObject(0.2f,0.5f,1.0f);
    m1.insert(std::pair<std::string,GameObject>("s3",GameObject(2.f,1.f,5.f)));
    m1.insert(std::pair<std::string,GameObject>("s0",GameObject(-2.f,-1.f,-5.f)));
    
    for(const auto& m : m1)
    {
        std::cout<<m.first<<": ";
        std::cout<<m.second<<std::endl;
    }
    //erase
    auto iterator = m1.begin();
    ++iterator;
    std::cout<<iterator->second<<std::endl;
    m1.erase(iterator);
    //std::cout<<iterator->second<<std::endl;
    std::cout<<"----------------"<<std::endl;
    for(const auto& m : m1)
    {
        std::cout<<m.first<<": ";
        std::cout<<m.second<<std::endl;
    }

    m1.insert(std::pair<std::string,GameObject>("s2",GameObject(100.f,0.f,10.f)));
    for(const auto& m : m1)
    {
        std::cout<<m.first<<": ";
        std::cout<<m.second<<std::endl;
    }
    //
    auto ret = m1.find("s1");
    std::cout<<ret->first<<std::endl;//这一步操作触发程序断言，因为此时m1中没有“s1”键。
    //当试图访问一个不存在的key时，map会调用默认的构造函数，在map中添加一个元素
    std::cout<<m1["s1"]<<std::endl;
    std::cout<<m1["s2"]<<std::endl;
    
    std::cout<<m1["s6"]<<std::endl;
    std::cout<<&m1["s6"]<<std::endl;
    for(const auto& m : m1)
    {
        std::cout<<m.first<<": ";
        std::cout<<m.second<<std::endl;
    }
    
    return 0;
}

常用操作的时间复杂度

insert() / erase() / count() / find()
时间复杂度均为O(logN)

优点

增删查的效率高
元素排列有序

缺点

使用[]查找失败时会增加map的元素数量，导致map的存储元素混乱不清
通过find()查找失败时，返回的迭代器是无效的。
删除后元素的迭代器也会失效。

应用场景

需要以键值对查找元素，元素保持一定的顺序时的情形可以使用map。比如，管理一个UI系统，可以使用map将枚举类和UI对应起来。

无序映射 unordered_map

unordered_map是基于哈希表实现的无序容器，其不会像map一样按键值排序。

每个键只出现一次，若插入元素的键已经存在，则原元素会被新插入的元素替换。

当通过访问不存在的键查找值时，unordered_map会自动创建一个新的pair元素，其键是用户给定的查找值，值将通过默认的构造函数创建，一个新的变量。

#include <iostream>
#include <string>
#include <unordered_map>

struct Vector3f
{
    float x,y,z;
    Vector3f():x(0),y(0),z(0){}
    Vector3f(float a, float b,float c):x(a),y(b),z(c){}
};

struct GameObject
{
public:
    Vector3f Position;
    GameObject():Position(Vector3f()){}
    GameObject(float a, float b,float c):Position(a,b,c){}

    // bool operator < (const GameObject& object)
    // {
    //     if(this->Position.x<object.Position.x)
    //         return true;
    //     return false;
    // }

    friend std::ostream& operator << (std::ostream &out,const GameObject &obj)
    {
        out<<"("<<obj.Position.x<<","<<obj.Position.y<<","<<obj.Position.z<<")";
        return out;
    }
};

int main(int argc, char* argv[])
{
    //create map
    std::unordered_map<std::string,GameObject> m1;
    //insert element
    GameObject obj1(10.f,2.f,1.f);
    m1.insert(std::pair<std::string,GameObject>("s1",obj1));
    m1["s2"] = GameObject(0.2f,0.5f,1.0f);
    m1.insert(std::pair<std::string,GameObject>("s3",GameObject(2.f,1.f,5.f)));
    m1.insert(std::pair<std::string,GameObject>("s0",GameObject(-2.f,-1.f,-5.f)));
    
    for(const auto& m : m1)
    {
        std::cout<<m.first<<": ";
        std::cout<<m.second<<std::endl;
    }
    //erase
    auto iterator = m1.begin();
    ++iterator;
    std::cout<<iterator->second<<std::endl;
    m1.erase(iterator);
    //std::cout<<iterator->second<<std::endl;
    std::cout<<"----------------"<<std::endl;
    for(const auto& m : m1)
    {
        std::cout<<m.first<<": ";
        std::cout<<m.second<<std::endl;
    }

    m1.insert(std::pair<std::string,GameObject>("s2",GameObject(100.f,0.f,10.f)));
    for(const auto& m : m1)
    {
        std::cout<<m.first<<": ";
        std::cout<<m.second<<std::endl;
    }
    //
    auto ret = m1.find("s2");
    std::cout<<ret->first<<std::endl;
    //当试图访问一个不存在的key时，unordered_map会调用默认的构造函数，在容器中添加一个新元素
    std::cout<<m1["s1"]<<std::endl;
    std::cout<<m1["s2"]<<std::endl;
    
    std::cout<<m1["s6"]<<std::endl;
    std::cout<<&m1["s6"]<<std::endl;
    for(const auto& m : m1)
    {
        std::cout<<m.first<<": ";
        std::cout<<m.second<<std::endl;
    }
    
    return 0;
}

常用操作的时间复杂度

insert() / erase() / count()
平均时间复杂度为O(1)，最坏情况O(n)
find()
时间复杂度O(1)

优点

增删查的效率高

缺点

元素无序存储
可能存在哈希冲突
使用[]查找时会导致unordered_map数量增加
通过find()查找失败时，返回的迭代器是失效的

应用场景

不需要元素有序排列，且需要快速查找元素。

集合 set

set是基于红黑树实现的简单关联容器，和数学集合的概念相似，set不允许出现相同元素，但set不能存储无限集。使用序列化的方式创建新的set本质是复制对象的值，开辟新的地址。set的元素地址是连续的。与map和unordered_map不同的是，向set中插入重复的元素并不会发生什么，原有元素并不会被新元素替代。对于自定义类型(or结构体)需要重载<运算符以完成自动排序。

#include <iostream>
#include <set>

struct Vector2D
{
public:
    int x,y;
    Vector2D():x(0),y(0){}
    Vector2D(int a,int b):x(a),y(b){}
    Vector2D(const Vector2D& vec):x(vec.x),y(vec.y){std::cout<<"Copy Vector2D"<<std::endl;}

    bool operator < (const Vector2D& vec) const
    {
        if(this->x< vec.x)
            return true;
        return false;
    }
};

int main(int argc, char* argv[])
{
    std::set<int> s1;
    std::set<int> s2{2,1,4,5,0};
    std::set<int> s3{20,10,40,50};
    std::set<Vector2D> s4{Vector2D(1,2),Vector2D(3,4),Vector2D(12,5)};
    //插入
    s1.insert(2);
    s1.insert(1);
    s1.insert(5);
    s1.insert(3);
    for(const auto &ele:s1)
    {
        std::cout<<ele<<" ";
    }
    std::cout<<std::endl;
    
    //删除
    s1.erase(5);
    for(const auto &ele:s1)
    {
        std::cout<<ele<<" ";
    }
    std::cout<<std::endl;
    
    //遍历
    for(const auto &ele:s2)
    {
        std::cout<<ele<<" ";
    }
    std::cout<<std::endl;

    //插入重复元素
    Vector2D vec(1,2);
    s4.insert(vec);
    for(const auto &ele:s4)
    {
        std::cout<<ele.x<<","<<ele.y<<"||";
    }
    std::cout<<std::endl;
    
    //内存地址
    for(const auto &ele:s1)
    {
        std::cout<<&ele<<" ";
    }
    std::cout<<std::endl;
    //查找
    auto it = s1.find(2);
    std::cout<<*it<<std::endl;
    
    return 0;
}

set的元素地址是连续的，但set的删除操作并不会引发其他元素的移动。

1	0000022E37DA8EAC 0000022E37DA902C 0000022E37DA932C //未进行操作的s1内存地址

//内存地址
    for(const auto &ele:s1)
    {
        std::cout<<&ele<<" ";
    }
    std::cout<<std::endl;
    auto it1 = s1.begin();
    it1++;
    s1.erase(it1);
    for(const auto &ele:s1)
    {
        std::cout<<&ele<<" ";
    }
    std::cout<<std::endl;

输出：

1 2	0000016F4B37821C 0000016F4B3781BC 0000016F4B37827C 0000016F4B37821C 0000016F4B37827C

常用操作的时间复杂度

插入、删除、查找
时间复杂度均为O(logN)

优点

插入元素自动排序，保证集合有序性

缺点

对于成员变量均为非数值型的类或结构体来说需要找到一个合适的变量用于比较大小进行排序的目的。（可以字符或id，字符可能会程序员被混淆，而增加id又需要一个额外的空间存储）
元素很少时，查找删除插入等操作的效率较低。

应用场景

需要元素有序且唯一的场景。与map类似
也可用于剔除一些重复的元素（比如，构建布料结构时的需要剔除重复的）

关于迭代器失效

迭代器是一个用于存储数据的模板类，成员变量包含一个指向模板数据的指针。迭代器失效本质是指向数据的指针为空。造成迭代器失效的原因是对STL进行操作时，内部数据地址变化引发的问题。因此由删除等操作引发的内部数据地址的变化的操作都会引发迭代器失效。特别是vector、map、set等有特殊结构的容器都可能触发迭代器失效。

对于vector容器，在中间插入，删除会导致插入位置后面的数据内存地址发生变化，而扩容则会导致容器内的数据被复制到其他内存中。从而使迭代器失效。

对于其他容器，删除一个数据可能引发数据结构的变化，也就是说数据的内存地址发生了变化。比如map的本质是一棵红黑树，删除一个数据，树会自平衡，从而数据内存发生变化。

迭代器失效常见于在循环中删除数据这一操作，比如上面map、set、unordered_map、list中的错误均属这一类。为避免这种错误，可以使用break跳出循环体，或者将迭代器重新赋值。