c++中容器之總結(jié)篇
C++中的容器大致可以分為兩個(gè)大類:順序容器和關(guān)聯(lián)容器。順序容器中有包含有順序容器適配器。
順序容器:將單一類型元素聚集起來成為容器,然后根據(jù)位置來存儲和訪問這些元素。主要有vector、list、deque(雙端隊(duì)列)。順序容器適配器:stack、queue和priority_queue。
關(guān)聯(lián)容器:支持通過鍵來高效地查找和讀取元素。主要有:pair、set、map、multiset和multimap。
接下來依次對于各種容器做詳細(xì)的介紹。
一、順序容器
1、順序容器定義
為了定義一個(gè)容器類型的對象,必須先包含相關(guān)的頭文件:
定義vector:#include <vector>
定義list:#include <list>
定義deque:#include <deque>
定義示例
vector<int> vi; list<int> li; deque<int> di;
2、順序容器初始化
初始化示例:
//初始化為一個(gè)容器的副本 vector<int> vi; vector<int> vi2(vi); //利用vi來初始化vi2 //初始化為一段元素的副本 char*words[] = {"stately", "plump", "buck", "mulligan"}; size_twords_size = sizeof(words)/sizeof(char*); list<string> words2(words, words + words_size); //分配和初始化指定數(shù)目的元素 constlist<int>::size_type list_size = 64; list<string> slist(list_size, "a"); // 64 strings, each is a
3、順序容器支持的指針運(yùn)算
①所有順序都支持的指針運(yùn)行
②vector 和 deque 容器的迭代器提供額外的運(yùn)算
③迭代器失效:一些容器操作會修改容器的內(nèi)在狀態(tài)或移動容器內(nèi)的元素。這樣的操作使所有指向被移動的元素的迭代器失效,也可能同時(shí)使其他迭代器失效。使用無效迭代器是沒有定義的,可能會導(dǎo)致與懸垂指針相同的問題。
④begin和end成員:begin和end操作產(chǎn)生指向容器內(nèi)第一個(gè)元素和最后一個(gè)元素的下一位置的迭代器。
3、順序容器操作
①添加元素
添加元素示例:
//在容器首部或者尾部添加數(shù)據(jù) list<int> ilist; ilist.push_back(ix);//尾部添加 ilist.push_front(ix);//首部添加 //在容器中指定位置添加元素 list<string> lst; list<string>::iterator iter = lst.begin(); while (cin >> word) iter = lst.insert(iter, word); // 和push_front意義一樣 //插入一段元素 list<string> slist; string sarray[4] = {"quasi", "simba", "frollo", "scar"}; slist.insert(slist.end(), 10, "A");//尾部前添加十個(gè)元素都是A list<string>::iterator slist_iter = slist.begin(); slist.insert(slist_iter, sarray+2, sarray+4);//指針范圍添加
②容器大小的操作
示例:
list<int> ilist(10, 1); ilist.resize(15); // 尾部添加五個(gè)元素,值都為0 ilist.resize(25, -1); // 再在尾部添加十個(gè)元素,元素為-1 ilist.resize(5); // 從尾部刪除20個(gè)元素
③訪問元素
int vector<int> vi; for(int i=0;i<10;i++)vi.push_back(i); cout<<vi[0]<<endl; cout<<vi.at(0)<<endl; cout<<vi[10]<<endl; //越界錯(cuò)誤 cout<<vi.at(10)<<endl;//越界錯(cuò)誤
④刪除元素
示例:
//刪除第一個(gè)或最后一個(gè)元素 list<int> li; for(int i=0;i<10;i++)list.push_back(i); li.pop_front();//刪除第一個(gè)元素 li.pop_back(); //刪除最后一個(gè)元素 //刪除容器內(nèi)的一個(gè)元素 list<int>::iterator iter =li.begin(); if(iter!= li.end())li.erase(iter); //刪除容器內(nèi)所有元素 li.clear();
⑤賦值與swap
list<string> sl1,sl2; for(int i=0;i<10;i++)sl2.push_back("a"); sl1.assign(sl2.begin(),sl2.end());//用sl2的指針范圍賦值,sl1中十個(gè)元素都為a sl1.assign(10, "A"); //s1被重新賦值,擁有十個(gè)元素,都為A
swap示例:
vector<string> vs1(3); // vs1有3個(gè)元素
vector<string> vs(5); // vs2有5個(gè)元素
vs1.swap(vs2);//執(zhí)行后,vs1中5個(gè)元素,而vs2則存3個(gè)元素。
⑥vector的自增長:capacity 和 reserve 成員
為了提高vector的效率,不用每次添加元素都重新分配空間。vector會在分配空間時(shí)候預(yù)分配大于需要的空間。vector 類提供了兩個(gè)成員函數(shù):capacity 和reserve 使程序員可與 vector 容器內(nèi)存分配的實(shí)現(xiàn)部分交互工作。
capacity操作:獲取在容器需要分配更多的存儲空間之前能夠存儲的元素總數(shù)
reserve操作:告訴vector容器應(yīng)該預(yù)留多少個(gè)元素的存儲空間
capacity(容量)與size(長度)的區(qū)別:size指容器當(dāng)前擁有的元素個(gè)數(shù),而capacity則指容器在必須分配新存儲空間之前可以存儲的元素總數(shù)。capacity是比size大的一般情況下。
示例:
vector<int> ivec; cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;//都為0 for (vector<int>::size_type ix = 0; ix != 24; ++ix)ivec.push_back(ix); cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;//capacity大于size
可以通過函數(shù)reserve()來操作預(yù)留空間
//在之前一段代碼的基礎(chǔ)上
ivec.reserve(ivec.capacity()+50);//為ivec增加了50的預(yù)留空間
另外:如果不手動操作來預(yù)留空間,每當(dāng) vector 容器不得不分配新的存儲空間時(shí),以加倍當(dāng)前容量的分配策略實(shí)現(xiàn)重新分配。
4、容器的選用
選擇容器類型的常規(guī)法則:
①如果程序要求隨機(jī)訪問元素,則應(yīng)使用 vector 或 deque 容器。
②如果程序必須在容器的中間位置插入或刪除元素,則應(yīng)采用 list 容器。
③如果程序不是在容器的中間位置,而是在容器首部或尾部插入或刪除元素,則應(yīng)采用 deque 容器。
④如果只需在讀取輸入時(shí)在容器的中間位置插入元素,然后需要隨機(jī)訪問元素,則可考慮在輸入時(shí)將元素讀入到一個(gè) list 容器,接著對此容器重新排序,使其適合順序訪問,然后將排序后的 list 容器復(fù)制到一個(gè) vector容器。
如果程序既需要隨機(jī)訪問又必須在容器的中間位置插入或刪除元素,選擇何種容器取決于下面兩種操作付出的相對代價(jià):隨機(jī)訪問 list 容器元素的代價(jià),以及在 vector 或 deque 容器中插入/刪除元素時(shí)復(fù)制元素的代價(jià)。通常來說,應(yīng)用中占優(yōu)勢的操作(程序中更多使用的是訪問操作還是插入/刪除操作)將決定應(yīng)該什么類型的容器。
5、容器適配器
①適配器通用的操作和類型
②適配器的初始化
所有適配器都定義了兩個(gè)構(gòu)造函數(shù):默認(rèn)構(gòu)造函數(shù)用于創(chuàng)建空對象,而帶一個(gè)容器參數(shù)的構(gòu)造函數(shù)將參數(shù)容器的副本作為其基礎(chǔ)值。
默認(rèn)的stack和queue都基于deque容器實(shí)現(xiàn),而priority_queue則在vector容器上實(shí)現(xiàn)。
示例:
vector<int> vi; deque<int> deq; stack<int> stk(deq); //用deq初始化stk stack<int> stk1(vi); //報(bào)錯(cuò)
③適配器的操作
棧適配器:
隊(duì)列和優(yōu)先級隊(duì)列:
二、關(guān)聯(lián)容器
1、pair
①pairs類型提供的操作
②pairs類型定義和初始化
pair<string, string> test("A", "B");
③pairs其他操作
//pairs對象的操作 string firstBook; if (author.first == "James" && author.second == "Joyce")firstBook = "Stephen Hero"; //生成新的pair對象 pair<string, string> next_auth; next_auth = make_pair("A","B");//第一種方法 next_auth = pair<string, string>("A","B"); //第二種方法 cin>>next_auth.first>>next_auth.second;//第三種方法
2、map
map 是鍵-值對的集合。map 類型通??衫斫鉃殛P(guān)聯(lián)數(shù)組:可使用鍵作為下標(biāo)來獲取一個(gè)值,正如內(nèi)置數(shù)組類型一樣。而關(guān)聯(lián)的本質(zhì)在于元素的值與某個(gè)特定的鍵相關(guān)聯(lián),而并非通過元素在數(shù)組中的位置來獲取。
①map對象的定義
map<string, int> word_count;
這個(gè)語句定義了一個(gè)名為 word_count 的 map 對象,由 string 類型的鍵索引,關(guān)聯(lián)的值則int型。
map訪問:對迭代器進(jìn)行解引用時(shí),將獲得一個(gè)引用,指向容器中一個(gè)pair<const string,int>類
型的值。通過pair類型的訪問方式進(jìn)行訪問。
②map的構(gòu)造函數(shù)
③鍵類型的約束
在使用關(guān)聯(lián)容器時(shí),它的鍵不但有一個(gè)類型,而且還有一個(gè)相關(guān)的比較函數(shù)。所用的比較函數(shù)必須在鍵類型上定義嚴(yán)格弱排序(strict weak ordering):可理解為鍵類型數(shù)據(jù)上的“小于”關(guān)系,雖然實(shí)際上可以選擇將比較函數(shù)設(shè)計(jì)得更復(fù)雜。
對于鍵類型,唯一的約束就是必須支持 < 操作符,至于是否支持其他的關(guān)系或相等運(yùn)算,則不作要求。
④map類定義的類型
value_type是存儲元素的鍵以及值的pair類型,而且鍵為const。例如,word_count 數(shù)組的value_type 為pair<const string,int> 類型。value_type 是 pair 類型,它的值成員可以修改,但鍵成員不能修改。
⑤map添加元素
添加元素有兩種方法:1、先用下標(biāo)操作符獲取元素,然后給獲取的元素賦值 2、使用insert成員函數(shù)實(shí)現(xiàn)
下標(biāo)操作添加元素:如果該鍵已在容器中,則 map 的下標(biāo)運(yùn)算與 vector 的下標(biāo)運(yùn)算行為相同:返回該鍵所關(guān)聯(lián)的值。只有在所查找的鍵不存在時(shí),map 容器才為該鍵創(chuàng)建一個(gè)新的元素,并將它插入到此 map 對象中。此時(shí),所關(guān)聯(lián)的值采用值初始化:類類型的元素用默認(rèn)構(gòu)造函數(shù)初始化,而內(nèi)置類型的元素初始化為 0。
insert 操作:
示例:
word_count.insert(map<string, int>::value_type("Anna", 1)); word_count.insert(make_pair("Anna", 1));
insert的返回值:包含一個(gè)迭代器和一個(gè)bool值的pair對象,其中迭代器指向map中具有相應(yīng)鍵的元素,而bool值則表示是否插入了該元素。如果該鍵已在容器中,則其關(guān)聯(lián)的值保持不變,返回的bool值為true。在這兩種情況下,迭代器都將指向具有給定鍵的元素。
pair<map<string, int>::iterator, bool> ret =
word_count.insert(make_pair(word, 1));
ret存儲insert函數(shù)返回的pair對象。該pair的first成員是一個(gè)map迭代器,指向插入的鍵。ret.first從insert返回的pair對象中獲取 map 迭代器;ret.second從insert返回是否插入了該元素。
⑥查找并讀取map中的元素
map中使用下標(biāo)存在一個(gè)很危險(xiǎn)的副作用:如果該鍵不在 map 容器中,那么下標(biāo)操作會插入一個(gè)具有該鍵的新元素。所以map 容器提供了兩個(gè)操作:count 和 find,用于檢查某個(gè)鍵是否存在而不會插入該鍵。
int occurs = 0; if (word_count.count("foobar"))occurs = word_count["foobar"]; map<string,int>::iterator it = word_count.find("foobar"); if (it != word_count.end())occurs = it->second;
⑦從map對象中刪除元素
string removal_word = "a"; if (word_count.erase(removal_word)) cout << "ok: " << removal_word << " removed\n"; else cout << "oops: " << removal_word << " not found!\n";
3、set
①set容器的定義和使用
set 容器的每個(gè)鍵都只能對應(yīng)一個(gè)元素。以一段范圍的元素初始化set對象,或在set對象中插入一組元素時(shí),對于每個(gè)鍵,事實(shí)上都只添加了一個(gè)元素。
vector<int> ivec; for (vector<int>::size_type i = 0; i != 10; ++i) { ivec.push_back(i); ivec.push_back(i); } set<int> iset(ivec.begin(), ivec.end()); cout << ivec.size() << endl; //20個(gè) cout << iset.size() << endl; // 10個(gè)
②在set中添加元素
set<string> set1; set1.insert("the"); //第一種方法:直接添加 set<int> iset2; iset2.insert(ivec.begin(), ivec.end());//第二中方法:通過指針迭代器
③從set中獲取元素
set 容器不提供下標(biāo)操作符。為了通過鍵從 set 中獲取元素,可使用 find運(yùn)算。如果只需簡單地判斷某個(gè)元素是否存在,同樣可以使用 count 運(yùn)算,返回 set 中該鍵對應(yīng)的元素個(gè)數(shù)。當(dāng)然,對于 set 容器,count 的返回值只能是1(該元素存在)或 0(該元素不存在)
set<int> iset; 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
3、multimap 和 multiset
關(guān)聯(lián)容器 map 和 set 的元素是按順序存儲的。而 multimap 和multset 也一樣。因此,在multimap和multiset容器中,如果某個(gè)鍵對應(yīng)多個(gè)實(shí)例,則這些實(shí)例在容器中將相鄰存放。迭代遍歷multimap或multiset容器時(shí),可保證依次返回特定鍵所關(guān)聯(lián)的所有元素。
①迭代器的關(guān)聯(lián)容器操作
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助。
相關(guān)文章
Qt連接MySQL數(shù)據(jù)庫的實(shí)現(xiàn)(保姆級成功版教程)
本文主要介紹了Qt連接MySQL數(shù)據(jù)庫的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06淺談#ifndef,#define,#endif的作用和用法
下面小編就為大家?guī)硪黄獪\談#ifndef,#define,#endif的作用和用法。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-12-12C語言數(shù)據(jù)結(jié)構(gòu)線性表教程示例詳解
這篇文章主要為大家介紹了C語言數(shù)據(jù)結(jié)構(gòu)線性表的示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-02-02C語言數(shù)據(jù)結(jié)構(gòu)不掛科指南之棧&隊(duì)列&數(shù)組詳解
自考重點(diǎn)、期末考試必過指南,這篇文章讓你理解什么是棧、什么是隊(duì)列、什么是數(shù)組。文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2022-09-09C語言SetConsoleCursorPosition函數(shù)使用方法
這篇文章介紹了C語言SetConsoleCursorPosition函數(shù)的使用方法,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12Cocos2d-x學(xué)習(xí)筆記之Hello World!
這篇文章主要介紹了Cocos2d-x學(xué)習(xí)筆記之Hello World!本文基于vs2010和C++語言開發(fā),需要的朋友可以參考下2014-09-09