C++自修入門實境秀、C++ Primer 5版研讀秀 72/ ~ v11關聯式容器~11.3.1. Associative Containe...





串列初始化回傳值

串列初始化(list initialize,動詞 ⑦先抓動詞 )回傳的值

已經被串列初始化的回傳值

將回傳的值串列初始化 4:28:20

回傳一個串列初始化(list initialization)的值

第72集3:36:00

vector<string> process()

{

// ...

// expected 和 actual都是string

if (expected.empty())

return {}; // 回傳一個空的 vector

else if (expected == actual)

return {"functionXn, " okay”}; // 回傳串列初始化的 vector

else

return {"functionX", expected, actual};

}





因為串列初始化(list initialization)通常是來初始化陣列或container(ex. vector),所以我們可以定義一個回傳值型別為vector的函式→應該說,我們可以回傳一個回傳型別業經串列初始化(list initialization)的值



練習11.7

第72集 5:27:10擴編此程式





為鍵值型別使用一個比較函式

The type of the operation that a container uses to organize its elements is part of the type of that container.

一個容器用來組織它元素所用上的運算,其所屬的型別,也是這個容器型別構成的一部分

可以用一個進行比較運算的函式(Comparison Function,如compareIsbn function)來定義、建構一個關聯式容器。

For example, we can’t directly define a multiset of Sales_data because Sales_data doesn’t have a < operator. However, we can use the compareIsbn function from the exercises in § 10.3.1 (p. 387) to define a multiset. That function defines a strict weak ordering based on their ISBNs of two given Sales_data objects.

只要函式定義了某型別嚴格的大小次序(strict weak ordering),就能用來作為建構關聯式容器的引數。第72集6:40

頁426

在定義關聯式容器multiset時,要用自訂的運算來取代預設的,就必須同時提供兩個型別作為建構用的引數:一個為其原來的鍵值型別(key type),一為比較運算用的型別(comparison type)。(因為默認的運算,只須一個鍵值型別即可建構multiset)

比較運算用的型別comparison type,是一個函式指標(function pointer)的型別,它是用來指向我們要用來替代預設比較運算用的函式的:

comparison type, which is a function pointer type (§ 6.7, p. 247) that can point to compareIsbn. When we define objects of this type, we supply a pointer to the operation we intend to use. In this case, we supply a pointer to compareIsbn:

第72集11:00





∵ 要定義一個關聯式容器須提供建構其容器的型別引數,蓋一個關聯式容器是由的元素型別,如陣列大小為陣列型別之一部分,關聯式容器的元素型別也是它型別的一部分,我們必須為它們提供適當的型別作為其元素的型別,以構成其容器型別。

∴ 因為函式本身不是型別,要把它作為型別來定義容器,就必須使用函式指標(function pointer),這才是型別,應即是指標此一複合型別(compound type):

the comparison type, which is a function pointer type (§ 6.7 , p. 247 ) that can point to compareIsbn .

multiset<Sales_data, decltype(compareIsbn) *> bookstore(compareIsbn);



複習前面的函式指標(function pointer)

第72集25:00

可見在定義multiset這種容器時,必須提供想使用計算的型別是指標型別,而不是函式型別。因為decltype(compareIsbn)傳回來的是函式型別(function type),而不是函式指標(function pointer)型別,所以才要再後端再加上「*」以表我們要取用的是函式指標,而不是函式型別。



我們可以寫出compareIsbn而非&compareIsbn作為建構器引數,因為使用 —個函式的名稱時,如果需要,它會自動被轉換為一個指標(§6.7,頁248)。我們也可以寫成 &compareIsbn,效果相同。

&在此為取址運算子,「&compareIsbn」即以函式指標型別來傳遞compareIsbn此函式。





練習11.11

6:53:24

32:30

函式被當作指標來傳遞

因此在建構一個multiset時,提供替代的運算函式,在被當作引數傳遞給其建構器(constructor)的時候,就只是指標,而不是函式來傳遞。故須提供一個函式指標,而不是函式型別。然函式在被當作引數傳遞時,默認的情況下就是被直接轉成指標來傳遞的。

39:45

1:34:00

#include<iostream>

#include<vector>

#include<set>

#include"Sales_data.h"

using namespace std;

