C++STL筆記

本文主要內容如下：

1.vector

1.1vector的定義

1.2vector容器內元素的訪問

1.3vector常用函數

2.set

2.1 set的定義

2.2set容器內元素的訪問

2.3set常用函數

3.string

3.1 string 的定義

3.2string容器內元素的訪問

3.3string 常用函數

4.map

4.1 map的定義

4.2 map容器內元素的訪問

4.3 map常用函數

5. queue

5.1 queue的定義

5.2 queue 容器內元素的訪問

5.3 queue 常用函數

5.4 queue常見用途

6.priority_queue

6.1 priority_queue的定義

6.2 priority_queue 容器內元素的訪問

6.3 priority_queue 常用函數

6.4 priority_queue內元素優先級的設置

7. stack

7.1stack的定義

7.2stack容器內元素的訪問

8. pair

8.1 pair的定義

8.2 pair中元素的訪問

8.3 pair常用函數

8.4 pair常見用途

9. algorithm頭文件

1.vector

向量，長度可變的數組

頭文件

#include<vector>

1.1vector的定義

vector<typename> name;

例如：

vector<int> name;

如果typename是vector

vector<vector<int>>name;

相當于二維數組

vector<typename> ArrayName[arraySize];

例如：

vector<int> vi[100];

1.2vector容器內元素的訪問

（1）通過下標訪問

vi[index];

（2）通過迭代器訪問

vector<typename>：：iterator  it;

例如：

vector<int>::iterator  it;

有上下文環境時，可以直接用 auto it=vi.begin();

例如：

for(auto it=vi.begin();it!=vi.end();it++)

printf(“%d”,*it);

注：vi.begin()和vi.end()左閉右開。

1.3vector常用函數

（1）push_back()

在末尾添加一個元素。

vi.push_back(i);

（2）pop_back()

刪除一個尾元素。

  vi.pop_back();

（3）size()

返回vector元素的個數，注意是unsigned類型。

vi.size();

（4）clear()

清空vector中所有的元素。

vi.clear();

（5）insert()

insert(it,x)在迭代器it前插入一個元素x。

vi: 1 2 3 4 5

vi.insert(vi.begin()+2,-1);

vi:1 2 -1 3 4 5

（6）erase()

1.刪除單個元素

vi:5 6 7 8 9

vi.erase(vi.begin()+3)

vi:5 6 7 9

2.刪除一個區間內的所有元素

erase[first,last); 左閉右開

vi:5 6 7 8 9

vi.erase(vi.begin()+1,vi.begin+4)

vi:5 9

2.set

集合，一個內部自動有序且不含重復元素的容器

頭文件

#include<set>

2.1 set的定義

set<typename> name;

例如：

set<int> name;

set數組

set<typename>ArrayName[arraySize];

例如：

set<int> a[100];

2.2set容器內 元素的訪問

set只能用迭代器訪問

set<typename>::iterator it;

例如：

set<int>::iterator it;

set<int> st;

for(auto it=st.begin();it!=st.end();it++)

print(“%d”,*it);

st:2 3 5

set元素自動遞增排序，且自動去除重復元素。

注意：不能用it<st.end();

除了vector和string容器外不能用*(it+i)

2.3set常用函數

（1）insert()

insert(x)將x插入set容器中，并自動遞增排序和去重。

st.insert(x)

（2）find()

find(value)返回set中對應值為value的迭代器。

set<int>::iterator it = st.find(2);

（3）erase()

1.刪除單個元素

st.erase(it); //it 為迭代器

st.erase(find(100));

st.erase(value)，value 為所要刪除元素的值。

st.erase(100);

2.刪除區間內所有元素

erase[first,last); 左閉右開

st.erase(first,last);

st.erase(it,st.end());

（4）size()

返回set內元素的個數，unsigned類型

（5）clear()

清空set內所有的元素

3.string

字符串數組

3.1 string 的定義

string str=”abcd”;

3.2string容器內元素的訪問

（1）通過下標訪問

str[index];

輸出str

cout<<str;

printf(“%s”,str.c_str());

