初識STL STL，(Standard Template Library)，即"標準模板庫"，由惠普實驗室開發，STL中提供了非常多對信息學奧賽很有用的東西。 vector vetor是STL中的一個容器，可以看作一個不定長的數組，其基本形式為: vector<數據類型> 名字; 如: 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;
}
