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





Understanding settings in Visual Studio

這是唯一一次我已經會且常在用的功能 哈哈 感恩感恩 南無阿彌陀佛



10:19

10.4.3. Reverse Iterators

10.4.3反向迭代器

所以其實如果我們想取得容器中最後一個元素,可以使用rend()、crend(),只要該容器不是forward_list型別。因為forward_list並不會提供這樣的迭代器,因為與其forward行逕/行徑相違

和一般的迭代器一樣,反向迭代器(reverse iterator)也有常值與非常值(nonconst)的

21:00可見begin和end與元素無關,是與迭代器行徑的方向有關。

頁408

++r_iter) //遞減迭代器一個元素

其實++仍應說遞增,只是行徑的方向不同而已。而英文版已如此

30:00

除了前面所見,我們可配合sort,用<或>運算子來決定sort的結果是遞增或遞減排序;我們也可以用反向迭代器傳給sort來讓原來是遞增的變成遞減

33:20

Reverse Iterators Require Decrement Operators

反向迭代器需要遞減運算子

35:00 forward_list容器也只支援++運算子

資料流迭代器stream iterator是不支援遞減運算的,它是不能逆轉的

38:22

Relationship between Reverse Iterators and Other Iterators

反向迭代器與其他迭代器之間的關係

40:00在一個用逗號分隔的,而不是用空格分隔的字串序列中

頁409

generates bogus output. For example, had our input been

會產生多餘的輸出。舉例來說,假設我們的輸入是

→不如預期的、意外的。中文版應翻錯了。下文「as expected」可證bogus即不如預期之意:

Given the same preceding input, this statement prints LAST as expected.



54:00 將反向迭代器(reverse iterator)轉向、轉換成一般的迭代器

What we need to do is transform rcomma back into an ordinary iterator that will go forward through line .

We can do so by calling the reverse_iterator ’s base member, which gives us its corresponding ordinary iterator:

要用base()這個反向迭代器(reverse iterator)物件型別的成員函式來轉置迭代器的方向



反向迭代器應該還是只有在元素順序上反向讀取,只是這裡「string」是當作一個字元容器在用,並不是當作元素型別,才會被倒過來讀了。

如果是一個vector<string>應該就不會有這樣字母倒過來讀的問題了

反向迭代器是在容器類別中的型別成員,與資料流迭代器另外定義在iterator標頭檔中不同

1:17:40

#include<iostream>

#include<vector>

#include<string>

using namespace std;

int main() {

vector<string>v{"孫守真","任真","good"};

vector<string>::const_reverse_iterator ri = find(v.crbegin(), v.crend(), "good");

cout<<*ri<<endl;

}

這時候 good 當然不會倒過來

1:19:30

不僅反轉回來,反向迭代器所指的元素,與用base()轉置回來的一般迭代器指向的元素並不是同一個,而是差一個:

rcomma and rcomma.base() refer to different elements,

rcomma與 rcomma.base()指向不同的元素,line.crbegin()與line.cend()也是。這些差異是必要的,以確保那個範圍的元素,不管是正向處理或反向處理,都是相同的。

不論是正向處理或反向處理,元素的範圍都是一樣的

In order for that to happen, rcomma and rcomma.base() must yield adjacent positions差一個位置, rather than the same position, as must crbegin() and cend() .

has an important consequence:

應該翻為「不容忽視的事實」

反向迭代器是用來表示一個範圍,且這個範圍與一般所指定的,並不對稱,這個事實,有個不容忽視的結果,那就是:1:45:00

1:36:40

從一個普通的迭代器(一般的迭代器)去初始化或指定給一個反向迭代器,那麼這個得出來的迭代器,指向的並不是原來那個迭代器的元素(位置)

也就是bace()完了之後,迭代器位置會往右移一位。

1:49:10

頁410

練習10.34

#include<iostream>

#include<vector>

#include<string>

#include<iterator>

using namespace std;

int main() {

vector<string>v{"孫守真","任真","good"};

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

copy(v.crbegin(), v.crend(), o);

}

1:53:50

練習10.35

#include<iostream>//cout

#include<vector>

#include<string>

#include<iterator>//ostream_iterator<string>

#include<algorithm>//reverse_copy

using namespace std;

int main() {

vector<string>v{"孫守真","任真","good"};

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

reverse_copy(v.cbegin(), v.cend(), o);

}

所以要用一般的迭代器,就要配合reverse_copy演算法才能「顛倒」前後元素

