算法競賽100天第2天——STLINC++（算法競賽必備知識總結(jié)匯總）-創(chuàng)新互聯(lián)

本文已收錄于專欄 🌲《百日算法競賽》🌲

創(chuàng)新互聯(lián)IDC提供業(yè)務(wù):綿陽服務(wù)器托管,成都服務(wù)器租用,綿陽服務(wù)器托管,重慶服務(wù)器租用等四川省內(nèi)主機(jī)托管與主機(jī)租用業(yè)務(wù);數(shù)據(jù)中心含:雙線機(jī)房,BGP機(jī)房,電信機(jī)房,移動機(jī)房,聯(lián)通機(jī)房。

前言：

序列容器

序列的要求：

1.vector

vector常用方法

vector遍歷

2、deque

頭文件

方法

3、list

頭文件

方法

4、queue

方法：

關(guān)聯(lián)容器

1、map

2、set

添加

獲取

總結(jié)

使用

不斷補(bǔ)充……

vector

pair

string

queue

priority_queue 優(yōu)先隊列（堆），默認(rèn)是大根堆

stack

deque 雙向隊列

set , map , multiset , multimap 基于平衡二叉樹（紅黑樹），動態(tài)維護(hù)有序序列

unordered_set , unordered_map ,

unordered_multiset , unorder_multimap 哈希表

bitset 壓位

前言：

我們在打比賽的時候為了方便通常會使用模板庫，C++有STL標(biāo)準(zhǔn)模板庫，Java對應(yīng)的則是集合框架，C++比賽經(jīng)常用容器，那么什么是容器呢？

容器是儲存其他對象的對象。被儲存的對象必須是同一類型。

只要是學(xué)過編程的兄弟都知道，這個定義后半句好像數(shù)組，確實，但是不盡相同。

分類：
容器分為兩個部分，一是序列容器（是一種各元素之間有順序關(guān)系的線性表，是一種線性結(jié)構(gòu)的可序群集。順序性容器中的每個元素均有固定的位置，除非用刪除或插入的操作改變這個位置。順序容器的元素排列次序與元素值無關(guān)，而是由元素添加到容器里的次序決定）（forword_list,list,queue,priority_queue,stack,deque,vector,array）。
另一個是關(guān)聯(lián)容器（關(guān)聯(lián)式容器是非線性的樹結(jié)構(gòu)，更準(zhǔn)確的說是二叉樹結(jié)構(gòu)。各元素之間沒有嚴(yán)格的物理上的順序關(guān)系，也就是說元素在容器中并沒有保存元素置入容器時的邏輯順序。但是關(guān)聯(lián)式容器提供了另一種根據(jù)元素特點排序的功能，這樣迭代器就能根據(jù)元素的特點“順序地”獲取元素。元素是有序的集合，默認(rèn)在插入的時候按升序排列（set,multiset,map,multimap）

序列容器
序列的要求：

X a(n,t)  //聲明一個名為a的有n個t組成的序列
X(n,t)     //匿名序列（這里我們不做過多的解釋）
X a(i,j)   //聲明一個名為a的序列，并且初始化(i,j)
的內(nèi)容
X(i,j)      //匿名序列
v.insert()   //由于insert重載方法比較多
   1.v.insert(p,t)//將t插到p的前面
   2.v.insert(p,n,t)//將n個t插入p之前
   3.v.insert(p,i.j)//將區(qū)間[i,j)的元素插入到p之前
v.erase(t,k)
   1.v.erase(t,k)//刪除他們之間的元素
   2.v.erase(p)//刪除p指向的元素
v.chear===v.erase(begin(),end());

1.vector

vector表示一段連續(xù)的內(nèi)存，基于數(shù)組實現(xiàn)，他有自動的內(nèi)存管理功能!

可以動態(tài)的改變vector的長度，并隨著元素的增加與減小來自動改變數(shù)組大小，它提供了直接添加尾部元素或者刪除元素的方法！
特點：
他可以反轉(zhuǎn)序列，所以它可以反向遍歷可反轉(zhuǎn)序列！（基于他的rbegin,rend）

使用前要調(diào)用頭文件

 #include

vectorv;//默認(rèn)初始化
vectorv(v1);//用v1初始化v
vectorv(v1.begin(),v1.end());//用v1初始化v
vectorv(100);//定義一個大小為100的數(shù)組！
vectorv(100,1)//定義個全為1而且長度為190的數(shù)組

