一、序列式容器

容器的通用查询方法

InputIterator find (InputIterator first, InputIterator last, const T& val);

其中，first 和 last 为输入迭代器，[first, last) 用于指定该函数的查找范围；val 为要查找的目标元素。

该函数会返回一个输入迭代器，当 find() 函数查找成功时，其指向的是在 [first, last) 区域内查找到的第一个目标元素；如果查找失败，则该迭代器的指向和 last 相同。

count(first,last,value);

其中first是容器的首迭代器，last是容器的末迭代器，value是询问的元素。函数返回和value相同的元素个数；
count可以用于关联容器的查询：

map<Key_Type, ValType> mymap;
if(map.count(value1) == 0){/*.没有元素.*/}

1. vector

特点：从尾部快速插入和删除，可直接访问任意元素。
实现：动态数组。malloc、rela
常用方法：

1. 头文件： #include <vector>

2. 创建和初始化

   vector<Type> arr;
   vector<Type> arr(n [, val]); //创建长度为n，[初始值为val]的数组
   vector<vector<Type>> arr(n, vector<Type>(m, val)); //n*m的二维数组，初值为val

3. 尾部插入和删除

   arr.push_back(elem); //尾部插入
   arr.pop_back(); //尾部删除

4. 查询

   arr[i]; //下标访问
   arr.front();    //返回头部元素
   arr.back();     //返回尾部元素

5. 容器大小

   arr.size(); //返回元素个数
   arr.capacity(); //容器容量

6. 任意位置插入

   arr.insert(pos, elem); //pos位置插入elem
   arr.insert(pos, n, elem); //pos位置插入n个elem

7. 任意位置删除

   arr.erase(pos); //删除pos位置元素，返回下一个元素位置
   arr.erase(begin, end); //删除[begin, end)元素，返回下一个的位置

8. 逆序存储

   arr.reverse(pos1, pos2); //pos1到pos2的元素逆序存储

9. 迭代器

   arr.begin();
   arr.end();
   for(auto i = arr.begin(); i != arr.end(); i++){
      cout<<*i<<endl;
   }

2. deque (Double-Ended Queue)

特点：从前面或后面快速的插入与删除，直接访问任何元素。
实现：双端队列。中控器（map，索引数组）+缓冲区（分段数组，实际存储体），像二维数组。
常用方法：

1. 头文件： #include <deque>

2. 创建和初始化（同vector）

   deque<Type> deq;

3. 头部/尾部插入和删除

   deq.push_front(elem);    //头部插入
   deq.pop_front();         //头部删除
   deq.push_back(elem);
   dqe.pop_back();

4. 查询

   dqe[i];
   dqe.front();    //返回头部元素
   dqe.back();

5. 任意位置插入/删除（同vector）

6. 迭代器（同vector）

3. list

特点：从任何地方快速插入与删除
实现：双向链表
常用方法：

1. 头文件 #include <list>

2. 创建和初始化（同vector）

   list<Type> li;

3. 插入和删除

   li.push_front(elem);
   li.pop_front();
   li.push_back(elem);
   li.pop_back();

4. 查询：使用迭代器

   //遍历访问
   for(auto i = li.begin(); i != li.end(); i++){
       cout<<*i<<endl;
   }
   //搜索
   list<int>::iterator int_itor=find(li.begin(),li.end(),3);
   cout <<*int_itor << endl;

5. 容器大小

6. 任意位置插入（同vector）

   代码块

7. 任意位置删除（同vector）

8. 迭代器（同vector）

   li.begin();
   li.end();

二、关联容器

特点：都是有序的，升序排列

1. set

特点：快速查找，不允许重复值。存储的是一组无重复的元素。如果要修改某一个元素值，必须先删除原有的元素，再插入新的元素。
实现：红黑树
常用方法：

1. 头文件 #include <set>

2. 创建和初始化

   set<Type> myset;
   set<Type, op> myset; //op为仿函数，排序规则，默认是 升序less<T>，降序为greater<T>
   //仿函数
   struct cmp{
      bool operator()(T &a, T &b){
          return a < b;   //降序
      }
   }

