STL
嘿，c++好久不见，再次遇见你熟悉又陌生。很多刷题练出来的感觉一点点褪去，需要用实际题目再一次熟悉起来。今天来及时补救一下STL的概念，方便今后更高效的刷题。
【本文章将持续更新，不可能面面俱到，主要是搜集在刷题过程中遇到的用法。】
STL中,是把容器中迭代器传给算法，在算法中通过迭代器访问/遍历元素
[参考教程1]
[参考教程2]
当然最终的参考资料是官方文档：https://www.cplusplus.com/reference/
前提
- 输出迭代器（output iterator，记为：OutIt）：可以修改它所指向的容器元素
- 输入迭代器（input iterator，记为：InIt）：只能读取它所指向的容器元素
- 谓词：函数返回值是Bool；Pred 一元谓词，一个元素作为参数的函数；BinPred 二元谓词
string
string s;
string s5 = s1 + s2; //拼接
s2.insert(5, "bbb"); //在5下标处插入
s2.erase(5); // 删除5位置以及以后的所有
s3.erase(5, 3); //3表示要删除子字符串的长度
s1.find(s2,5) ; //查找从5位置开始的s2字符串
// find (const string& str, size_t pos = 0)
//find()返回值是字母在母串中的位置，没有找到则返回整数-1
s.front()='1';
s.back();
vector
vector<int> v;
vector<int> v(5,10); //5个元素内容为10
//迭代
for( auto it=v.begin();it!=v.end();it++){
cout<<*it<<endl;
}
v.push_back(10);
v.pop_back();//向量尾部删除
v.insert(v.begin(),10); //在最前端插入数据10
v.insert(v.begin(),k.begin(),k.end()); //在v最前端插入向量K的全部内容
v.erase(v.begin()); //删除元素
//erase (iterator position);
//erase (iterator first, iterator last);
v.clear(); //清空
// 输入vector的方法！！
vector<int> v(n);
for(int& i:v){
cin>>i;
}
// 求最小元素
*min_element(v.begin(), v.end());
list
-
概述：双向链表，任意位置增/删 【不可以用下表随意访问元素！！也没有find】
list<int> li;
li.empty(); //判空
li.size();
li.push_front(10);
li.pop_front(); //链表前增删
li.push_back(10);
li.pop_back(); //链表后增删
//insert和erase与vector相同
li.sort(); //升序排序
li.reverse(); //降序排列 (vector没有)
deque
deque<int> d;
//静态操作
d.size();
d.empty();
d.front();
d.back();
d[idx];
//动态操作
d.insert(pos,elem);
d.push_back(elem);
d.pop_back(elem);
d.erase(pos);
d.erase(beg,end);
stack
- 仅在尾部增/删元素
- 可基于
deque、list或vector来实现。
stack<int> s;
s.empty();
s.top(); //返回栈顶元素
s.pop(); //栈顶元素释放
s.push(); //入栈
Priority_queue
- 尾部增加、头部删除元素,自动排序（头部元素最大）
- 初始化→priority_queue<T, Container, Compare>//T数据类型，Container容器类型(必须是数组实现的容器：vector，deque)，compare比较方法
struct cmp
{ //这个比较要用结构体表示
bool operator()(int &a, int &b) const
{
return a > b;
}
};
priority_queue<int,vector<int>,cmp> q; //使用自定义比较方法
priority_queue< int, vector<int>, less<int> > q;
priority_queue< int, vector<int>, greater<int> > pq;
q.pop();
q.push();
q.top();
set
- 红黑树实现，每一次插入数据都会自动进行排序且数据唯一
set<int> s;
// C11实现
for (auto it=s.cbegin(); it!=s.cend(); ++it)
cout << *it;
s.insert();
s.erase(s.begin()); //使用迭代器的方法删除第一个元素
s.erase(s.begin(),s.end()); //删除一段内容，这里是全部删除
cout<< *s.find(4) ; //返回迭代器
s.erase(s.find(4)); //删除找到的元素
map
//查找电话的例子
map<string,int> m;
m["zhou"]=1234;
m["xiao"]=2345;
m["weng"]=3456;
for(pair<string,int>item: m){ //遍历输出
cout<<item.first<<":"<<item.second;
}
string name;
cin >> name;
map<string,int>::const_iterator it;
it=m.find(name);
if(it==m.end()) cout<<"not found";
else cout << it->first << ": " << it->second << endl; // 找到
//排序，转化为vector!
bool cmp(const PAIR& p1,const PAIR& p2){
if(p1.second==p2.second) return p1.first<p2.first;
return p1.second>p2.second;
}
...
map<int,int> m;
vector<PAIR> ans(m.begin(),m.end());
sort(ans.begin(),ans.end(),cmp);
for(PAIR& i:ans){
cout<<i.first<<" "<<i.second<<endl;
}
Pair类
- pair将一对值（可以有不同的数据类型）和为一个值
map<char,int> m;
m.insert(pair<char,int>('a',10));
//用first和second返回两个元素
pair<int,int> p(10,20);
cout<<p.first<<" "<<p.second;
//make_pair生成pair
pair<int,int> p(10,20);
cout<<p.first<<" "<<p.second<<endl;
array类
- C++11 标准中新增的序列容器,基于普通数组，大小固定
array<int,2> a;
a.begin();a.end();a.size();a.empty();
//实际用法【多用于需要点坐标时】
set<array<int,2>> s;
s.insert({k1,k2});
cout<<s.size();
其他函数
int sum = accumulate(vec.begin() , vec.end() , 42);//accumulate带有三个形参：头两个形参指定要累加的元素范围，第三个形参则是累加的初值。
//整数转化为字符串
int i=10;
if(to_string(i).find("7")==-1) ... //如果整数i中没有找到7
//判断char是否是字符
if(isdigit(c)) ...
//结构体排序
struct Point{
int x,y;
//重载+运算符
const Point operator+(Point other){
Point result(this->x+other.x,this->y+other.y);
return result;
}
};
//降序排列 great的在前面
bool GreaterSort(Point a,Point b){
if(a.x==b.x)return a.y>b.y;
return a.x>b.x;}
int main(){
int n;
cin>>n;
vector<Point> v(n);
for(Point &i:v){
cin>>i.x>>i.y;
}
sort(v.begin(),v.end(),GreaterSort);
for(Point i:v){
cout<<i.x<<" "<< i.y<<endl;
}
总结：
| int | long long int |
|---|
| 字节 | 4 | 8 | | 表示范围 | - 2147483648 ~ -2147483647 | -9223372036854775808 ~ 9223372036854775807 | | 量级 | 1 0 9 {10^{9}}109 | 1 0 21 {10^{21}}1021 |
find()函数
//原型：InputIterator find (InputIterator first, InputIterator last, const T& val);
//返回：找到元素的迭代器位置
vector<int>::iterator it;
it = find(myvector.begin(), myvector.end(), 30);
next()/prev()函数
- 返回一个距离 it 迭代器 n 个元素的新迭代器。
- next()：n为正则向后找，负则向前找
- prev()：与next相反
template <class BidirectionalIterator>
BidirectionalIterator prev (BidirectionalIterator it, typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
template <class ForwardIterator>
ForwardIterator next (ForwardIterator it, typename iterator_traits<ForwardIterator>::difference_type n = 1);
//获取一个距离 it 迭代器 2 个元素的迭代器，由于 2 为正数，newit 位于 it 右侧
list<int> l; ...
auto newit = next(l.begin(), 2);
cout << "next(it, 2) = " << *newit << endl;
erase函数
iterator erase (iterator position);
iterator erase (iterator first, iterator last);
|