reference：c语言中文网：STL教程

STL组成（6大组件+13个头文件）

STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成，其中后面 4 部分是为前 2 部分服务的；
6大组成部分：

13个头文件：

迭代器 iterator

常用的迭代器按功能强弱分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器 5 种。

输入迭代器和输出迭代器比较特殊，它们不是把数组或容器当做操作对象，而是把输入流/输出流作为操作对象。

常用迭代器

1) 前向迭代器（forward iterator）假设 p 是一个前向迭代器，则 p 支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。

2) 双向迭代器（bidirectional iterator）
双向迭代器具有正向迭代器的全部功能，除此之外，假设 p 是一个双向迭代器，则还可以进行 —p 或者 p— 操作（即一次向后移动一个位置）。

3) 随机访问迭代器（random access iterator）
随机访问迭代器具有双向迭代器的全部功能。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
p+=i：使得 p 往后移动 i 个元素。
p-=i：使得 p 往前移动 i 个元素。
p+i：返回 p 后面第 i 个元素的迭代器。
p-i：返回 p 前面第 i 个元素的迭代器。
p[i]：返回 p 后面第 i 个元素的引用。

此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。另外，表达式 p2-p1 也是有定义的，其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）。

C++ 11 标准中不同容器指定使用的迭代器类型:

容器适配器 stack 和 queue 没有迭代器，它们包含有一些成员函数，可以用来对元素进行访问

迭代器的定义方式

尽管不同容器对应着不同类别的迭代器，但这些迭代器有着较为统一的定义方式：
着较为统一的定义方式，具体分为 4 种，如表 1 所示。

通过定义以上几种迭代器，就可以读取它指向的元素，*迭代器名就表示迭代器指向的元素。
常量迭代器和非常量迭代器的分别在于，通过非常量迭代器还能修改其指向的元素。
正向迭代器++的方向和反向迭代器相反；
注意，以上 4 种定义迭代器的方式，并不是每个容器都适用。有一部分容器同时支持以上 4 种方式，比如 array、deque、vector；

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v{1,2,3,4,5,6,7,8,9,10}; 
    cout << "第一种遍历方法：" << endl;
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] <<" "; //像普通数组一样使用vector容器
    //创建一个正向迭代器
       cout << endl << "第二种遍历方法：" << endl;
       vector<int>::iterator i;
    //用 != 比较两个迭代器
    for (i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";
       cout << endl << "第三种遍历方法：" << endl;
    for (i = v.begin(); i < v.end(); ++i) //用 < 比较两个迭代器
        cout << *i << " ";
       cout << endl << "第四种遍历方法：" << endl;
    i = v.begin();
    while (i < v.end()) { //间隔一个输出
        cout << *i << " ";
        i += 2; // 随机访问迭代器支持 "+= 整数"  的操作
    }
}
output：
    第一种遍历方法：
    1 2 3 4 5 6 7 8 9 10
    第二种遍历方法：
    1 2 3 4 5 6 7 8 9 10
    第三种遍历方法：
    1 2 3 4 5 6 7 8 9 10
    第四种遍历方法：
    1 3 5 7 9

不同容器天然对应着不同的迭代器；可从前表中查询；不同迭代器有不同的功能；
c++ 容器功能表：

序列式容器

序列容器大致包含以下几类容器：

• array（数组容器）；
• vector（向量容器）；
• deque（双端队列容器）；
• list（链表容器）；
• forward_list（正向链表容器）；

容器常见的函数成员

array,vector,deque

list,forward

array 用法

它就是在 C++ 普通数组的基础上，添加了一些成员函数和全局函数。在使用上，它比普通数组更安全，且效率并没有因此变差。
array的大小在初始化之后就固定了，无法动态改变。

初始化

std::array<double, 10> values;//初始化10个double数组
std::array<double, 10> values {};//初始化10个double型数据，并且值都是0.0
std::array<double, 10> values {0.5,1.0,1.5,2.0};//初始化10个double数组，前4位赋值

实例

