您的位置:首頁 >聚焦 >

【C++】STL梳理

2022-12-02 18:44:34    來源:程序員客棧

點擊關(guān)注,與你共同成長!


(資料圖片)


0x1 C++ STL

C++ STL(標準模板庫)是一套功能強大的 C++ 模板類,提供了通用的模板類和函數(shù),這些模板類和函數(shù)可以實現(xiàn)多種流行和常用的算法和數(shù)據(jù)結(jié)構(gòu),如向量、鏈表、隊列、棧。

C++ 標準模板庫的核心包括以下三個組件:

容器(Containers):用來管理某類對象的集合。每一種容器都有其優(yōu)點和缺點,所以為了應(yīng)付程序中的不同需求,STL 準備了七種基本容器類型。迭代器(Iterators):用來在一個對象集合的元素上進行遍歷動作。這個對象集合或許是個容器,或許是容器的一部分。每一種容器都提供了自己的迭代器,而這些迭代器了解該種容器的內(nèi)部結(jié)構(gòu)。算法(Algorithms):用來處理對象集合中的元素,比如 Sort,Search,Copy,Erase 那些元素。通過迭代器的協(xié)助,我們只需撰寫一次算法,就可以將它應(yīng)用于任意容器之上,這是因為所有容器的迭代器都提供一致的接口。

STL 的基本觀念就是將數(shù)據(jù)和操作分離。數(shù)據(jù)由容器進行管理,操作則由算法進行,而迭代器在兩者之間充當粘合劑,使任何算法都可以和任何容器交互運作。

0x2 C++ STL常用容器

為了應(yīng)付程序中的不同需求,STL 準備了兩類共七種基本容器類型:

序列式容器(Sequence containers):此為可序群集,其中每個元素均有固定位置—取決于插入時機和地點,和元素值無關(guān)。如果你以追加方式對一個群集插入六個元素,它們的排列次序?qū)⒑筒迦氪涡蛞恢隆TL提供了三個序列式容器:向量(vector)、雙端隊列(deque)、列表(list),此外你也可以把 string 和 array 當做一種序列式容器。關(guān)聯(lián)式容器(Associative containers):此為已序群集,元素位置取決于特定的排序準則以及元素值,和插入次序無關(guān)。如果你將六個元素置入這樣的群集中,它們的位置取決于元素值,和插入次序無關(guān)。STL提供了四個關(guān)聯(lián)式容器:集合(set)、多重集合(multiset)、映射(map)和多重映射(multimap)。

對于容器,主要的操作有:容器的建立、插入元素、刪除元素、查詢、遍歷、計算元素個數(shù)、檢查元素是否為空、輸出容器包含的內(nèi)容。

0x3 vector

一種序列式容器,事實上和數(shù)組差不多,但它比數(shù)組更優(yōu)越。一般來說數(shù)組不能動態(tài)拓展,因此在程序運行的時候不是浪費內(nèi)存,就是造成越界。而 vector 正好彌補了這個缺陷,當內(nèi)存空間不夠時,需要重新申請一塊足夠大的內(nèi)存并進行內(nèi)存的拷貝。

0x31 特點擁有一段連續(xù)的內(nèi)存空間,因此它能非常好的支持隨機訪問,即 [] 操作符和 .at(),隨機訪問快。(優(yōu)點)當向其頭部或中間插入或刪除元素時,為了保持原本的相對次序,插入或刪除點之后的所有元素都必須移動,所以插入或刪除的效率比較低。(缺點)在后面插入刪除元素最快,此時一般不需要移動內(nèi)存。(優(yōu)點)

總結(jié):相當于可拓展的數(shù)組(動態(tài)數(shù)組),隨機訪問快,在頭部和中間插入或刪除效率低,但在尾部插入或刪除效率高,適用于對象簡單,變化較小,并且頻繁隨機訪問的場景。

