STL笔记 之 vector
初识STL
STL,(Standard Template Library),即"标准模板库",由惠普实验室开发,STL中提供了非常多对信息学奥赛很有用的东西。
vector
vetor是STL中的一个容器,可以看作一个不定长的数组,其基本形式为:
vector<数据类型> 名字;
如: vector<int> v
或vector<char> t
。
vector的基本操作
先定义一个vector:vector<int> p;
,
p.clear()
清空vector的所有数据。
p.empty()
判断vector是否为空,返回值为 true
或 false
。
p.erase(pos)
删除pos位置的数据。
p.erase(begin,end)
删除begin~end之间的数据。
p.front()
返回vector的第一个数据。
p.insert(pos,data)
在vector的pos位置插入data。
p.push_back(data)
在vector的尾部加入一个数据data。
p.pop_back()
弹出vector末尾的数据。
p.resize(len)
重设vector的大小为len。
p.size()
返回vector实际数据的个数。
p.begin()
返回指向vector的第一个数据的迭代器。
p.end()
返回指向vector的最后一个数据的迭代器。
下面是一个vector代码的例子:
#include<bits/stdc++.h>
using namespace std;
vector<int> t;
int main(){
t.push_back(1);
t.push_back(2);
t.push_back(3);
cout<<t.size()<<endl;
cout<<t.front()<<endl;
t.push_back(10);
t.push_back(11);
t.erase(t.end()-1);
while(t.size()){
cout<<t[t.size()-1]<<" ";
t.pop_back();
}
return 0;
}
代码先向t中插入了1,2,3,然后输出t的数据的数量和t的第一个数据,即3 1
,又插入了10,11,把最后一个元素删去了(t.erase(t.end()-1);
),最后从后往前输出t中所有的数据,即10 3 2 1
。
一维vector代码示例
vector也可以像数组一样操作:
#include<bits/stdc++.h>
using namespace std;
vector<int> t;
int main(){
int n,m,a;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a;
t.push_back(a);
}
for(int i=1;i<=m;i++){
int k;
cin>>k;
cout<<t[k]<<endl;
}
return 0;
}
但是需要注意,vector初始插入下标为0!
vector对于未插入数据的下标使用时会RE!
#include<bits/stdc++.h>
using namespace std;
vector<int> t;
int main(){
cout<<t[100];//错误
return 0;
}
vector的遍历方式有两种:
(1)下标遍历
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int a;
cin>>a;
v.push_back(a);
}
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
return 0;
}
(2)迭代器遍历
迭代器类似于一个指针,它可以访问vector的所有元素。
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
vector<int>::iterator it;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int a;
cin>>a;
v.push_back(a);
}
for(it=v.begin();it!=v.end();it++){//使迭代器指向v的起始
cout<<*it<<" ";
}
return 0;
}
vector可以相互赋值,如:
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int a;
cin>>a;
v.push_back(a);
}
vector<int> v1(v);//把v的所有元素复制到v1
for(int i=0;i<v1.size();i++){
cout<<v1[i]<<" ";
}
return 0;
}
二维vector
二维的vector稍有些繁琐:
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > v;
vector<int> v1;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
v1.clear();
for(int j=1;j<=n;j++){
int a;
cin>>a;
v1.push_back(a);//先把数据添加进v1,再把v1插入到v
}
v.push_back(v1);
}
for(auto it=v.begin();it!=v.end();it++){//遍历
for(auto it2=it->begin();it2!=it->end();it2++){
cout<<*it2<<" ";
}
cout<<endl;
}
return 0;
}
例题 (洛谷P1540 机器翻译)
题目背景
NOIP2010 提高组 T1
题目描述
小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。
假设内存中有 \(M\) 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过 \(M-1\),软件会将新单词存入一个未使用的内存单元;若内存中已存入 \(M\) 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。
假设一篇英语文章的长度为 \(N\) 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。
输入格式
共 \(2\) 行。每行中两个数之间用一个空格隔开。
第一行为两个正整数 \(M,N\),代表内存容量和文章的长度。
第二行为 \(N\) 个非负整数,按照文章的顺序,每个数(大小不超过 \(1000\))代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。
输出格式
一个整数,为软件需要查词典的次数。
样例 #1
样例输入 #1
3 7
1 2 1 5 4 4 1
样例输出 #1
5
提示
样例解释
整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况:
1
:查找单词 1 并调入内存。1 2
:查找单词 2 并调入内存。1 2
:在内存中找到单词 1。1 2 5
:查找单词 5 并调入内存。2 5 4
:查找单词 4 并调入内存替代单词 1。2 5 4
:在内存中找到单词 4。5 4 1
:查找单词 1 并调入内存替代单词 2。
共计查了 \(5\) 次词典。
数据范围
- 对于 \(10\%\) 的数据有 \(M=1\),\(N \leq 5\);
- 对于 \(100\%\) 的数据有 \(1 \leq M \leq 100\),\(1 \leq N \leq 1000\)。
题目可以使用vector解决:
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int main(){
int n,m,ans=0;
cin>>m>>n;
for(int i=1;i<=n;i++){
int a;
cin>>a;
if((find(v.begin(),v.end(),a))==v.end()){//查找a是否存在于v中,不存在会指向v.end()
v.push_back(a);//加入内存
ans++;//查字典次数+1
}
if(v.size()>m){//如果大小大于内存容量删除v的第一个元素
v.erase(v.begin());
}
}
cout<<ans;
return 0;
}