（2）通過迭代器訪問

string迭代器不需要參數

string::iterator it;

for(it=str.begin();it!=str.end();it++)

printf(“%c”,*it);

3.3string 常用函數

（1）operator+=

str1+=str2;

（2）compare operator

可直接使用 == ,!=,<=,<,>,>=比較大小，比較規則是字典序

（3）length()/size()

返回字符串長度，兩者基本相同。

（4）insert()

1.insert(pos.string);

在pos號位置插入字符串string

string str1=”abcxyz”;

string str2=”opq”;

str1.insert(3,str2);

str1:abcopqxyz

2.insert(it,it2,it3); //it為原字符串待插入位置，it2，it3位待插入字符串首尾迭代器。[it2,it3) 左開右閉

string str1=”abcxyz”;

string str2=”opq”;

str1.insert(str1.begin()+3,str2.begin(),str2.end())

str1:abcopqxyz

（5）erase()

1.刪除單個元素

str.erase(it) //it為所要刪除元素位置的迭代器

2.刪除一個區間內的所有元素

(1)str.erase(first,last); [first,last)左開右閉

string str=”abcdefg”;

str.erase(str.begin()+2,str.end()-1);

str:abg

(2)str.erase(pos,length);

pos為起始位置，刪除后面長度為length的字符串。

string str=”abcdefg”;

str.erase(3,2);

str:abcfg

（6）clear()

str.clear(); 清空字符串

（7）substr()

substr(pos,len); 返回從pos號位開始、長度為len的子串。

string str=”Thank you for your smile”;

str.substr(0,5);

Thank

str.substr(14,4);

your

str.substr(19,5);

smile

（8）string::npos

 string::npos是一個常數，其本身值為-1，unsigned_int類型，作為find函數失配時的返回值。

（9）find()

str1.find(str2); 當str2是str1的子串時，返回str2在str1中第一次出現的位置；如果str2不是str1的子串，返回string：：npos。

str1.find(str2,pos); 從str1的pos號位開始匹配str2，返回值與上文相同。

string str1=”Thank you for your smile”;

string str2=”you”;

string str3=”me”;

cout<<str1.find(str2);

6

cout<<str1.find(str2,7);

14

（10）replace()

1.str1.replace(pos,len,str2);  把str1從pos號位開始、長度為len的子串替換為str2.

2.str1.replace(it1,it2,str2);  把str1的迭代器[it1,it2)范圍的子串替換成str2.

string str1=”Maybe you will turn around”;

string str2=”will not”;

striing str3=”surely”;

cout<<str1.replace(10,4,str2);

Maybe you will not turn around

cout<<str1.replace(str1.begin(),str1.begin()+5,str3);

surely you will not turn around

4.map

映射，map可以將任何基本類型（包括STL容器）映射到任何基本類型（包括STL容器）。

例如：

字符串-->頁碼。

頭文件

#include<map>

4.1 map的定義

map<typename1,typename2> mp;

map<key,value> mp;

map<int,int> mp 相當于普通的int型數組。

如果是字符串到整型的映射，必須用string，不能用char數組。

map<string,int>  mp;

map的鍵和值也可以是STL容器。

例如:

map<set<int>,string> mp;

4.2 map容器內元素的訪問

1.通過下標訪問

與訪問普通數組一樣，例如

map<char,int> mp;

mp[‘c’]來訪問它對應的整數。

mp[‘c’]=20;

注：map的鍵值是唯一的。

2.通過迭代器訪問

map<typename1,typename2>::iterator it;

用it->first訪問鍵

用it->second訪問值

map<char,int>mp;

mp[‘m’]=20;

mp[‘r’]=30;

mp[‘a’]=40;

for(auto it=mp.begin();it!=mp.end();it++)

printf(“%c %d\n”,it->first,it->second);

map會按鍵值從小到大自動排序。

4.3 map常用函數

（1）find()

find(key)返回鍵值為key的映射的迭代器。

auto it = mp.find(‘c’);

（2）erase()

1.刪除單個元素。