在C++中reverse就是顛倒之義(頭變腳,腳變頭)

2:3:59

練習10.36

#include<iostream>//cout

#include<list>

#include<iterator>//ostream_iterator<string>

#include<algorithm>//find

using namespace std;

int main() {

list<int>v{1,2,3,0,4,11,3,3,2,0};

list<int>::const_reverse_iterator lit=find(v.crbegin(), v.crend(), 0);

list<int>::const_iterator litOrdinary=find(v.cbegin(), v.cend(), 0);

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

o = *lit;

lit++;//backward

*o++ = *lit;

*o++ = *litOrdinary;

*o++ = *(++litOrdinary);

}

2:15:10

練習10.37

#include<iostream>

#include<list>

#include<vector>

#include<iterator>

//#include<algorithm>//copy不在此標頭檔中

using namespace std;

int main() {

vector<int>v{1,2,3,0,4,11,3,5,2,0};

list<int>lst(7-(3-1));//the elements from positions 3 through 7

//copy的目的地容器要有和copy來源的容器至少有一樣的size()

copy(v.crbegin() + (v.size() - 7), v.crbegin() + (v.size() - 2), lst.begin());

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

/*copy(v.crbegin() + (v.size() - 7), v.crbegin() + (v.size() - 2),oIter); cout << endl;

copy(v.cbegin() + 2, v.cbegin() + 6,oIter); cout << endl;

cout << endl; copy(v.cbegin() , v.cend() ,oIter); cout << endl; */

copy(lst.cbegin(), lst.cend(),oIter);cout << endl;

}

4:42:20

10.5. Structure of Generic Algorithms

10.5泛用演算法的結構

演算法和元素是焦不離孟,孟不離焦,而與迭代器更是,因為演算法就是要對元素進行操作、運算而生也

The most fundamental property of any algorithm is the list of operations it requires from its iterator(s).

對任何的演算法來說,最基本的特質都是它對其迭代器要求的運算組合。

任何算法的最基本屬性是其迭代器所需的操作列表。(google翻譯)

2:51:30

2:54:30

The iterator operations required by the algorithms

演算法所需的迭代器運算(較為道地的中文)

被演算法需要的迭代器運算(直譯英文,較為笨拙的中文)

演算法所需的迭代器運算分為五大類,詳表10.5,而每個演算法都會指明它所帶的迭代器參數是需要哪一種的迭代器:

可見「input」(輸入)的對象(受詞)是迭代器,指將元素輸入/讀入迭代器中 ⑧找對主詞

單回(single-pass)

→單向(single-pass)、單程(只去不回的)

②單字想複詞

就類似我們「代詞性助詞」講的,成了單向的「相」了。(相類、相送、相責……的「相」)

正向迭代器(forward iterator )

→單向、向前迭代器(forward iterator )

雙向迭代器(bidirectional iterator )

③字形結構兼音義 ③字形結構換部首




3:8:20

Table 10.5. Iterator Categories 迭代器型錄型別目錄

Input iterator Read, but not write; single-pass, increment only



Output iterator Write, but not read single-pass, increment only

Forward iterator Read and write; multi-pass, increment only



Bidirectional iterator

Read and write; multi-pass, increment and decrement

Random-access iterator Read and write; multi-pass, full iterator arithmetic

表10.5 :迭代器分類

輸入迭代器(input iterator ) 讀取,但不寫入;單回(single-pass),僅遞增

輸出迭代器(output iterator) 寫入,但不讀取;單回,僅遞增

正向迭代器(forward iterator ) 讀取及寫入;多回(multi-pass),僅遞增

雙向迭代器(bidirectional iterator ) 讀取及寫入;多回,遞增及遞減

隨機存取迭代器(random-access iterator) 讀取及寫入;多回,完整的迭代器算術

完整的迭代器算術:指具備迭代器所有的運算性能

3:18:10

A second way is to classify the algorithms (as we did in the beginning of this chapter) is by whether they read, write, or reorder the elements in the sequence. 不見題目只見關鍵字

Appendix A covers all the algorithms according to this classification.

第一個is應是衍文?

演算法還共享了一組傳遞參數的公約和參數命名的規則,這些,將在瞭解迭代器分類、迭代器型錄(iterator categories)之後討論。



10.5.1. The Five Iterator Categories

10.5.1五種迭代器分類

五個迭代器型錄

五種類別的迭代器

3:36:30

ostream_iterator s have only increment, dereference, and assignment.

increment(永不回頭,只能advance向前)