0x32 構(gòu)造函數(shù)vector():無參數(shù) - 構(gòu)造一個空的vectorvector(size_type num):數(shù)量(num) - 構(gòu)造一個大小為num,值為Type默認值的Vectorvector(size_type num, const TYPE &val):數(shù)量(num)和值(val) - 構(gòu)造一個初始放入num個值為val的元素的Vectorvector(const vector &from):vector(from) - 構(gòu)造一個與vector from 相同的vectorvector(input_iterator start, input_iterator end):迭代器(start)和迭代器(end) - 構(gòu)造一個初始值為[start,end)區(qū)間元素的Vector(注:半開區(qū)間).vector(initializer_list il, const allocator_type& alloc = allocator_type())C++11新提供的方法,類似如下方式:std::vectora{1, 2, 3, 4, 5}std::vectora = {1, 2, 3, 4, 5}0x33 常用APIOperators : 對vector進行賦值或比較v1 == v2v1 != v2v1 <= v2v1 >= v2v1 < v2v1 > v2v[]assign():對Vector中的元素賦值at(): 返回指定位置的元素back(): 返回最末一個元素begin(): 返回第一個元素的迭代器capacity(): 返回vector所能容納的元素數(shù)量(在不重新分配內(nèi)存的情況下)clear(): 清空所有元素empty(): 判斷Vector是否為空(返回true時為空)end(): 返回最末元素的迭代器(譯注:實指向最末元素的下一個位置)erase(): 刪除指定元素front(): 返回第一個元素get_allocator(): 返回vector的內(nèi)存分配器insert(): 插入元素到Vector中max_size(): 返回Vector所能容納元素的最大數(shù)量(上限)pop_back(): 移除最后一個元素push_back(): 在Vector最后添加一個元素rbegin(): 返回Vector尾部的逆迭代器rend(): 返回Vector起始的逆迭代器reserve(): 設(shè)置Vector最小的元素容納數(shù)量resize(): 改變Vector元素數(shù)量的大小size(): 返回Vector元素數(shù)量的大小swap(): 交換兩個Vector0x34 example

#include#includeusingnamespacestd;intmain(){vectorvecTemp;for(inti=0;i<6;i++){vecTemp.push_back(i);}for(inti=0;i

Output

012345

0x4 deque

deque是Double-Ended Queues(雙向隊列)的縮寫,是雙向開口的連續(xù)內(nèi)存空間(動態(tài)將多個連續(xù)空間通過指針數(shù)組接合在一起),隨時可以增加一段新的空間。deque 的最大任務(wù)就是在這些分段的連續(xù)空間上,維護其整體連續(xù)的假象,并提供隨機存取的接口。

0x41 特點一旦要在 deque 的頭部和尾部增加新空間,便配置一段定量連續(xù)空間,串在整個 deque 的頭部或尾部,因此不論在頭部或尾部插入元素都十分迅速。 (優(yōu)點)在中間部分安插元素則比較費時,因為必須移動其它元素。(缺點)deque 是 list 和 vector 的折中方案。兼有 list 的優(yōu)點,也有 vector 隨機訪問效率高的優(yōu)點。

總結(jié):支持隨機訪問,但效率沒有 vector 高,在頭部和尾部插入或刪除效率高,但在中間插入或刪除效率低,適用于既要頻繁隨機訪問,又要關(guān)心兩端數(shù)據(jù)的插入與刪除的場景。

0x42 構(gòu)造函數(shù)deque queT:queue采用模板類實現(xiàn),queue對象的默認構(gòu)造形式deque queT(size):構(gòu)造大小為size的deque,其中值為T類型的默認值deque queT(size, val):構(gòu)造大小為size的deque,其中值為valdeque(const deque &que):拷貝構(gòu)造函數(shù)deque(input_iterator start, input_iterator end):迭代器構(gòu)造函數(shù)0x43 常用APIback():返回最后一個元素front():返回第一個元素insert()pop_back(): 刪除尾部的元素pop_front(): 刪除頭部的元素push_back():在尾部加入一個元素push_front(): 在頭部加入一個元素at():訪問指定位置元素operator[] (size_type n):重載[]操作符empty():判斷隊列是否為空size():返回隊列的大小0x44 example

#include#includeusingnamespacestd;intmain(){std::dequefirst;///默認構(gòu)造形式std::dequesecond(5,200);///構(gòu)造大小為5的deque,其中值為200std::dequethird(second.begin(),second.end());///迭代器構(gòu)造函數(shù)std::dequefourth(third);///拷貝構(gòu)造函數(shù)///迭代器構(gòu)造函數(shù)可用于復制數(shù)組intmyInts[]={19,20,21,22};std::dequefifth(myInts,myInts+sizeof(myInts)/sizeof(int));std::cout<<"Thecontentsoffifthare:";for(std::deque::iteratorit=fifth.begin();it!=fifth.end();++it)std::cout<<""<<*it;std::cout<<"\n";return0;}

