1.C++ STL标准库简介
长久以来，软件界一直希望建立一种可重复利用的东西，以及一种得以制造出”可重复运用的东西”
的方法，从函数(functions)，类别(classes),函数库(function libraries),类别库(class libraries)、各种
组件，从模块化设计，到面向对象(object oriented )，为的就是复用性的提升。
复用性必须建立在某种标准之上。但是在许多环境下，就连软件开发最基本的数据结构(data
structures) 和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作，竟然是为
了完成前人已经完成而自己手上并未拥有的程序代码，这不仅是人力资源的浪费，也是挫折与痛苦
的来源。
为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹
性、交互操作性(相互合作性,interoperability),诞生了STL。
STL(Standard Template Library,标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要
出现在 c++中，但是在引入 c++之前该技术已经存在很长时间了。
STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator)。
容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数，这
相比传统的由函数和类组成的库来说提供了更好的代码重用机会。
STL(Standard Template Library)标准模板库,在我们 c++标准程序库中隶属于 STL 的占到了 80%以
上。
2.STL容器使用时机
| . | vector | deque | list | set | multiset | map | multimap |
|---|---|---|---|---|---|---|---|
| 典型内存结构 | 单端数组 | 双端数组 | 双向链表 | 二叉树 | 二叉树 | 二叉树 | 二叉树 |
| 可随机存取 | 是 | 是 | 否 | 否 | 否 | 对key而言：不是 | 否 |
| 元素搜寻速度 | 慢 | 慢 | 非常慢 | 快 | 快 | 对key而言：快 | 对key而言：快 |
| 元素安插移除 | 尾端 | 头尾两端 | 任何位置 | - | - | - | - |
vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记
录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。
deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，
尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。
vector与deque的比较：
一：vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置 却是不固定的。
二：如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
三：deque支持头部的快速插入与快速移除，这是deque的优点。
list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移
除插入。
set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。
map的使用场景：比如按ID号存储十万个用户，想要快速要通过ID查找对应的用户。二叉树的查找
效率，这时就体现出来了。如果是vector容器，最坏的情况下可能要遍历完整个容器才能找到该用
户。
?
3.vector容器
vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。
Array是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎得由
自己来，首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。
Vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的
运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要
求一个大块头的array了。
Vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector旧空间
满了，如果客户每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓的扩
充空间(不论多大)，一如刚所说，是”配置新空间-数据移动-释放旧空间”的大工程,时间成本很高，
应该加入某种未雨绸缪的考虑，稍后我们便可以看到vector的空间配置策略。
基本使用：
#include "stdafx.h"
#include <iostream>
#include <vector>//动态数组
using namespace std;
int main()
{
vector<int> v1;//构造一个空的vector
cout << "容量为："<<v1.capacity() << " 元素个数: " << v1.size() << endl;
vector<int> v2(5);//构造一个空间大小为5，并且元素为5个（有默认值）的vector
cout << "容量为：" << v2.capacity() << " 元素个数: " << v2.size() <<" v2[0]:"<<v2[0]<< endl;
vector<int> v3(5,111);//构造一个空间大小为5，并且元素为5个（每个元素初始值为111）的vector
cout << "容量为：" << v3.capacity() << " 元素个数: " << v3.size() << " v3[0]:" << v3[0] << endl;
vector<int> v4(v3);//拷贝构造vector
cout << "容量为：" << v4.capacity() << " 元素个数: " << v4.size() << " v4[0]:" << v4[0] << endl;
//像数组一样的访问vector
v2[0] = 1;//vector重载了[]运算符
v2[1] = 2;
v2[2] = 3;
v2.at(3) = 4;
v2.at(4) = 5;
for (size_t i = 0; i < v2.size(); i++)
{
//cout << v2[i] << " ";
//cout << v2.at(i)<< " ";
cout << &v2[i] << " ";//输出地址，说明存储空间是连续的
}
cout << endl;
return 0;
}
迭代器使用：
#include<iostream>
#include<vector>//动态数组
using namespace std;
template<class T>
void Print(T begin, T end)
{
//此处编写代码
for (T p = begin; p != end; ++p)
{
cout << *p << " ";
}
cout << endl;
}
int main()
{
vector<int> v(5);//构造一个空间大小为5，并且元素为5个（有默认值）的vector
//像数组一样的访问vector
v[0] = 1;//vector重载了[]运算符
v[1] = 2;
v[2] = 3;
v.at(3) = 4;
v.at(4) = 5;
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
{
//验证vector的迭代器是随机访问迭代器（支持++ 、-- 、 +n、 +=n 、-=n 、 -n 、 *、[] ）
//random_access_iterator
cout << typeid(vector<int>::iterator::iterator_category).name() << endl;
vector<int>::iterator it = v.begin();//begin返回v的第一个元素的迭代器
cout << "v开头的迭代器指向的元素值：" << *it << endl;
++it;//it的值改变
cout << "v第二个的元素值：" << *it << endl;
cout << "v第四个的元素值：" << *(it + 2) << endl;//此刻这里的it还是指向第二个，没变
it -= 1;//it的值改变
cout << "v第一个的元素值：" << *it << endl;
cout << "v第五个的元素值：" << it[4] << endl;//这里的it没变
}
//可以改变指向元素的值
vector<int>::iterator it = v.begin();
*it = 111;
//使用迭代器遍历元素
for (vector<int>::iterator it = v.begin() ; it!=v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
//常迭代器 指向的元素值不可改变, 类似 const int *p;
vector<int>::const_iterator it2 = v.cbegin();
//*it2 = 111;
//反向迭代器
for (vector<int>::reverse_iterator it3 = v.rbegin(); it3 != v.rend(); it3++)
{
cout << *it3 << " ";
}
cout << endl;
//测试我们自己实现的Print算法,迭代器架起了 算法与容器之间的桥梁
Print<vector<int>::iterator>(v.begin(), v.end());
Print(v.begin(), v.end());
Print<vector<int>::reverse_iterator>(v.rbegin(), v.rend());
return 0;
}
添加、删除、插入元素：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int > v;//定义一个空的动态数组
cout << "容量:" << v.capacity() << " 元素个数:" << v.size() << endl;
//往尾部插入元素 // 1
v.push_back(1);
cout << "容量:" << v.capacity() << " 元素个数:" << v.size() << endl;
v.push_back(2); // 1 2
cout << "容量:" << v.capacity() << " 元素个数:" << v.size() << endl;
//向某一个迭代器指向的位置插入
v.insert(v.begin(), 3);// 3 1 2
cout << "容量:" << v.capacity() << " 元素个数:" << v.size() << endl;
//向某一个迭代器指向的位置插入2个值为4的元素
v.insert(v.end()-1 , 2, 4);// 3 1 4 4 2
cout << "容量:" << v.capacity() << " 元素个数:" << v.size() << endl;
//使用迭代器遍历
for (vector<int >::const_iterator it = v.cbegin(); it!= v.cend(); it++)
{
cout << *it << " ";
}
cout << endl;
//访问第一个元素
cout <<"front " <<v.front() << endl;
//访问最后一个元素
cout << "back " << v.back() << endl;
//访问某一个下标的元素
cout << "at " << v.at(3) << endl;
//删除最后一个元素
v.pop_back();
cout << "容量:" << v.capacity() << " 元素个数:" << v.size() << endl;
//删除开头的元素
v.erase(v.begin());
cout << "容量:" << v.capacity() << " 元素个数:" << v.size() << endl;
//删除结尾的元素, end()指向最后一个元素的下一个
v.erase(v.end()-1);
cout << "容量:" << v.capacity() << " 元素个数:" << v.size() << endl;
//使用迭代器遍历
for (vector<int >::const_iterator it = v.cbegin(); it != v.cend(); it++)
{
cout << *it << " ";
}
cout << endl;
//删除所有元素，不会清除容量
v.clear();
cout << "容量:" << v.capacity() << " 元素个数:" << v.size() << endl;
/*
当size和capacity相等时继续添加数据，否则vector会扩容，
每次扩容都是增加当前空间的1/2(第一次除外);
*/
{
vector<int> v;
cout << "------------------------capacity容量随元素个数size增加的规律----------------------------" << endl;
for (int i = 0; i < 50; i++)
{
v.push_back(i);
cout << "v的容量：" << v.capacity() << " 元素个数:" << v.size() << endl;
}
}
return 0;
}
?vector常用赋值操作：
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
vector& operator=(const vector &vec);//重载等号操作符
swap(vec);// 将vec与本身的元素互换。
vector大小操作:
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。
vector数据存取操作:
at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
operator[];//返回索引idx所指的数据，越界时，运行直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素
vector插入和删除操作:
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素
4.deque容器
Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。
所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以
在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。
deque容器实现原理:
Deque容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想到array和
vector,array无法成长，vector虽可成长，却只能向尾端成长，而且其成长其实是一个假象，事实上
(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间 三步骤，如果不是vector每次配置新的空间
时都留有余裕，其成长假象所带来的代价是非常昂贵的。
Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便
配置一段连续定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连
续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮
回，代价就是复杂的迭代器架构。
既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计
及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。
Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续
的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称
作缓冲区。缓冲区才是deque的存储空间的主体。
基本使用?:
#include<iostream>
#include<deque>
using namespace std;
int main()
{
//空的双端队列
deque<int> d;
cout << "元素个数" << d.size() << endl;
deque<int> d2(5);//指定元素个数，默认值为类型默认值
cout << "元素个数" << d2.size() <<" "<<d2[0]<< endl;
deque<int> d3(5,111);//指定元素个数，每一个指定元素值111
cout << "元素个数" << d3.size() << " " << d3[4] << endl;
deque<int> d4(d3);//拷贝构造
cout << "元素个数" << d4.size() << " " << d4[3] << endl;
//像数组一样的访问元素（内存空间并不是连续的）
d2[0] = 1;
d2[1] = 2;
d2[2] = 3;
d2.at(3) = 4;
for (size_t i = 0; i < d2.size(); i++)
{
cout << d2[i] << " ";
}
cout << endl;
//验证deque的内存空间不是连续的
{
deque<int> d;
for (size_t i = 0; i < 20; i++)
{
d.push_back(i);
cout << "元素" << d[i] << " " << &d[i] << '\t';
if ((i + 1) % 4 == 0)cout << endl;
}
cout << endl;
}
return 0;
}
?迭代器使用：
#include<iostream>
#include<deque>
using namespace std;
template<class T>
void Print(T begin, T end)
{
for (T p = begin; p != end; ++p)
{
cout << *p << " ";
}
cout << endl;
}
int main()
{
deque<int> d2(5);//指定元素个数，默认值为类型默认值
cout << "元素个数" << d2.size() << " " << d2[0] << endl;
//像数组一样的访问元素（内存空间并不是连续的）
d2[0] = 1;
d2[1] = 2;
d2[2] = 3;
d2.at(3) = 4;
d2.at(4) = 5;
for (size_t i = 0; i < d2.size(); i++)
{
cout << d2[i] << " ";
}
cout << endl;
//deque<int>::iterator是随机访问迭代器
cout << typeid( deque<int>::iterator::iterator_category ).name() << endl;
//支持++ 、--、+=n、 -=n、[]、* 、+n、-n
deque<int>::iterator it = d2.begin();//获取指向容器的第一个元素的迭代器
cout << "begin返回的迭代器指向的元素："<<*it << endl;
*it = 111;//deque<int>::iterator可以改变迭代器指向的元素值
it++;//下一个元素，it自身改变
cout <<"++后:"<< *it << endl;
it += 2;//往后移2个位置，it自身改变，指向第4个元素
cout << "+=2后:" << *it << endl;
cout << "-3后:" << *(it-3) << endl; // it-3代表it位置的前3个位置，it自身不变
cout << "[1]后:" << it[1] << endl; //指向最后一个
it = d2.begin();//置为开头
cout << "[i]后:" << it[1] << endl; //指向第二个
//const_iterator只读的迭代器
deque<int>::const_iterator it2 = d2.cbegin();
//*it2 = 11111; //无法改变元素的值，只能读取，类似于 const int *
//使用迭代器正向遍历
for (deque<int>::iterator it = d2.begin(); it != d2.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
//使用反向迭代器反向向遍历
for (deque<int>::reverse_iterator it = d2.rbegin(); it != d2.rend(); ++it)
{
cout << *it << " ";
}
cout << endl;
//测试自己写的算法(无需知道deque容器的内存结构，具有通用性)
Print<deque<int>::iterator>(d2.begin(), d2.end());
Print(d2.rbegin(), d2.rend());//自动推导
return 0;
}
添加、删除、插入元素：
#include<iostream>
#include<deque>
using namespace std;
int main()
{
deque<int> d;
d.push_back(1);//从尾部插入元素
d.push_front(2);//从头部插入元素（vector没有此方法）
d.insert(d.begin(), 3);//在迭代器位置插入
d.insert(d.end(), 2, 4);//在迭代器位置插入2个元素值为4
for ( int i = 0; i < d.size(); i++)
{
cout <<d[i]<< " ";
}
cout << endl;
//访问元素
//d.at(0) = 111;
//d[4] = 555;
cout << d.front() << endl;//返回第一个元素
cout << d.back() << endl;//返回第一个元素
//删除元素
d.pop_back();//从尾部删除
d.pop_front();//从头部删除（vector不提供）
d.erase(d.begin());//删除某个迭代器指向的元素
for (int i = 0; i < d.size(); i++)
{
cout << d[i] << " ";
}
cout << endl;
d.clear();//全部清空
cout << "元素个数："<<d.size() << endl;
return 0;
}
deque赋值操作：
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符
swap(deq);// 将deq与本身的元素互换
deque大小操作：
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。
deque双端插入和删除操作：
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据
deque数据存取：
at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据
deque插入操作：
insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
deque删除操作：
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
5.list容器
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针
链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包
括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是
配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，
对于任何位置的元素插入或元素的移除，list永远是常数时间。
List和vector是两个最常被使用的容器。
List容器是一个双向链表。
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
- 链表灵活，但是空间和时间额外耗费较大
基本使用:
#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int> l;//空的双向链表
cout << "元素个数:" << l.size() << endl;
list<int> l2(5);//初始化5个元素，默认值为类型的默认值
cout << "元素个数:" << l2.size() <<" "<< * (l2.begin() )<< endl;
list<int> l3(5,111);//初始化5个元素，每个元素初始值为111
cout << "元素个数:" << l3.size() << " " << *(l3.begin()) << endl;
list<int> l4( l3 );//拷贝构造
cout << "元素个数:" << l4.size() << " " << *(l4.begin()) << endl;
//不支持[]运算符，因为效率低
//cout << l4[0] << endl;
//验证了list容器的内存空间是不连续的
for (list<int>::iterator it = l3.begin(); it !=l3.end(); it++)
{
cout << &(*it) << " ";
}
cout << endl;
return 0;
}
迭代器使用:
#include<iostream>
#include<list>
using namespace std;
template<class T>
void Print(T begin, T end)
{
//此处编写代码
for (T p = begin; p != end; ++p)
{
cout << *p << " ";
}
cout << endl;
}
int main()
{
list<int> l3(5, 111);//初始化5个元素，每个元素初始值为111
cout << "元素个数:" << l3.size() << " " << *(l3.begin()) << endl;
//验证list容器的迭代器类型（5种之一）
//双向迭代器bidirectional_iterator_tag
cout << typeid(list<int>::iterator::iterator_category).name() << endl;
//双向迭代器比随机访问迭代器弱一些，支持 ++ -- != == = * 不支持[] +n -n +=n -=n
list<int>::iterator it = l3.begin(); //指向容器l3的第一个元素
cout << *it << endl;
*(++it) = 222;
*(++it) = 333;
*(++it) = 444;
*(++it) = 555;
++it;//指向最后一个元素的下一个
cout <<"迭代器指向末尾的下一个"<< (it == l3.end() )<< endl;
--it;//指向最后一个元素
cout << *it << endl;
//it += 3;//不支持
//it + 3;//不支持
//it[0];//不支持
//const_iterator常迭代器，类似于 const int *
list<int>::const_iterator it2 = l3.cbegin();
//*it2 = 1;//不能修改常迭代器指向的内容
//正向遍历
for (list<int>::iterator it = l3.begin(); it != l3.end(); it++)
{
cout << *it << " ";
}
cout << endl;
//反向遍历
for (list<int>::reverse_iterator it = l3.rbegin(); it != l3.rend(); it++)
{
cout << *it << " ";
}
cout << endl;
//测试自己的算法(迭代器带来的好处，算法无需关系容器的具体内存结构，就可以遍历)
Print<list<int>::iterator>(l3.begin(), l3.end());
Print(l3.crbegin(), l3.crend());//自己推到迭代器类型
return 0;
}
增加、删除、插入元素:
#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int> l;
//头部插入一个节点（list容器肯定知道头部的位置）
l.push_front(111);
//尾部插入一个节点（list容器肯定知道尾部的位置）
l.push_back(444);
l.push_back(555);
//在某个迭代器的位置之前插入
l.insert(l.begin(), 222);
//在某个迭代器的位置之前插入n个相同值元素
l.insert(l.begin(), 3,333);
//访问链表第一个元素
l.front() = 1;
cout <<"第一个元素:"<< l.front() << endl;
//访问链表最后一个元素
cout << "最后一个元素:" << l.back() << endl;
for (list<int>::iterator it = l.begin(); it!= l.end(); it++)
{
cout << *it << " ";
}
cout << endl;
//删除链表头的元素
l.pop_front();
//删除链表尾的元素
l.pop_back();
//删除某个迭代器指向的元素
l.erase(l.begin());
//删除一段迭代器区间
l.erase(l.begin(),l.end());
//清空链表
l.clear();
for (list<int>::iterator it = l.begin(); it != l.end(); it++)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
list数据元素插入和删除操作
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。
list大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num，
若容器变长，则以默认值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num，
若容器变长，则以elem值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
list赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换。
list数据的存取
front();//返回第一个元素。
back();//返回最后一个元素。
list反转排序
reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort(); //list排序
6.set/multiset容器
set（集合）是一种每个元素值都是唯一的有序的关联容器。
multiset（多重集合）是一种元素值?可复的、有序的?关联容器。
set/multiset容器内部结构采用红黑树（Red-Black tree）的平衡二叉树，它可以在O(logn)时间内
高效的做查找，插入和删除。
?基本使用:
#include<set>
#include<vector>
#include<iostream>
using namespace std;
int main()
{
//set 的特点， 值必须唯一， 有序
set<int> s;//构造空的集合,默认less 升序
cout << "元素个数" << s.size() << endl;
set<int> s2 = {3,2,5,1,4 ,3};//初始化列表
//set<int, greater<int>> s2 = {3,2,5,1,4 ,3};//初始化列表,降序
cout << "元素个数" << s2.size() << endl;
set<int> s3(s2.begin(),s2.end()); //拷贝迭代器范围内的元素
cout << "元素个数" << s3.size() << endl;
//插入元素 ,成功后返回值的成员second为1，失败为0
//cout << typeid(s2.insert(9)).name() << endl;
cout<< s2.insert(9).second <<endl;
//重复插入元素
cout << s2.insert(9).second << endl;
vector<int> v = {6,7,8,9};
s2.insert(v.begin(), v.end());//插入其它容器中元素的值
for (set<int>::iterator it = s2.begin(); it!=s2.end(); it++)
{
cout << *it << " ";
}
cout << endl;
//删除值为6的元素
s2.erase(6);
//删除迭代器指向的元素
s2.erase(s2.begin());
for (set<int>::iterator it = s2.begin(); it != s2.end(); it++)
{
cout << *it << " ";
}
cout << endl;
//删除迭代器区间
set<int>::iterator it = s2.begin();
it++; it++; it++;
s2.erase(s2.begin(), it);
//s2.clear();//清空集合元素
for (set<int>::iterator it = s2.begin(); it != s2.end(); it++)
{
cout << *it << " ";
}
cout << endl;
//查找集合中的元素 ,找到返回指向该元素的迭代器，否则返回end()
set<int>::iterator it2 = s2.find(99);
if (it2 != s2.end())
{
cout << "找到:" <<*it2<< endl;
}
else
{
cout << "未找到！" << endl;
}
return 0;
}
迭代器使用
STL为set容器提供了相应的迭代器类set<T>::iterator，它是一个双向迭代器（Bidirectional
iterator），以供我们方便的访问容器内部的元素。
#include<set>
#include<iostream>
using namespace std;
template<class T>
void Print(T begin, T end)
{
for (T p = begin; p != end; ++p)
{
cout << *p << " ";
}
cout << endl;
}
int main()
{
//set 的特点， 值必须唯一， 有序
set<int> s2 = { 3,2,5,1,4,3 };//初始化列表
//输出set迭代器的类别: bidirectional_iterator_tag 双向迭代器
cout << typeid(set<int>::iterator::iterator_category).name() << endl;
//双向迭代器，支持++ -- * != == = 不支持 [] +=n -=n +n -n
set<int>::iterator it = s2.begin();//获取第一个元素
cout <<"第一个元素"<< *it << endl;
// *it = 111; //不可更改，说明set中元素值不可改变
//符合逻辑，因为set中每个元素都已经根据值排列好了大小，此刻你若更改值，顺序无法保证
++it;
cout << "第二个元素" << *it << endl;
--it;
cout <<"是否指向开头"<< (it == s2.begin())<< endl;
//常迭代器，不可更改指向的元素的内容
set<int>::const_iterator it2 = s2.cbegin();//获取第一个元素
// *it2 = 111; //不可更改set元素中的值
//验证下， set<int>::iterator 与 set<int>::const_iterator 是一样的
cout << typeid(set<int>::iterator ).name() << endl;
cout << typeid(set<int>::const_iterator).name() << endl;
//正向遍历
for (set<int>::iterator it = s2.begin(); it != s2.end(); it++)
{
cout << *it << " ";
}
cout << endl;
//反向遍历
for (set<int>::reverse_iterator it = s2.rbegin(); it != s2.rend(); it++)
{
cout << *it << " ";
}
cout << endl;
//测试自定义的Print算法(迭代器，算法无需关心容器的内存结构)
Print<set<int>::iterator>(s2.begin(), s2.end());
return 0;
}
set赋值操作
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器
set大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空
set插入和删除操作
insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。
set查找操作
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
7.map/multimap容器
map（映射）是一种存储键值（key-value）对，?key是唯一的、有序的?关联容器。
multimap（多重映射）是一种存储键值（key-vauekey是?允许重复的、有序的?关联容器。
map内部结构采用红黑树（Red-Black tree）平衡二叉树，它可以在O(log n)时间内高效的做查
找，插入和删除。
Map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所
有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。
Multimap和map的操作类似，唯一区别multimap键值可重复。
?基本使用?
#include<map>
#include<iostream>
using namespace std;
int main()
{
//map映射 ， 每个元素都是 key-value 键值对， key不能重复，value可以，有序的
map<int, string> m;//构造空的map
cout <<"元素个数："<< m.size() << endl;
//初始化列表构造map
map<int, string> m2 = { {3,"CCC"} , {1,"AAA"} , {2,"BBB"} };
cout << "元素个数：" << m2.size() << endl;
//拷贝构造
map<int, string> m3(m2);
cout << "元素个数：" << m3.size() << endl;
//验证map容器中的元素类型 pair<int, string>
cout << typeid(map<int, string>::value_type).name() << endl;
//一对值 pair 类模板
pair<int, float> p1;
p1.first = 1;
p1.second = 2.34f;
pair<int, float> p2(2, 3.45f); //有参构造
cout << "first: " << p2.first << " second:" << p2.second<< endl;
//使用make_pair函数构造pair
pair<short, char> p3 = make_pair<short, char>(3, 'A');
//pair<short, char> p3 = make_pair(3, 'A');//自动推导
cout << "first: " << p3.first << " second:" << p3.second << endl;
map<int, string> m4 = { pair<int, string>( 3,"CCC" ) , make_pair( 2,"BBB"), make_pair(1,"AAA"), };
cout << "元素个数：" << m4.size() << endl;
return 0;
}
插入、删除元素
#include<vector>
#include<map>
#include<iostream>
using namespace std;
int main()
{
//map映射 关联容器 ， 每个元素都是 key-value 键值对 pair，
//key不能重复，value可以， 有序的
map<int, string> m;//构造空的map
//插入pair
pair<int, string> p1(2, "BBB");
m.insert(p1);
m.insert(pair<int, string>(1, "AAA"));
//可以通过insert返回值的 成员.second查看是否插入成功，true成功，false是失败
m.insert( make_pair<int, string>(2, "bbb")); //插入重复的key, 插入失败
m.insert(make_pair(3, "CCC"));
// 插入其它容器中迭代器范围中的元素
vector<pair<int, string>> v = { {3,"ccc"}, {5, "EEE"},{ 4,"DDD" },{6, "FFF"} };
m.insert(v.begin(), v.end());
//[key]= value
m[7] = "GGG"; //对于不存在的key， 插入，相当于 (7,"GGG")
m[8]; //对于不存在的key，插入，相当于 ( 8,"")
m[2] = "bbb";// 已经存在的key，相当于是修改元素的value
for (map<int, string>::iterator it = m.begin(); it!= m.end(); ++it)
{
cout << it->first << "->" << it->second.c_str() << " ";
}
cout << endl;
//查找key为3的元素，成功返回迭代器，失败返回end()
{
map<int, string>::iterator it = m.find(33);
if (it != m.end())
{
cout << "找到：" << it->first << "->" << it->second.c_str() << endl;
}
else
{
cout << "未找到!" << endl;
}
}
//[key] 如果key存在，直接返回value
//陷阱 ,如果key不存在，他会自动插入key，value为默认值再返回
cout << "[key] "<< m[33].c_str() << endl;
for (map<int, string>::iterator it = m.begin(); it != m.end(); ++it)
{
cout << it->first << "->" << it->second.c_str() << " ";
}
cout << endl;
//删除key为3的元素
m.erase(3);
//删除某个迭代器指向的元素
m.erase(m.begin());
//删除迭代器区间[)的元素
map<int, string>::iterator it = m.begin();
++it; ++it; ++it; //往后移动
m.erase(m.begin(), it);
//删除所有元素
m.clear();
for (map<int, string>::iterator it = m.begin(); it != m.end(); ++it)
{
cout << it->first << "->" << it->second.c_str() << " ";
}
cout << endl;
return 0;
}
迭代器使用
STL为map容器提供了相应的迭代器类map<T1,T2>::iterator，它是一个双向迭代器
（Bidirectional iterator）以供我们方便的访问容器内部的元素。
#include<map>
#include<iostream>
using namespace std;
template<class T>
void Print(T begin, T end)
{
for (T p = begin; p != end; ++p)
{
cout << *p << " ";
}
cout << endl;
}
//为 map<int, string>元素类型提供 <<运算符重载
ostream & operator<<(ostream & os, map<int, string>::value_type &p)
{
cout << p.first << "->" << p.second.c_str() ;
return os;
}
int main()
{
//map映射 关联容器 ， 每个元素都是 key-value 键值对 pair，
//key不能重复，value可以， 有序的
map<int, string> m;//构造空的map
m.insert(make_pair(3, "CCC"));
m.insert(make_pair(1, "AAA")); m.insert(make_pair(2, "BBB"));
//map<int, string>::iterator是双向迭代器 bidirectional_iterator_tag
cout << typeid(map<int, string>::iterator::iterator_category).name() << endl;
//双向迭代器，支持 ++ -- * = != == ， 不支持 [] 、+=n， -=n +n -n
map<int, string>::iterator it = m.begin();
// it->first = 111; //map的key值不允许修改, map是按照key排好序的，如果你更改key值，会打乱顺序
it->second = "aaa"; //map的value允许修改
++it;
cout << it->first << "->" << it->second.c_str() <<endl;
--it;
cout << "回到开头"<<(it == m.begin()) << endl;
//const_iterator 指向的元素内容不可修改
map<int, string>::const_iterator it2 = m.begin();
// it2->first = 111; //均不可修改
// it2->second = "aaa";//均不可修改
//查看两种iterator的真实类型
cout << typeid(map<int, string>::iterator).name() << endl;
cout << typeid(map<int, string>::const_iterator).name() << endl;
//正向遍历
for (map<int, string>::iterator it = m.begin(); it != m.end(); ++it)
{
cout << it->first << "->" << it->second.c_str() << " ";
}
cout << endl;
//反向遍历
for (map<int, string>::reverse_iterator it = m.rbegin(); it != m.rend(); ++it)
{
cout << it->first << "->" << it->second.c_str() << " ";
}
cout << endl;
//使用Print ，无需知道map的内部结构，通过迭代器就可以遍历map的所有元素
Print<map<int, string>::iterator>(m.begin(), m.end());
return 0;
}
map赋值操作
map& operator=(const map &mp);//重载等号操作符
swap(mp);//交换两个集合容器
map大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空
map插入数据元素操作
map.insert(...); //往容器插入元素，返回pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";
map删除操作
clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。
map查找操作
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。