容器（container），顾名思义表示对象的集合，这些对象的类型都相同，
每个对象都有一个自己的索引，用这个索引我们就可以方便的访问该对象了。
只有顺序容器的构造函数才接受大小参数，关联容器并不支持。
vector 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。
vector<int> vi(10, -1); // 10个-1
deque 双端队列。支持快速快速访问。在头尾位置插入/删除速度很快。
deque<double> deqd(10); // 10个元素 0
list 双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快。
list<int> li(5,1); // 5个1
forward_list 单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快。
forward_list<string> fls(10); // 10个元素 0
array 固定大小数组。支持快速随机访问，不能添加或删除元素。
array<int, 42> ia; // 42个int的数组, 支持拷贝构造
array<int, 42> ia2 = ia;
而内置数组不支持拷贝构造.
std::array也提供了 at() 函数。
string 与vector相似的容器，但专门用于保存字符。随机访问快，在尾部插入/删除都很快。
1、通常vector是最好的选择，除非你有很好的理由选择其他容器；
2、如果程序有很多小的元素，且空间额外开销很重要，则不要使用 list 或 forward_list 容器；
3、如果程序要求随机访问，应使用 vector 或 deque 容器；
4、如果程序要在头尾位置插入/删除，且不会在中间位置进行插入/删除操作，则应使用deque容器。
vector<vector<int>> vvi;//相当于二维数组
STL中的vector容器就是动态大小数组。
vector<int> v;
v.push_back(k); 在后面插入 k 这个元素
v.size() 返回容器中实际元素的个数
v.resize() 重新设定容器的大小
v.at(index) 返回索引位置的元素
v.begin() 返回第一个元素的迭代器 vector<T>::iterator
v.end() 返回最后一个元素后面位置的迭代器
v.front() 返回第一个元素
v.back() 返回最后一个元素
v.empty() 返回1为空，0为非空
v.swap() 交换两容器
rbegin() 返回逆向容器中的第一个元素的迭代器
rend() 返回逆向容器中的最后一个元素后面位置的迭代器
clear() 清除容器中所有元素
insert() 插入
max_size() 返回最大数据量
v.erase() 擦除元素
#include <vector> //头文件包含
using namespace std; //或者using std::vector;
//vector定义并初始化
vector<int> v1;
for (int i=0;i<10;i++)
v1.push_back(i+1); // 从后面一次插入元素
//使用迭代器遍历vector
vector<int>::iterator iter = v1.begin();
for (;iter!=v1.end();iter++)
{
cout<<*iter<<" ";
}
vector容器中存储的元素在内存中是连续存储的。
假如容器中没有空间容纳新元素，此时由于元素必须连续存储以便索引访问，
所以不能在内存中随便找个地方存储这个新的元素，于是vector必须重新分配空间 v.resize(10)，
用于存放原来的元素和新添加的元素：
存放在旧容器中的元素被复制到新的容器中，接着插入新的元素，最后撤销旧的存储空间。
为了使vector容器实现快速的内存分配，
其实际分配的容量要比当前所需的空间多一些，vector容器预留这些空间，用于存放新的元素。
v.push_back(val)
先将容器c中的元素拷贝到新的内存空间中，
然后在将val值拷贝到新空间的末尾，
最后析构掉原始空间。
当push_back检测到空间不足时，将自动以 2倍 的方式扩展空间。
对于大量数据来说，这是一个弊端，可以使用可以使用 vector::reserve 方法来改善。
push_back()使用 vector::insert 方法实现，在容器尾部insert来实现的。
void push_back(_Elem _Ch)
{ // insert element at end
insert(end(), _Ch); // 算法
}
pop_back() 使用vector::earse，擦除最后一个位置元素来实现的。
删除容器尾部元素，同时c.size()会减少。
void pop_back()
{ // erase element at end
erase(this->_Mysize - 1); // throws if _Mysize == 0
}
v.shrink_to_fit();
// 为了不让vector浪费太多的内存，我们在最后调用了shrink_to_fit。
// 该函数会为元素分配足够的空间，将剩余的元素移到该空间内，并且删除之前那个比较大的内存空间。
// 会将多余的空间归还给系统
随机存取，即 vi[i] 操作 和 vi.at(i)。
at() 函数会检查给定的索引值是否越界，如果越界则返回一个异常。
因为检查越界要花费一些时间，所以at函数会让程序慢一些。
当需要非常快的索引成员时，并能保证索引不越界，我们会使用[]快速访问vector实例。
很多情况下，at() 函数在牺牲一点性能的基础上，有助于发现程序内在的bug。
默认使用 at() 函数时一个好习惯。
当代码的性能很差，但有没有bug存在时，可以使用性能更高的操作符[]来替代at函数。
动态操作, 尾部插入 vi.push_back() 与 尾部插删除 vi.pop_back()
自动调整内存，节省空间
try{} catch(){} 捕获 vector访问越界 异常
try{
temp = v.at(k);
}
catch(std::out_of_range &e){
std::cout << e.what() << std::endl;
} 实现插入与删除操作效率低
只能在尾部插入与删除，在头部插入与删除消耗时间规模与容器大小成正比,它会将后面的元素依次前移。
当动态添加的数据超过默认内存大小时，要进行整体的重新分配，拷贝与释放。
注意此操作会改变数组顺序，对于未排序的数组没什么问题，对于已排序的数组不可用，或者删除之后再排序
// 输入 vector，和要删除的 元素的索引 idx
template <typename T>
void quick_remove_at(std::vector<T> &v, std::size_t idx)
{
if (idx < v.size()) // 索引为出界
{
v[idx] = std::move(v.back());// 最后的元素移动到要删除的位置
// std::move(v.back()); // 避免拷贝，相当于只是拷贝了指针
// *it = v.back(); // 会进行拷贝
v.pop_back(); // 删除最后的元素
}
}
// 输入 vector，和要删除的 元素的迭代器 it
template <typename T>
void quick_remove_at(std::vector<T> &v,
typename std::vector<T>::iterator it)
{
if (it != std::end(v))// 迭代器未出界
{
*it = std::move(v.back());// 最后的元素移动到要删除的位置
v.pop_back(); // 删除最后的元素
}
}
list容器中添加元素时，只需要创建一个新的元素，
然后将该元素连接到已经存在的链表中，
不需要重新分配存储空间，也不用复制任何已存在的元素。
非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。
支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。
每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。
可以不分配必须的内存大小方便的进行添加和删除操作。
使用的是非连续的内存空间进行存储。
list<char> lit;
//-----------链表可以从两端插入-------------------
lit.push_back('b');
lit.push_front('d');
//-----------链表打印-------------------
list<char>::iterator it;
for(it=lit.begin();it!=lit.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;
//-----------链表可以从两端删除-------------------
lit.pop_back();
lit.pop_front();
//-------------删除所有的a---------------------------------
//lit.remove('a'); //删除所有的a;
//-----------将list里的数据倒序排列---------------
lit.reverse();
//-------------移除连续且相同的a，只剩下一个;--------------------------------
lit.unique(); //移除连续且相同的a，只剩下一个;
list<char> lit1;
list<char>::iterator it1;
//-------------将一个链表插入到另一个链表---------------------------------
it1=find(lit.begin(),lit.end(),'f'); //先的找到要插入的位置，在该位置的前一个插入；
////lit.splice(it1,lit1); //将第二个链lit1表插入到第一个链表lit中；合并后的链表就没了，因为传的是&
// 打印函数
void printList(const list<int>& a)
{
// 注意形参中是const list，所以下面也需要用const_iterator
// 否则distance无法使用
list<int>::const_iterator iter;
for (iter = a.begin(); iter != a.end(); ++iter)
{// 计算数组下标，distance包含在algorithm中 #include<algorithm>
size_t index = distance(a.begin(), iter);
cout << "a[" << index << "] = " << *iter << endl;
}
cout << endl;
}
list<int> a;
// push_front、push_back插入数据
a.push_front(4);
a.push_front(3);
a.push_front(2);
a.push_front(1);
a.push_back(50);
printList(a);
// insert插入数据
list<int>::iterator iter;
iter = a.begin();
a.insert(iter, 0);
a.insert(++iter, 10);
a.insert(++iter, 4, 20); // 插入4个20
printList(a);
// sort排序
cout << "sort排序" << endl;
a.sort();
printList(a);
// reverse逆序
cout << "reverse逆序" << endl;
a.reverse();
printList(a);
// erase删除指定元素
cout << "erase删除指定元素" << endl;
a.erase(iter);
printList(a);
// erase删除指定区间的元素
cout << "erase删除指定区间元素" << endl;
a.erase(++a.begin(), --a.end());
printList(a);
1）不使用连续内存完成动态操作。
2）在内部方便的进行插入和删除操作 动态操作，插入与删除效率高
3）可在两端进行push、pop
1) 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
2) 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
deque连续存储结构，即其每个元素在内存上也是连续的，类似于vector，
不同之处在于，deque提供了两级数组结构， 第一级完全类似于vector，代表实际容器；
另一级维护容器的首位地址。
这样，deque除了具有vector的所有功能外，还支持高效的首/尾端插入/删除操作。
deque 双端队列 double-end queue
deque是在功能上合并了vector和list。
//
deque<int> a;
// 在末尾插入数据
a.push_back(3);
a.push_back(4);
a.push_back(5);
// 在开头插入数据
a.push_front(2);
a.push_front(1);
a.push_front(0);
// 以数组方式输出
for (size_t n = 0; n < a.size(); ++n)
cout << "a[" << n << "] = " << a[n] << endl;
cout << endl;
//删除末尾的数据
a.pop_back();
//删除开头的数据
a.pop_front();
// 以迭代器方式输出
deque<int>::iterator iter;
for (iter = a.begin(); iter < a.end(); ++iter)
{
// 计算数组下标，distance包含在algorithm中 #include<algorithm>
int index = distance(a.begin(), iter);
cout << "a[" << index << "] = " << *iter << endl;
}
1）随机访问，即[]操作和deque.at()
2) 在内部方便的进行插入和删除操作
3）可在双端进行pop，push
占用内存多。
vector：支持快速随机访问、可高效的在vector容器 尾部 添加删除数据
deque：支持快速随机访问、可高效的在deque容器 头部和尾部 添加删除数据
list：支持顺序访问，但是在任何位置插入删除元素都很快。
相同点：三者都能实现resize（）来重新调整容器的大小。
不同点：
1）vector能实现随即存取，即[]操作，而list不能，deque是二者的结合体，也能够实现索引操作[]，但效率没有vector高。
2）vector适合在文件的末尾实现删除元素的操作pop_back（）与插入操作push_back（），在中间时效率非常低下。
而list可以在容器的任何位置实现插入与删除操作。
原因：vector的元素地址连续，如果在中间插入与删除操作，可能会导致原来的内存地址不足以存储当前的元素，
需要重新分配内存地址，这就需要将原来的所有元素拷贝到新内存，释放旧的内存地址等操作，操作代价高昂。
而list元素内存地址不连续，用指针操作，其本身是一个双向链表，它的高效率体现在插入，删除以及排序等移动大量元素的操作。
a. vector与deque的迭代器支持算术运算，list的迭代器只能进行++/--操作，不支持普通的算术运算。
b. 向量中的iterator在使用后就释放了，但是链表list不同，它的迭代器在使用后还可以继续用；链表特有的；
1）如果需要随机访问一个容器，vector 比 list好
2）如果经常 需要 插入或删除 容器元素，list比vector好
3）如果既要随机存取，又要关心两端数据的插入与删除，则选择 deque
a、若需要随机访问操作，则选择vector；
b、若已经知道需要存储元素的数目，则选择vector；
c、若需要随机插入/删除（不仅仅在两端），则选择list
d、只有需要在首端进行插入/删除操作的时候，还要 兼顾 随机访问效率，才 选择deque， 否则都选择vector。
e、若既需要随机插入/删除，又需要随机访问，则需要在vector与list间做个折中-deque。
f、当要存储的是大型负责类对象时，list要优于vector；
当然这时候也可以用vector来存储指向对象的指针，
同样会取得较高的效率，但是指针的维护非常容易出错，因此不推荐使用。
map<名字，电话号码> 利用名字来查询电话号码类似电话簿
set<bad_checks_name> 定义一个曾经开过空头支票的客户的名字，在接收一张支票前查询其名字是否在其中。
只有顺序容器的构造函数才接受大小参数，关联容器并不支持。
#include <map>
#include <ext/hash_map>
#include <tr1/unordered_map>
using namespace std;
using namespace std::tr1;
//typedef map<int,int> MapKey; //采用map
//typedef hash_map<int,int> MapKey; //采用hash_map
typedef unordered_map<int,int> MapKey; //采用unordered_map
map 关联数组：保存关键字-值对
set 关键字即值,只保存关键字的容器
multimap 关键字可重复出现的 map
multiset 关键字可重复出现的 set
unordered_map 哈希函数组织的map
unordered_set 哈希函数组织的set
unordered_multimap 哈希函数组织的multimap, 关键字可以重复出现
unordered_multiset 哈希函数组织的multiset， 关键字可以重复出现
hash_map
hash_set
hash_multimap
hash_multiset
运行效率方面：unordered_map最高，hash_map其次，而map效率最低
占用内存方面：hash_map内存占用最低，unordered_map其次，而map占用最高
map<string, size_t> word_count;//string 到 size_t 的空map
string word;
while(cin >> word) ++word_count[word];//提取word的计数器并将其加1
for(const auto &w : word_count) //对map中的每一个元素 pair类型 first成员保存关键字 second成员保存对应的值
cout << w.first << " occurs " << w.second
<< ((w.second > 1)? "times" : "time") << endl;// 报告每个单词出现的次数 单词按 字典排序
map<string, size_t> word_count;//string 到 size_t 的空map
set<string> exclude = {"The", "But", "And", "Or", "An", "A",
"the", "but", "and", "or", "an", "a"};//需要剔除的单词
string word;
while(cin >> word)
if(exclude.find(word) == exclude.end()) ++word_count[word];// 统计合理的词的出现次数
// exclude.find(word) word没有在exclude中出现时，返回 exclude.end()
//map初始化为空
map<string, size_t> word_count;//string 到 size_t 的空map
//set的列表初始化
set<string> exclude = {"The", "But", "And", "Or", "An", "A",
"the", "but", "and", "or", "an", "a"};//需要剔除的单词
//map的列表初始化 三个元素 将姓 映射为 名字
map<string, string> authers = {{"Jyly", "Jeam"}，
{"Aust", "Amy"},
{"Dickens", "Charles"} };
// multimap multisetde初始化,一个单词对应多个相互关联的词义,就是说 关键字可以重复出现
vector<int> ivec;
for(vector<int>::size_type i = 0; i != 10; ++i){
ivec.push_back(i);
ivec.push_back(i);// 每个数重复保存一次
}
// iset包含来自ivec的不重复的元素 含有10个元素
set<int> iset(ivec.cbegin(), ivec.cend());
// multiset 包含ivec的所有20个元素
multiset<int> miset(ivec.cbegin(), ivec.cend());
pair<string, string> anon;//
pair<string, size_t> word_count;//
pair<string, vector<int>> line;//保存 string 和 vector<int>
pair<string, string> author{"James", "Joyce"};//列表初始化
// pair类型的返回值类型函数
pair<string, int> process(vector<string> &v){
if(!v.empty())//back() 返回最后一个元素
return {v.back(), v.back().size()};//列表初始化
// return pair<string, int>(v.back(), v.back().size());
// return make_pair(v.back(), v.back().size()):
else
return pair<string, int>();//隐式构造返回值
}
set<string>::value_type va;//va 是一个string
set<string>::key_type vb;//vb 也是一个string
map<string, int>::key_type vc;//vc 是一个string
map<string, int>::mapped_type vd;//vd 是一个int
mep<string, int>::value_type ve;//ve map元素的类型 是pair类型 pair<const string, int>
map<string, size_t> word_count;//string 到 size_t 的空map
auto map_it = word_count.begin();//迭代器指针
// *map_it 是一个指向 pair<const string, size_t>类型对象的 引用
cout << map_it->first;//打印关键字
cout << " " << map_it->second;//
map_it->first = "new key";//错误 map的关键字类型 是 const的 不能改变 可以读取
++map_it->second;//正确 值类型不是const 可以改变
//set的关键字也是只读的即const，不能被改变的
set<int> iset = {0,1,2,3,4,5,6,7,8,9};//列表初始化
set<int>::iterator set_it = iset.begin();
if( set_it != iset.end()){
*set_it = 42;// 错误 不能修改set的关键字
cout << *set_it << endl;//可以读取set的关键字
}
map<string, size_t> word_count;//string 到 size_t 的空map
string word;
while(cin >> word) ++word_count[word];//提取word的计数器并将其加1
// 范围for访问
for(const auto &w : word_count) //对map中的每一个元素 pair类型 first成员保存关键字 second成员保存对应的值
cout << w.first << " occurs " << w.second
<< ((w.second > 1)? "times" : "time") << endl;// 报告每个单词出现的次数
//迭代器访问
auto map_it = word_count.cbegin();//迭代器指针
// *map_it 是一个指向 pair<const string, size_t>类型对象的 引用
while(mep_it != word_count.cend()){
cout << map_it->first << " occurs "
<< map_it->second
<< ((w.second > 1)? "times" : "time") << endl;// 报告每个单词出现的次数
++map_it;//递增迭代器，移动到下一个元素
}
word_count.insert({word, 1});// c++11标准最方便
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t>(word, 1));
word_count.insert(map<string, size_t>::value_type(word, 1));
multimap<string, string> authors;
authors.insert({"Breath, John", "Sot-Weed Factor"});//插入第一个元素，关键字为 Breath, John
authors.insert({"Breath, John", "Lost in the funhouse"});//插入第二个元素，关键字也为 Breath, John
string search_item("Breath, John");
auto cnt = authors.count(search_item);//关键字出现的次数
auto iter = authors.find(search_item);//关键字指向的 值序列
while(cnt){
cout << iter->second << endl;//打印作者的每一个书名
++iter;//前进到下一步书
--cnt;//记录剩余未打印的书本数量
}
// 迭代器lower_bound 范围for 访问
for(auto beg = authors.lower_bound(search_item), end = authors.upper_bound(search_item);
beg != end; ++beg)
cout << beg->second <<endl;//打印作者的每一个书名
// 范围for equal _range() 访问
for(auto pose = authors.equal _range(search_item); pose.first != pose.second; ++pose.first)
cout << pose.first->second << endl;//打印作者的每一个书名
unordered_map<string, size_t> word_count;//string 到 size_t 的空unordered_map 无序map
string word;
while(cin >> word) ++word_count[word];//提取word的计数器并将其加1
for(const auto &w : word_count) //对map中的每一个元素 pair类型 first成员保存关键字 second成员保存对应的值
cout << w.first << " occurs " << w.second
<< ((w.second > 1)? "times" : "time") << endl;// 报告每个单词出现的次数 单词 无序
无序容器在存储组织上为一组桶(bucket)，每个桶保存零个或多个元素，使用一个hash function(哈希函数)将元素映射到桶，
为了访问元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶，容器将具有固定哈希值的所有元素都保存在相应的桶中。
//哈希函数
size_t hasher(const Sales_data &sd){
return hash<string>()(sd.isbn());//h哈希类型
}
//比较函数
bool eqOp(const Sales_data &lhs, const Sales_data &rhs){
return lhs.isbn() == rhs.isbn();// 比较函数
}
// 定义特定类的 unordered_multiset
using = sd_unordered_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>// 两个函数指针