int main() {

Sales_data s; vector<Sales_data>v;

while (read(cin, s))

{

v.push_back(s);

}



// bookstore 可能會有數筆交易記錄有相同的ISBN

// bookstore 中的元素會以ISBN排序

multiset<Sales_data, decltype(compareIsbn)*>

bookstore(v.cbegin(),v.cend(),compareIsbn);



typedef decltype(compareIsbn)* compIsbn;//頁249

multiset<Sales_data, compIsbn>

bookstore_typedef_decltype(v.cbegin(),v.cend(),compareIsbn);



using compISbn=bool(*)(const Sales_data& ,const Sales_data&) ;//頁249

multiset<Sales_data, compISbn>

bookstore_using(v.cbegin(),v.cend(),compareIsbn);



typedef bool(*compISBn)(const Sales_data&, const Sales_data&) ; //和一般typedef的寫法不同。函式指標的別名得寫在「*」後,不能寫在參數列(parameter list)後(即整個原型別名稱的後端)

multiset<Sales_data, compISBn>

bookstore_typedef(v.cbegin(),v.cend(),compareIsbn);



multiset<Sales_data, bool(*)(const Sales_data&, const Sales_data&)>//頁249

bookstore_PF(v.cbegin(),v.cend(),compareIsbn);



for (Sales_data s : bookstore_using)//以上5種(bookstore……bookstore_PF)全對了

{

print(cout, s); cout << endl;

}

}



原型別名稱完整的就是:

bool(*)(const Sales_data&, const Sales_data&)

函式名稱並非型別的一部分。

Sales_data.cpp

bool compareIsbn(const Sales_data& Lsd, const Sales_data& Rsd)

{//不能用inline

return Lsd.isbn()<Rsd.isbn();

}



Sales_data.h

bool compareIsbn(const Sales_data&, const Sales_data&);//不能用inline



copy(v.cbegin(), v.cend(), back_inserter(bookstore));

Severity Code Description

Error C2039 'push_back': is not a member of 'std::multiset<Sales_data,bool (__cdecl *)(const Sales_data &,const Sales_data &),std::allocator<_Ty>>' with [ _Ty=Sales_data ]

因為multiset沒有push_back成員函式,所以只能用它的建構器(constructor)來初始化(第一次增加元素,後面要再增減元素,就要讀第3節:11.3. Operations on Associative Containers。容器的運算,就包括容器內元素的增減等)



11.2.3. The pair Type

對組型別

對組的型別要求

對組型別的必要條件

和前面11.2.2. Requirements on Key Type遙相呼應,只是作文上換句話說而已

the library type named pair , which is defined in the utility header.

對組此一程式庫型別儲存、有著、包含hold了一對資料成員,也和容器(container)一樣,對組(pair)也是一個模板(template,MS Word叫「範本」),我們可以由它來產生一個特定的對組型別(看我們想產生出哪一種對組型別)

A pair holds two data members. Like the containers, pair is a template from which we generate specific types.

We must supply two type names when we create a pair .

The data members of the pair have the corresponding types. There is no requirement that the two types be the same:

pair的資料成員會有對應的型別。並沒有限制兩個型別要相同:

要建構一種對組型別,我們必須同時指定二個型別名稱,用來給其二個資料成員(data member)用。這兩個型別要有對應的關係,但不必是完全相同的型別。

這兩個資料成員前一個是鍵值,後一個是值

鍵值與值對組(key-value pairs)

鍵值與值的型別關係有點像表哥原理

頁427

pair類別的預設建構器(default constructor)會將其二個資料成員(data member)作值的初始化

課本所舉3例皆未提供建構器,故是默認使用預設建構器,而pair的預設建構器是以值初始化(value initialize)來初始化鍵值與值此二個(一對組)資料成員的

除了用預設建構器來值初始化pair中的二個成員,也可以自訂初始器給它們

pair<string, string> author{"James", "Joyce"};

前面好像也學過是要用大括弧的串列初始化(list initialization)

不像其他程式庫型別(library type)對組的成員都是公開的public

These members are named first and second, respectively. We access these members using the normal member access notation (§ 1.5.2, p. 23),

成員存取記號

成員存取運算子、點運算子

程式碼定義關於對組pair型別的運算很有限,列見表11.2:

Table 11.2. Operations on pairs



表11.2 : pair上的運算

pair<T1, T2> p; p是一個pair,具有型別分別是T1和T2,並以值初始 化(§3.3.1)的成員。

pair<Tl, T2> p(v1,v2) ; p是一個pair,具有型別T1和T2 ;而first和second 成員則分別以vl和v2初始化。

