/*
vector,变长数组,倍增的思想
ver.size() 返回vector数组元素个数 时间复杂度为O(1)
ver.empty() vector数组为空返回true,不为空返回false 时间复杂度为O(1)
ver.clear() 清空
ver.front()/back() 返回vector数组的第一个元素/返回vector数组的最后一个元素
ver.push_back()/pop_back() 向vector数组的末尾插入一个元素/删除vector数组的最后一个元素
ver.begin()/end() vector数组的第一个元素的迭代器/vector数组的最后一个元素后边一个位置的迭代器
ver[] []随机访问
支持比较运算(按字典序)
ver.reserve() 重新分配内存 // ver.resize()
pair<int,int>,存储二元组
first 第一个元素
second 第二个元素
支持比较运算 以first为第一关键字,以second为第二关键字 (按字典序)
string,字符串
str.size()/stg.length() 返回字符串元素个数/返回字符串长度 时间复杂度为O(1)
str.empty() string数组为空返回true,不为空返回false 时间复杂度为O(1)
str.clear() 清空
str.substr(a,b) 返回str字符串中从a开始长度为b的子串,b如果大于字符串长度或者省略默认b为最后一个元素
str.c_str() 返回str字符串首元素地址
str.append() append函数是向str的后面追加字符或字符串。
queue,队列
que.size() 返回队列元素个数 时间复杂度为O(1)
que.empty() 队列为空返回true,不为空返回false 时间复杂度为O(1)
que.push() 向队尾插入一个元素
que.front() 返回队头元素
que.back() 返回队尾元素
que.pop() 弹出对头元素
priority_queue,优先队列(默认大根堆)
prque.push() 插入一个元素
prque.top() 返回堆顶元素
prque.pop() 弹出堆顶元素
定义成小根堆的方式 priority_queue<int,vector<int>,greater<int>> prque;
stack,栈
stk.size() 返回栈的元素个数 时间复杂度为O(1)
stk.empty() 栈为空返回true,不为空返回false 时间复杂度为O(1)
stk.push() 向栈顶插入一个元素
stk.top() 返回栈顶元素
stk.pop() 弹出栈顶元素
deque,双端队列 (加强版vector,缺点是速度非常慢)
dee.size() 返回双端队列元素个数 时间复杂度为O(1)
dee.empty() 双端队列为空返回true,不为空返回false 时间复杂度为O(1)
dee.clear() 清空双端队列
dee.front()/back() 返回双端队列的第一个元素/返回双端队列的最后一个元素
dee.push_back()/push_back() 向双端队列的末尾插入一个元素/弹出双端队列的最后一个元素
dee.pop_front()/pop_front() 向队首插入一个元素/弹出队首元素
dee.begin()/end() 双端队列的第一个元素的迭代器/双端队列的最后一个元素后边一个位置的迭代器
dee[] []随机寻址
set,map,multiset,multimup, 基于二叉平衡树(红黑树),动态维护有序序列(从小到大)
size() 时间复杂度为O(1)
empty() 时间复杂度为O(1)
clear()
begin()/end() 支持++,--操作(时间复杂度是O(log)) 返回前驱和后继
set/multiset set里面的元素不重复,multiset里面的元素可以重复 所有操作时间复杂度为O(logn),除特例
insert() 插入一个元素
find() 查找一个元素(如果不存在的话返回迭代器end())
count() 返回某一个元素的个数 (set返回0 or 1,multiset返回 >=0)
erase()
(1) 输入的是一个数x ,删除所有x 时间复杂度O(k+logn)
(2) 输入的是一个迭代器,删除这个迭代器
lower_bound()/upper_bound() (核心操作)
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimup
insert() 插入的元素是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 随机访问 时间复杂度是O(logn)
lower_bound()/upper_bound() (核心操作)
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
unordered_set(不按顺序),unordered_map,unordered_multiset,unordered_multimup,哈希表
和上面类似,增删查改的时间复杂度为O(1)
不支持lower_bound()/upper_bound()
不支持迭代器的++,--操作以及排序的一切操作
bitset, 压位
bitset<10000> s;
支持 ~ , & , | , ^
>>,<<
==,!=
[] 等操作
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置置为1
set(k,v) 把第k位变为v
reset 把所有位置变为0
flip() 等价于~
flip(k) 把第k位取反
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
int main()
{
//开始:vector数组的三种枚举方式
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;
//a.begin()=a[0] a.end()=a[a.size()]
for(auto x:a) cout<<x<<' ';
cout<<endl;
//结束
//开始: vector的比较运算
vector<int> b(3,4),c(4,3);
if(a<b) puts("a<b");
//结束
//开始: 创建pair变量及初始化
pair<int,string> d; //两种属性
pair<int,pair<int,int>> e; //三种属性
d=make_pair(10,"hhm");
d={10,"yxc"};
//结束
//开始: string 常用操作
string f="abc";
f+="avc"; //可以加上一个字符串
f+='s'; //也可以加上一个字符
cout<<f<<endl;
cout<<f.substr(1,2)<<endl;
cout<<f.substr(1)<<endl;
cout<<f.substr(1,100)<<endl;
printf("%s\n",f.c_str());
//结束
//开始:清空队列的实现方式
queue<int> g;
g=queue<int>();
//结束
//开始:定义大根堆与小根堆 的方式
priority_queue<int> h_head; //大根堆
priority_queue<int> i_head; i_head.push(-1); //间接定义小根堆(向大根堆中插入负数,较为技巧性)
priority_queue<int,vector<int>,greater<int>> j_head;
//结束
//开始:map的使用方法
map<string,int> k;
k["hhm"]=1; //插入操作
cout<<k["hhm"]<<endl;
//结束
return 0;
}