Output

Thecontentsoffifthare:19202122

0x5 list

List 由雙向鏈表(doubly linked list)實現(xiàn)而成,元素存放在堆中,每個元素都是放在一塊內(nèi)存中。沒有空間預留習慣,所以每分配一個元素都會從內(nèi)存中分配,每刪除一個元素都會釋放它占用的內(nèi)存。

0x51 特點內(nèi)存空間可以是不連續(xù)的,通過指針來進行數(shù)據(jù)的訪問,這個特點使得它的隨機存取變得非常沒有效率,因此它沒有提供 [] 操作符的重載。(缺點)由于鏈表的特點,在任意位置的插入和刪除效率都較高。(優(yōu)點)只支持首尾兩個元素的直接存取,想獲取其他元素(訪問時間一樣),則需要遍歷鏈表。(缺點)

總結(jié):不支持隨機訪問,在任意位置的插入和刪除效率都較高,適用于經(jīng)常進行插入和刪除操作并且不經(jīng)常隨機訪問的場景。

0x52 構(gòu)造函數(shù)list (const allocator_type& alloc = allocator_type())list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type())template list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())list (const list& x)0x53 常用APIassign():給list賦值back():返回最后一個元素begin():返回指向第一個元素的迭代器clear():刪除所有元素empty():如果list是空的則返回trueend():返回末尾的迭代器erase():刪除一個元素front():返回第一個元素get_allocator():返回list的配置器insert():插入一個元素到list中max_size():返回list能容納的最大元素數(shù)量merge():合并兩個listpop_back():刪除最后一個元素pop_front():刪除第一個元素push_back():在list的末尾添加一個元素push_front():在list的頭部添加一個元素rbegin():返回指向第一個元素的逆向迭代器remove():從list刪除元素remove_if():按指定條件刪除元素rend():指向list末尾的逆向迭代器resize():改變list的大小reverse():把list的元素倒轉(zhuǎn)size():返回list中的元素個數(shù)sort():給list排序splice():合并兩個listswap():交換兩個listunique():刪除list中重復的元素0x54 example

#include#includeusingnamespacestd;intmain(){listlistTemp;for(charc="a";c<="z";++c)listTemp.push_back(c);while(!listTemp.empty()){cout<

Output

abcdefghijklmnopqrstuvwxyz

0x6 set

set(集合)顧名思義,就是數(shù)學上的集合,集合中以一種特定的順序保存唯一的元素。

0x61 特點使用紅黑樹實現(xiàn),其內(nèi)部元素依據(jù)其值自動排序,每個元素值只能出現(xiàn)一次,不允許重復。每次插入值的時候,都需要調(diào)整紅黑樹,效率有一定影響。(缺點)map 和 set 的插入或刪除效率比用其他序列容器高,因為對于關(guān)聯(lián)容器來說,不需要做內(nèi)存拷貝和內(nèi)存移動。(優(yōu)點)

總結(jié):由紅黑樹實現(xiàn),其內(nèi)部元素依據(jù)其值自動排序,每個元素值只能出現(xiàn)一次,不允許重復,且插入和刪除效率比用其他序列容器高,適用于經(jīng)常查找一個元素是否在某集合中且需要排序的場景。

0x62 構(gòu)造函數(shù)set():無參數(shù) - 構(gòu)造一個空的setset(InputIterator first, InputIterator last):迭代器的方式構(gòu)造setset(const set &from):copyd的方式構(gòu)造一個與set from 相同的setset(input_iterator start, input_iterator end):迭代器(start)和迭代器(end) - 構(gòu)造一個初始值為[start,end)區(qū)間元素的Vector(注:半開區(qū)間).set (initializer_list il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())C++11新提供的方法,類似如下方式:std::seta{1, 2, 3, 4, 5};0x63 常用APIbegin():返回指向第一個元素的迭代器clear():清除所有元素count():返回某個值元素的個數(shù)empty():如果集合為空,返回trueend():返回指向最后一個元素的迭代器equal_range():返回集合中與給定值相等的上下限的兩個迭代器erase():刪除集合中的元素find():返回一個指向被查找到元素的迭代器get_allocator():返回集合的分配器insert():在集合中插入元素lower_bound():返回指向大于(或等于)某值的第一個元素的迭代器key_comp():返回一個用于元素間值比較的函數(shù)max_size():返回集合能容納的元素的最大限值rbegin():返回指向集合中最后一個元素的反向迭代器rend():返回指向集合中第一個元素的反向迭代器size():集合中元素的數(shù)目swap():交換兩個集合變量upper_bound():返回大于某個值元素的迭代器value_comp():返回一個用于比較元素間的值的函數(shù)0x64 example