Iterators on vector , string s, and deque s support these operations and the decrement, relational, and arithmetic operators.

Iterators on就是類別class下的型別成員(type member)的迭代器

arithmetic就如練習10.37所見整數加減的運算

迭代器是藉由它們支援的運算來分類的,而這些分類組成了一個分級、統屬的架構

除了輸出迭代器(output iterators),高層的迭代器,皆具備低層的迭代器所有的運算

高可以涵蓋低,而低不可涵蓋高

The standard specifies the minimum category for each iterator parameter of the generic and numeric algorithms. For

以上的標準指明了泛用和數值演算法每個迭代器參數所需的最低層級的型錄屬性(即其參數所需的迭代器的最低需求)。

頁411

比如說 find演算法就實作了一個:

舉例來說,find實作了對一個序列的單回(onepass)、唯讀的巡訪,最少需要一個輸入迭代器。

For example, find—which implements a one-pass, read-only traversal over a sequence—minimally requires an input iterator最起碼需要一個輸入迭代器.

→最基本的需求、最低需求

4:7:00可見演算法定義其迭代器參數是採用哪一種型錄的迭代器,是根據其對元素演算操作時最起碼(at least)的需求是什麼來決定的

as powerful as 夠力、夠格、堪當(大任),一樣都是最低需求的意思

如果傳遞一個不夠力、不夠格、擔當不起的迭代器給所要執行的演算,當然是個錯誤

4:14:10

當我們傳遞一個錯誤型錄/性能的迭代器給一個演算法來執行,決定是錯誤的,但編譯未必會提醒我們:

Warning

Many compilers will not complain when we pass the wrong category of iterator to an algorithm.

許多編譯器不會抱怨我們傳入了錯誤分類的迭代器給演算法。

這種中文!抱怨能這樣用嗎?可以用在編譯器這樣沒有生命、感知的東西上嗎?又不是在作文,寫作,搞文藝,也太擬人化了吧!

總之,迭代器參數的配對,至少要「門當戶對」「配得起、配得上」

The Iterator Categories 迭代器型錄

迭代器分類

輸入迭代器(input iterator,讀取元素用迭代器)

→翻成「讀取」還比較恰當

input的對象是迭代器,將元素輸入(讀取)到迭代器中

必備性能:

1.相等與不等運算子,來比較兩個迭代器是否相等

2.前綴與後綴運算子來推進(advance)迭代器所指元素

3.解參考(dereference)運算子,來解讀一個元素值。且此解參考只能在指定(assingment)的右運算元位置上出現

解參考只能出現在一個指定式的右手邊

4.箭號運算子(arrow operator:-> operator)。即具備提取元素成員的能力。

可見讀取迭代器不但須具備讀取元素的能力,還須具備選取其成員的能力

讀取迭代器只能照順序來讀

推進(遞增)一個輸入迭代器,可能會使序列中原有的迭代器都失效

因此,若我們想透過一個已儲存的輸入迭代器來讀取其所指元素,可能會因該迭代器失效而讀取失敗。因為先前儲存的輸入迭代器極有可能在迭代器操作、運算後便失效。也就是因為這個,輸入迭代器才只能用在單程、單向(single-pass)的演算法,是不能回溯的。這裡pass ⑧找對主詞 應該是指作為指向元素的操作,就像引數的傳遞,只能傳遞一次!

The find and accumulate algorithms require input iterators; istream_iterators are input iterators.

4:42:52

輸出迭代器(output iterator,寫入元素用的迭代器)

可說是輸入迭代器input iterators的加強版complementary functionality:

can be thought of as having complementary functionality to input iterators

可以想成具有跟輸入迭代器互補的功能性

具有輸入迭代器所有沒的額外功能。其必備的性能是:

1.前綴與後綴的遞增運算子

2.解參考運算子,只能在指定的左運算元位置出現。解讀後的元素值要被寫入、改寫,當然要在左邊。而輸入迭代器因為對元素是唯讀的,當然只能在指定的右邊。

指定的定義就是把右邊的值,指定給左邊。左邊是可變的,右邊不可。



輸出迭代器解參考後只能指定其值一次(single pass)。

和輸入迭代器一樣也只能用在單程演算上。

當作一個目的地用的迭代器,就是輸出迭代器的典型範例:

Iterators used as a destination are typically output iterators.

copy演算法的第3個參數,就是這種迭代器

ostream_iterator也是這種型別

5:0:40

正向迭代器(forward iterators)