pair<T1, T2> p = {vl, v2}; 等同於 p(vl, v2)。

make_pair(v1, v2) 回傳以v1和v2初始化的一個pair。這個pair的型別會從v1和 v2的型別推論而出。

p.first 回傳p名為first的(public )資料成員。

p.second 回傳p名為second的(public)資料成員。

p1 relop p2

relop 意為 關係運算子(relational operator) 關係運算子(<、>、<=、>=)。關係運算子被定義為字典順序:舉例來說,如果 p1.first < p2.first 或!(p2.first < p1.first) && p1.second < p2.second,那 p1 < p2 就為 true。使用元素 的<運算子。

p1 == p2

p1 !=p2 如果它們的first及second成員都分別相等,那麼兩個pair就相等。使用元素的==運算子。

3:21:00



A Function to Create pair Objects

用來創建pair物件的一個函式

會/能夠產生/創建/建構pair型別物件的函式

make_pair(v1, v2)

3:24:00

串列初始化(list initialization)回傳值(頁226,List Initializing the Return Value)

頁428

pair<string, int>

process(vector<string> &v)

{

// process v

if (!v.empty())

return {v.back(), v.back().size()}; // list initialize

else

return pair<string, int>(); // explicitly constructed return

value

}

參見List Initializing the Return Value所舉例,此不過多了vector<string> &v非空的參數列,而pair<string, int>是回傳型別,process是函式名稱。

pair<string, int>() ()是呼叫運算子(call operator),此是呼叫pair的建構器,所以叫「explicitly constructed return:回傳明確→具體、實經、具實建構後的pair」

這個例子是說:要嘛用預設建構器(default constructor)建構一個空的pair來回傳,要嘛串列初始化(list initialization)回傳值型別(此為pair型別)

這裡用composed就是initialized:

If v isn’t empty, we return a pair composed of the last string in v and the size of that string. Otherwise, we explicitly construct and return an empty pair.

4:4:10

we could have used make_pair to generate a new pair of the appropriate type from its two arguments:

標題作「Create」A Function to Create pair Objects,這裡作「generate」

練習11.12

4:7:30

可見pair只是型別,並不是關聯式容器專用的型別,循序容器也能用,如此地是vector



5:18:00

#include<iostream>

#include<vector>

//#include<utility>//pair雖定義在此標頭中,但卻不必include就能用,如copy演算法等亦然

using namespace std;

pair<string, int>return_pair(vector<pair<string, int>>::const_iterator iter) {

return {iter->first,iter->second};

}

int main() {

vector<pair<string,int>>v;

vector<pair<string,int>>v1;

vector<pair<string,int>>v2;

vector<pair<string,int>>v3;

//istream_iterator<string>in(cin), end;

//while (in!=end) {

string w;int i;

vector<pair<string, int>>::const_iterator v1iter;

size_t vNo = 0;

while(cin>>w){

if (cin >> i) {

pair<string, int>pr(w, i);//v建構器初始化

v.push_back(pr);

pair<string, int>prLI = {w, i };//v1串列初始化(list initialization)

v1.push_back(prLI);

v1iter = v1.cbegin();//因為插入元素後原迭代器會失效,所以每次都要重取第一元素的迭代器

v2.push_back(return_pair(v1iter+vNo)); ++vNo;//v2最複雜,由函式傳回值來初始化

v3.push_back(make_pair(w, i));//v3此式最簡單而直觀!

}

}

vNo=0;

vector<pair<string, int>> a[4] = { v,v1,v2,v3 };

for(vector<pair<string, int>> v:a){

cout << vNo++ << ":" << endl;

for (pair<string,int>p:v)

{

cout<< p.first; cout << ":"

<<p.second << endl;

}

cout << "---------" << endl;

}

}



練習11.13

已見前一題。

練習11.14

參見練習11.7

#include<iostream>

#include<iterator>

#include<vector>

#include<map>

using namespace std;

int main() {

map<string, vector<pair<string,string>>> m;

//test text:

//Wells Oscar Wells joy Sun Oscar Washington Smith Sun June Wells Steve Washington Jack Sun Judy

//multimap<string, vector<string>> m;

istream_iterator<string>in(cin), end;

string lastName,firstname;

while (in!=end)

{

lastName = *in;

firstname=*++in;

m[lastName].push_back(make_pair(firstname, *++in));

++in;

}

ostream_iterator<string>out(cout,",");

for (auto a :m)

{

cout << a.first << ":";

for (pair<string,string> s : a.second)

{

*out++ = s.first;

*out++ = s.second;

cout << "、";

}

cout << endl;

cout <<"----------------"<< endl;

}

}

