1、容器

定义

容器（container）用于存放数据的类模板。

分类

（1）顺序容器：
顺序容器有以下三种：可变长动态数组 vector、双端队列 deque、双向链表 list。
它们之所以被称为顺序容器，是因为元素在容器中的位置同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么位置（尾部、头部或中间某处）插入，元素就会位于什么位置。
（2）关联容器：
关联容器有以下四种：set、multiset、map、multimap。
关联容器内的元素是排序的。插入元素时，容器会按一定的排序规则将元素放到适当的位置上，因此插入元素时不能指定位置。
（3）容器适配器：
三种容器适配器：栈 stack、队列 queue、优先级队列priority_queue。

成员函数

所有容器都有以下两个成员函数：

int size()：返回容器对象中元素的个数。
bool empty()：判断容器对象是否为空。

顺序容器和关联容器还有以下成员函数：

begin()：返回指向容器中第一个元素的迭代器。
end()：返回指向容器中最后一个元素后面的位置的迭代器。
rbegin()：返回指向容器中最后一个元素的反向迭代器。
rend()：返回指向容器中第一个元素前面的位置的反向迭代器。
erase(...)：从容器中删除一个或几个元素。
clear()：从容器中删除所有元素。

顺序容器还有以下常用成员函数：

front()：返回容器中第一个元素的引用。
back()：返回容器中最后一个元素的引用。
push_back()：在容器末尾增加新元素。
pop_back()：删除容器末尾的元素。
insert(...)：插入一个或多个元素。

向量(vector>

vector是一个线性顺序结构，相当于动态数组，也常被用来做动态数组的功能，其大小是动态扩展的，当存储的数据超过分配的空间（即capacity）的返回值时，vector会首先申请一个更大的内存块，将现有的内存数据拷入新内存块，然后销毁原内存块中的数据，并释放掉内存。
特点：
（1）空间连续，可动态扩展（push_back与pop_back)。
（2）随机访问方便且速度快([]或at)。
（3）存储区域空间不浪费，但未存储区域的空间浪费（未存满）。
（4）内部插入与删除操作效率低，因为会操作先操作该位数据，再将其后面的数据进行移位操作。

双向链表(list)

list是一个线性链表结构，数据由若干个节点构成，每个节点都包括实际存储数据、前驱指针与后驱指针。
无需分配指定的内存大小，并可以任意伸缩，因为它存储再不连续的内存空间中，通过指针连接起来。
特点：
（1）内存空间不连续，可随意动态操作。
（2）内部任意位置插入与删除，可两端push与pop。
（3）不能进行内部随机访问，即不支持[]与at。
（4）占用较多的内存空间（因为还要存储指针）。

双端队列(deque)

deque是一种优化了的、对序列两端元素可添加与删除的基本序列容器。
是vector与list的结合，使用一段段连续的子空间来构成。
特点：
（1）随机访问比list方便，但不如vector，支持[]与at。
（2）可以内部插入与删除，但不如list。
（3）可以两端push与pop。

关联容器

set, multiset, map, multimap 是一种非线性的树结构，具体来说采用比较高效的特殊平衡检索二叉树-红黑树结构。
set又称集合，元素不重复，且是排好序的，其插入比vector快，查找和末尾添加比vector慢。
multiset又称多重集合，其元素可以不唯一，也是排好序的。
map提供了一种"键-值"的关系，"键"相当于"值"的索引，不可重复，并也是排好序的，按照链表的方式存储。
multimap允许"键"重复。

容器适配器

三种适配器：栈stack 、队列queue 和优先级priority_queue 。
适配器是容器的接口，本身不能直接保存元素，其机制相当于调用另一种顺序容器去实现。
默认下，stack与queue基于deque实现，priority_queue 则基于vector实现。
stack的特点是先进后出，故可以关联任意一种顺序容器。
queue的特点是先进先出，故不能建立在vector容器上。
priority_queue是优先级队列，要求提供随机访问功能，故不能建立在list容器上。

map与unordered_map的区别

内部实现机理不同：
map： map内部实现了一个红黑树，红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。
unordered_map: unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。
优缺点及适用：
map：
优点：有序性，红黑树。
缺点：空间占用率高。
适用处：对于那些有顺序要求的问题，用map会更高效一些。
unordered_map：
优点：因为内部实现了哈希表，因此其查找速度非常的快。
缺点：哈希表的建立比较耗费时间。
适用处：对于查找问题，unordered_map会更加高效一些。
操作举例：

#include <iostream>  
#include <unordered_map>  
#include <map>
#include <string>  
using namespace std;  
int main()  
{  
    unordered_map<int, string> myMap={{ 5, "张大" },{ 6, "李五" }};//使用{}赋值
    myMap[2] = "李四";  //使用[ ]进行单个插入，若已存在键值2，则赋值修改，若无则插入。
    myMap.insert(pair<int, string>(3, "陈二"));//使用insert和pair插入

    //遍历输出+迭代器的使用
    auto iter = myMap.begin();//auto自动识别为迭代器类型unordered_map<int,string>::iterator
    while (iter!= myMap.end())
    {  
        cout << iter->first << "," << iter->second << endl;  
        ++iter;  
    }  

    //查找元素并输出+迭代器的使用
    auto iterator = myMap.find(2);//find()返回一个指向2的迭代器
    if (iterator != myMap.end())
        cout << endl<< iterator->first << "," << iterator->second << endl;  
    system("pause");  
    return 0;  
}

二、编程基础-容器