最近要找工作,免不得要有一番筆試,今年好像突然就都流行在線筆試了,真是搞的我一塌糊塗。有的公司呢,不支持Python,Java我也不會,C有些數據結構又有些復雜,所以是時候把STL再看一遍了…不會告訴你距離上次使用可能已經有半年以上了。
STL為C++的標准模版庫,又稱為C++泛型庫,在std命名空間中定義了常用的數據結構和算法,使用起來十分方便。
STL提供三種類型的組件:
這一節主要說一下各種容器的常用操作,直接看代碼實例即可。
向量容器可以像數組一樣對元素進行隨機訪問,還可以在尾部插入元素,完全可以替代數組。具有內存自動管理的功能,對元素的插入和刪除可以動態調整所占用的內存空間。
#include<vector>
#include<iostream>
using namespace std;
// sort指定的排序算法
bool Comp(const int &a, const int &b){
if(a!=b)
return a>b;
else
return a>b;
}
int main(void){
// 初始化有三種方式
// 元素下標均從0開始
vector<int> v1; //不指定元素個數
vector<double> v2(10); // 10個元素,每個初值窦唯0.0
vector<int> v3(10, 1); // 10個元素,每個值都為1
// 尾部追加新元素
v1.push_back(1);
// 有2種方式訪問元素
// 使用下標方式訪問元素
cout<<v2[8]<<endl;
// 使用迭代器訪問
vector<int>::iterator it;
for(it=v1.begin();it!=v1.end();it++)
cout<<*it<<" ";
// 元素的插入 注意:插入的位置為迭代器的位置,不是下標
v3.insert(v3.begin()+2, 0);
// 元素的刪除,刪除迭代器所指的一個元素或一段區間的所有元素
v3.erase(v3.begin()+2); // 刪除第3個元素
v3.erase(v3.begin()+1, v3.begin()+5); // 第二到第五個,前開後閉
// 清空
v3.clear();
// 判斷是否為空
v1.empty(); // 為空則返回假,反之為真
// 查看元素個數
v2.size();
// reverse反向排列算法,需#include<algorithm>
reverse(v1.begin(), v1.end());
// 排序,需#include<algorithm>
sort(v1.begin(), v1.end());
// 自己指定排序算法
sort(v1.begin(), v1.end(), Comp);
}
可以把string理解為字符串類,提供了添加、刪除、替換、查找和比較豐富的方法,當然也可以使用vector來處理字符串,但是不如string功能豐富。同時可以使用vector這樣的向量,類似於字符數組。
#include<string>
#include<vector>
#include<iostream>
using namespace std;
// sort指定的排序算法
bool Comp(const int &a, const int &b){
if(a!=b)
return a>b;
else
return a>b;
}
int main(void){
// 創建string對象
string s;
// 賦值
s = "abc"; // or cin>>s; or char ss[5000]; scanf("%s", &ss); s=ss;
// 尾部添加字符
s = s + 'd';
// 尾部添加字符串
s = s + "hello world";
// append()方法添加
s.append("123");
// 插入字符到迭代器的位置之前
s.insert(s.begin(), 'p');
// 訪問string對象元素
cout<<s[0]<<endl;
//刪除string對象元素
s.erase(s.begin());
s.erase(s.begin(), s.begin()+2);
//長度
cout<<s.length()<<endl;
// 判斷空
cout<<s.empty()<<endl;
// 替換
s.replace(3, 3, "good"); // 從第四個起,連續三個字符替換成good
// 搜索
cout<<s.find('c')<<endl; // 查到返回下標,反之返回4294967295
cout<<s.find("123")<<endl;
// 比較
cout<<s.compare("cat")<<endl; // 比對方大返回1,小為-1,相等為0
// 反向排列reverse
reverse(s.begin(), s.end());
// string對象做vector元素
vector<string> v;
}
set實現了紅黑樹的平衡二叉檢索樹的數據結構,在插入元素的時候會自動調整二叉樹的排列,把元素放到適當的位置,以確保每個子樹根節點鍵值大於左子樹所有節點,同時小於右邊節點;另外,還要得確保左右子樹高度相等。不會插入同樣鍵值的元素。
平衡二叉檢索樹的檢索采用中序遍歷算法,構造set的目的是為了快速檢索。
#include<string>
#include<vector>
#include<set>
#include<iostream>
using namespace std;
// sort指定的排序算法
bool Comp(const int &a, const int &b){
if(a!=b)
return a>b;
else
return a>b;
}
int main(void){
set<int> s;
// 插入
s.insert(0);
s.insert(2);
s.insert(0); // 只有一個0
// 遍歷
set<int>::iterator it;
for(it=s.begin();it!=s.end();it++)
cout<<*it<<endl;
// 反向遍歷
for(set<int>::reverse_iterator rit=s.rbegin();rit!=s.rend();rit++)
cout<<*rit<<endl;
// 刪除元素
s.erase(0);
// 檢索,find(),找到,返回迭代器位置,反之返回最後一個元素的後一個位置,即end()
s.find(20);
}
map映照容器的元素數據由key, value組成,也采用紅黑樹實現,不允許重復鍵,比較函數只對value值比較,各項數據可以通過key檢索。
#include<string>
#include<vector>
#include<set>
#include<map>
#include<iostream>
using namespace std;
// sort指定的排序算法
bool Comp(const int &a, const int &b){
if(a!=b)
return a>b;
else
return a>b;
}
int main(void){
// 初始化
map<string, float> m;
// 插入元素
m["wang"] = 99.9;
m["zhao"] = 100.0;
// 前向遍歷
map<string, float>::iterator it;
for(it=m.begin();it!=m.end();it++)
cout<<(*it).first<<":"<<(*it).second<<endl;
// 刪除元素
m.erase("wang");
// 搜索 ,和set一樣
it = m.find("zhao");
}
雙端隊列,可以在兩側進行操作。
#include<string>
#include<vector>
#include<set>
#include<map>
#include<deque>
#include<iostream>
using namespace std;
// sort指定的排序算法
bool Comp(const int &a, const int &b){
if(a!=b)
return a>b;
else
return a>b;
}
int main(void){
// init
deque<int> d;
deque<float> dd(10);
deque<int> ddd(10, 1);
// 尾部插入,擴張隊列
d.push_back(1);
d.push_back(2);
d.push_back(3);
// 頭部插入,會覆蓋原有元素
d.push_front(10);
d.push_front(20); // 此時為 20, 10, 1
// 前向遍歷
for(int i=0;i<d.size();i++)
cout<<d[i]<<endl;
for(deque<int>::iterator it=d.begin();it!=d.end();it++)
cout<<*it<<endl;
// 反向遍歷, deque<int>::reverse_iterator rit, rbegin, rend
// 刪除
d.pop_front();
d.pop_back();
d.erase(d.begin());
// 清空
d.clear();
return 0;
}
雙向鏈表,節點保存不在連續內存中,所以迭代器只能通過 ++ 或 -- 操作來移動到前驅或者後繼節點,不能使用 +n 或者 -n 來操作。
#include<string>
#include<vector>
#include<set>
#include<map>
#include<deque>
#include<iostream>
using namespace std;
// sort指定的排序算法
bool Comp(const int &a, const int &b){
if(a!=b)
return a>b;
else
return a>b;
}
int main(void){
// init
list<int> l;
list<int> ll(10);
// 插入,3種方法鏈表都會自動擴張
l.push_back(1);
l.push_front(2);
l.push_back(3);
l.push_back(4);
l.insert(l.begin(), 20);
// 遍歷同其他容器
// 刪除
l.remove(1); // 刪除值為 1的所有元素
l.pop_front();
l.pop_back();
l.erase(l.begin());
// 清空
l.clear();
// find
l.find(l.begin(), l.end(), 5);
// sort
l.sort(); // 升序排序
// 刪除重復元素
l.unique();
return 0;
}
#include<stack>
#include<iostream>
using namespace std;
// sort指定的排序算法
bool Comp(const int &a, const int &b){
if(a!=b)
return a>b;
else
return a>b;
}
int main(void){
// init
stack<int> s;
s.push(1);
s.push(3);
s.pop();
s.top();
cout<<s.size()<<endl;
cout<<s.empty()<<endl;
return 0;
}
#include<queue>
#include<iostream>
using namespace std;
// sort指定的排序算法
bool Comp(const int &a, const int &b){
if(a!=b)
return a>b;
else
return a>b;
}
int main(void){
queue<int> q;
q.push(1);
q.push(1);
q.push(1);
cout<<q.size()<<endl;
cout<<q.front()<<endl; // 讀取隊首位置元素
cout<<q.back()<<endl; // 隊尾
cout<<q.empty()<<endl;
q.pop();
}