5:52:50 5:59:55

11.3. Operations on Associative Containers

關聯式容器也都支援Table 9.2. Container Operations的運算

除了這些運算,關聯式容器還定義了表11.3的型別,這些型別其實就是容器元素值的型別(鍵值和值)

頁429

Table 11.3. Associative Container Additional Type Aliases

表11.3 :關聯式容器額外的型別別名

key_type 這個容器型別的鍵值之型別

mapped_type 與每個鍵值關聯的型別;僅限map。即「值」的型別。

value_type 對 set 來說,等同於 key_type ;對 map 而言是 pair<const key_type, mapped_type>



6:14:40

6:6:50

因為關聯式容器的元素鍵值是無法改變的,所以pair中的鍵值就是const的:

Because we cannot change an element’s key, the key part of these pair s is const :

和循序容器(sequential container)一樣,是用範疇運算子來提取fetch其型別成員(type member)

11.3.1. Associative Container Iterators



當我們解參考(dereference)關聯式容器的迭代器時,是傳回value_type的值。對map而言,傳回的此型別是pair型別。

++map_it->second; // ok :我們可以透過一個迭代器變更這個值

此例並無變更,只有讀取。

要記得的重點是,一個map的value_type是pair,而我們能夠改變那個pair的值,但不能改變其鍵值成員。

pair的值指「鍵值」的另一個資料成員(data member)「值」。6:34:00不能完全照原文翻嘛!

we can change the value but not the key member of that pair.

英文原文乃是涉後文省略

we can change the value member of but not the key member of that pair.

Iterators for sets Are const

就如同我們不能改動map中元素的鍵值部分,因為鍵值就是值,所以一個set的鍵值也不能再被改動。

6:39:00即使set定義了const與nonconst的迭代器,但對於元素值仍只提供的唯讀存取權限。

頁430

Iterating across an Associative Container

Iterating across就是iterator advances就是traverse通過pass through

跨越一個關聯式容器的迭代

→翻成「迭代一個關聯式容器」或「關聯式容器的迭代」還差不多

不應當翻成「跨越」。中文跨越會有「跨出」之含意,這樣翻會以為這個迭代是會超出一個關聯式容器的!

set、map都支援Table 9.2. Container Operations所有的運算

6:55:00發現Ctrl+win+O螢幕小鍵盤

6:59:40

用map、multimap、set或multiset的迭代器來考索(查考、考察,檢索)其內的元素,會是照遞增鍵值的方式來呈現的。

Associative Containers and Algorithms

7:10:10

關聯式容器與演算法

通常是不會對關聯式容器使用泛用演算法(algorithm)

鍵值是唯讀的屬性就限制了我們無法在關聯式容器上套用那些會更動元素值與位置的演算法

因為迭代器是演算法必備的條件,怎樣的迭代器決定了可用上哪些的演算法,或決定了演算法可以怎樣運用一個容器對象。

7:17:10

Because elements in an associative container can be found (quickly) by their key,

因為一個關聯式容器中的元素能藉由它們的鍵值(快速)找到,使用泛用的捜尋演算法幾乎一定會是壞主意。

→是非常不智的抉擇/選擇/策略/辦法。

可見此key也類似Access資料庫中的索引index,所以能加速搜尋

關聯式容器定義了一個find成員函式(方法)

7:25:30

We could use the generic find algorithm to look for an element, but that algorithm does a sequential search.

我們會用泛用的find演算法來捜尋一個元素,但這種演算法做的是循序捜尋。

sequential search就是挨家挨戶地查訪

這裡could應翻成「可以」或「也可以」「也會」因為承前文而來,「也」這裡不能省,不能單提一個「會」字。

關聯式容器和演算法配合的常態是作為演算法的來源序列或目標容器對象

頁431

練習11.15

7:27:40

一個 int 對 vector<int> 的 map 中,mapped_type、key_type 與 value_type分別是什麼?

翻成「一個 int 對 vector<int> 的 map 中」這樣誰看得懂?

value_type 九陽神功 連這裡也用得上!value_type還不如取成「element_type」