#include#includeusingnamespacestd;intmain(){setsetTemp;setTemp.insert(3);setTemp.insert(1);setTemp.insert(2);setTemp.insert(1);for(intit:setTemp){cout<

Output

123

當 set 集合中的元素為結(jié)構(gòu)體時,該結(jié)構(gòu)體必須實現(xiàn)運算符 <的重載:

#include#includeusingnamespacestd;structPeople{stringname;intage;booloperator<(constPeoplep)const{returnagesetTemp;setTemp.insert({"天理",19});setTemp.insert({"天工",20});setTemp.insert({"天大",21});setTemp.insert({"南開",18});set::iteratorit;for(it=setTemp.begin();it!=setTemp.end();it++){printf("學校:%s就讀年齡:%d\n",(*it).name.c_str(),(*it).age);}return0;}

Output

學校:南開就讀年齡:18學校:天理就讀年齡:19學校:天工就讀年齡:20學校:天大就讀年齡:21

可以看到結(jié)果是按照年齡由小到大的順序排列。另外 string 要使用c_str()轉(zhuǎn)換一下,否則打印出的是亂碼。

Multiset 和 set 相同,只不過它允許重復元素,也就是說 multiset 可包括多個數(shù)值相同的元素。這里不再做過多介紹。

0x7 map

map 由紅黑樹實現(xiàn),其元素都是 “鍵值/實值” 所形成的一個對組(key/value pairs),map 內(nèi)部自建一顆紅黑樹,這顆樹具有對數(shù)據(jù)自動排序的功能,所以在 map 內(nèi)部所有的數(shù)據(jù)都是有序的。

0x71 特點每個元素都有一個鍵,且只能出現(xiàn)一次,不允許重復。根據(jù) key 值快速查找記錄,查找的復雜度基本是 O(logN),如果有 1000 個記錄,二分查找最多查找 10次(1024)。(優(yōu)點)每次插入值的時候,都需要調(diào)整紅黑樹,效率有一定影響。(缺點)增加和刪除節(jié)點對迭代器的影響很小,除了那個操作節(jié)點,對其他的節(jié)點都沒有什么影響。(優(yōu)點)對于迭代器來說,可以修改實值,而不能修改 key。

總結(jié):元素為鍵值對,key 和 value 可以是任意你需要的類型,每個元素都有一個鍵,且只能出現(xiàn)一次,不允許重復,根據(jù) key 快速查找記錄,適用于需要存儲一個數(shù)據(jù)字典,并要求方便地根據(jù)key找value的場景。

0x72 構(gòu)造函數(shù)map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())template map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type())map (const map& x)map (const map& x, const allocator_type& alloc)map (map&& x)map (map&& x, const allocator_type& alloc)map (initializer_list il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())0x73 常用APIbegin():返回指向map頭部的迭代器clear():刪除所有元素count():返回指定元素出現(xiàn)的次數(shù)empty():如果map為空則返回trueend():返回指向map末尾的迭代器equal_range():返回特殊條目的迭代器對erase():刪除一個元素find():查找一個元素get_allocator():返回map的配置器insert():插入元素–key_comp():返回比較元素key的函數(shù)lower_bound():返回鍵值>=給定元素的第一個位置max_size():返回可以容納的最大元素個數(shù)rbegin():返回一個指向map尾部的逆向迭代器rend():返回一個指向map頭部的逆向迭代器size():返回map中元素的個數(shù)swap():交換兩個mapupper_bound():返回鍵值>給定元素的第一個位置value_comp():返回比較元素value的函數(shù)0x74 example

