C++自修入門實境秀、C++ Primer 5版研讀秀 66/ ~ v10 泛用演算法(generic algorithms)10.4.2. ...



第66集

10:00

〈Visual Studio extensibility is better with IntelliCode〉

Notice how the IntelliSense items starting with a ★ help write the code. That’s IntelliCode providing the guidance when I’m using the Visual Studio SDK. Since the SDK is so huge, it can really make exploring the APIs and choosing the right methods and properties much easier to do by popping the most relevant items to the top of my suggestion list. It has helped me on numerous occasions, so I’m a big fan.

17:55 19:04

頁407

練習10.29

#include<iostream>

#include<fstream>

#include<iterator>//for「istream_iterator」

#include<string>

#include<vector>

using namespace std;

int main() {

ifstream ifstm("V:\\Programming\\C++\\3.txt");

//在Visual Studio預設情況下,文字檔僅支援ANSI或Big5編碼。UTF-8應該是要用到轉碼功能

istream_iterator<string>inf(ifstm), endf;

vector<string>v(inf,endf);//是迭代器(iterator)的話就可以直接用首尾二個迭代器來指出要建構元素的範圍及其值

//凡是用到迭代器範圍的通常都是要巡覽該範圍內元素一遍的,所以這個迭代(iterate)或巡覽,就是交由vector的建構器(constructor)來執行吧

//才可以看似不用寫迴圈,卻能不斷執行、迭代、巡覽若此

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

//沒有#include<algorithm> 卻能用copy,也是一絕。應與已經「using namespace std;」有關

copy(v.cbegin(), v.cend(), outf);//一樣是指出了「迭代器範圍」然後巡覽(迭代(iterate))每個範圍內的元素,到outf上頭

//所以巡覽(迭代(iterate))的工作是由用到這個迭代器範圍引數的函式、建構器或演算法等來負責的

/*以上寫法比以下精簡多了 詳頁406上方:

我們可以不用自己寫這種迴圈,而是呼叫copy輕鬆地印出vec中的元素:*/

//for (string s : v)

// *outf++ = s;

// //outf = s;//解參考運算子和遞增運算子也可省略(詳頁406)

cout << endl;//此行是讓Visual Studio在 start without debugging的時候,最末它提供的提示文字可以放在下一行再印出

}

41:50 52:05

練習10.30

#include<iostream>

#include<iterator>//for「istream_iterator」

#include<deque>

#include<algorithm>//for sort()

using namespace std;

int main() {

istream_iterator<int>i(cin),end;

deque<int>dq(i,end);//i用cin建構初始化,因為cin現在是空的,沒有元素,所以i一定時和end相等的,同時指著第一和最後的「元素」。

sort(dq.begin(), dq.end());

ostream_iterator<int>o(cout, ",");

copy(dq.cbegin(), dq.cend(), o);

}

1:4:06

練習10.31

#include<iostream>

#include<iterator>//for「istream_iterator」

#include<deque>

#include<algorithm>//for sort()、unique_copy()

using namespace std;

int main() {

istream_iterator<int>i(cin),end;

deque<int>dq(i,end);

sort(dq.begin(), dq.end());//汰重前一定要排序,由此亦可知unique演算法是什麼「演算」(推演、計算)的了

ostream_iterator<int>o(cout, ",");

unique_copy(dq.begin(),dq.end(),o);

}

1:11:49 1:17:59

練習10.32

1.1撰寫一個簡單的C++程式

main()函式

函式定義(function definition)

main函式必須有int的回傳型別(頁3)

分號標示C++中大部分述句的結尾。(頁3)



溫習1.6 Bookstore 程式(頁24): 1:27:40

Our program will combine the data for each ISBN in a variable named total.

我們的程式會將每個ISBN的資料結合在名為total的一個變數中

→ 加總。在名為total的變數中加總

1.6 Bookstore 程式(書店程式)原型如下:

#include<iostream>

#include "Sales_item.h"

int main()

{

Sales_item total; //存放下一筆交易記綠資料的變數

//讀取第一筆交易記錄,並確保有資料可以處理

if (std::cin >> total) {

Sales_item trans; //用來存放運行總和的變數

//讀取並處理剩餘的交易記錄

while (std::cin >> trans) {

//如果我們仍然是在處理同一本書

if (total.isbn() == trans.isbn())

total += trans; // 更新累計的 total

else {

//印出前一本書的結果

std::cout << total << std::endl;

total = trans; // total現在指向下一本書

}

}

std::cout << total << std::endl; // 印出最後一筆交易記錄

}

else {

//沒有輸入!警示使用者

std::cerr << "No data?!" << std::endl;

return -1; //指示失敗

}

return 0;

}

