C++自修入門實境秀、C++ Primer 5版研讀秀 60/ ~ v10 泛用演算法（generic algorithms） Write C...

頁375

Chapter 10. Generic Algorithms

泛用演算法

15:49 22:30

The library containers define a surprisingly small set of operations. Rather than adding lots of functionality to each container, the library provides a set of algorithms, most of which are independent of any particular container type.

程式庫容器定義的運算出乎意料的少。程式庫沒有為每個容器加上大量的功能性

它們大部分獨立於任何特定的容器型別。

這種中文真是要命！

「加上」可以和「XX性」配對嗎？

→加上大量的功能

或者說

→增強其性能、增加它的功能

→程式庫容器定義的運算出奇地少

→程式庫容器定義的運算少得可憐

中文能力重不重要？！

演算法獨立於容器型別，是演算法非容器？

該庫提供了一組算法，其中大多數算法與任何特定的容器類型無關。(google翻譯)

就是因為它們是通用（泛用）型別，所以與任何特定的容器型別都無關

頁376

它們可以在任何元素型別和容器型別上運作

41:20

10.1. Overview

10.1概觀

「蓋棺」？同音字還真多。呵呵。其實就是「概念」。觀念，同義複詞。②單字想複詞

大部分的演算法都是定義在algorithm 標頭檔

程式庫也定義了一些 generic numeric algorithms（泛用的數值演算法） 卻是定義在 numeric標頭檔

通常演算法不會直接作用在容器（container）本身上頭，而是藉由迭代、巡覽、逐一訪察（訪查）容器中的元素來作用的：

In general, the algorithms do not work directly on a container. Instead, they operate by traversing a range of elements bounded by two iterators (§ 9.2.1 , p. 331 ).

可見演算法與迭代器（iterator）或迭代器範圍是息息相關的，甚至可能是密不可分的

56:20

Typically,通常， as the algorithm traverses the range, it does something with each element.演算法在巡覽各個元素的同時也做了一些事情

演算法與元素的關係更是密不可分。焦不離孟，孟不離焦。

1:7:00

演，②單字想複詞 推演；推，②單字想複詞（推進，advance）

算，就是這裡的「does something with each element」

原來find在C++，不算入函式，而是作為程式庫定義的演算法algorithm,和函式一樣，動詞是用call

可能演算法就是一種特定的函式嘛！又多了一個名堂而已

程式庫find演算法（函式）傳回來的是一個的迭代器型別(應該說是傳回指定範圍的那種型別，是迭代器，或指標，乃至是常值const與否，都看引數指定什麼而定。是看您傳怎樣型別的引數而定。)

It returns an iterator to the first element that is equal to that value. If there is no match, find returns its second iterator to indicate failure.

調用演算法的方式及其傳回的值，和函式如出一轍！∴ 演算法極有可能只是一種特殊（可能係在定義時有特殊的格式）的函式



We do this test in the output statement, which uses the conditional operator (§ 4.7, p. 151) to report whether the value was found.

report為什麼只能呆呆地翻成「回報」呢？

我們在要輸出的陳述句中使用了條件運算子來判斷（用它來指出）我們想找的值找到了沒

判斷就包函了測試(test)的意思在內了，所以不必一定要翻出！

我們在輸出述句中進行這個測試，它用到條件運算子（§4.7）來回報是否有找到那個值。

我們也不是專業的翻譯家，憑什麼可以翻得比妳好？不過就是中文程度有差嘛！

為什麼專業中常見這種翻譯水平，原因不外：

1.中文程度不夠

2.忽略中文語境與原文不同。要留意中文習慣的表述方式，才能使得翻譯出來的中文文句傳神、易懂、好掌握（四個字，就是「簡單明瞭」「言簡意賅」「要言不煩」）。

活該您們輕視中文程度的現世報！有種就再繼續輕視、漫不用心啊……

這時候都反而喜歡講專業中的「文言文」(即所謂的「術語」)！請白話一點好嗎？(in chinese!)



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:

所以叫「泛用（generic）、通用」或泛型

也就是不在成員函式的束縛下，可以跨類別來作用、都有作用、都有效。不但是程式庫型別（library type）中的各個類別，內建型別（builtin type）一樣一體適用：

頁377

Similarly, because pointers act like iterators on built-in arrays, we can use find to look in an array:

提前修飾「like iterators」，④倒序重組 為了強調

原文宜是：because pointers act on built-in arrays like iterators。可見放在最末，氣勢太弱，不易引人注意，才會刻意置前，似乎不合文法，卻又合理。猶如「吾誰與歸」就是「吾歸與誰」或「吾與誰歸」。為了強調「誰」，就刻意拉到前面來突顯他，讓讀者措手不及、反應不過來，加深了印象。

