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

目錄

創新互聯IDC提供業務:綿陽服務器托管,成都服務器租用,綿陽服務器托管,重慶服務器租用等四川省內主機托管與主機租用業務;數據中心含:雙線機房,BGP機房,電信機房,移動機房,聯通機房。

前言：

序列容器

序列的要求：

1.vector

vector常用方法

vector遍歷

2、deque

頭文件

方法

3、list

頭文件

方法

4、queue

方法：

關聯容器

1、map

2、set

添加

獲取

總結

使用

不斷補充……

vector

pair

string

queue

priority_queue 優先隊列（堆），默認是大根堆

stack

deque 雙向隊列

set , map , multiset , multimap 基于平衡二叉樹（紅黑樹），動態維護有序序列

unordered_set , unordered_map ,

unordered_multiset , unorder_multimap 哈希表

bitset 壓位

---

前言：

我們在打比賽的時候為了方便通常會使用模板庫，C++有STL標準模板庫，Java對應的則是集合框架，C++比賽經常用容器，那么什么是容器呢？

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

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

分類：
容器分為兩個部分，一是序列容器（是一種各元素之間有順序關系的線性表，是一種線性結構的可序群集。順序性容器中的每個元素均有固定的位置，除非用刪除或插入的操作改變這個位置。順序容器的元素排列次序與元素值無關，而是由元素添加到容器里的次序決定）（forword_list,list,queue,priority_queue,stack,deque,vector,array）。

另一個是關聯容器（關聯式容器是非線性的樹結構，更準確的說是二叉樹結構。各元素之間沒有嚴格的物理上的順序關系，也就是說元素在容器中并沒有保存元素置入容器時的邏輯順序。但是關聯式容器提供了另一種根據元素特點排序的功能，這樣迭代器就能根據元素的特點“順序地”獲取元素。元素是有序的集合，默認在插入的時候按升序排列（set,multiset,map,multimap）

序列容器
序列的要求：

X a(n,t)  //聲明一個名為a的有n個t組成的序列
X(n,t)     //匿名序列（這里我們不做過多的解釋）
X a(i,j)   //聲明一個名為a的序列，并且初始化(i,j)
的內容
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)//將區間[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表示一段連續的內存，基于數組實現，他有自動的內存管理功能!

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

使用前要調用頭文件

 #include

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

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)      //將區間[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遍歷

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

2、deque

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

頭文件

#include

方法

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

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

3、list

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

頭文件

#include

方法

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

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

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

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

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

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

??

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

4、queue

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

方法：

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

關聯容器

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

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 類型通常可理解為關聯數組：可使用鍵作為下標來獲取一個值，正如內置數組類型一樣。而關聯的本質在于元素的值與某個特定的鍵相關聯，而并非通過元素在數組中的位置來獲取。

mapmap1; ? ?//默認為空

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

2、set

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

set 容器的每個鍵都只能對應一個元素。以一段范圍的元素初始化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)// 返回指向元素內容為1的指針
iset.find(11)// 返回指針iset.end()
iset.count(1)// 存在，返回1
iset.count(11)// 不存在，返回0

總結

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

使用

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

不斷補充…… vector

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

pair

 ? pair ? first ?第一個元素
? ? second ?第二個元素
? ? 支持比較運算符，以first為第一關鍵字，以second為第二關鍵字（字典序）

string

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

queue

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

priority_queue 優先隊列（堆），默認是大根堆

 ? push()
? ? top()
? ? pop()
定義成小根堆的方式：（1）存入其相反數-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 基于平衡二叉樹（紅黑樹），動態維護有序序列

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

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

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站名稱：算法競賽100天第2天——STLINC++（算法競賽必備知識總結匯總）-創新互聯
轉載注明：http://m.newbst.com/article30/dpidso.html

成都網站建設公司_創新互聯，為您提供云服務器、營銷型網站建設、動態網站、手機網站建設、搜索引擎優化、企業網站制作

廣告

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