【C++】STL梳理
點(diǎn)擊關(guān)注,與你共同成長(zhǎng)!
(資料圖片)
0x1 C++ STL
C++ STL(標(biāo)準(zhǔn)模板庫(kù))是一套功能強(qiáng)大的 C++ 模板類,提供了通用的模板類和函數(shù),這些模板類和函數(shù)可以實(shí)現(xiàn)多種流行和常用的算法和數(shù)據(jù)結(jié)構(gòu),如向量、鏈表、隊(duì)列、棧。
C++ 標(biāo)準(zhǔn)模板庫(kù)的核心包括以下三個(gè)組件:
容器(Containers):用來(lái)管理某類對(duì)象的集合。每一種容器都有其優(yōu)點(diǎn)和缺點(diǎn),所以為了應(yīng)付程序中的不同需求,STL 準(zhǔn)備了七種基本容器類型。迭代器(Iterators):用來(lái)在一個(gè)對(duì)象集合的元素上進(jìn)行遍歷動(dòng)作。這個(gè)對(duì)象集合或許是個(gè)容器,或許是容器的一部分。每一種容器都提供了自己的迭代器,而這些迭代器了解該種容器的內(nèi)部結(jié)構(gòu)。算法(Algorithms):用來(lái)處理對(duì)象集合中的元素,比如 Sort,Search,Copy,Erase 那些元素。通過(guò)迭代器的協(xié)助,我們只需撰寫一次算法,就可以將它應(yīng)用于任意容器之上,這是因?yàn)樗腥萜鞯牡鞫继峁┮恢碌慕涌凇?p>STL 的基本觀念就是將數(shù)據(jù)和操作分離。數(shù)據(jù)由容器進(jìn)行管理,操作則由算法進(jìn)行,而迭代器在兩者之間充當(dāng)粘合劑,使任何算法都可以和任何容器交互運(yùn)作。0x2 C++ STL常用容器為了應(yīng)付程序中的不同需求,STL 準(zhǔn)備了兩類共七種基本容器類型:
序列式容器(Sequence containers):此為可序群集,其中每個(gè)元素均有固定位置—取決于插入時(shí)機(jī)和地點(diǎn),和元素值無(wú)關(guān)。如果你以追加方式對(duì)一個(gè)群集插入六個(gè)元素,它們的排列次序?qū)⒑筒迦氪涡蛞恢隆TL提供了三個(gè)序列式容器:向量(vector)、雙端隊(duì)列(deque)、列表(list),此外你也可以把 string 和 array 當(dāng)做一種序列式容器。關(guān)聯(lián)式容器(Associative containers):此為已序群集,元素位置取決于特定的排序準(zhǔn)則以及元素值,和插入次序無(wú)關(guān)。如果你將六個(gè)元素置入這樣的群集中,它們的位置取決于元素值,和插入次序無(wú)關(guān)。STL提供了四個(gè)關(guān)聯(lián)式容器:集合(set)、多重集合(multiset)、映射(map)和多重映射(multimap)。對(duì)于容器,主要的操作有:容器的建立、插入元素、刪除元素、查詢、遍歷、計(jì)算元素個(gè)數(shù)、檢查元素是否為空、輸出容器包含的內(nèi)容。
0x3 vector一種序列式容器,事實(shí)上和數(shù)組差不多,但它比數(shù)組更優(yōu)越。一般來(lái)說(shuō)數(shù)組不能動(dòng)態(tài)拓展,因此在程序運(yùn)行的時(shí)候不是浪費(fèi)內(nèi)存,就是造成越界。而 vector 正好彌補(bǔ)了這個(gè)缺陷,當(dāng)內(nèi)存空間不夠時(shí),需要重新申請(qǐng)一塊足夠大的內(nèi)存并進(jìn)行內(nèi)存的拷貝。
0x31 特點(diǎn)擁有一段連續(xù)的內(nèi)存空間,因此它能非常好的支持隨機(jī)訪問(wèn),即 [] 操作符和 .at(),隨機(jī)訪問(wèn)快。(優(yōu)點(diǎn))當(dāng)向其頭部或中間插入或刪除元素時(shí),為了保持原本的相對(duì)次序,插入或刪除點(diǎn)之后的所有元素都必須移動(dòng),所以插入或刪除的效率比較低。(缺點(diǎn))在后面插入刪除元素最快,此時(shí)一般不需要移動(dòng)內(nèi)存。(優(yōu)點(diǎn))總結(jié):相當(dāng)于可拓展的數(shù)組(動(dòng)態(tài)數(shù)組),隨機(jī)訪問(wèn)快,在頭部和中間插入或刪除效率低,但在尾部插入或刪除效率高,適用于對(duì)象簡(jiǎn)單,變化較小,并且頻繁隨機(jī)訪問(wèn)的場(chǎng)景。
0x32 構(gòu)造函數(shù)vector():無(wú)參數(shù) - 構(gòu)造一個(gè)空的vectorvector(size_type num):數(shù)量(num) - 構(gòu)造一個(gè)大小為num,值為Type默認(rèn)值的Vectorvector(size_type num, const TYPE &val):數(shù)量(num)和值(val) - 構(gòu)造一個(gè)初始放入num個(gè)值為val的元素的Vectorvector(const vector &from):vector(from) - 構(gòu)造一個(gè)與vector from 相同的vectorvector(input_iterator start, input_iterator end):迭代器(start)和迭代器(end) - 構(gòu)造一個(gè)初始值為[start,end)區(qū)間元素的Vector(注:半開(kāi)區(qū)間).vector(initializer_list#include#include usingnamespacestd;intmain(){vector vecTemp;for(inti=0;i<6;i++){vecTemp.push_back(i);}for(inti=0;i Output
0123450x4 dequedeque是Double-Ended Queues(雙向隊(duì)列)的縮寫,是雙向開(kāi)口的連續(xù)內(nèi)存空間(動(dòng)態(tài)將多個(gè)連續(xù)空間通過(guò)指針數(shù)組接合在一起),隨時(shí)可以增加一段新的空間。deque 的最大任務(wù)就是在這些分段的連續(xù)空間上,維護(hù)其整體連續(xù)的假象,并提供隨機(jī)存取的接口。
0x41 特點(diǎn)一旦要在 deque 的頭部和尾部增加新空間,便配置一段定量連續(xù)空間,串在整個(gè) deque 的頭部或尾部,因此不論在頭部或尾部插入元素都十分迅速。 (優(yōu)點(diǎn))在中間部分安插元素則比較費(fèi)時(shí),因?yàn)楸仨氁苿?dòng)其它元素。(缺點(diǎn))deque 是 list 和 vector 的折中方案。兼有 list 的優(yōu)點(diǎn),也有 vector 隨機(jī)訪問(wèn)效率高的優(yōu)點(diǎn)。總結(jié):支持隨機(jī)訪問(wèn),但效率沒(méi)有 vector 高,在頭部和尾部插入或刪除效率高,但在中間插入或刪除效率低,適用于既要頻繁隨機(jī)訪問(wèn),又要關(guān)心兩端數(shù)據(jù)的插入與刪除的場(chǎng)景。
0x42 構(gòu)造函數(shù)dequequeT:queue采用模板類實(shí)現(xiàn),queue對(duì)象的默認(rèn)構(gòu)造形式deque queT(size):構(gòu)造大小為size的deque,其中值為T類型的默認(rèn)值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():返回最后一個(gè)元素front():返回第一個(gè)元素insert()pop_back(): 刪除尾部的元素pop_front(): 刪除頭部的元素push_back():在尾部加入一個(gè)元素push_front(): 在頭部加入一個(gè)元素at():訪問(wèn)指定位置元素operator[] (size_type n):重載[]操作符empty():判斷隊(duì)列是否為空size():返回隊(duì)列的大小0x44 example #include#include usingnamespacestd;intmain(){std::deque first;///默認(rèn)構(gòu)造形式std::deque second(5,200);///構(gòu)造大小為5的deque,其中值為200std::deque third(second.begin(),second.end());///迭代器構(gòu)造函數(shù)std::deque fourth(third);///拷貝構(gòu)造函數(shù)///迭代器構(gòu)造函數(shù)可用于復(fù)制數(shù)組intmyInts[]={19,20,21,22};std::deque fifth(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:192021220x5 listList 由雙向鏈表(doubly linked list)實(shí)現(xiàn)而成,元素存放在堆中,每個(gè)元素都是放在一塊內(nèi)存中。沒(méi)有空間預(yù)留習(xí)慣,所以每分配一個(gè)元素都會(huì)從內(nèi)存中分配,每刪除一個(gè)元素都會(huì)釋放它占用的內(nèi)存。
0x51 特點(diǎn)內(nèi)存空間可以是不連續(xù)的,通過(guò)指針來(lái)進(jìn)行數(shù)據(jù)的訪問(wèn),這個(gè)特點(diǎn)使得它的隨機(jī)存取變得非常沒(méi)有效率,因此它沒(méi)有提供 [] 操作符的重載。(缺點(diǎn))由于鏈表的特點(diǎn),在任意位置的插入和刪除效率都較高。(優(yōu)點(diǎn))只支持首尾兩個(gè)元素的直接存取,想獲取其他元素(訪問(wèn)時(shí)間一樣),則需要遍歷鏈表。(缺點(diǎn))總結(jié):不支持隨機(jī)訪問(wèn),在任意位置的插入和刪除效率都較高,適用于經(jīng)常進(jìn)行插入和刪除操作并且不經(jīng)常隨機(jī)訪問(wèn)的場(chǎ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())templatelist (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())list (const list& x)0x53 常用APIassign():給list賦值back():返回最后一個(gè)元素begin():返回指向第一個(gè)元素的迭代器clear():刪除所有元素empty():如果list是空的則返回trueend():返回末尾的迭代器erase():刪除一個(gè)元素front():返回第一個(gè)元素get_allocator():返回list的配置器insert():插入一個(gè)元素到list中max_size():返回list能容納的最大元素?cái)?shù)量merge():合并兩個(gè)listpop_back():刪除最后一個(gè)元素pop_front():刪除第一個(gè)元素push_back():在list的末尾添加一個(gè)元素push_front():在list的頭部添加一個(gè)元素rbegin():返回指向第一個(gè)元素的逆向迭代器remove():從list刪除元素remove_if():按指定條件刪除元素rend():指向list末尾的逆向迭代器resize():改變list的大小reverse():把list的元素倒轉(zhuǎn)size():返回list中的元素個(gè)數(shù)sort():給list排序splice():合并兩個(gè)listswap():交換兩個(gè)listunique():刪除list中重復(fù)的元素0x54 example #include#include usingnamespacestd;intmain(){list
listTemp;for(charc="a";c<="z";++c)listTemp.push_back(c);while(!listTemp.empty()){cout< Output
abcdefghijklmnopqrstuvwxyz0x6 setset(集合)顧名思義,就是數(shù)學(xué)上的集合,集合中以一種特定的順序保存唯一的元素。
0x61 特點(diǎn)使用紅黑樹實(shí)現(xiàn),其內(nèi)部元素依據(jù)其值自動(dòng)排序,每個(gè)元素值只能出現(xiàn)一次,不允許重復(fù)。每次插入值的時(shí)候,都需要調(diào)整紅黑樹,效率有一定影響。(缺點(diǎn))map 和 set 的插入或刪除效率比用其他序列容器高,因?yàn)閷?duì)于關(guān)聯(lián)容器來(lái)說(shuō),不需要做內(nèi)存拷貝和內(nèi)存移動(dòng)。(優(yōu)點(diǎn))總結(jié):由紅黑樹實(shí)現(xiàn),其內(nèi)部元素依據(jù)其值自動(dòng)排序,每個(gè)元素值只能出現(xiàn)一次,不允許重復(fù),且插入和刪除效率比用其他序列容器高,適用于經(jīng)常查找一個(gè)元素是否在某集合中且需要排序的場(chǎng)景。
0x62 構(gòu)造函數(shù)set():無(wú)參數(shù) - 構(gòu)造一個(gè)空的setset(InputIterator first, InputIterator last):迭代器的方式構(gòu)造setset(const set &from):copyd的方式構(gòu)造一個(gè)與set from 相同的setset(input_iterator start, input_iterator end):迭代器(start)和迭代器(end) - 構(gòu)造一個(gè)初始值為[start,end)區(qū)間元素的Vector(注:半開(kāi)區(qū)間).set (initializer_listil, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())C++11新提供的方法,類似如下方式:std::set a{1, 2, 3, 4, 5};0x63 常用APIbegin():返回指向第一個(gè)元素的迭代器clear():清除所有元素count():返回某個(gè)值元素的個(gè)數(shù)empty():如果集合為空,返回trueend():返回指向最后一個(gè)元素的迭代器equal_range():返回集合中與給定值相等的上下限的兩個(gè)迭代器erase():刪除集合中的元素find():返回一個(gè)指向被查找到元素的迭代器get_allocator():返回集合的分配器insert():在集合中插入元素lower_bound():返回指向大于(或等于)某值的第一個(gè)元素的迭代器key_comp():返回一個(gè)用于元素間值比較的函數(shù)max_size():返回集合能容納的元素的最大限值rbegin():返回指向集合中最后一個(gè)元素的反向迭代器rend():返回指向集合中第一個(gè)元素的反向迭代器size():集合中元素的數(shù)目swap():交換兩個(gè)集合變量upper_bound():返回大于某個(gè)值元素的迭代器value_comp():返回一個(gè)用于比較元素間的值的函數(shù)0x64 example #include#include usingnamespacestd;intmain(){set setTemp;setTemp.insert(3);setTemp.insert(1);setTemp.insert(2);setTemp.insert(1);for(intit:setTemp){cout< Output
123當(dāng) set 集合中的元素為結(jié)構(gòu)體時(shí),該結(jié)構(gòu)體必須實(shí)現(xiàn)運(yùn)算符 <的重載:
#include#include usingnamespacestd;structPeople{stringname;intage;booloperator<(constPeoplep)const{returnage setTemp;setTemp.insert({"天理",19});setTemp.insert({"天工",20});setTemp.insert({"天大",21});setTemp.insert({"南開(kāi)",18});set ::iteratorit;for(it=setTemp.begin();it!=setTemp.end();it++){printf("學(xué)校:%s就讀年齡:%d\n",(*it).name.c_str(),(*it).age);}return0;} Output
學(xué)校:南開(kāi)就讀年齡:18學(xué)校:天理就讀年齡:19學(xué)校:天工就讀年齡:20學(xué)校:天大就讀年齡:21可以看到結(jié)果是按照年齡由小到大的順序排列。另外 string 要使用c_str()轉(zhuǎn)換一下,否則打印出的是亂碼。
Multiset 和 set 相同,只不過(guò)它允許重復(fù)元素,也就是說(shuō) multiset 可包括多個(gè)數(shù)值相同的元素。這里不再做過(guò)多介紹。
0x7 mapmap 由紅黑樹實(shí)現(xiàn),其元素都是 “鍵值/實(shí)值” 所形成的一個(gè)對(duì)組(key/value pairs),map 內(nèi)部自建一顆紅黑樹,這顆樹具有對(duì)數(shù)據(jù)自動(dòng)排序的功能,所以在 map 內(nèi)部所有的數(shù)據(jù)都是有序的。
0x71 特點(diǎn)每個(gè)元素都有一個(gè)鍵,且只能出現(xiàn)一次,不允許重復(fù)。根據(jù) key 值快速查找記錄,查找的復(fù)雜度基本是 O(logN),如果有 1000 個(gè)記錄,二分查找最多查找 10次(1024)。(優(yōu)點(diǎn))每次插入值的時(shí)候,都需要調(diào)整紅黑樹,效率有一定影響。(缺點(diǎn))增加和刪除節(jié)點(diǎn)對(duì)迭代器的影響很小,除了那個(gè)操作節(jié)點(diǎn),對(duì)其他的節(jié)點(diǎn)都沒(méi)有什么影響。(優(yōu)點(diǎn))對(duì)于迭代器來(lái)說(shuō),可以修改實(shí)值,而不能修改 key。總結(jié):元素為鍵值對(duì),key 和 value 可以是任意你需要的類型,每個(gè)元素都有一個(gè)鍵,且只能出現(xiàn)一次,不允許重復(fù),根據(jù) key 快速查找記錄,適用于需要存儲(chǔ)一個(gè)數(shù)據(jù)字典,并要求方便地根據(jù)key找value的場(chǎng)景。
0x72 構(gòu)造函數(shù)map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())templatemap (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():返回特殊條目的迭代器對(duì)erase():刪除一個(gè)元素find():查找一個(gè)元素get_allocator():返回map的配置器insert():插入元素–key_comp():返回比較元素key的函數(shù)lower_bound():返回鍵值>=給定元素的第一個(gè)位置max_size():返回可以容納的最大元素個(gè)數(shù)rbegin():返回一個(gè)指向map尾部的逆向迭代器rend():返回一個(gè)指向map頭部的逆向迭代器size():返回map中元素的個(gè)數(shù)swap():交換兩個(gè)mapupper_bound():返回鍵值>給定元素的第一個(gè)位置value_comp():返回比較元素value的函數(shù)0x74 example #include#include Output
編號(hào):1崗位:后端碼匠編號(hào):2崗位:音視頻開(kāi)發(fā)編號(hào):3崗位:后端開(kāi)發(fā)編號(hào):4崗位:前端開(kāi)發(fā)multimap 和 map 相同,但允許重復(fù)元素,也就是說(shuō) multimap 可包含多個(gè)鍵值(key)相同的元素。這里不再做過(guò)多介紹。
0x8 容器配接器除了以上七個(gè)基本容器類別,為滿足特殊需求,STL還提供了一些特別的(并且預(yù)先定義好的)容器配接器,根據(jù)基本容器類別實(shí)現(xiàn)而成。包括:
0x81 stackstack(堆棧)實(shí)現(xiàn)了一個(gè)先進(jìn)后出(FILO)的數(shù)據(jù)結(jié)構(gòu)。
0x811 構(gòu)造函數(shù)stackstkT:采用模板類實(shí)現(xiàn),stack對(duì)象的默認(rèn)構(gòu)造形式stack(const stack &stk):拷貝構(gòu)造函數(shù)0x812 常用APIsize():返回棧中的元素?cái)?shù)top():返回棧頂?shù)脑豴op():從棧中取出并刪除元素push(x):向棧中添加元素xempty():在棧為空時(shí)返回true0x82 queue queue 容器對(duì)元素采取 FIFO(先進(jìn)先出)的管理策略。也就是說(shuō),它是個(gè)普通的緩沖區(qū)(buffer)。
0x821 構(gòu)造函數(shù)explicit queue (const container_type& ctnr)explicit queue (container_type&& ctnr = container_type())templateexplicit 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():返回最后一個(gè)元素empty():如果隊(duì)列空則返回真front():返回第一個(gè)元素pop():刪除第一個(gè)元素push():在末尾加入一個(gè)元素size():返回隊(duì)列中元素的個(gè)數(shù)0x83 priority_queue 優(yōu)先隊(duì)列類似隊(duì)列, 但是在這個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素按照一定的規(guī)則排列有序。在優(yōu)先隊(duì)列中,元素被賦予優(yōu)先級(jí)。當(dāng)訪問(wèn)元素時(shí),具有最高優(yōu)先級(jí)的元素最先刪除。優(yōu)先隊(duì)列具有最高優(yōu)先級(jí)先出 (first in, largest out)的行為特征。首先要包含頭文件#include, 他和queue不同的就在于我們可以自定義其中數(shù)據(jù)的優(yōu)先級(jí), 讓優(yōu)先級(jí)高的排在隊(duì)列前面,優(yōu)先出隊(duì)。優(yōu)先隊(duì)列具有隊(duì)列的所有特性,包括隊(duì)列的基本操作,只是在這基礎(chǔ)上添加了內(nèi)部的一個(gè)排序,它本質(zhì)是一個(gè)堆實(shí)現(xiàn)的。
0x831 構(gòu)造函數(shù)priority_queue
Type 就是數(shù)據(jù)類型,Container 就是容器類型(Container必須是具備隨機(jī)存取能力的容器,支持如下方法:empty(), size(), front(), push_back(),pop_back()。比如vector,deque等等,但不能用list。STL里面默認(rèn)用的是vector)??蛇xFunctional 就是比較的方式??蛇x0x832 常用APItop():訪問(wèn)隊(duì)頭元素empty():隊(duì)列是否為空size():返回隊(duì)列內(nèi)元素個(gè)數(shù)push():插入元素到隊(duì)尾 (并排序)emplace():原地構(gòu)造一個(gè)元素并插入隊(duì)列pop():彈出隊(duì)頭元素swap():交換內(nèi)容: 【音視頻】Android音頻開(kāi)發(fā)基本概念
【Android】NDK開(kāi)發(fā)Crash分析
【C++】PK游戲(玩轉(zhuǎn)多態(tài))
以上,便是今天的分享,希望大家喜歡,覺(jué)得內(nèi)容不錯(cuò)的,歡迎「分享」「贊」或者點(diǎn)擊「在看」支持,謝謝各位。
關(guān)鍵詞: 構(gòu)造函數(shù) 插入或刪除
相關(guān)閱讀
-
【C++】STL梳理
點(diǎn)擊關(guān)注,與你共同成長(zhǎng)!0x1C++STLC++STL(標(biāo)準(zhǔn)模板庫(kù))是一套功能... -
環(huán)球觀熱點(diǎn):【NDK】封裝日志庫(kù)
點(diǎn)擊關(guān)注,與你共同成長(zhǎng)!【NDK】封裝日志庫(kù)0x1需求供C++、Java調(diào)用... -
【Android】JNI靜態(tài)與動(dòng)態(tài)注冊(cè)介紹_環(huán)球看熱訊
點(diǎn)擊關(guān)注,與你共同成長(zhǎng)!【Android】JNI靜態(tài)與動(dòng)態(tài)注冊(cè)介紹JNI的兩... -
世界熱推薦:今晚7:00直播丨下一個(gè)突破...
今晚19:00,Cocos視頻號(hào)直播馬上點(diǎn)擊【預(yù)約】啦↓↓↓在運(yùn)營(yíng)了三年... -
NFT周刊|Magic Eden宣布支持Polygon網(wǎng)...
Block-986在NFT這樣的市場(chǎng),每周都會(huì)有相當(dāng)多項(xiàng)目起起伏伏。在過(guò)去... -
環(huán)球今亮點(diǎn)!頭條觀察 | DeFi的興衰與...
在比特幣得到機(jī)構(gòu)關(guān)注之后,許多財(cái)務(wù)專家預(yù)測(cè)世界將因?yàn)榧用茇泿诺?..