find演算法就是傳什麼型別的引數給它前2個引數就回傳什麼型別的值

find一樣可以在一個子範圍中作尋找，只要給定一個有效的範圍的指標或迭代器即可。

2:9:30 2:25:00

How the Algorithms Work

演算法的運作方式

演算法是如何運作的

可由仔細觀察find的運作方式來瞭解演算法是如何作用在各式各樣的容器上的,也就能夠明白為什麼演算法（algorithm）並不需要倚靠容器的型別、或者是不是容器才能成事了。只要能夠存在對一個序列元素的存取機制，那麼就能夠運用像find這樣的演算法功能

2:47:40

Iterators Make the Algorithms Container Independent, ...

迭代器讓演算法獨立於容器

迭代器（iterator）還是每個容器型別裡頭定義的型別成員（type member）。

演算法就是靠迭代器（或類似迭代器的功能，如指標（pointer））才能成事的



露出馬腳，演算法（algorithm）根本就是函式嘛：

All but the second step in the find function can be handled by iterator operations:

迭代器（iterator）負責找到人，比對的工作就是由其他演算法或運算子負責的

真是大道至簡！



2:54:30

為什麼英文完成式要用「have」現在也能知其所以然了！

有(have)就是已經形成、完成的意思嘛，所以才用have（有）字來表達；而在中文語境中，有時不能用「有」字，要用「完成」或「已經」，也是同樣的原理；所以我們中文人才要用「完成」或「已經」來翻「have」也。

所以再看到英文的have或has had完成式，別再只會用「有」來翻譯了，可以用中文的「已經」或「完成」來譯。因為這是中文人的思維、語義與邏輯。

都是 表哥原理 啊！

看似不相關，實則相關！



3:2:00

可見中文、英文（乃至一切語文）只是用不同的符號來表述而已嘛！其字義、詞義、乃至語法結構的原理，根本都是相通的嘛！

看穿了，沒什麼大不了，斬瓜切菜，輕鬆自在；看不穿、想不透，自然難上加難，舉步維艱。

學習只要碰到瓶頸，難上加難，就要警惕自己的學法，是否是學錯了！

緣木求魚，豈易得魚？



只要一個語文能力真的好，我相信沒有一個語文他會學不好的！因為原理都類似相通的，只看自己有沒有察覺爾

頁378

3:10:10

頁378

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

演算法的罩門在於它確實是依靠元素型別的運算

Other algorithms require that the element type have the ＜ operator.

如果元素型別不存在關係比較運算子的話，就無法做演算法（algorithm）了

要寫我們自己定義的運算，就必須倚仗演算法提供給我們機制：

大部分的演算法都提供了方式來讓我們以自己的運算取代預設的運算子。

3:32:59

練習10.1

#include＜vector＞

#include＜string＞

#include ＜iostream＞

//#include ＜algorithm＞

using namespace std;



int main() {

vector＜int＞vec{0,12,42,3, 5050 , 3900 , 4050 , 3050 , 4650 , 1200 , 9950 , 1800 , 6465 , 1230 , 2400 , 2600 , 1900 , 1900 , 2600 , 2835 , 6450 , 15266 , 1800 , 1800 , 1800 , 1080 , 4320 , 30 ,42,43,42 ,1850 , 50 };

int val = 42; // value we'll look for

// result will denote the element we want if it's in vec, or vec.cend() if not

auto result = count(vec.cbegin(), vec.cend(), val);

// report the result

cout ＜＜ "The value " ＜＜ val＜＜ " is found "

＜＜ (result ==0

? " is not present" : to_string(result) +" counts") ＜＜ endl;

}



3:51:10

練習10.2

#include＜list＞

#include＜string＞

#include ＜iostream＞

//#include ＜algorithm＞

using namespace std;



int main() {

list＜string＞vec{ "0","12","42","3","5050","3900","4050","3050","4650","1200","9950","1800","6465","1230","2400","2600","1900","1900","2600","2835","6450","15266","1800","1800","1800","1080","4320","30","42","43","42","1850","50" };

string val = "42"; // value we'll look for

// result will denote the element we want if it's in vec, or vec.cend() if not

auto result = count(vec.cbegin(), vec.cend(), val);

// report the result

cout ＜＜ "The value " ＜＜ val＜＜ " is found "

＜＜ (result ==0

? " is not present" : to_string(result) +" counts") ＜＜ endl;

}

3:54:20

Key Concept: Algorithms Never Execute Container Operations

