c++STL学习

模板类
实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。

核心包括以下三个组件

容器（Containers） 容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器，比如 deque、list、vector、map 等。
算法（Algorithms） 算法作用于容器。它们提供了执行各种 *** 作的方式，包括对容器内容执行初始化、排序、搜索和转换等 *** 作。
迭代器（iterators） 迭代器用于遍历对象集合的元素。这些集合可能是容器，也可能是容器的子集。

#include 
#include 
using namespace std;
 
int main()
{
   vector<int> vec; // 创建一个向量存储 int
   int i;
   cout << "vector size = " << vec.size() << endl;   // 显示 vec 的原始大小
   for(i = 0; i < 5; i++){  // 推入 5 个值到向量中
      vec.push_back(i);
   }
   
   cout << "extended vector size = " << vec.size() << endl; // 显示 vec 扩展后的大小
   for(i = 0; i < 5; i++){
      cout << "value of vec [" << i << "] = " << vec[i] << endl;  // 访问向量中的 5 个值
   }
   
   vector<int>::iterator v = vec.begin();
   while( v != vec.end()) {
      cout << "value of v = " << *v << endl; // 使用迭代器 iterator 访问值
      v++;
   }
 
   return 0;
}

迭代器：iterator 相当于一种指针类型的类，类的实例是一个返回下一个元素的指针；
deque ouble-ended queue，双端队列 是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端d出，相比list增加[]运算符重载。
deque运行常数时间对头端或尾端进行元素的插入和删除 *** 作。
deque没有所谓的容器概念，因为它是动态地以分段连续空间组合而成随时可以增加一块新的内存空间并拼接起来。

vector: 向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
容器特性
1.顺序序列
顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。
2.动态数组
支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该 *** 作。提供了在序列末尾相对快速地添加/删除元素的 *** 作。
3.能够感知内存分配器的（Allocator-aware）
容器使用一个内存分配器对象来动态地处理它的存储需求。

map
C++ 中 map 提供的是一种键值对容器，里面的数据都是成对出现的,如下图：每一对中的第一个值称之为关键字(key)，每个关键字只能在 map 中出现一次；第二个称之为该关键字的对应值。在一些程序中建立一个 map 可以起到事半功倍的效果，本文为大家总结了 map 的一些基本简单的 *** 作！

list
list是一种序列式容器。list容器完成的功能实际上和数据结构中的双向链表是极其相似的，list中的数据元素是通过链表指针串连成逻辑意义上的线性表，也就是list也具有链表的主要优点，即：在链表的任一位置进行元素的插入、删除 *** 作都是快速的。list的实现大概是这样的：list的每个节点有三个域：前驱元素指针域、数据域和后继元素指针域。前驱元素指针域保存了前驱元素的首地址；数据域则是本节点的数据；后继元素指针域则保存了后继元素的首地址。其实，list和循环链表也有相似的地方，即：头节点的前驱元素指针域保存的是链表中尾元素的首地址，list的尾节点的后继元素指针域则保存了头节点的首地址，这样，list实际上就构成了一个双向循环链。由于list元素节点并不要求在一段连续的内存中，显然在list中是不支持快速随机存取的，因此对于迭代器，只能通过“++”或“–” *** 作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的 *** 作，这点，是与vector等不同的地方。

vector ：vector和built-in数组类似，拥有一段连续的内存空间，能非常好的支持随即存取，即[] *** 作符，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝，另外，当插入较多的元素后，预留内存空间可能不够，需要重新申请一块足够大的内存并把原来的数据拷贝到新的内存空间。这些影响了vector的效率，但是实际上用的最多的还是vector容器，建议大多数时候使用vector效率一般是不错的。

list：list就是数据结构中的双向链表(根据sgi stl源代码)，因此它的内存空间是不连续的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它没有提供[] *** 作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。

deque： deque是一个double-ended queue，它的具体实现不太清楚，但知道它具有以下两个特点：它支持[] *** 作符，也就是支持随即存取，并且和vector的效率相差无几，它支持在两端的 *** 作：push_back,push_front,pop_back,pop_front等，并且在两端 *** 作上与list的效率也差不多。

向量：因为只能在首尾 *** 作，存储线性，所以是有方向的；