⑧找對主詞 誰的value? 誰的? 關聯式容器的元素值,不是關聯式容器的元素它的值

所以在map中元素型別為pair,當然元素值的型別就是value_type,當然也就是pair;在這裡就是pair<int,vector<int>>

mapped_type,被映射(mapped)的,就是pair中的「值」資料成員(data member)的型別,這裡就是vector<int>

key_type就是pair中的「鍵值」資料成員的型別,這裡就是int

7:40:30

練習11.16

#include<iostream>

#include<iterator>

#include<map>

using namespace std;

int main() {

map<string, string> m;m["孫"]= "守真" ;

map<string, string>::iterator map_it=m.begin();

ostream_iterator<string>out(cout);

*out = map_it->first;

*out++ = map_it->second; cout << endl;

map_it->second = "任真";

*out = map_it->first;

*out++ = map_it->second; cout << endl;

}

7:51:20

練習11.17

#include<iostream>

#include<iterator>

#include<vector>

#include<set>

using namespace std;

int main() {

multiset<string> c ;

istream_iterator<string>in(cin),end;

ostream_iterator<string>out(cout, ",");

copy(in, end, inserter(c, c.end()));

vector<string>v;

copy(in, end, inserter(v, v.end()));

copy(c.cbegin(), c.cend(), out); cout << endl;

//copy(v.begin(), v.end(), inserter(c, c.end()));//OK

//copy(v.begin(), v.end(), back_inserter(c));//Error C2039 'push_back': is not a member of 'std::multiset<std::string,std::less<_Kty>,std::allocator<_Kty>>'

//copy(c.begin(), c.end(), inserter(v, v.end()));//OK

copy(c.begin(), c.end(), back_inserter(v));//OK,與前式同。因vector有push_back()也

copy(c.cbegin(), c.cend(), out);

cout << '\n' << "----------" << endl;

copy(v.cbegin(), v.cend(), out); cout << endl;

}

8:18:40

練習11.18

#include<iostream>

#include<iterator>

#include<map>

using namespace std;

int main() {

// get an iterator positioned on the first element

map<string, unsigned>word_count;

istream_iterator<string>in(cin), end;

while (in != end) ++word_count[*++in] ;

map<string, unsigned>::const_iterator map_it = word_count.cbegin();

// compare the current iterator to the off-the-end iterator

while (map_it != word_count.cend()) {

// dereference the iterator to print the element key--value pairs

cout << map_it->first << " occurs "

<< map_it->second << " times" << endl;

++map_it; // increment the iterator to denote the next element

}

}

8:40:00

練習11.19

參見練習11.11

8:51:00

#include<iostream>

#include<vector>

#include<set>

#include"Sales_data.h"

using namespace std;

int main() {

Sales_data s; vector<Sales_data>v;

while (read(cin, s))

{

v.push_back(s);

}



// bookstore 可能會有數筆交易記錄有相同的ISBN

// bookstore 中的元素會以ISBN排序

multiset<Sales_data, decltype(compareIsbn)*>

bookstore(v.cbegin(),v.cend(),compareIsbn);



typedef decltype(compareIsbn)* compIsbn;//頁249

multiset<Sales_data, compIsbn>

bookstore_typedef_decltype(v.cbegin(),v.cend(),compareIsbn);



using compISbn=bool(*)(const Sales_data& ,const Sales_data&) ;//頁249

multiset<Sales_data, compISbn>

bookstore_using(v.cbegin(),v.cend(),compareIsbn);



typedef bool(*compISBn)(const Sales_data&, const Sales_data&) ;

multiset<Sales_data, compISBn>

bookstore_typedef(v.cbegin(),v.cend(),compareIsbn);



multiset<Sales_data, bool(*)(const Sales_data&, const Sales_data&)>//頁249

bookstore_PF(v.cbegin(),v.cend(),compareIsbn);



for (Sales_data s : bookstore_using)//以上5種(bookstore……bookstore_PF)全對了

{

print(cout, s); cout << endl;

}

//練習11.19改用迭代器回傳

cout << "------------" << endl;

multiset<Sales_data, compISbn>::iterator bookstore_using_it{bookstore_using.begin()};

while (bookstore_using_it != bookstore_using.end())

{

print(cout, *bookstore_using_it++); cout << endl;

}

cout << endl;

}



11.3.2. Adding Elements

在關聯式容器中新增元素、加入元素

留言

熱門文章