3. 插入和删除

   myset.empty();    //判断是否为空
   myset.insert(elem);    //插入elem
   myset.insert(pos, elem);    //pos位置插入elem
   myset.erase(elem);    //删除elem
   myset.erase(pos);     //删除pos位置元素
   myset.clear();    //清空集合

4. 查询

   myset.find(elem); //返回迭代器，=myset.end()时则找不到元素
   myset.count(elem);    //返回elem元素的数目

5. 容器大小

   myset.size();
   myset.max_size();    //可容纳最大元素数量

6. 迭代器

   //顺序遍历
   myset.begin(); 
   myset.end();
   //逆序遍历
   myset.rbegin();
   myset.rend();

2. multiset

特点：快速查找，允许重复值
实现：红黑树
常用方法：

1. 头文件 #include <set>

3. map

特点：单重映射，基于关键字快速查找，不允许重复值
实现：红黑树，按Key排序
常用方法：

1. 头文件 #include <map>

2. 创建和初始化

   map<KeyType, ValType> m;
   map<KetType, ValType, op> m; //op为排序规则，仿函数，默认是less<T>,升序

3. 插入和删除

• 直接插入（修改式）

  m[key] = vlaue;    //不适用于multimap

• 用pair<>构造键值对，然后插入

  m.insert(pair<KeyType, ValType>(key, value));

• 使用make_pair()函数构建键值对，然后插入

  m.insert(make_pair(key, value));

• 使用value_type标志

  m.insert(map<KeyType, ValType>::value_type(key, value));

4. 查询

m[key];    //使用前需要保证key在m中，否则会自动插入key的值
m.find(key);    //返回迭代器，找不到时返回m.end()
m.count(key);   //返回数量，找不到时返回值为0

使用m.begin()和m.end()迭代器遍历

for(auto i = m.begin(); i != m.end(); i++){
      cout<<i->first<<" "<<i->second<<endl;
}

5. 容器大小

   m.size();
   m.max_size();

6. 迭代器

   m.begin();
   m.end();

4. multimap

特点：一对多映射，基于关键字快速查找，允许重复值
实现：红黑树
常用方法：

5. C++11新特性

用hash实现map、multimap、set、multiset

1. unordered_map
2. unordered_multimap
3. unordered_set
4. unordered_multimset

三、容器适配器

1. stack栈

特点：先进后出
实现：deque
常用方法：

1. 头文件 #include <stack>

2. 创建

   stack<Type> st;

3. 插入和删除

   st.push(elem);    //elem插入到栈顶
   st.pop();         //删除栈顶元素

4. 查询

   st.top();    //返回栈顶元素

5. 容器大小

   st.size();

6. 判断是否为空

   st.empty();

2. queue

特点：先进先出，只能在尾部插入，只能在头部弹出
实现：deque
常用方法：

1. 头文件 #inclue <queue>

2. 创建和初始化

   queue<Type> que;

3. 插入和删除

   que.push(elem);    //队列尾部插入元素
   que.pop();         //弹出队列头部元素

4. 查询

   que.front();    //返回队列头的元素引用
   que.back();     //返回队列尾的元素引用

5. 容器大小

   que.size();

6. 判断是否为空

   que.empty();

3. priority_queue

特点：优先级最大的先出
实现：vector，堆排序，大顶堆/小顶堆
常用方法：

1. 头文件 #include <queue>

2. 创建和初始化

   priority_queue<int> pq；
   priority_queue<Type, container<Type>, op> pq;
   //container可以是C++中任意一种容器。op为排序规则，是仿函数。对基本类型，默认less<T>是大顶堆，也可以选greater<T>
   //仿函数
   struct cmp{
      bool operator() (Type &a, Type &b){
            return a > b; //小顶堆
      }
   }

3. 插入和删除

   pq.push(elem);    //插入元素elem，并调整堆
   pq.pop();         //弹出堆顶（优先级最大）元素

4. 查询

   pq.top();    //返回堆顶元素索引

5. 容器大小

   pq.size();

6. 判断优先队列是否为空

   pq.empty();