關鍵概念：演算法永遠都不會執行容器的運算

→演算法並不會執行容器的運算

您說哪一種叫中文嘛！

演算法可以改變儲存在容器中的元素的值，而它們也能在容器中到處移動元素。然而，它們不能直接新增或移除元素。

即演算法的操作絕對不會影響容器的大小，除了它在inserter這樣的迭代器上運算；但那也是inserter在作怪，不是演算法本身對容器進行了插入元素的動作。

10.2. A First Look at the Algorithms



程式庫提供了超過100個演算法。幸好，就跟容器一樣，這些演算法都有一致的架構。

幸好→好在

The library provides more than 100 algorithms. Fortunately, like the containers, the algorithms have a consistent architecture. Understanding this architecture makes learning and using the algorithms easier than memorizing all 100+ of them.



4:22: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）

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



頁379

10.2.1. Read-Only Algorithms

唯讀的演算法:

find、count、accumulate（定義在numeric標頭檔）、

Algorithms and Element Types

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

頁380

4:45:10

Algorithms That Operate on Two Sequences

作用在兩個序列上的演算法

在兩個序列上運作的演算法：

equal

However, equal makes one critically important assumption: It assumes that the second sequence is at least as big as the first.

然而，equal做了一個關鍵的重要假設：它假設第二個序列至少必須與第一個一樣大。

然而，equal演算法存在一個基本的假設（預設）：它預設了要拿來作比較的序列與被比較的至少有一樣多的元素

「基本的」或「根本的」，在中文語境中本來就有著關鍵而重要的意思（含意）就不必都要翻出來才行

也就是它對要被比較的序列的每一個元素是一定會去逐一檢查（巡覽）的，而拿來比較的就未必了



Warning: Algorithms that take a single iterator denoting a second sequence assume that the second sequence is at least as large at the first.

接受代表第二個序列的單一迭代器的演算法假設第二個序列至少與第一個一樣大。

來界定劃定

我們中文加個「來」就類似英文加上「ing」

演算法的引數如果只用一個迭代器來界定第2個序列的輸入範圍（input range），那麼它就是預設這第2個序列一定是至少和前1個序列有著一樣多的元素（是一樣大的）

也就是說，只要發現要劃定一個輸入範圍時卻僅只用了一個迭代器作參數/引數，那就可以確定它的前提是假設這個迭代器所在的序列/容器的大小，一定是小於另一個要同時操作的序列/容器。

練習10.3

5:7:40

#include ＜iostream＞

#include ＜vector＞

#include ＜numeric＞

using namespace std;



int main() {

vector＜int＞vec{ 0,12,42,3,5050,3900 };

int val = 0;

auto result = accumulate(vec.cbegin(), vec.cend(), val);

cout ＜＜ "The sum is " ＜＜ result ＜＜ endl;

}



5:15:40

練習10.4

Warning C4244 '=': conversion from 'double' to '_Ty', possible loss of data

#include ＜iostream＞

#include ＜vector＞

#include ＜numeric＞

using namespace std;



int main() {

vector＜double＞v{ 0,12.111,42,3,5050,3900 };

auto result = accumulate(v.cbegin(), v.cend(), 0.00);

cout ＜＜ "The sum is " ＜＜ result ＜＜ endl;

}



練習10.5

5:21:59

將這些運算子用在定義相似的C-style字串會比較指標的值，而非字串本身：(頁123)

const char ca1[] = "A string example";

const char ca2[] = "A different string";

if (cal ＜ ca2) //未定義的：比較兩個無關的位址



#include ＜iostream＞

#include ＜vector＞

using namespace std;



int main() {

//auto roster1="there is ";

//vector＜const char*＞roster2="there is ";

const char ca1[] = "A string example";

const char ca2[] = "A different string";

const char ca3[] = "A different string";

vector＜const char*＞roster1;

vector＜const char*＞roster2;

roster1.push_back(ca1); roster2.push_back(ca1);

roster1.push_back(ca2); roster2.push_back(ca3);

//roster2.push_back(ca1);

//可見比較的是指標（pointer）記憶體位址值，而不是「字串」文字本身

//可見提供2個迭代器的，其大小一定要等於、小於1個的那個。

//equal比較的是roster1是否和roster2相等，或為其子集合

//vector＜const char*＞roster1{ca1,ca2,ca1};

//vector＜const char*＞roster2{ca1,ca2,"1"};

//vector＜const char*＞roster1{"there is ","","a"};

//vector＜const char*＞roster2{"there is ","","b"};

auto result = equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

cout ＜＜ result ＜＜ endl;

}



6:2:20 5:59:49 6:2:00

