1、vector——变长数组
倍增的思想
计算机申请空间的特点：花费时间与申请的大小无关，与申请速度有关（也就是和申请次数有关：申请1000个长度为1的空间花费时间可能是申请1个长度为1000的空间花费时间的1000倍）
//基本函数
vector<int> b;
b.size();//返回元素个数
b.empty();//判空
b.claer();//清空
front()/back(); //
push_back()/pop_back();
begin()/end();
[]支持随机存储
支持比较运算（按字典序比较）
#include <iostream>
#include <cstdio>
#include <csting>
#include <vector>
using namespace std;
int main()
{
//初始化
vector<int> b(10, 3);
//遍历方式1
for(auto k:b) cout << k << endl;
//用法
vector<int> a;
for(int i = 0; i < 10; i++) a.push_back(i);
//遍历方式2
for(int i = 0; i < a.size(); i++) cout << a[i] << ' ';
cout << endl;
//遍历方式3
for(vactor<int>::iterator i = a.begin(); i != a.end(); i++) cout << *i << ' ';
cout << endl;
}
pair<T, T > —— 定义二元组
pair<T, pair<T, T>> ——定义三元组
//基本用法
first
second
支持比较（以first为第一关键字，以second为第二关键字，字典序）
pair<int, string> a;
//两种
a = make_pair(10, "abc");
a = {10, "abc"};
2、string——字符串
#include <iostream>
#include <string>
using namespace std;
int main ()
{
std::string s0 ("Hello World"); //根据已有字符串构造新的string实例
//字符串长度
cout << "字符串长度：" << endl;
std::string s("1234567");
std::cout << "size=" << s.size() << std::endl;
std::cout << "length=" << s.length() << std::endl; //size()和length()：返回string对象的字符个数，他们执行效果相同。
if(s[8] == ' ')
std::cout << "yes" << std::endl; //数组越界访问，后一个为' ',但在计算长度时会忽略' '
std::cout << "max_size=" << s.max_size() << std::endl; //max_size()：返回string对象最多包含的字符数，超出会抛出length_error异常
std::cout << "capacity=" << s.capacity() << std::endl; //capacity()：重新分配内存之前，string对象能包含的最大字符数
//C ++字符串支持常见的比较操作符（>,>=,<,<=,==,!=）,按照自左到右，按字典序比较
cout << "字符串比较：" << endl;
string A("aBcdef");
string B("AbcdEf");
string C("123456");
string D("123dfg");
int m = A.compare(B); //将A、B比较
int n = A.compare(1, 5, B); //A的字串从1开始包含5个（Bcdef）, 与B比较
int p = A.compare(1, 5, B, 4, 2); //A的字串（Bcder）,与B的字串（Ef）
int q = A.compare(0, 3, "abcd", 3); //A的字串（aBc）,与"abcd"的子串，前3个（123）,不能是字符数组名
cout << "m=" << m << endl; //1
cout << "n=" << n << endl; //1
cout << "p=" << p << endl; //-1
cout << "q=" << q << endl; //-1 1大， -1小， 0等于
//字符串初始化
cout << "字符串初始化：" << endl;
std::string s1; //默认初始化，s1是个空字符串；
std::string s2(s0); //通过复制一个string构造一个新的string
std::string s3(s0, 8, 3);//通过复制一个string的一部分来构造一个新的string。8为起始位置，3为偏移量。
std::string s4 ("A character sequence"); //与s0构造方式相同。
std::string s5 ("Another character sequence", 12); //已知字符串，通过截取指定长度来创建一个string
std::string s6a (10, 'x'); //指定string长度，与一个元素，则默认重复该元素创建string
std::string s6b (10, 42); // 42 is the ASCII code for '*' //通过ASCII码来代替s6a中的指定元素。
std::string s7 (s0.begin(), s0.begin()+7); //通过迭代器来指定复制s0的一部分，来创建s7
std::cout << "s1: " << s1 << "
s2: " << s2 << "
s3: " << s3;
std::cout << "
s4: " << s4 << "
s5: " << s5 << "
s6a: " << s6a;
std::cout << "
s6b: " << s6b << "
s7: " << s7 << '
';
//字符串更改
cout << "字符串更改：" << endl;
string str7("123456");
string str;
str.assign(str7); //将str7赋给str
cout << str << endl;
str.assign(str7, 3, 3); //str7从3开始3个（456）赋给str
cout << str << endl;
str.assign(str7, 2, str7.npos); //str7从2开始到末尾（3456）赋给str
cout << str << endl;
str.assign(5, 'X'); //把5个X赋给str
cout << str << endl;
/*string::iterator itB = str7.begin();
string::iterator itE = str7.end();
str.assign(itB, --itE);
cout << str << endl << endl;*/ //迭代器
str.clear();
cout << str << endl; //字符串清空s="";s.erase();
//尾部添加
cout << "尾部添加：" << endl;
str += str7;
cout << str << endl; //123456
str += "789";
cout << str << endl; //123456789
str += 'a';
cout << str << endl; //加1个字符, 123456789a
str.append(str7);
cout << str << endl; //123456789a123456
str.append(str7,1,3);
cout << str << endl; //同前面的函数参数assign的解释(234),123456789a123456234
str.append(str7,4,string::npos);
cout << str << endl; //不解释了(56) ,123456789a12345623456
str.append("000");
cout << str << endl; //123456789a12345623456000
str.append("nico",5);
cout << str << endl; //123456789a12345623456000nico
str.append(5,'x');
cout << str << endl; //123456789a12345623456000nico xxxxx
str.push_back('a');
cout << str << endl; //这个函数只能增加单个字符对STL熟悉的理解起来很简单 123456789a12345623456000nico xxxxxa
str.clear();
//插入
cout << "插入：" << endl;
str.insert(0,"my name");
cout << str << endl;
str.insert(1,str7); //从1位置开始插入
cout << str << endl;
str.insert(6,1,'j'); //位置，个数，单个字符
cout << str << endl;
//删除
cout << "删除：" << endl;
str.replace(1,2,"nternationalizatio");
cout << str << endl; //从索引1开始的2个替换成后面的C_string
str.erase(13);
cout << str << endl; //从索引13开始往后全删除
str.erase(7,5);
cout << str << endl; //从索引7开始往后删5个
//提取字串及字符串连接（就是+）
cout << "提取：" << endl;
str.assign("abcdefghijklmnopqrstuvwxyz");
string str1 = str.substr();
cout << str1 << endl; //返回s的全部内容
str1 = str.substr(11);
cout << str1 << endl; //从索引11往后的子串
str1 = str.substr(5,6);
cout << str1 << endl; //从索引5开始6个字符
//字符串查找
cout << "查找：" << endl;
str.assign("1234567890");
int x = str.find("34", 0);
cout << x << endl; //查找字符串（34）（也可查询单个字符），并返回第一个字符的索引。第二个参数为开始查找起始位置。若查询失败返回-1。
x = str.rfind("34");
cout << x << endl; //逆向查找字符串（34）（也可查询单个字符），并返回第一个字符的索引。第二个参数为开始查找起始位置。若查询失败返回-1。
str.assign("1234563456340");
x = str.find_first_of("34");
cout << x << endl; //查找字符串（34）（也可查询单个字符），并返回第一次出现的第一个字符的索引。若查询失败返回-1。
x = str.find_last_of("34");
cout << x << endl; //查找字符串（34）（也可查询单个字符），并返回最后一次出现的第一个字符的索引。若查询失败返回-1。
x = str.find_first_not_of("34");
cout << x << endl; //查找不是字符串（34）的字符串（也可查询单个字符），并返回第一次出现的第一个字符的索引。若查询失败返回-1。
x = str.find_last_not_of("34");
cout << x << endl; //查找不是字符串（34）的字符串（也可查询单个字符），并返回第一次出现的第一个字符的索引。若查询失败返回-1。
return 0;
}
//Output:
//s1:
//s2: Initial string
//s3: str
//s4: A character sequence
//s5: Another char
//s6a: xxxxxxxxxx
//s6b: **********
//s7: Initial
3、queue——队列
//基本用法
size();
empty();
push(); //相队尾插入一个元素
front(); //返回队头元素
back(); //返回队尾元素
pop(); //弹出队头元素
4、priority_queue——优先队列（堆）
默认是定义大根堆。
//基本用法
push(); //插入一个元素
top(); //返回对顶元素
pop(); //弹出堆顶元素
//定义一个小根堆
(push(-x);)
priority_queue<int, vactor<int>, greater<int>> heap;
5、stack——栈
//基本用法
size();
empty();
push(); //向栈顶插入一个元素
top(); //返回栈顶元素
pop(); //弹出栈顶元素
6、deque——双端队列
效率非常低
//基本用法
size();
empty();
clear();
front();
back();
push_back()/pop_back();
push_front()/pop_front();
begin()/end();
[]支持随机存取
7、set、map、multiset、multimap
基于平衡二叉树（红黑树），动态维护有序序列
//set(不能有重复的数)/multiset(允许有重复的数)
size();
empty();
clear();
begin()/end(); //++,--返回前驱和后继，时间复杂度O(logn)
insert(); //插入一个数
find(); //查找一个数，若不存在返回end()
count(); //返回某一个数的个数
erase();
(1)输入一个数x,删除所有x; O(k * logn)
(2)输入一个迭代器，删除这个迭代器
lower_bound(); //返回大于等于x的最小的数的迭代器
upper_bound(); //返回大于x的最小的数的迭代器
//map/multimap
//将一个参数映射为另一个参数
size();
empty();
clear();
begin()/end();
insert(); //插入一个pair
erase(); //输入参数是pair或者迭代器
find();
[] // O(logn)
/* map<T1, T2> a[T1] = T2 */
8、unordered_set、unordered_map、unordered_multiset、unordered_multimap
基于哈希表
和上面类似，增删改查操作时间复杂度为O(1)
不支持lower_bound()和upper_bound()，迭代器的++、--
9、bitset
压位
//初始化
bitset<数量> s;
支持所有的位运算：~、&、|、^、<<、>>、==、!=
[]
count(); //返回有多少个1
any(); //判断是否至少有一个1
none(); //判断是否权威0
set(); //把所有位置1
reset(); //把所有位置0
set(k, v); //将第k位变成v
flip(); //等价于~
flip(k); //把第k为取反