先看第2頁 1:19:00

複習Algorithms and Element Types(頁379)

accumulate第3個引數的型別決定了accumulate能做怎樣的運算(只要該型別有定義「+」運算子,如本書所自訂的Sales_item型別也有加法運算)



改寫後:

1:47:30 5:23:20 7:21:00

#include<iostream>

#include<iterator>

#include<vector>

#include<algorithm>

#include<numeric>

#include "Sales_item.h"

#include <functional>

using namespace std::placeholders;

using namespace std;

inline bool compareIsbn1(const Sales_item& s1, const Sales_item& s2) {

return s1.isbn() < s2.isbn();//排序sort不能用等於「=」運算子

}

int main()

{

istream_iterator<Sales_item>i(cin), end;

ostream_iterator<Sales_item>o(cout,"\n");

vector<Sales_item>v(i, end);

//若要檢查沒有輸入或輸入錯誤,可在此加判斷

if (v.empty()) {//沒有輸入!警示使用者

cerr << "No data?!" << std::endl;

return -1; //指示失敗

}

vector<Sales_item>vUniqu;

sort(v.begin(), v.end(), compareIsbn1);

//unique_copy(v.begin(), v.end(), inserter(vUniqu,vUniqu.begin()));

//演算法要增減容器大小(元素個數)一定要請「介入者(插入者)迭代器」「代理」!

//因為 Sales_item定義要資料成員(data member)都相同才算重複,所以不能用它內建的==

vector<Sales_item>::const_iterator f,fnext=v.cbegin();

//for (Sales_item s : vUniqu) {

// f = find(fnext, v.cend(), s);

// while (find(++f, v.cend(), s) != v.cend()) {//找到相同的Sales_item

// }

// *o++=accumulate(fnext, f, Sales_item());

// fnext = f;

//}

//

//所以只能逐一其比對.isbn()==.isbn()

while (fnext!=v.cend())

{

f = find_if_not(fnext, v.cend(),bind(compareIsbn,_1, *fnext));//找到ISBN不同的另一本書在容器中的位置

//auto a= accumulate(fnext, f, Sales_item());

* o++ = accumulate(fnext, f, Sales_item(fnext->isbn()));

//用 Sales_item 帶了一個ISBN參數的建構器來建構accumulate的基點

fnext = f; //現在指向下一本書

}

//以下是本書原型(頁24)

//Sales_item total; //存放下一筆交易記綠資料的變數

////讀取第一筆交易記錄,並確保有資料可以處理

//if (std::cin >> total) {

// v.push_back

// Sales_item trans; //用來存放運行總和的變數//孫守真按:原書註解錯置,中文版亦未訂正:此當為total的註解,反之亦然。已在線上勘誤,尚未見刊出。頁255在另做Sales_data時已其訂正,可參證

// //讀取並處理剩餘的交易記錄

// while (std::cin >> trans) {

// //如果我們仍然是在處理同一本書

// if (total.isbn() == trans.isbn())

// total += trans; // 更新累計的 total

// else {

// //印出前一本書的結果

// std::cout << total << std::endl;

// total = trans; // total現在指向下一本書

// }

// }

// std::cout << total << std::endl; // 印出最後一筆交易記錄

//}

//else {

// //沒有輸入!警示使用者

// std::cerr << "No data?!" << std::endl;

// return -1; //指示失敗

//}

//return 0;

}

7:42:30

compareIsbn在本書所附Sales_item.h檔中

全部程式碼詳見我的GitHub Repository

7:45:50總結演算法、函式、迭代器、容器、元素的關係

練習10.33

7:54:59 8:24:00

#include<fstream>

#include<iterator>

using namespace std;

int main() {

ifstream ifstm("V:\\Programming\\C++\\2.txt");

/*ofstream ofstmOdd("V:\\Programming\\C++\\2odd.txt",ofstream::app);

ofstream ofstmEven("V:\\Programming\\C++\\2even.txt",ofstream::app);;*/

ofstream ofstmOdd("V:\\Programming\\C++\\2odd.txt");

ofstream ofstmEven("V:\\Programming\\C++\\2even.txt");;

/*The only way to preserve the existing data in a file opened by an ofstream is to specify app or in mode explicitly.(p.320

8.2.2. File Modes :Opening a File in out Mode Discards Existing Data)*/

istream_iterator<int>in(ifstm), end;

int i;

ostream_iterator<int>od(ofstmOdd, " ") ,oe(ofstmEven, "\n");

while (in != end)

{

i = *in++;

if((i % 2)==0)

*oe++=i ;

else

*od++ =i;

}

}