vector常用方法

a.front(),a.rbegin() ?    //首元素
a.back(),a.rend() ?       //末尾元素
v.push_back() ? ?         //增加元素

v.insert() ?              
? ?1.v.insert(p,t)        //將t插到p的前面
? ?2.v.insert(p,n,t)      //將n個t插入p之前
? ?3.v.insert(p,i.j)      //將區(qū)間[i,j)的元素插入到p之前

v.pop_back() ? ? ?        //刪除

v.erase(t,k)
? ?1.v.erase(t,k)         //刪除他們之間的元素
? ?2.v.erase(p)           //刪除p指向的元素

v.clear===v.erase(begin(),end());//清空vector

vector遍歷

//下標(biāo)
int length = v.size();
for(int i=0;i::const_iterator iterator = v.begin();
?for(;iterator != v.end();iterator++)
{
?    cout<<*iterator;
}

2、deque

雙端隊列，他的實現(xiàn)與vector類似，支持隨機(jī)訪問，但是它訪問首元素的插入（push_front()）與刪除（pop_front()）的時間是固定的！而且他的執(zhí)行速度要比vector快很多！所以題目中有大量的操作發(fā)生在序列的起始位置與結(jié)尾處，我們就要考慮用deque!

頭文件

#include

方法

只是比vector多了兩個處理頭的方法

d.push_front(1)；
d.pop_front(1);

3、list

雙向鏈表，list在鏈表中的任意一個位置插入與刪除一個元素時間是固定的！但是他不能隨機(jī)訪問，優(yōu)點是元素的快速插入與刪除！從容器中插入與刪除元素之后i，迭代器指向元素將不變，不會移動已有元素，只是修改鏈表信息。

頭文件

#include

方法

void sort() ?                //使用<運(yùn)算符對鏈表進(jìn)行快速排序，時間復(fù)雜度O（NlogN）

void merge(list&x) ?
//將x與調(diào)用鏈表合并，要求：兩個鏈表必須要已經(jīng)排好序！
//元素將保存在調(diào)用鏈表中，x為空，這個時間復(fù)雜度為線性！

void remove(const T &val)    //刪除val的所有實例

void splice(iterator pos,listx)
//將鏈表x的內(nèi)容加到pos的前面

void unique（）     //去重(對list里面所有重復(fù)元素進(jìn)行去重，然后再排序)

forward_list 容器以單鏈表的形式存儲元素。
forward_list 的模板定義在頭文件 forward_list 中。
fdrward_list 和 list 最主要的區(qū)別是:它不能反向遍歷元素；只能從頭到尾遍歷。

想要深入了解forward_list的看這里C++ forward_list用法詳解 (biancheng.net)

4、queue

這是一個配適器類，ostream_iterator就是一個配適器，讓輸出流能夠使用迭代器接口，同樣它實現(xiàn)了隊列接口！它不僅不允許隨機(jī)訪問元素，而且還不能遍歷隊列！元素只能先進(jìn)先出（FIFO）.

方法：

bool empty()//判斷是否為空
front()//隊首元素的訪問
back()//隊尾元素的訪問
push(x)//隊尾插入x
pop()//刪除隊首元素

關(guān)聯(lián)容器

它運(yùn)用了鍵值對（value-key），與java類似的map,例如hashmap，有點在于他提供了利用key快速訪問功能，它的底層結(jié)構(gòu)應(yīng)該是一種樹來實現(xiàn)的，所以他才有如此快的查找速度，最簡單的set，他的鍵值對類型是一致的，而且唯一，元素默認(rèn)按升序排列。map他的鍵值對類型不同，鍵是唯一的,元素默認(rèn)按鍵的升序排列。

m.lower_bound(k)//返回一個迭代器，指向鍵不小于 k 的第一個元素
m.upper_bound(k)//返回一個迭代器，指向鍵大于 k 的第一個元素
m.equal_range(k)//返回一個迭代器的 pair 對象。它的 first 成員等價于 m.lower_bound(k)。而 second 成員則等價于 m.upper_bound(k)

1、map

map 是鍵－值對的集合。map 類型通?？衫斫鉃殛P(guān)聯(lián)數(shù)組：可使用鍵作為下標(biāo)來獲取一個值，正如內(nèi)置數(shù)組類型一樣。而關(guān)聯(lián)的本質(zhì)在于元素的值與某個特定的鍵相關(guān)聯(lián)，而并非通過元素在數(shù)組中的位置來獲取。

mapmap1; ? ?//默認(rèn)為空

m.insert()
? ? 1.m.insert(e)//e是一個用在m上的value_kry 類型的值。如果鍵（e.first不在m中，則插入一個值為e.second 的新元素；如果該鍵在m中已存在，則保持m不變。該函數(shù)返回一個pair類型對象，包含指向鍵為e.first的元素的map迭代器，以及一個 bool 類型的對象，表示是否插入了該元素
? ? 2.m.insert(begin,end)//begin和end是標(biāo)記元素范圍的迭代器，其中的元素必須為m.value_key 類型的鍵－值對。對于該范圍內(nèi)的所有元素，如果它的鍵在 m 中不存在，則將該鍵及其關(guān)聯(lián)的值插入到 m。返回 void 類型
? ? 3.m.insert(iter,e)//e是一個用在m上的 value_key 類型的值。如果鍵（e.first）不在m中，則創(chuàng)建新元素，并以迭代器iter為起點搜索新元素存儲的位置。返回一個迭代器，指向m中具有給定鍵的元素
m.count(k) //返回m中k的出現(xiàn)次數(shù)
m.find() ? //如果m容器中存在按k索引的元素，則返回指向該元素的迭代器。如果不存在，則返回超出末端迭代器.
m.erase() ?//具體與序列該方法一致！

2、set

支持插入，刪除，查找等操作，就像一個集合一樣。所有的操作的都是嚴(yán)格在logn時間之內(nèi)完成，效率非常高。set和multiset的區(qū)別是：set插入的元素不能相同，但是multiset可以相同。Set默認(rèn)自動排序。使用方法類似list。
set容器的定義和使用

set 容器的每個鍵都只能對應(yīng)一個元素。以一段范圍的元素初始化set對象，或在set對象中插入一組元素時，對于每個鍵，事實上都只添加了一個元素。

vectorivec;
for(vector::size_type i = 0; i != 10; ++i) {
ivec.push_back(i);
ivec.push_back(i);
}
setiset(ivec.begin(), ivec.end());
cout<< ivec.size()<< endl;//20個
cout<< iset.size()<< endl;// 10個

添加

setset1;
set1.insert("the"); //第一種方法：直接添加
setiset2;
iset2.insert(ivec.begin(), ivec.end());//第二中方法：通過指針迭代器

獲取

setiset;
for(int i = 0; i<10; i++)
iset.insert(i);
iset.find(1)// 返回指向元素內(nèi)容為1的指針
iset.find(11)// 返回指針iset.end()
iset.count(1)// 存在，返回1
iset.count(11)// 不存在，返回0

總結(jié)

有序容器（除了list）：存儲底層vector,只是添加了不同的接口！
deque（隊列）：它不像vector 把所有的對象保存在一塊連續(xù)的內(nèi)存塊，而是采用多個連續(xù)的存儲塊，并且在一個映射結(jié)構(gòu)中保存對這些塊及其順序的跟蹤。向deque 兩端添加或刪除元素的開銷很小，它不需要重新分配空間。
list（列表）：是一個線性鏈表結(jié)構(gòu)，它的數(shù)據(jù)由若干個節(jié)點構(gòu)成，每一個節(jié)點都包括一個信息塊（即實際存儲的數(shù)據(jù)）、一個前驅(qū)指針和一個后驅(qū)指針。它無需分配指定的內(nèi)存大小且可以任意伸縮，這是因為它存儲在非連續(xù)的內(nèi)存空間中，并且由指針將有序的元素鏈接起來。
后面的關(guān)聯(lián)與無序關(guān)聯(lián)都是用的一種樹狀結(jié)構(gòu)！

使用

當(dāng)數(shù)組大小未知時，和需要高效的查詢功能，用vector!高效地隨機(jī)存儲。
不使用連續(xù)的內(nèi)存空間,而且可以隨意地進(jìn)行動態(tài)操作，有大量的插入、刪除操作，用list！
需要在兩端進(jìn)行push 、pop用daque！它兼顧了數(shù)組和鏈表的優(yōu)點，它是分塊的鏈表和多個數(shù)組的聯(lián)合。所以它有被list 好的查詢性能，有被vector 好的插入、刪除性能。如果你需要隨即存取又關(guān)心兩端數(shù)據(jù)的插入和刪除，那么deque 是最佳之選。
需要查找或者打表可以選擇map與set,當(dāng)然一定條件下我們可以優(yōu)秀考慮用無序關(guān)聯(lián)容器！

不斷補(bǔ)充…… vector

 ? size() ?
? ? empty() ?
? ? clear()
? ? front()/back()
? ? push_back()/pop_back()
? ? begin()/end()
? ? 支持比較運(yùn)算符，按字典序 例:vectora(3,4);vectorb(4,3); 444>3333 ?a>b
? ? nth_element(a,a+x,a+n)數(shù)組a的總長度為n，函數(shù)執(zhí)行完后前x個數(shù)都比x+1位置上的小，后面所有數(shù)都比x+1位置上的數(shù)大，但不要求有序

pair

 ? pair ? first ?第一個元素
? ? second ?第二個元素
? ? 支持比較運(yùn)算符，以first為第一關(guān)鍵字，以second為第二關(guān)鍵字（字典序）

string

 ? substr()第一個參數(shù)開始位置，第二個參數(shù)截取的長度
? ? c_str() ?返回字符串首地址
? ? size()/length() ?返回字符串長度
? ? empty()
? ? clear()
? ? push_back('c') ?string拼接char型

queue

 ? size()
? ? empty()
? ? push()
? ? pop()
? ? front()
? ? back()

priority_queue 優(yōu)先隊列（堆），默認(rèn)是大根堆

 ? push()
? ? top()
? ? pop()
定義成小根堆的方式：（1）存入其相反數(shù)-x ? （2）priority_queue,greater>q;

stack

 ? size()
? ? empty()
? ? push()
? ? pop()
? ? top()

deque 雙向隊列

 ? size()
? ? empty()
? ? clear()
? ? front()/back()
? ? push_back()/pop_back()
? ? push_front()/pop_front()
? ? begin()/end()
? ? []

set , map , multiset , multimap 基于平衡二叉樹（紅黑樹），動態(tài)維護(hù)有序序列

 ? size()
? ? empty()
? ? clear()
? ? begin()/end() ++,-- 返回前驅(qū)和后繼

? ? set/multiset ?set里元素維一，multiset里可以有多個相同的元素
? ? ? ? insert() ?插入一個數(shù)
? ? ? ? find() 如果不存在返回end()
? ? ? ? count() 返回某一個數(shù)的個數(shù)
? ? ? ? erase()
? ? ? ? ? ? (1)輸入的是一個數(shù)x，刪除所有x ? o(k+logn)
? ? ? ? ? ? (2)輸入的是一個迭代器，刪除這個迭代器
? ? ? ? lower_bound()/upper_bound()
? ? ? ? ? ? lower_bount(x) ?返回大于等于x的最小的數(shù)
? ? ? ? ? ? upper_bount(x) ?返回大于x的最小的數(shù)
? ? map/multimap
? ? ? ? insert() ?插入一個pair
? ? ? ? erase() ?輸入的參數(shù)是pair或者迭代器
? ? ? ? [ ] ?時間復(fù)雜度o(logn)

unordered_set , unordered_map , unordered_multiset , unorder_multimap 哈希表

和上面類似，增刪改更快o(1)
但不支持 lower_bound()/upper_bound()/迭代器++，--

bitset 壓位

 ? bitset<10000>s;
? ? ~ & | ^
? ? >>,<<,==,!=,[]
? ? count() 返回有多少個1
? ? any() 判斷是否至少有一個1
? ? none() 判斷是否全為0
? ? set() 把所有位置置成1
? ? set(k,v) 把第k位變成1
? ? reset()把所有位變成0
? ? flip() 等價于~
? ? flip(k) 把第k位取反

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱：算法競賽100天第2天——STLINC++（算法競賽必備知識總結(jié)匯總）-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://muchs.cn/article30/dpidso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、營銷型網(wǎng)站建設(shè)、動態(tài)網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、搜索引擎優(yōu)化、企業(yè)網(wǎng)站制作

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容