#include#include#includeusingnamespacestd;intmain(){mapmapTemp;mapTemp.insert({1,"后端碼匠"});mapTemp.insert({2,"音視頻開發(fā)"});mapTemp.insert({3,"后端開發(fā)"});mapTemp.insert({4,"前端開發(fā)"});mapTemp.insert({4,"客戶端開發(fā)"});map::iteratorit;for(it=mapTemp.begin();it!=mapTemp.end();it++){printf("編號:%d崗位:%s\n",(*it).first,(*it).second.c_str());}return0;}

Output

編號:1崗位:后端碼匠編號:2崗位:音視頻開發(fā)編號:3崗位:后端開發(fā)編號:4崗位:前端開發(fā)

multimap 和 map 相同,但允許重復元素,也就是說 multimap 可包含多個鍵值(key)相同的元素。這里不再做過多介紹。

0x8 容器配接器

除了以上七個基本容器類別,為滿足特殊需求,STL還提供了一些特別的(并且預先定義好的)容器配接器,根據(jù)基本容器類別實現(xiàn)而成。包括:

0x81 stack

stack(堆棧)實現(xiàn)了一個先進后出(FILO)的數(shù)據(jù)結(jié)構(gòu)。

0x811 構(gòu)造函數(shù)stack stkT:采用模板類實現(xiàn),stack對象的默認構(gòu)造形式stack(const stack &stk):拷貝構(gòu)造函數(shù)0x812 常用APIsize():返回棧中的元素數(shù)top():返回棧頂?shù)脑豴op():從棧中取出并刪除元素push(x):向棧中添加元素xempty():在棧為空時返回true0x82 queue

queue 容器對元素采取 FIFO(先進先出)的管理策略。也就是說,它是個普通的緩沖區(qū)(buffer)。

0x821 構(gòu)造函數(shù)explicit queue (const container_type& ctnr)explicit queue (container_type&& ctnr = container_type())template explicit queue (const Alloc& alloc)template queue (const container_type& ctnr, const Alloc& alloc)template queue (container_type&& ctnr, const Alloc& alloc)template queue (const queue& x, const Alloc& alloc)template queue (queue&& x, const Alloc& alloc)0x822 常用APIback():返回最后一個元素empty():如果隊列空則返回真front():返回第一個元素pop():刪除第一個元素push():在末尾加入一個元素size():返回隊列中元素的個數(shù)0x83 priority_queue

優(yōu)先隊列類似隊列, 但是在這個數(shù)據(jù)結(jié)構(gòu)中的元素按照一定的規(guī)則排列有序。在優(yōu)先隊列中,元素被賦予優(yōu)先級。當訪問元素時,具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊列具有最高優(yōu)先級先出 (first in, largest out)的行為特征。首先要包含頭文件#include, 他和queue不同的就在于我們可以自定義其中數(shù)據(jù)的優(yōu)先級, 讓優(yōu)先級高的排在隊列前面,優(yōu)先出隊。優(yōu)先隊列具有隊列的所有特性,包括隊列的基本操作,只是在這基礎(chǔ)上添加了內(nèi)部的一個排序,它本質(zhì)是一個堆實現(xiàn)的。

0x831 構(gòu)造函數(shù)

priority_queue

Type 就是數(shù)據(jù)類型,Container 就是容器類型(Container必須是具備隨機存取能力的容器,支持如下方法:empty(), size(), front(), push_back(),pop_back()。比如vector,deque等等,但不能用list。STL里面默認用的是vector)??蛇xFunctional 就是比較的方式。可選0x832 常用APItop():訪問隊頭元素empty():隊列是否為空size():返回隊列內(nèi)元素個數(shù)push():插入元素到隊尾 (并排序)emplace():原地構(gòu)造一個元素并插入隊列pop():彈出隊頭元素swap():交換內(nèi)容

【音視頻】Android音頻開發(fā)基本概念

【Android】NDK開發(fā)Crash分析

【C++】PK游戲(玩轉(zhuǎn)多態(tài))

以上,便是今天的分享,希望大家喜歡,覺得內(nèi)容不錯的,歡迎「分享」「贊」或者點擊「在看」支持,謝謝各位。

關(guān)鍵詞: 構(gòu)造函數(shù) 插入或刪除

相關(guān)閱讀