知识点整理（3）STL常用
本篇突发奇想来记录一下平时刷题的时候容易用到的API，免得每次都去百度搜（开一堆csdn的窗口hhhh）。
常用算法
以下算法基本都在$algorithm$头文件中
lower_bound（begin,end,num）:该函数常常用于在一个排好序的数组中查找第一个大于等于num的数，其需要三个参数，第一个是查找范围的起始迭代器或地址，第二个是结束点，第三个就是需要比较的数。其返回查找到的数的迭代器，如果查找不到就返回
xxx.end()。所以使用的时候往往减去起始地址来获取索引，例子如下：int index=lower_bound(nums.begin(),nums.end(),cnt)-nums.begin();
该函数底层实现为二分查找（这玩意之后应该会单开一章讲），时间复杂度为$O(logn)$。upper_bound（begin,end,num）:把上面的大于等于变成大于，over。
上述两个函数都可以加第四个参数，即
greater<type>()，加了之后大于等于变成小于等于，大于变小于。sort（begin,end,mycmp）:懒人排序必备，注意的是自定义比较函数的编写，当return true的时候表示第一个数放在前面，第三个参数可以用greater来替代，表示从大排到小。
max、min:不必多说，只用知道也可以自定义比较函数就行了。
reverse（begin,end）: 常用于数组，字符串，容器中元素的反转，底层是遍历调用swap，所以时间复杂度为$O(n)$。
remove（begin,end,val）:remove并不是删除，只是把给定序列中不等于val的所有数移动到序列前面，最后返回该序列最后一个不等于val的数的末尾的地址
copy（begin,end,new_begin）:将前两个参数所给定的序列复制到第三个参数的序列中，第三个参数给的序列要先初始化
unique（begin,end）:对给定序列中的元素进行去重，但是并不是删除，而是像remove一样将相邻的重复元素移到后面去，在使用前要先排序，返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。实操起来会发现，最后得到的序列其实在返回的迭代器后面还有元素，就是一堆去重序列最后一个元素的复制。（离散化往往用得上）
distance（begin,end）:用于计算两个迭代器表示的范围内包含元素的个数
find_if（begin,end,mycmp）:它可以在前两个参数指定的范围内查找可以使第三个参数指定的谓词返回 true 的第一个对象。谓词不能修改传给它的对象。
transform(first,last,result,op):first是容器的首迭代器，last为容器的末迭代器，result为存放结果的容器，op为要进行操作的一元函数对象或sturct、class。比如op是一个将小写字母转为大写字母的函数，则这个就可以将first到last的元素中所有小写转大写并将结果的首迭代器存在result中
常用数据结构
这里是介绍一些常用数据结构的API
Vector
不必多说，基本算是用的最多的了，相当于能动态插入和删除的数组
std::vector<T> v(n);//初始化n个元素
v.push_back(T val);//尾部插入元素
v.pop_back();//删除尾部元素
v.insert(iterator it,T val);//在it的前面插入val
v.erase(begin,end);//删除指定范围中的元素
v.size();//元素个数
v.assign(begin,end);//复制另一个vector的内容
v.front();//第一个元素
v.back();//最后一个元素string
string这个这么常见的东西当然也算常用数据结构啦。
string s="adkajda1";
int n=s.length();//长度
//迭代器和[]都可以进行遍历
s+="123";//+运算符已被重载，方便！
string s1=s.substr(3,5);//从索引3开始连续5个字符组成的子串，注意索引从0开始
int pos=s1.find("123",1,6);//第二个参数和第三个参数代表从起始查询位置1起的6个字符，返回值是子串在母串中的位置（下标记录），如果没有找到，那么会返回一个特别的标记string::npos。
auto pos2=s1.rfind("123",9);//从索引为9的地方开始反着寻找子串
s1.find_first_of("123");
s1.find_last_of("123");//都是字面意思
s1.replace(pos,len,str);//用str替换指定字符串从起始位置pos开始长度为len的字符,这个函数用法请参照https://blog.csdn.net/cai_niaocainiao/article/details/81260902
std::replace(s1.begin(),s1.end(),'1','2');//将字符串中所有的1变成2，但是要注意的是只能替换一个字符
s2.assign(s1,7,3);//取s1从起始位置7开始长度为3的子串
s2.assign(5,'a')//aaaaa
s2.assign(s1.begin()+1,s1.end());
s2.erase(6,4); // 从位置pos=6处开始，删除4个字符,第二个参数不给出将默认为结尾
s2.erase(10);//// 从位置pos=10处开始删除，直到结尾
s3.c_str();//转成const char*型
s3=to_string(123)//s3="123",to_string实现将数字直接转成字符串，好用
int a=stoi("12331");//将string类型转换成int,atoi是将const char*转成int
float b=stof("123.123");//string转float哈希容器
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
STL中包括两个常用的哈希数据结构，unordered_map和unordered_set，这两个容器都可以使用迭代器来进行遍历（其实一般不用遍历），都没法用[]来遍历。使用哈希容器一般是用于查找键值，要注意的是键是唯一的。
unordered_map
其与map都为关联容器，都是存键值对的。其与map不同的地方是，map底层是用红黑树实现的，查询和修改都是$O(logn)$的时间复杂度，而unordered_map查询是$O(1)$的，快就完事了。但哈希容器都是无序的，所以对于那些有顺序要求的题，还得用map。
unordered_map<int,string> um{{2,"234"}};//初始化方式
unordered_map<Key,T>::iterator it;
um[1]="123";//存键值对方式
um.insert(make_pair(3,"456"));//插入一个pair
um.size();//返回键值对个数
//下列三种查找方式
str1=um[1];//通过[]
str2=um.at(1);//同上
it=um.find(1);//通过find方法,返回迭代器
int a=it->first;
string b=it->second;//迭代器取值
//erase的三种用法
int n=um.erase(1);//返回删除元素的个数，如果返回0代表没找到
it=um.erase(it1);//返回的迭代器指向被移除元素后的元素,如果返回end()代表没找到
it=um.erase(begin,end);//删除指定序列，返回的迭代器指向被移除的最后一个元素的下一个位置。
//遍历
for(auto&[a,b]:um){
//a是key,b是值
}unordered_set
首先说明一下，unorder版本的map和set只提供前向迭代器（非unorder版本提供双向迭代器）。
其与set相同的是其中都没有相同元素，且不能被修改。
unordered_set<int>us{1,2};//初始化
us.insert(3);//插入新元素，此时它会返回一个 pair 对象，这个 pair 对象包含一个迭代器，以及一个附加的布尔值用来说明插入是否成功。如果元素被插入，返回的迭代器会指向新元素；如果没有被插入，迭代器指向阻止插入的元素
us.insert(us.begin(),4);//只返回迭代器
//emplace同上
us.find(3);//查找元素是否在容器中，返回对应迭代器，不存在则返回us.end()
us.count(4);//统计该键在容器中的个数，返回1或者0
us.erase(us.find(2));//通过迭代器删除，配合find常用,返回被删除元素的个数
us.erase(1);//根据键值删除
us.erase(us.find(4),us.end());// erasing by range栈与队列
栈是filo序列（先进后出），而队列是fifo序列（先进后出）。而在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出的特征。
stack
只能访问栈顶元素，不能遍历,不能直接用对象进行初始化，但是可以用list来初始化。
stack<int>s;
s.push(1);
int a=s.top();
int b=s.size();
s.pop();queue
只能在容器的末尾添加新元素，只能从头部移除元素。
queue<int>q;
q.push(1);
int a=q.size();
a=q.front();//常用取对首
a=q.back();
q.pop();priority_queue
每次插入和删除元素时，优先队列内部都会自动维护，让优先级高的元素出现在顶部。
priority_queue <int,vector<int>,greater<int> > q1;//小顶堆，记得第三个参数到末尾要有空格，不然就变成右移运算符了
priority_queue <int,vector<int>,less<int> >q;//大顶堆，默认
priority_queue<pair<int, int> > a;//pair的比较，先比较第一个元素，第一个相等比较第二个。
//下面是自定义比较方式
//方法1
struct tmp1 //运算符重载<
{
int x;
tmp1(int a) {x = a;}
bool operator<(const tmp1& a) const
{
return x < a.x; //大顶堆
}
};
//方法2
struct tmp2 //重写仿函数
{
bool operator() (tmp1 a, tmp1 b)
{
return a.x < b.x; //大顶堆
}
};
int main()
{
tmp1 a(1);
tmp1 b(2);
tmp1 c(3);
priority_queue<tmp1> d;
d.push(b);
d.push(c);
d.push(a);
while (!d.empty())
{
cout << d.top().x << '\n';
d.pop();
}
cout << endl;
priority_queue<tmp1, vector<tmp1>, tmp2> f;
f.push(b);
f.push(c);
f.push(a);
while (!f.empty())
{
cout << f.top().x << '\n';
f.pop();
}
}