10.2.2. Algorithms That Write Container Elements

10.2.2寫入容器元素的演算法

會修改元素值的演算法

6:13:25

要用演算法對容器或序列做指定元素值的工作，一定要確保要操作的序列或容器的大小，要與演算法所擬（ask）的大小相等或更大，決定不能小於它。即

要被指定元素值的序列或容器，有著與演算法所要(ask)操作的有最起碼的大小。



fill演算法（algorithm） 6:37:10

比較沒有「超標」（溢位（overflow））的問題

6:21:00

頁381

6:22:30

Key Concept: Iterator Arguments

關鍵概念：迭代器引數

→在演算法用到迭代器引數時的注意要項



What is required is that we be able to compare elements from the two sequences.

What is required:所需要(的)

中文的「所」就是英文的這個「what」

你看，很妙呴；這時候中文與英文的語法排序是一致的！

可見「所以」二字真的很重要，弄得真懂了，不知多少中文乃至外文的問題、關係會弄到更精而明

就像函式的多載或重載一樣，演算法的不同也是看它所帶有的參數數量與型別



Algorithms Do Not Check Write Operations

演算法不會檢查寫入運算

→演算法並不會為使用它的人把關

6:41:50

fill_n function

可見演算法（algorithm）與函式的關係了



頁382

6:53:50

back_inserter 簡介

插入迭代器（insert iterator）

back_inserter，它是定義在iterator標頭中的一個函式。



7:7:40

We frequently use back_inserter to create an iterator to use as the destination of an algorithm.

我們會頻繁地使用back_inserter創建一個迭代器來用作演算法的目的地。

頻繁地→經常



7:14:00

Copy Algorithms

拷貝演算法

copy：

像前面的fill、fill_n一樣，是識別項，專有名詞。不宜翻譯

指的是名為「copy」的這個演算法

copy的第3個引數所指向的序列或容器，一定要比前2個所指的來得大或至少一樣

雖然內建型別（builtin type）的陣列沒有拷貝，但可以用此copy演算法來將一個陣列的元素拷貝到另一個陣列或其他可容下此種元素的容器或序列

7:22:20

頁383

不少的演算法（algorithm）都提供了一種叫做拷貝的演算，但其實並不是真的拷貝到目的序列或容器，而是另外新建一個序列或容器來儲存運算出來的結果：

有幾個演算法都提供所謂的「拷貝」版本（“copying” versions)。這些演算法會計算出新 的元素值，但不是將它們放回其輸入序列，而是演算法會創建一個新的序列來包含結果。

replace這種演算法就有一個copy的版本replace_copy，就是不會改動到原序列或容器，而是另建一個新的序列或容器來置放運算的結果。

10.2.3. Algorithms That Reorder Container Elements



頁384

習題章節10.2.2

練習10.6

7:42:29

#include＜vector＞

#include ＜iostream＞

using namespace std;

int main() {

vector＜int＞vec;

fill_n(back_inserter(vec), 11,- 233);

fill_n(vec.begin(),vec.size(),0);

}



7:48:55

練習10.7

（a）

#include＜vector＞

#include＜list＞

#include ＜iostream＞

using namespace std;

int main() {

vector＜int＞ vec; list＜int＞ lst; int i;

while (cin ＞＞ i)

lst.push_back(i);

//copy(lst.cbegin(), lst.cend(), vec.begin());//vec.size()=0

//copy(lst.cbegin(), lst.cend(), back_inserter(vec));//1

vec.resize(lst.size());

copy(lst.cbegin(), lst.cend(), vec.begin());//2

/*vec.reserve(lst.size());//reserve只影響 capacity 不能用！

copy(lst.cbegin(), lst.cend(), vec.begin());*/

}



（b）

#include＜vector＞

#include ＜iostream＞

using namespace std;

int main() {

vector＜int＞ vec;

//vec.reserve(10); // reserve is covered in § 9.4 (p. 356)

vec.resize(10);

fill_n(vec.begin(), 10, 0);

//剛好剛才(a)已演示過了！哈哈

}



練習10.8

8:4:55

Key Concept: Algorithms Never Execute Container Operations

……

Algorithms never change the size of the underlying container. Algorithms may change the values of the elements stored in the container, and they may move elements around within the container. They do not, however, ever add or remove elements directly.

As we’ll see in § 10.4.1 (p. 401), there is a special class of iterator, the inserters, that do more than traverse the sequence to which they are bound. When we assign to these iterators, they execute insert operations on the underlying container. When an algorithm operates on one of these iterators, the iterator may have the effect of adding elements to the container. The algorithm itself, however, never does so.