總結演算法、函式、迭代器、容器、元素的關係

1.演算法就是一種特殊的函式,它是專門針對元素的運算而生

2.演算法的運算只依賴:

1)迭代器的運算

2)元素型別(與回傳型別有關)

3)元素型別支援的運算子。參考練習10.32

4)和容器或序列運算無關。只會藉助迭代器來對容器或序列的元素動手腳



程式庫find演算法(函式)傳回來的是一個的迭代器型別(應該說是傳回指定範圍的那種型別,是迭代器,或指標,乃至是常值const與否,都看引數指定什麼而定。是看您傳怎樣型別的引數而定。 第66集 4:17:30 用 accumulate 就明白此元素型別與回傳型別的關係)



調用演算法的方式及其傳回的值,和函式如出一轍!∴ 演算法極有可能只是一種特殊(可能係在定義時有特殊的格式)的函式(參考演算法與函式的異同 第66集 4:21:30



Because find operates in terms of iterators, we can use the same find function to look for values in any type of container. For example, we can use find to look for a value in a list of string s:

in terms of中文版翻成「透過」也好,但竊疑即中文的「藉助(借助)」或「藉由(借由)」之義;也正符合演算法與迭代器在實作上的關係。

find operates in terms of iterators :find演算法是藉助迭代器才能對元素動手腳

這裡它「find」又稱「function」可見演算法與函式的異同了。總之,演算法就是一種特殊的函式,是針對元素處理而設的專用函式 第66集 4:48:00

同樣的,我們也可以藉由find來在本書定義的Sales_item中找值。參見練習10.32



第66集 4:55:00

//從ia[1] 開始搜尋元素,一直到但不包含ia[4]

auto result = find(ia + lr ia + 4, val);

→一直到ia[4],但不包含ia[4](它本身)

中文沒有英文這樣的表達方式的,翻譯過來不能照套其句式。語用學、語義學很重要!



How the Algorithms Work

演算法的運作方式

演算法是如何運作的

要看看演算法如何被用在各種型別的容器上,讓我們更靠近一點檢視find。

→更仔細來來看看 我的天啊 這是什麼中文啊 更靠近一點檢視,在中文上,怎麼能用在這種東西、情境上呢

它的工作是在一個未排序的元素序列中找尋一個特定元素。概念上,我們可以列出find必須採取的步驟:

→作用、運作方式 都在幫譯者改作文了 Orz

巡覽、逐一察看、檢查、迭代、巡訪…

巡訪一詞太擬人化了 第66集5:5:00

這些運算都不取決於存放那些元素的容器型別。只要有迭代器可用來存取那些元素,find就不會以任何方式依存於容器型別(甚至不管元素有沒有儲存在一個容器中)。不見題目只見關鍵字

→這些運算都與容器的型別無關,都不涉及容器型別的運算,所以演算法的操作並不需要倚仗容器是什麼型別,而只要有一個能夠指向與操作元素的介面、工具只要有可以存取元素的方式,就可以進行演算了。因此也不需要有迭代器的存在,因此內建型別(builtin type)的陣列(存取元素的介面工具是指標(pointer)或下標(subscript))也才能接受演算法的操作。第66集 5:13:00

總之,演算法的運算是靠迭代器運算不是容器運算。



頁378

...But Algorithms Do Depend on Element-Type Operations

演算法的罩門在於它確實是依靠元素型別的運算 第66集 5:15:30演算法與元素型別息息相關



如我們會在§10.4.1中看到的,有一個特殊類別的迭代器,即插入者(inserters),所做的事 不僅止於巡訪它們所繫結的序列。

其實inerter翻成插足者或介入者,或許更傳神!之乎者也,不都用「者」嗎?豈是文言文?!

當我們對這些迭代器進行指定,它們會在底層的容器上執行插入運算。

執行者是這些介入者,而幕後黑手、教唆者,卻是演算法也。演算法在這裡是借刀殺人嘛

演算法既然和元素息息相關(焦不離孟,孟不離焦)它則是藉由迭代器(iterator)來操縱、支配、左右、干涉……元素也

當一個演算法作用在這些迭代器其中一個,這種迭代器可以有新增元素到容器的效果。然而,演算法本身永遠都不會這麼做。

演算法永遠是殺人不沾血腥的人=元素 第66集3:38:00

10.2. A First Look at the Algorithms

這裡翻「初探」就內容要義上不太適合。應是對演算法要先建立一個正確的觀念,日後才容易把握其要領而不致迷惘的意思。就是最初的概念、印象要釐清、要正確,才不會影響後來。就是基礎要打好的意思。如第一印象。否則一開始就落入錯知見,日後就有苦頭吃了。



附錄A會列出所有的演算法,以它們的運作方式來分類。第66集2:55:00



With only a few exceptions, the algorithms operate over a range of elements.

看吧!演算法(algorithm)和元素密不可分

We’ll refer to this range as the “input range.”

輸入範圍(input range)

帶有輸入範圍的演算法都是用它前兩個迭代器引數來指認那個輸入範圍

第66集2:55:00

除了少數幾個例外,這些演算法都作用在一個範圍的元素。我們會將這個範圍稱作「輸入範圍(input range)」。接受一個輸入範圍的演算法永遠都會用它們的頭兩個參數來代表那個範圍。這些參數是迭代器,代表要處理的第一個元素和超出最後一個元素一個位置處。

演算法(algorithm)就是為了要逐一(巡覽、迭代(iterate))處理它前2個引數所劃出範圍內的所有元素而生

不見題目只見關鍵字 這裡用寶藍色字來點醒。寶藍的寶,即寶石的寶,謂如寶石發光也;《國語辭典》也都不解釋。

雖然大部分的演算法作用在輸入範圍的方式都類似,它們的差異在於如何使用在那個範圍中的元素。理解這些演算法最基本的方法是了解它們是否會讀取元素、寫入元素或重新安排元素的順序。

→明白這些演算法最簡捷的方式、最易掌握的切入點就是注意它們是否會讀取元素、寫入元素或重新安排元素的順序。

焦不離孟,孟不離焦

可見演算法與函式的不同在於,它們是有針對性的而函式沒有,函式在此處反而更堪當「泛用(generic)或通用」之名、之義」(函式定義的四個要素必要條件見本書第2頁),針對序列或容器中的每個元素的處理,可以簡單地總結地說:「演算法是為了處理序列容器元素而生」第66集3:10:00 本書由循序容器(sequential container)下來接著介紹演算法(algorithm),用意之深,至此亦不言可喻了



頁379

10.2.1. Read-Only Algorithms

唯讀的演算法:

find、count、accumulate(定義在numeric標頭檔)、

第66集2:22:20

accumulate函式接受三個引數。頭兩個指定要加總的一個範圍的元素。第三個是這個總和的初始值。假設vec是一 個整數序列,下列程式碼

//加總vec中的元素,以值0開始加總

int sum = accumulate{vec.cbegin(), vec.cend(), 0);

accumulate第三個引數的型別決定了要用哪個加法運算子,並且是accumulate所回傳的型別。

Algorithms and Element Types

演算法和元素型別的關係

你看,都跟元素息息相關嘛

「accumulate使用它的第三個引數作為加總的起點」這個事實,有一個重大的後果:你必須能夠將元素型別加到那個總和的型別。

→ 有個決定性的影響。第66集2:26:00

也就是accumulate第3個引數的型別決定了accumulate能做怎樣的運算(加法。只要該型別有定義「+」運算子,如本書所自訂的Sales_item型別也有加法運算)

因為string有一個+運算子,我們可以呼叫accumulate來串接由string 構成的一個vector的元素:

string sum = accumulate (v.cbegin(), v.cend(), string(""));

這個呼叫會將v中的每個元素串接到一個最初為空的string。注意到,我們明確的創建了一個string作為第三個參數。以字串字面值(string literal)的形式傳入一個空字串會是編譯期錯誤:

因為字串字面值(string literal)並非string型別,實是C式字元字串:

那個字串必須是一個C-style的字元字串(即一個字串字面值,或指向一個null-terminated陣列的一個指標)。(見頁405)

//錯誤:const char*上沒有+運算

string sum = accumulate(v.cbegin{), v.cend(),"");

假設我們傳入一個字串字面值,那麼用來存放總和的物件之型別會是const char*。那個型別決定了會使用哪個+運算子。因為型別const char*沒有+運算子,這個呼叫就沒辦法編譯。

而如本書定義的Sales_item型別因為有「+」運算子,因此也可以應用在accumulate演算法上。參練習10.32。第66集2:45:00

養成好習慣Best Practices:

一般來説,最好是使用cbegin()和cend() ( § 9.2.3 )來搭配讀取但不寫入元素的 演算法。然而,如果你計畫使用演算法所回傳的迭代器來更改一個元素的值,那麼你 就得傳入begin()和end()。

→打算;想要。中文語境的「計畫」是用在很正式、大條的事務上好嗎?拜託。中文程度真的很重要!這裡怎麼會用「計畫」呢?要會自己改作文吶!所以國文才是必修課咩。沒有好好修,只能書到用時方恨少!

留言

熱門文章