可以對一個序列做存、取的迭代器

迭代器怎麼推進advance,和pass是不一樣的。

這裡forward是指推進(advance)不是pass

They move in only one direction through the sequence.

正向迭代器(forward iterators)提供了輸入迭代器、輸出迭代器所有的運算;可見其階層、層級較高





moreover

超過這個還有→甚至、此外

single pass就是 only one times for reading and writing the element the iterator refer to.



5:6:55

single pass或single-pass應該翻成「一次性的」(迭代器與元素之間的聯繫只傳一次、只用一次,類似免洗餐具)

5:19:06

Moreover, they can read or write the same element multiple times.

可見pass的意思是「read or write the same element how many times」

Therefore, we can use the saved state of a forward iterator. Hence, algorithms that use forward iterators may make multiple passes through the sequence.

make(做到、能夠做到 make it的make ②單字想複詞 ) passes through

passes through

所以 single-pass mult-pass 的pass是pass through the swquence的意思!

pass through類似traverse、iterate

頁412

使用正向迭代器的演算法可以多次處理過該序列。

→用到了正向迭代器(forward iterators)的演算法,就有能力對它要處理的序列,藉由這種迭代器的性能,來做多重、多次的巡覽與存取。

因此,使用前向迭代器的算法可能會對該序列進行多次遍歷。(google翻譯)



The replace algorithm requires a forward iterator; iterators on forward_list are forward iterators.

5:34:11

雙向迭代器(bidirectional iterators)

可以來回雙向地讀取(input)與寫入(output)

除了正向迭代器(forward iterators)的所有操作外,雙向迭代器猶支援前綴與後綴的遞減運算子

The reverse algorithm requires bidirectional iterators, and aside from forward_list , the library containers supply iterators that meet the requirements for a bidirectional iterator.

reverse演算法需要雙向迭代器,而除了forward_list以外,程式庫容器都提供符合雙向迭代器需求的迭代器。

5:41:40程式庫容器除了forward_list都提供了符合雙向迭代器條件(性能)的迭代器型別成員(type member)。

中文版中文翻譯一大堆語病,皆因中文程度不夠所致也

5:39:47

隨機存取迭代器(random-access iterators ):

這是最高層級的迭代器型錄

provide constant-time(恆定時距,duration) access to any position in the sequence.

隨機存取迭代器提供的性能是能在序列中,以同樣時間,讀取任何元素。

除了前述各項迭代器(原文雖作bidirectional iterators,但其實應即囊括所有)的功能皆具備外,它還支援了表3.7(頁111)所列的運算:

1.關係運算子(relational operator),來比較兩個迭代器的相對位置,誰先誰後。

2.加減運算子(+,+=,-,-=)。只支援與整數的加減運算

The result is the iterator advanced (or retreated) the integral number of elements within the sequence.

參見練習10.37。

3.減號運算子,套用在兩個迭代器上來比較二者所指元素的間距(distance)

4.下標運算子([]運算子,subscript operator)

( iter[n] ) as a synonym for * (iter + n) .

表3.7(頁111)不具此項。就是對這個元素下標,這個元素是在iter所指元素「後或前n若為負值」n個位置的元素,以讀取其值。

sort演算法所需的就是這種迭代器

程式庫容器,除了list、forward_list也都提供了這種迭代器成員(型別成員,type member)

array、deque 、string與vector的迭代器都是隨機存取迭代器,就跟我們用來存取一個內建陣列元素的指標一樣。

練習10.38

6:7:40

寫出五種迭代器型錄,並指出每種型錄所支援的運算

Table 10.5. Iterator Categories

練習10.39

6:11:10

list不具備隨機存取迭代器(random-access iterator),但具備雙向迭代器(bidirectional iterator)

而vector則具備最高層級的隨機存取迭代器(random-access iterator)

6:12:36

練習10.40

copy演算法所需的是輸入迭代器(input iterator)作為它前二個參數,而第3個參數則是用輸出迭代器(output iterator)。因為它只需要「single pass」就可以了,不必往復操作



reverse演算法則需要雙向迭代器(bidirectional iterator)

unique演算法應是需要隨機存取迭代器(random-access iterator),就像sort也是需要把序列中的元素重排、重調其位置;unique會將排序過後的元素,將其唯一的一個置於序列的前部,其它歸於後部、且或以它值取代。

10.5.2. Algorithm Parameter Patterns

10.5.2演算法參數模式

演算法參數的模型

演算法的參數模型

留言

熱門文章