在 头文件中还重载了 get() 全局函数，该重载函数的功能是访问容器中指定的元素，并返回该元素的引用。
C++ 11 标准库还新增加了 begin() 和 end() 这 2 个函数，和 array 容器包含的 begin() 和 end() 成员函数不同的是，标准库提供的这 2 个函数的操作对象，既可以是容器，还可以是普通数组。当操作对象是容器时，它和容器包含的 begin() 和 end() 成员函数的功能完全相同；如果操作对象是普通数组，则 begin() 函数返回的是指向数组第一个元素的指针，同样 end() 返回指向数组中最后一个元素之后一个位置的指针。

array<int, 4> values{};
//初始化 values 容器为 {0,1,2,3}
for (int i = 0; i < values.size(); i++) {
    values.at(i) = i;
}
//使用 get() 重载函数输出指定位置元素
cout << get<3>(values) << endl;
//如果容器不为空，则输出容器中所有的元素
if (!values.empty()) {
    for (auto val = values.begin(); val < values.end(); val++) {
        cout << *val << " ";
    }
}
output：
    3
    0 1 2 3

迭代器

array对应的是随机访问迭代器。

值得一提的是，迭代器函数在实际使用时，其返回值类型都可以使用 auto 关键字代替，编译器可以自行判断出该迭代器的类型。

数据访问

单个元素

• 容器名[]的方式直接访问和使用容器中的元素：由于没有做任何边界检查，所以即便使用越界的索引值去访问或存储元素，也不会被检测到。
• at（）成员函数访问：可以有效避免越界访问的问题。
• get 模板函数，它是一个辅助函数，能够获取到容器的第 n 个元素。参数的实参必须是一个在编译时可以确定的常量表达式，所以它不能是一个循环变量。
• array 容器提供了 data() 成员函数，通过调用该函数可以得到指向容器首个元素的指针。通过该指针，我们可以获得容器中的各个元素。

  values[4] = values[3] + 2.O*values[1];
  values.at (4) = values.at(3) + 2.O*values.at(1);
  cout << get<3>(words) << endl; // Output words[3]
  cout << *( words.data()+1);

  多个元素访问

  除了for循环外还有一个简洁的遍历方法 ：

  for(auto&& value : values)
    total += value;//在gcc上编译位通过***（已解决，c++版本未改成11）

vector 容器

vector 常被称为向量容器，因为该容器擅长在尾部插入或删除元素，在常量时间内就可以完成，时间复杂度为O(1)；而对于在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶O(n)。

初始化

std::vector<double> values;//空容器，没有分配空间
values.reserve(20);//容器增加20个元素容量，起始位置等可能会失效，使用后最好重新生成一下迭代器
std::vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};//初始化并指定初值//{}写初值，（）写个数
std::vector<double> values(20);//初始化20个元素0
std::vector<double> values(20, 1.0);//也可以指定其他初值
std::vector<char>value1(5, 'c');
std::vector<char>value2(value1);//通过存储元素类型相同的其它 vector 容器，也可以创建新的 vector 容器
int array[]={1,2,3};//用一对指针或者迭代器来指定初始值的范围
std::vector<int>values(array, array+2);//values 将保存{1,2}

迭代器