mp.erase(it);  it為迭代器。

mp.erase(key); key為欲刪除的映射的鍵。

2.刪除一個區間內的所有元素。

map.erase(first，last)  [first,last) 刪除迭代器區間，左閉右開。

（3）size()

返回map中映射的對數。

（4）clear()

清空map中所有的元素。

5.queue

隊列，一個先進先出的容器。

頭文件

#include<queue>

5.1 queue的定義

queue<typename> name;

5.2 queue 容器內元素的訪問

queue是一種先進先出的限制訪問的數據結構。

只能front()訪問隊首元素，back()訪問隊尾元素。

queue<int> q;

q.front();

q.back();

5.3 queue 常用函數

（1）push()

q.push(x)將x進行入隊

（2）front() / back()

訪問隊首和隊尾元素。

（3）pop()

q.pop()令隊首元素出隊。

（4）empty()

檢測queue是否為空，返回true為空，返回false則非空。

（5）size()

返回queue內元素的個數。

5.4 queue常見用途

例如廣度優先搜索。

6.priority_queue

優先隊列，底層用堆來實現。在優先隊列中，隊首元素是當前隊列中優先級最高的一個。

頭文件

#include<queue>

6.1 priority_queue的定義

priority_queue<typename> name;

6.2 priority_queue 容器內元素的訪問

只能用q.top()函數訪問。

6.3 priority_queue 常用函數

（1）push()

q.push(x)將x入隊。

（2）top()

q.top()可以獲得隊首元素。

（3）pop()

令隊首元素（堆頂元素）出隊。

q.pop();

（4）empty()

檢測優先隊列是否為空，為空則返回true，返回false為空。

（5）size()

返回優先隊列內元素的個數。

6.4 priority_queue內元素優先級的設置

1.基本數據類型的優先級設置

基本數據類型指int、double、char型等數據類型。

下面兩種優先隊列的定義是等價的。

priority_queue<int> q;

priority_queue<int,vector<int>,less<int> > q;

vector<int> 是來承載底層數據結構堆（heap）的容器，而less<int>是比較類。

less<int> 表示數字大的優先級越大，而greater<int>表示數字小的優先級越大。char類型按字典序。

2.結構體的優先級設置

需要重載比較符號。

例如：

struct fruit{

string name;

int price;

friend bool operator<(fruit f1,fruit f2){

return f1.price<f2.price;
}

};

判斷f1==f2,則相當于!(f1<f2)&&!(f2<f1)。

所以 priority_queue<fruit> q; 內部以價格高的水果優先級高。

同理，如果想以價格低的水果為優先級高，那么把<改成>。

struct fruit{

string name;

int price;

friend bool operator<(fruit f1,fruit f2){

return f1.price>f2.price;
}

};

注：只能重載<,重載>會編譯錯誤。

不用greater<typename>,不重載<,不用friend函數

用cmp。

#include<iostream>

#include<queue>

#include<string>

using namespace std;

struct fruit{

string name;

int price;

}f1,f2,f3;

struct cmp{

bool operator () (fruit f1,fruit f2){

return f1.price>f2.price;

}

};

int main()

{

priority_queue<fruit,vector<fruit>,cmp> q;

f1.name="a";

f1.price=3;

f2.name="b";

f2.price=2;

f3.name="c";

f3.price=1;

q.push(f1);

q.push(f2);

q.push(f3);

cout<<q.top().name<<" "<<q.top().price;

return 0;

}

結果： c  1

即便是基本數據類型或其他STL容器（如set），也可以用同樣的方式定義優先級。如果結構體內數據較龐大，前面加const & 引用來提高效率。

friend bool operator<(const & fruit f1,const & fruit f2){

return f1.price>f2.price;

}

struct cmp{

bool operator () (const & fruit f1,const & fruit f2){

return f1.price>f2.price;

}

};

priority_queue的本質是堆。

7.stack

棧，一個后進先出的容器。

頭文件

#include<stack>

7.1stack的定義

stack<typename> name;

7.2stack容器內元素的訪問

