/*
vector 变长数组 数组长度可以动态变化 基本思想是倍增思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front() 返回vector的第一个数
back() 返回vector的最后一个数
push_back() 向vector最后插入一个数
pop_back() 把vector最后一个数删掉
vector也是有迭代器的：
begin() vector的第0个数
end() vector的最后一个数后面一个数
vector支持随机寻址 跟数组一样
string 字符串, substr()可以返回子串, c_str()可以返回string对应的字符数组的头指针
size() / length()它的作用和size()是一模一样的 都是返回字符串长度
empty()
clear()
queue 队列 队尾插入队头弹出
size()
empty()
但queue是没有clear这个函数的 同样queue priorty_queue stack是没有clear这个函数的
如何清空一个queue q = queue<int>(); 直接构造一个空的queue就可以了
push() 往队尾插入
front()返回队头元素
back() 返回队尾元素
pop() 把队头弹出
priorty_queue优先队列/堆, 默认是大根堆
push() 往堆里插入一个元素
top() 返回他的堆顶
pop() 把堆顶弹出
如何定义小根堆？
priority_queue<int, vector<int>, greater<int>> heap; 将后面两个参数写出 一个是vector 一个是greater
stack 栈
empty()
size()
push() 往栈顶添加一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
时间复杂度都是O(1)的
deque 双端队列 队头队尾都可以插入弹出 而且可以支持随机访问
size()
empty()
clear()
front()
back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
支持随机寻址
但效率比一般数组要慢好几倍
set, map, multiset, multimap 基于平衡二叉树（红黑树实现）, 本质上是动态维护一个有序序列
红黑树是平衡二叉树的一种
size() O(1)
empty() O(1)
clear()
begin()/end() 迭代器 可以支持 ++ --操作 分别返回前驱和后继 时间复杂度 O(logN)
有序序列里的前驱指的是前面一个数
有序序列里的后继指的是后面一个数
set所有操作时间复杂度是log(N)
set/multiset
insert() 插入一个数
find() 查找一个数 如果不存在的话返回的是 end迭代器
count() 返回某一个数的个数
erase()
(1)输入是一个数，删除所有x O(k + logN) k是x的个数
(2)输入是一个迭代器，删除这个迭代器
*核心操作 注意混淆 意思并不是相反
1)lower_bound() 返回大于等于x的最小的数的迭代器
2)upper_bound() 返回大于x的最小的数的迭代器
如果不存在的话 返回 end迭代器
map/multimap 东西有点多 最好去往上搜一下C++STL的详细介绍 用的时候现用现查 不用背
map是C++里很常用的操作
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 时间复杂度是O(logN)
下面四个C++里已经帮我们实现的哈希表
unordered_set, unordered_map,
unordered_multiset, unordered_multimap
上面四个都是基于哈希表来实现的
操作跟上面类似 但绝大部分操作是O(1)的 即增删改查
不支持 lower_bound()/upper_bound() 因为他内部是没有序的
不支持 迭代器的++ --
压位实现
bitset 状态压缩 位存储
bit<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置或1
set(k, v)将第k位变成v
reset() 把所有位变成0
flip() 把所有位取反 等价于~
flip(k) 把第k位取反
list用的不多不讲
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
int main(){
// vector<int> a(10, 3);//初始化vector 这个效果是 定义一个长度为10的vector它里面每个数都是3
// //系统内某一程序分配空间时，所需时间与空间大小无关，与申请次数有关
// // 所以变长数组要尽量减少申请空间的次数
// //vector在优化的时候是尽量减少申请空间的次数 但是可以浪费空间 所以用的是倍增的思想
// //这两个函数所有容器都有 时间复杂度是O(1)的
// a.size();//返回的是a里面元素的个数
// a.empty();//返回的是a是不是空的
// clear();//清空这个函数不是所有容器都有 比方说队列queue就没有清空这个函数
// for(auto x : a) cout << x << endl;
// vector<int> a;
// for(int i = 0; i < 10; i++) a.push_back(i);
// for(int i = 0; i < a.size(); i++) cout << a[i] << ' ';
// cout << endl;
// for(vector<int>::iterator i = a.begin(); i != a.end(); i++) cout << *i << ' ';
// cout << endl;//用迭代器进行遍历
// // for(auto i = a.begin(); i != a.end(); i++) cout << *i << ' ';//当变量类特别长的时候 我们写auto就特别省事儿
// for(auto x : a) cout << x << ' ';
// cout << endl;
/*
pair<int, int>p;//pair可以存储一个二元组
pair<int, pair<int, int>>p;//这样pair可以存储三个东西
pair可以看成是帮我们实现了一个结构体 而且自带一个比较函数 比一般的结构体要省一些代码
p.first();//取得pair的第一个元素
p.second();//取得pair的第二个元素
// 支持比较运算，按照字典序比较运算，以first为第一关键字，以second为第二关键字（字典序）
p = make_pair(10, "yxc");
p = {20, "abc"};
vector<int> a(4, 3), b(3, 4);
if(a < b) puts("a < b");//按照字典序来比较 4个3是小于3个4的 所以3333 < 444是成立的
*/
// string a = "yxc";
// a += "def";
// a += 'c';
// cout << a << endl;
// cout << a.substr(1, 2) << endl;//从下标1开始返回2个字母
//当第二个数很大的时候 即超过最大长度的时候 我们就会输出到最后一个字母为止
//也可以把第二个数删掉 即直接返回从1开始到最后的字符串
// 注意：
// C++里的 substr 第一个值是起始位置 第二个值是子串长度
// 很多语言里第二个数是截至位置 不用语言注意区分 只有C++是子串长度 其他语言都是截至位置
set<int> S;
multiset<int> MS;
//set中是不能有重复元素的
map<string, int> a;
a["yxc"] = 1;
// yxc就映射到了1
cout << a["yxc"] << endl;
//这是查找 可以直接查找yxc
return 0;
}
