c++常用STL库及常用函数

临近各种算法比赛，相信很多人想笔者一样还总是记不住很多函数的用法，特此总结一下常用的STL标准库以及标准函数，希望能够有所帮助。

1. 输入输出

输入输出一般用两个标准库：

#include<cstdio>
#include<iostream>

一般笔者更习惯一些iostream库，iostream唯一比较常用但是难记的或许就是以下这句。

ios::sync_with_stdio(0);
cin.tie(0);
// cout.tie(0);

这句可以使得c++的cin，cout语句拥有接近printf和scanf的速度。

之所以不用printf和scanf，则纯粹是大学先接触的cin、cout罢了

2. 数组

一般来说，使用c++标准的数组也就足够了：

int arr[10005];

不过一些特殊情况下，我们肯能还是需要用到c++封装好的数组：vector。

vector可以支持在常数时间内的随机访问和尾部插入/删除操作，其使用案例如下：

# include<vector>

int<vector> vec(n); // n指定长度

// 常用函数
vec.push_back(number);
vec.pop_back();
int n=vec.size();

// 其它函数
vec.clear();
bool flag=vec.empty();

// 遍历方法
//1. 传统方法
int n=vec.size();
for(int i=0;i<n;i++{
  cout<<vec[i]<<endl;
}

//2. C++11中的方法
  for (auto num:vec)
  {
    cout<<num<<endl;
  }

3. set与map

可以说，set与map是C++中，除了数组之外最常用搞得数据结构了。set与map通常我们使用这四种类。

#include<set>
#include<unordered_set>

#include<map>
#include<unordered_map>

其中，加入unordered 前缀意味者不需要排序。如果没有unordered 前缀，那么该集合中的元素将会按照红黑树自动排序，这在我们需要有序数据或是遍历的时候较为有用。而加入unordered 前缀后，则集合中的元素会基于哈希表组织，插入和查找的时间复杂度很低（常数时间）。

以下是一些它们常用的函数（加入unordered 前缀与不加对应的函数是几乎一致的，只是内部实现略有不同）。

// 集合
set<int> s;

// 常用函数
int n=s.size();
s.insert(num);
s.erase(num);
s.count(num); // 常用来判断有无这一元素

// 遍历元素
set<int>::iterator it;
for(it = s1.begin(); it!=s1.end(); it++){ //自动排序元素
    cout<<*it<<endl;  // 这里的it是个指向数据的指针
}
//c++ 11
for(auto it : s){
    cout<<it<<endl;   // 这里的it就是数据本身
}
 
// map
map<string, int> m;

// 常用函数
int n=m.size();
m[key]=value; // 最简单的插入方法（个人认为）
m.erase(key);
s.count(key); // 常用来判断有无这一元素

// 遍历元素
map<string, int>::iterator it;
for (it = m.begin(); it != m.end(); it++) {
    cout<<it->first<<" "<<it->second<<endl;
}
// c++ 11
for(auto it : m){
    cout<<it.first<<" "<<it.second<<endl;
}

4. 常用算法（sort）

c++中，我们也会经常使用一些常用的算法，它们大多定义在algorithm包中，也有一些在std标准命名空间中：

using namespace std;

int max_value=max(a,b);

同时，algorithm中最常用的函数莫过于sort函数了，掌握sort函数非常重要。

#include<algorithm>

sort(vec.begin(),vec.end()); // 一般sort是针对vec或传统数组的，毕竟map和set本身自动排序

至于其它的算法，我认为不是特别重要，故直接省略

5. 栈和队列

除了上述所说的较为重要的库，栈和队列在数据结构中也是非常重要的。

#include <queue>
#include <stack>

// 队列
queue<int> q;
q.push(num);
q.pop();
int n=q.size();
bool isEmpty=q.empty();
int first=q.front(); // 队头
int last=q.back();   // 队尾：最后一个push进去的元素是队尾！

// 栈
stack<int>st;
st.push(num);
st.pop();
int top=q.top(); //栈顶元素
int n=st.size();
bool isEmpty=st.empty();

6. 优先队列和双端队列

优先队列

优先队列也在queue 库中，最简单的用法就是直接声明如下：

#include <queue>
priority_queue<int> q; 

这时q的元素就会自动从小到大排序。

当然，还有复杂一些的用法：

#include <queue>
// 大根堆
priority_queue<int> q; //等同于 priority_queue<int, vector<int>, less<int>> a;

// 小根堆
priority_queue<int, vector<int>, greater<int>> q;


// 常用函数
q.push(num);
int top=q.top();
q.pop();

我们可以使用实际的代码看看效果：

# include<iostream>
# include<queue> 
using namespace std;
int main(){
  priority_queue<int>q;
  q.push(1);
  q.push(3);
  q.push(2);
  cout<<q.top()<<endl; // 类似于普通队列的back()
  q.pop();
  cout<<q.top()<<endl; 
}
// 结果：3 2

# include<iostream>
# include<queue> 
using namespace std;
int main(){
  priority_queue<int,vector<int>,greater<int>>q;
  q.push(1);
  q.push(3);
  q.push(2);
  cout<<q.top()<<endl;
  q.pop();
  cout<<q.top()<<endl; 
}
// 结果：1 2

双端队列

与piriority_queue包含在queue中不同，双端队列在新的STL库（deque）中：

#include<deque>

queue<int>q;

// 常用函数： front指队头，back指队尾（新插入的）
q.push_back(num);
q.push_front(num);
q.pop_back();
q.pop_front();
int num=q.front();
int num=q.back();
int n=q.size();
bool flag=q.empty();