C++模板庫STL介紹——淺顯理解-創(chuàng)新互聯(lián)
變長數(shù)組,還可以以鄰接表的方式存儲圖.
#includeusing namespace std;
vectorname;
例子
vectorname;
vectorname;
//二維數(shù)組
vector>name;
vectorvi[100]; 普通訪問,通過下標(biāo)訪問即可
通過迭代器訪問
iterator 類似指針,可以實現(xiàn)++it和it++.
vector::iterator it; //我們有了迭代器it,可以用*it來訪問vector里面的元素 vector vi; vector ::iterator it =vi.begin(); //這里 *(it+i)=vi[i] 除了begin還有end,取的是末尾元素地址的下一位
- vi.push_back(i) 在vector后面添加一個元素i,O(1)
- vi.pop_back(i) 刪除vector的尾元素 O(1)
- vi.size() 返回的是vi的長度 O(1)
- vi.clear() 清空vi的所有元素,O(n)
- vi.insert(it,x) 在迭代器it處插入一個元素x,O(n)
- vi.erase(it) 刪除it處的元素,vi.erase(first,last) 刪除[first,last)內(nèi)的所有元素,注意左開右閉
- vector本身可以作為數(shù)組使用，而且在一些元素個數(shù)不確定的場合可以很好地節(jié)省空間
- 有些場合需要根據(jù)一些條件把部分數(shù)據(jù)輸出在同一行，數(shù)據(jù)中間用空格隔開。由于輸出數(shù)據(jù)的個數(shù)是不確定的，為了更方便地處理最后一個滿足條件的數(shù)據(jù)后面不輸出額外的空格，可以先用 vector記錄所有需要輸出的數(shù)據(jù)，然后一次性輸出。
set翻譯為集合，是一個內(nèi)部自動有序且不含重復(fù)元素的容器
setname;
seta[100]; set只能通過迭代器(iterator)訪問,由于除開 vector和 string之外的STL容器都不支持*(it+i)的訪問方式，因此只能按如下方式枚舉：
#include;
using namespase std;
setst;
set.insert(3);
for(set:: iterator it=st.begin();it!=st.end();it++){printf("%d",*it);
} st.insert(x),可將x插入set容器中，并自動遞增排序和去重，時間復(fù)雜度O(log n)
st.find(value),回set中對應(yīng)值為value的迭代器，間復(fù)雜度O(log n)
set :: iterator it=st.find(3);
st.erase(it)刪除it處的元素,it為迭代器,st.erase(value),也可以傳入某個值進行刪除. st.erase(first,last) 刪除[first,last)內(nèi)的所有元素,注意左開右閉.
st.size() 返回的是st的長度 O(1)
st.clear() 清空st的所有元素,O(n)
set最主要的作用是自動去重并按升序排序，因此碰到需要去重但是卻不方便直接開數(shù)組的情況，可以嘗試用set解決。
3. string 的常見用法詳解 3.1 定義用之前記得#include using namespace std
tips
3.2 訪問C++要兼容C的標(biāo)準(zhǔn)庫，而C的標(biāo)準(zhǔn)庫里碰巧也已經(jīng)有一個名字叫做“string.h”的頭文件，包含一些常用的C字符串處理函數(shù)，比如strcmp。 這個頭文件跟C++的string類半點關(guān)系也沒有，所以并非
的“升級版本”，他們是毫無關(guān)系的兩個頭文件。 #include
#include
usingnamespace std;
是舊的C 頭文件，對應(yīng)的是基于char*的字符串處理函數(shù)；是包裝了std 的C++頭文件，對應(yīng)的是新的string 類
1.通過下標(biāo)訪問
如果要讀入和輸出整個字符串，則只能用cin和cout,也可用 c_str()將 string類型轉(zhuǎn)換為字符數(shù)組進行printf輸出
2.通過迭代器訪問
string::iterator it =str.begin();使用*it訪問
3.3 常用函數(shù)將兩個string直接拼接起來:+ eg: str1=str2+str3;
比較大小可以直接用==, != ,< ,<= ,>,>= 按照字典序排列
返回長度 length()或者size() O(1)
insert() O(N)
- insert(pos,string) 在pos位置插入string
- insert(it, it2,it3) it為原字符串欲插入位置,it2和it3為待插入字符串的收尾迭代器,用來表示串[it2,it3)將插在it的位置上
erase()
- 刪除單個元素erase(it) it為迭代器
- 刪除一個區(qū)間的 erase(pos,length) pos為起始位置,length為字符個數(shù)
clear() 清空 O(1)
substr(pos, len) 返回從pos號位開始,長度為len的子串
string::npos 是一個常數(shù),本身的值為-1,用來作為find函數(shù)失敗的返回值
str.find(str2) 當(dāng)str2是str的子串時,返回其在str中第一次出現(xiàn)的位置.如果str2不是,則返回-1 str.find(str2,pos) 從pos開始匹配
str.replace(pos, len,str2) 把str從pos號位開始,長度為len的子串替換成str2. str.replace(it1,it2,str2) 把str[it1,it2)的子串替換成str2
習(xí)題 A1060 轉(zhuǎn)換成科學(xué)記數(shù)法
map可以將任何基本類型（包括STL容器）映射到任何基本類型（包括STL容器），也就可以建立 string型到int型的映射。
第一個鍵的類型,第二個是值得類型,字符串到整型的映射必須使用string而不是char數(shù)組.
mapmp; 1.通過下標(biāo)訪問
和訪問普通的數(shù)組是一樣的，例如對一個定義為map
2.通過迭代器訪問
for(map::iterator it = mp . begin() ; it ! = mp.end();it++){printf("%c %d\n",it->first,it->second);
} map迭代器的使用方式和其他STL容器的迭代器不同，因為map的每一對映射都有兩個typename，這決定了必須能通過一個it來同時訪問鍵和值。事實上，map可以使用it->first來訪問鍵，使用it->second來訪問值。
map會以鍵從小到大的順序自動排序，這是由于map內(nèi)部是使用紅黑樹實現(xiàn)的（set也是），在建立映射的過程中會自動實現(xiàn)從小到大的排序功能。
4.3 常用函數(shù)1.find(key) 返回鍵為key的映射迭代器,時間復(fù)雜度為O(logN)
2.erase()
- 刪除單個元素 mp.erase(it) ,it為需要刪除的元素的迭代器,時間復(fù)雜度O(1),或者mp.erase(key) ,key為欲刪除的映射的鍵,復(fù)雜度為O(logN)
- 刪除區(qū)間內(nèi)的元素 mp.erase(first,last)刪除的是[first,last).
3.size()用來獲取映射的對數(shù).O(1)
4.clear() 清空元素 O(N)
4.4 常見用途①需要建立字符（或字符串）與整數(shù)之間映射的題目，使用map可以減少代碼
②判斷大整數(shù)或者其他類型數(shù)據(jù)是否存在的題目，可以把map當(dāng)bool數(shù)組用。
③字符串和字符串的映射也有可能會遇到。
延伸：map的鍵和值是唯一的，而如果一個鍵需要對應(yīng)多個值，就只能用 multimap另外，C++11標(biāo)準(zhǔn)中還增加了 unordered_map，以散列代替map內(nèi)部的紅黑樹實現(xiàn)，使其可以用來處理只映射而不按key排序的需求，速度比map要快得多
5. queue的常見用法詳解 5.1 定義先進先出 的隊列
#include
using namespace std;
queue name;
5.2 queue容器內(nèi)元素訪問由于隊列(queue)本身就是一種先進先出的限制性數(shù)據(jù)結(jié)構(gòu)，因此在STL中只能通過front()來訪問隊首元素，或是通過 back()來訪問隊尾元素。
5.3 常用函數(shù)1.push(x),將x進入隊列,時間復(fù)雜度O(1)
2.front()來訪問隊首元素，或是通過 back()來訪問隊尾元素 O(1)
3.pop() 令隊首元素出隊,O(1)
4.empty() 檢測queue是否為空,返回true則為空,false則非空,O(1)
5.size() 返回個數(shù)O(1)
5.4 用途當(dāng)需要實現(xiàn)廣度優(yōu)先搜索時，可以不用自己手動實現(xiàn)一個隊列，而是用 queue作為代替以提高程序的準(zhǔn)確性。
另外有一點注意的是，使用 front()和pop()函數(shù)前，必須用 empty判斷隊列是否為空，否則可能因為隊空而出現(xiàn)錯誤。
priority_queue又稱為優(yōu)先隊列，其底層是用堆來進行實現(xiàn)的。在優(yōu)先隊列中，隊首元素定是當(dāng)前隊列中優(yōu)先級最高的那一個。當(dāng)然，可以在任何時候往優(yōu)先隊列里面加入（push）元素，而優(yōu)先隊列底層的數(shù)據(jù)結(jié)構(gòu)堆（heap）會隨時調(diào)整結(jié)構(gòu)，使得每次的隊首元素都是優(yōu)先級大的
#include
using namespace std;
priority_queue name;
6.2 容器內(nèi)元素訪問和隊列不一樣的是，優(yōu)先隊列沒有front()函數(shù)與 back0函數(shù)，而只能通過top()函數(shù)來訪問隊首元素（也可以稱為堆頂元素），也就是優(yōu)先級最高的元素。
6.3 常用函數(shù)解析1.push(x),x入隊,O(logN)
2.top(),獲得隊首元素.(堆頂元素),O(1)
3.pop(),令隊首元素(堆頂元素)出隊,O(logN)
4.empty() 檢測queue是否為空,返回true則為空,false則非空,O(1)
5.size() 返回個數(shù)O(1)
6.4元素優(yōu)先級設(shè)置1.基本數(shù)據(jù)類型的優(yōu)先級設(shè)置
此處指的基本數(shù)據(jù)類型就是int型、 double型、char型等可以直接使用的數(shù)據(jù)類型，優(yōu)先隊列對它們的優(yōu)先級設(shè)置一般是數(shù)字大的優(yōu)先級越高，因此隊首元素就是優(yōu)先隊列內(nèi)元素大的那個（如果char型，則是字典序大的）。對基本數(shù)據(jù)類型來說，下面兩種優(yōu)先隊列的定義是等價的（以int型為例，注意最后兩個>之間有一個空格）
大頂堆
priority_queueq;
priority_queue, less>q; 可以發(fā)現(xiàn)，第二種定義方式的尖括號內(nèi)多出了兩個參數(shù)：一個是 vector，另一個是less。其中 vector（也就是第二個參數(shù)）填寫的是來承載底層數(shù)據(jù)結(jié)構(gòu)堆(heap)的容器，如果第一個參數(shù)是 double型或char型，則此處只需要填寫 vector< double>或 vector；而第三個參數(shù) less則是對第一個參數(shù)的比較類， less表示數(shù)字大的優(yōu)先級越大，而greater表示數(shù)字小的優(yōu)先級越大.
讓最小的元素放在隊首
小頂堆
priority_queue, greater>q; 2.結(jié)構(gòu)體的優(yōu)先設(shè)置
希望按水果的價格高優(yōu)先級高,需要重載小于號<.
優(yōu)先隊列的這個函數(shù)與sort中的cmp函數(shù)的效果是相反的。
struct fruit{string name;
int price;
friend bool operator< (fruit &f1, fruit &f2){//建議引用
return f1.priceq; 定義在外面也可以
6.5 用途可以解決貪心問題,也可以對dijkstra進行優(yōu)化.
7. stack 的常見用法詳解 7.1 定義#include
using namespace std;
stack name;
7.2 元素訪問只能通過top()來訪問棧頂元素.因為他是先進后出的數(shù)據(jù)結(jié)構(gòu)
7.3 常用函數(shù)解析1.push(x)入棧 O(1)
2.pop() 出棧 O(1)
3.top()獲得棧頂元素,O(1)
4.empty() 檢測stack是否為空,返回true則為空,false則非空,O(1)
5.size() 返回元素個數(shù) O(1)
7.4 常見用途stack用來模擬實現(xiàn)一些遞歸，防止程序?qū)?nèi)存的限制而導(dǎo)致程序運行出錯。
8.pair的常見用法詳解 8.1 定義pair,當(dāng)想要將兩個元素綁在一起作為一個合成元素、又不想此定義結(jié)構(gòu)體時，使用pair可以很方便地作為一個代替品。也就是說，par實際上可以看作一個內(nèi)部有兩個元素的結(jié)構(gòu)體，且這兩個元素的類型是可以指定的，如下面的短代碼所示
struct pair{typename1 first;
typename2 second;
};#includeusing namespace std;
pairp;
pairp;
pairp("haha",5);
pair("haha",5);
make_pair("haha",5); 用p.first和p.second訪問
8.3 常用函數(shù)解析比較操作數(shù)
兩個pai類型數(shù)據(jù)可以直接使用=、!=、<、<、>>比較大小，比較規(guī)則是先以frst的大小作為標(biāo)準(zhǔn)，只有當(dāng)frst相等時才去判別 second的大小
8.4 常見用途①用來代替二元結(jié)構(gòu)體及其構(gòu)造函數(shù)，可以節(jié)省編碼時間
②作為map的鍵值對來進行插入
mp.insert(make_pair("haha",5));- max(),min(),abs()
max（x,y）和min（x,y）分別返回x和y中的大值和最小值，且參數(shù)必須是兩個（可以是浮點數(shù)）。如果想要返回三個數(shù)x、y、z的大值，可以使用max（x,max（y,z）的寫法。
abs(x)返回x的絕對值。注意：x必須是整數(shù)，浮點型的絕對值請用math頭文件下的fabs.
swap() 交換兩個數(shù)
reverse(): reverse（it, it2）可以將數(shù)組指針在**[it,it2)**之間的元素或容器的迭代器在[it,i2)范圍內(nèi)的元素進行反轉(zhuǎn)。
int a[10]={10,11,12,13,14,15}; reverse(a,a+4); //輸出 13 12 11 10 14 1next_permutation() 給出一個序列在全排列中的下一個序列。
fill() fill()可以把數(shù)組或容器中的某一段區(qū)間賦為某個相同的值。和 memset不同，這里的賦值可以是數(shù)組類型對應(yīng)范圍中的任意值。
sort() 排序 前面講過了
lower_bound() 和upper_bound()
lower_bound（ first, last，val）用來尋找在數(shù)組或容器的[first,last)范圍內(nèi)第一個值大于等于val的元素的位置，如果是數(shù)組，則返回該位置的指針；如果是容器，則返回該位置的迭代器。upper_bound() 返回第一個大于val.如果沒找到,則返回可以插入該元素的位置的指針或迭代器.
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
文章名稱：C++模板庫STL介紹——淺顯理解-創(chuàng)新互聯(lián)
本文鏈接：http://m.jiaotiyi.com/article/jpjei.html