第十一章關聯容器
因翻譯太耗時了，還是看中文比較快，先做筆記如下
兩個主要的關聯容器:map和set
map表示：鍵-值對的集合
set表示：普通集合
如果是無序的，則加一個unordered.
如果允許重複，則加上一個multi
11.1 使用關聯容器
使用map
map<string,size_t> word_count;
string word;
while(cin >> word)
++word_count[word];
for(const auto &w:word_count)
cout << w.first << " occurs "<< w.second
<< ((w.second>1)?" times":" time") << endl;
說明：從标準輸入中，讀取到word中，然後從word_count中選擇這個單詞，并且加1.
如果word_count中沒有這個單詞，則建立這個單詞
輸入完成後，再把這些單詞的個數列印出來
word_count的成員為pair，它的first成員為，關鍵字。second成員為對應的值。
使用set
将上面一個例子，進行擴充，忽略“the”,“and”,"or"等單詞。可以使用set來儲存這些需要被忽略的單詞。
map<string,size_t> word_cout;
set<string> exclude = {"the","but","and","or","an","a","The","But","And","Or","An","A"};
string word;
while(cin >> word)
if(exclude.find(word) == exclude.end())
++word_cout[word];
11.2 關聯容器概述
11.2.1 定義關聯容器
建立關聯容器,可以使用預設構造函數,這樣會建立一個空的關聯容器;另外,也可以用一個關聯容器來建立另一個關聯容器;也可以使用值範圍來初始化關聯容器.
例子如下:
map<string,size_t> word_count;//空容器
set<string> exclude = {"the","but","and","or","an","a","The","But","And","Or","An","A"};
map<string,string> authors = {{"Joyce","James"},{"Austen","Jane"},{"Dickens","Charles"}};
11.2.2 關鍵字類型的要求
預設情況下,标準庫使用關鍵字類型的小于運算符來比較兩個關鍵字.是以,關鍵字的類型必須定義元素的比較方法.
既然有預設情況,也就有自定義的情況,此種情況下,使用自定義的操作來比較關鍵字的大小,而此時,我們自定義的操作必須遵循嚴格弱序.
嚴格弱序需要具備如下的性質:
- 兩個關鍵字不能同時小于等于對方;
- 如果k1小于等于k2,且k2小于等于k3,那麼k1一定要小于等于k3
- 如果存在兩個關鍵字,任何一個都不小于等于另外一個,那麼稱這兩個關鍵字是等價的.如果k1等價k2,且k2等價k3,那麼k1必須等價k3
例子如下:
首先定義一個可以用來比較的函數,當作自定義操作:
bool compareIsbn(const Sales_data &lhs,const Sales_data &rhs){
return lhs.isbn() < rhs.isbn();
}
接下來開始使用它:
decltype後面需要加上一個星号,表示函數指針,在構造的時候,将這個函數指針傳入.
這樣,bookStore就會使用自定義的操作,此處為compareIsbn函數,來進行比較操作.
即,booksotre中的元素将按他們的ISBN成員的值來排序.
11.2.3 pair類型
pair定義在utility頭檔案中
pair<string,string> anon;//儲存兩個string
pair<string,size_t> word_count;
pair<string,vector<int>> line;
pair的預設構造函數是對成員進行值初始化.是以,anon包含兩個空的string;word_count的sizt_t成員值為0.line的vector成員的值為空vector
pair的兩個成員,分别為first和second,他們是public的.
下面給出pair上面的操作
建立pair對象的函數
詳細用法見上圖
11.3關聯容器的操作
對于set類型來說,key_type和value_type是一樣的.
對于map來說,儲存的是pair對象,關鍵字為pair的first成員,值為pair的second成員.
set<string>::value_type v1;//string
set<string>::key_type v2;//string
map<string,int>::value_type v3;//pair<const stirng,int>
map<string,int>::key_type v4;//string
map<string,int>::mapped_type v5;//int
11.3.1 關聯容器疊代器
解引用一個關聯容器疊代器,會得到value_type,而map的value_type為一個pair對象.
//word_count是一個map容器
auto map_it = word_count.begin();
cout << map_it->first;
cout << " " << map_it->second;
map_it->first = "new key";//錯誤,關鍵字類型為const
++map_it->second;//正确
set的疊代器是const的
set容器中的關鍵字是const的.
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it = iset.begin();
if(set_it != iset.end()){
*set_it = 42;//錯誤
cout << *set_it << endl;//正确
}
關聯容器與算法
關聯容器的關鍵字的類型為const,是以,不能用于修改和重排容器元素的算法.
對于隻讀算法,需要搜尋序列.由于關聯容器中的元素不能通過他們的關鍵字進行快速查找,是以對其使用泛型搜尋算法幾乎總是壞主意.
在實際程式設計中,如果真要對一個關聯容器使用算法,要麼就是當做一個源序列,要麼當作一個目的位置.例如可以使用泛型copy算法将元素從一個關聯容器拷貝到另一個序列中.
11.3.2 添加元素
關聯容器的insert成員,向容器中添加一個元素或者一個元素範圍.由于map和set包含不重複的關鍵字,是以插入一個已經存在的元素對容器沒有任何影響.
vector<int> ivec = {2,4,6,8,2,4,6,8};
set<int> set2;
set2.insert(ivec.cbegin(),ivec.cend());//含有4個元素
set2.insert({1,3,5,7,1,3,5,7});//現在含有8個元素
向map中添加元素
注意,map的元素類型為pair
word_count.insert({word,1});
word_count.insert(make_pair(word,1)):
word_count.insert(pair<string,size_t>(word,1));
word_count.insert(map<string,size_t>::value_type(word,1));
下面給出關聯容器的插入操作
檢查insert的傳回值
insert(或者emplace)傳回值依賴于容器的類型和參數.
-
對于不重複的容器,插入操作傳回一個pair.pair的first成員是一個疊代器,指向具有給定關鍵字的元素;second成員是一個bool值,指出元素是插入成功,還是已經存在于容器中.
如果已經存在于容器中,插入操作什麼也不做,且傳回值的second成員為false.如果關鍵字不存在,元素被插入元素,此時second成員為true
- 對于可重複的容器,插入操作總會成功,傳回一個指向新元素的疊代器.無須傳回bool值,因為插入操作總會加入一個新的元素
11.3.3 删除元素
關聯容器定義了三個版本的erase,如下表:
可以傳遞給erase一個疊代器和一對疊代器,來删除一個元素,或者一個元素範圍.
關聯容器還提供一個額外的erase版本,它接收一個key_type參數.删除所有于給定關鍵字比對的元素.傳回實際删除的元素的數量.
if(word_count.erase(removal_word))
cout << "ok: " << removal_word << " removed\n";
else
cout << "oops: "<< removal_word << " not found!\n"
11.3.4 map的下标操作
map和unordered_map提供了下标和at成員的操作.如下圖:
multimap和unordered_multmap沒有提供下标操作.
map下标操作的傳回值類型為mapped_type.且為左值.
11.3.5 通路元素
在一個關聯容器中查找元素的操作,見下表:
當隻是想查找,而不想在沒有的情況下添加時,就不能使用下标運算符,應該使用find成員函數.
if(word_count.find("foobar") == word_count.end())
cout << "foobar is not in the map" << endl;
在multimap或者multiset中查找元素
string search_item("Alain de Button");//要查找的作者
auto entries = authors.count(search_item);//元素的數量
auto iter = authors.find(search_item);
while(entries){
cout << iter->second << endl;
++iter;
--entries;
}
還可以使用lower_bound和upper_bound來解決此問題.
這兩個成員接受一個關鍵字，然後傳回一個疊代器。如果關鍵字在容器中，lower_bound傳回的疊代器将指向第一個具有給定關鍵字的元素，而upper_bound傳回的疊代器則指向最後一個比對給定關鍵字的元素之後的位置。
如果元素不再容器中，則lower_bound和upper_bound傳回相等的疊代器，指向一個不影響排序的關鍵字插入位置。
注意：lower_bound傳回的疊代器可能指向一個具有給定關鍵字的位置，但也可能不指向。如果關鍵字不再容器中，則lower_bound傳回關鍵字的第一個安全出點
for(auto beg = authors.lower_bound(search_item),
end=authors.upper_bound(search_item);beg!=end;++beg)
cout << beg->second<<endl;
lower_bound的調用将beg定位到第一個與search_item比對的元素。如果容器中沒有這樣的元素，beg将指向第一個關鍵字大于search_item的元素，可能是尾後疊代器。
equal_range函數
equal_range接受一個關鍵字，傳回一個pair對象，first成員為一個疊代器，指向第一個關鍵字比對的元素。second成員指向最後一個比對的元素之後的位置。若未找到比對的元素，則兩個疊代器都指向關鍵字可以插入的位置。
for(auto pos = authors.equal_range(search_item);pos.first != pos.second;++pos.first){
cout << pos.first ->second << endl;
}
11.4 無序容器
四個無序容器：unordered_map,unordered_set,以及他們的可重複版本。
unordered_map<string,size_t> word_count;
string word;
while(cin >> word)
++word_count[word];
for(const auto &w:word_count)
cout << w.first << " occurs " << w.second
<< ((w.second >1)?" times":" time") <<endl;
管理桶
無序容器在存儲上組織為一組桶，每個桶儲存零個或多個元素。無序容器使用一個哈希函數将元素映射到桶。為了通路一個元素，容器首先計算元素的哈希值，他指出應該搜尋哪個桶。
容器将具有相同哈希值的所有元素都儲存在相同的桶中。如果容器允許重複關鍵字，所有具有相同關鍵字的元素都會在同一個桶中。是以，無序容器的性能依賴于哈希函數的品質和桶的數量和大小。
無序容器提供了一組管理桶的函數，如下表：
無序容器對關鍵字類型的要求
預設情況下，無序容器使用關鍵字類型的==運算符來比較運算，他們還使用一個hash<key_type>的對象來生成每個元素的哈希值。
标準庫為内置類型（包括指針）提供了hash模闆。還為一些标準庫類型，包括string和智能指針定義了hash。
是以，我們可以直接定義關鍵字是内置類型，指針類型，string和智能指針類型的無序容器。
不能直接定義關鍵字類型是自定義類型的無序容器。為了定義自定義類型的關鍵字，必須同時提供hash計算函數，和等于運算符。
size_t haser(const Sales_data &sd){
return hash<string>()(sd.isbn());
}
bool eqOp(const Sales_data &lhs,const Sales_data &rhs){
return lhs.isbn() == rhs.isbn();
}
using SD_multiset = unordered_multiset<Sales_data,decltype(hasher)*,decltype(eqOp)*>;
SD_multiset bookstore(42,hasher,eqOp);
如果定義了類的==運算符，則可以隻提供hash函數：
本章筆記完