• 和 array 容器不同，vector 容器可以随着存储元素的增加，自行申请更多的存储空间。因此，在创建 vector 对象时，我们可以直接创建一个空的 vector 容器，并不会影响后续使用该容器。
• 但这会产生一个问题，即在初始化空的 vector 容器时，不能使用迭代器。
• 同时在vector申请更多内存时，因为空间不够，容器中的所有元素都有可能被移动到其他位置，导致begin和end等失效。

  数据访问

  单个元素

  下标访问：

  cout << values[0] << endl;

  at函数：

  cout << values.at(0) << endl;

  front() 和 back()，它们分别返回 vector 容器中第一个和最后一个元素的引用，通过利用这 2 个函数返回的引用，可以访问（甚至修改）容器中的首尾元素：

  cout << "values 首元素为：" << values.front() << endl;
  cout << "values 尾元素为：" << values.back() << endl;

  data() 成员函数，该函数的功能是返回指向容器中首个元素的指针：

  cout << *(values.data() + 1) << endl;////修改容器中第 2 个元素的值

  多个元素

  for加size遍历：

  for (int i = 0; i < values.size(); i++) {
    cout << values[i] << " ";
  }//capacity() 成员函数返回的是容器容量，而不是实际元素个数

  使用基于范围的循环，此方式将会逐个遍历容器中的元素：

  for (auto&& value : values)
    cout << value << " ";

  使用 vector 迭代器遍历 vector 容器：

  for (auto first = values.begin(); first < values.end(); ++first) {
    cout << *first << " ";
  }

  添加数据

  emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。
  push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；
  而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

  class testDemo
  {
  public:
    testDemo(int num):num(num){
        std::cout << "调用构造函数" << endl;
    }
    testDemo(const testDemo& other) :num(other.num) {
        std::cout << "调用拷贝构造函数" << endl;
    }
    testDemo(testDemo&& other) :num(other.num) {
        std::cout << "调用移动构造函数" << endl;
    }
  private:
    int num;
  };
  int main()
  {
    cout << "emplace_back:" << endl;
    std::vector<testDemo> demo1;
    demo1.emplace_back(2);  
    cout << "push_back:" << endl;
    std::vector<testDemo> demo2;
    demo2.push_back(2);
  }

  output：

  emplace_back:
  调用构造函数
  push_back:
  调用构造函数
  调用移动构造函数

  这个程序的重点在于testDemo类的3个接口，都是构造方式；

  插入元素

  insert()

  | 语法格式 | 用法说明 | | —- | —- | | iterator insert(pos,elem) | 在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器。 | | iterator insert(pos,n,elem) | 在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器。 | | iterator insert(pos,first,last) | 在迭代器 pos 指定的位置之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器。 | | iterator insert(pos,initlist) | 在迭代器 pos 指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。 |

eg：

std::vector<int> demo{1,2};
//第一种格式用法
demo.insert(demo.begin() + 1, 3);//{1,3,2}
//第二种格式用法
demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}
//第三种格式用法
std::array<int,3>test{ 7,8,9 };
demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}
//第四种格式用法
demo.insert(demo.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}

emplace()

emplace() 每次只能插入一个元素，而不是多个。
语法：iterator emplace (const_iterator pos, args…);

demo1.emplace(demo1.begin(), 3);

总结

通过 insert() 函数向 vector 容器中插入 testDemo 类对象，需要调用类的构造函数和移动构造函数（或拷贝构造函数）；而通过 emplace() 函数实现同样的功能，只需要调用构造函数即可。
因此emplace的效率更高。

删除元素

删除元素除了用容器的成员函数，还可以用全局函数；

erase

iterator erase (pos);
iterator erase (iterator first, iterator last);
pos 为指定被删除元素位置的迭代器，同时该函数会返回一个指向删除元素所在位置下一个位置的迭代器。

auto iter = demo.erase(demo.begin() + 1);//删除元素 2
 auto iter = demo.erase(demo.begin()+1, demo.end() - 2);

swap

如果不在意容器中元素的排列顺序，可以结合 swap() 和 pop_back() 函数，同样可以实现删除容器中指定位置元素的目的。

注意，swap() 函数在头文件 和 中都有定义，使用时引入其中一个即可。

remove

如果要删除容器中和指定元素值相同的所有元素，可以使用 remove() 函数，该函数定义在 头文件中。

vector<int>demo{ 1,3,3,4,3,5 };
//交换要删除元素和最后一个元素的位置
auto iter = std::remove(demo.begin(), demo.end(), 3);
//输出剩余的元素
for (auto first = demo.begin(); first < iter;++first) {
    cout << *first << " ";
}

注意，在对容器执行完 remove() 函数之后，由于该函数并没有改变容器原来的大小和容量，因此无法使用之前的方法遍历容器，而是需要向程序中那样，借助 remove() 返回的迭代器完成正确的遍历。

remove() 的实现原理是，在遍历容器中的元素时，一旦遇到目标元素，就做上标记，然后继续遍历，直到找到一个非目标元素，即用此元素将最先做标记的位置覆盖掉，同时将此非目标元素所在的位置也做上标记，等待找到新的非目标元素将其覆盖。因此，如果将上面程序中 demo 容器的元素全部输出，得到的结果为 1 4 5 4 3 5。

可以在输出前加上 demo.erase(iter, demo.end());//将无用元素删除