由于棧是一種后進先出的數據結構，所以只能用top()來訪問棧頂元素。

st.top();

7.3 stack常用函數

（1）push()

st.push(x)將x入棧

（2）top()

st.top()訪問棧頂元素。

（3）pop()

st.pop()刪除棧頂元素。

（4）empty()

st.empty()檢測是否為空，為空返回true，否則返回false。

（5）size()

st.size()返回棧中元素的個數。

8.pair

當想要將兩個元素綁在一起作為一個合成元素，又不想定義結構體時，可以使用pair。

頭文件

#include<utility>

map實現用了pair，所以#include<map>包含#include<utility>，用map不需要再包含utility頭文件。

pair 相當于

struct pair{

typeName1 first;

typeName2 second;

};

8.1 pair的定義

pair<typeName1,typeName2> name;

例如：

pair<string ,int> p;

初始化：

pair<string ,int> p(“haha”,5);

pair<string,int> p=make_pair(“haha”,5);

8.2 pair中元素的訪問

用p.first和p.second訪問。

8.3 pair常用函數

（1）比較操作數，pair可以直接使用==,!=,<,<=,>,>=比較大 小。

       比較規則是先以first的大小作為標準，只有當first相等時才 去比較second的大小。

8.4 pair常見用途

例如：

#include<iostream>

#include<map>

using namespace std;

int main(){

map<string,int>mp;

mp.insert(make_pair("heihei",5));

mp.insert(pair<string,int>("haha",10));

//auto it ==map<string,int>::iterator it

for(auto it = mp.begin();it!=mp.end();it++)

cout<<it->first<<" "<<it->second<<endl;

return 0;

}

9.algorithm頭文件

（1）max() /min()/abs()

max和min返回兩個數x、y中的最大最小值。abs(x)中x必須為整數，浮點數用math頭文件下的fabs()。

（2）swap()

  swap(x,y)交換x和y的值。

（3）reverse()

reverse(it,it2)可以將數組指針在[it1,it2)之間的元素或容器的迭代器[it1,it2)范圍內的元素進行反轉。

例如：

int a[10]={10,11,12,13,14,15};

reverse(a,a+4); //將a[0]~a[3} 4個元素反轉。

13 12 11 10 14 15

string str =“abcdefghi”

reverse(str.begin()+2,str.begin()+6);

abfedcghi

（4）next_permutation()

next_permutation()給出一個序列在全排列中的下一個序列。

例如：

n=3的全排列為

123 132 213 231 312 321

231的下一個序列為312。

int a[10]={1,2,3};

do{

cout<<a[0]<<a[1]<<a[2]<<” ”;

}while(next_permutation(a,a+3));

輸出：123 132 213 231 312 321

（5）fill()

fill()可以把數組或某容器的某一段區間賦為某個相同的值，與memset不同，這里的賦值可以是數組類型對應范圍中的任意值。

int a[5];

fill(a,a+5,233);

（6）sort()

sort(a,a+4); //默認遞增排序

cmp函數

bool cmp(int a,int b){
return a>b; //從大到小排序 與priority_queue相反。

}

結構體

struct node{

int x;

int y;

}

bool cmp(node a,node b){

    if(a.x!=b.x)
return a.x>b.x; //按x從大到小排序 與priority_queue相反。

 else

return a.y<b.y; //若x相等，則按y從小到大排序。

}

STL中，只有vector，string，deque是可以用sort的，像set、map容器是用紅黑樹實現的，元素本身有序，不允許用sort排序。

（7）lower_bound()/upper_bound()

  lower_bound(first,last,val)用來尋找在數組或容器中的[first,last)范圍內第一個值大于等于val的元素的位置，如果是數組，返回該位置指針；如果是容器，返回該位置的迭代器。

upper_bound(first,last,val)用來尋找數組或容器的[first，last)范圍第一個值大于val的元素的位置，如果是數組，返回該位置指針；如果是容器，返回該位置的迭代器。

如果數組或容器中沒有尋找到該元素，則lower_bound()和upper_bound()返回可以插入該元素的位置的指針或迭代器。