STL笔记 之 vector

初识STL

STL,(Standard Template Library),即"标准模板库",由惠普实验室开发,STL中提供了非常多对信息学奥赛很有用的东西。

vector

vetor是STL中的一个容器,可以看作一个不定长的数组,其基本形式为:

vector<数据类型> 名字;

如: vector<int> vvector<char> t

vector的基本操作

先定义一个vector:vector<int> p;,

p.clear() 清空vector的所有数据。

p.empty() 判断vector是否为空,返回值为 truefalse

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. 1 2:查找单词 2 并调入内存。
  3. 1 2:在内存中找到单词 1。
  4. 1 2 5:查找单词 5 并调入内存。
  5. 2 5 4:查找单词 4 并调入内存替代单词 1。
  6. 2 5 4:在内存中找到单词 4。
  7. 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;
}

热门相关:腹中人的有嚼劲的肉   寒门状元   99次离婚:厉少,请低调   首席的亿万老婆   我的抖音太无敌