C++自修入門實境秀、C++ Primer 5版研讀秀 61/ ~ v10 泛用演算法(generic algorithms)10.3.2. ...
10.2.3. Algorithms That Reorder Container Elements
10.2.3改變容器元素順序的演算法
會重新排序元素的演算法
sort演算法
A call to sort arranges the elements in the input range into sorted order using the element type’s < operator.
不見題目只見關鍵字
4:20
我用Word VBA寫的文件字頻程式
20:30
33:30
38:20
Eliminating Duplicates
消除重複的
汰重
unique演算法
To eliminate the duplicated words, we will first sort the vector so that duplicated words appear adjacent to each other. Once the vector is sorted, we can use another library algorithm, named unique , to reorder the vector so that the unique elements appear in the first part of the vector .
可見演算法的演算比較像中國傳統的「推步、推測、推敲、推排、排布、推闡」
就是一步一步推出來嘛
Because algorithms cannot do container operations, we’ll use the erase member of vector to actually remove the elements:
簡單地來說,演算法對容器的操作計算就是白手套、殺人不帶刀啦。教唆殺人(元素),而自己不動手,請人(函式、成員函式)代勞。剛好和轉接器(adaptor)的角色相反,轉接器是代別人做、自己承擔、承攬、包辦;而委派和演算法則是丟給別人做。
55:17
// sort words alphabetically so we can find the duplicates
sort(words.begin(), words.end());
// unique reorders the input range so that each word appears once in the
// front portion of the range and returns an iterator one past the unique range
auto end_unique = unique(words.begin(), words.end());
// erase uses a vector operation to remove the nonunique elements
Using unique
1:2:20
頁385
unique演算法原來是做假的、善巧方便:
We put remove in quotes because unique doesn’t remove any elements. Instead, it overwrites adjacent duplicates so that the unique elements appear at the front of the sequence.
我們為「移除」二字加上引號,是因為unique沒有移除任何元素。取而代之,它,而是覆寫了相鄰近的重複項目,讓唯一的元素出現在序列的前端。
像改作文一樣!
unique傳回的迭代器(iterator)指向的點之後,一樣仍有元素,只不過我們無法知道它們究竟是什麼、有怎樣的值:
The elements beyond that point still exist, but we don’t know what values they have.
Note :
The library algorithms operate on iterators, not containers. Therefore, an algorithm cannot (directly) add or remove elements.
標準程式庫演算法只能假借他人之手來對容器大小動手
Using Container Operations to Remove Elements
unique演算法傳回一個迭代器(在這裡是「end_unique」)來指出唯一值範圍末端位置
1:36:30
It is worth noting that this call to erase would be safe even if words has no duplicated words.
這樣的erase即使在原序列容器沒有重複值的狀態下一樣安全
Both arguments to erase would have the same value: words.end() .
The fact that the iterators are equal would mean that the range passed to erase would be empty.
Erasing an empty range has no effect, so our program is correct even if the input has no duplicates.
前面學過由兩個/一對迭代器(iterator)劃出的範圍是可以不包括任何元素的,即空的範圍,此時此兩個迭代器是equal相等的
1:40:10
練習10.9
1:43:20
#include<vector>
#include<string>
#include <iostream>
#include<algorithm>
using namespace std;
void print(vector<string>& vec) {
for (string s : vec)
cout << s << ",";
}
void elimDups(vector<string>& vecStr) {
print(vecStr); cout << endl;
sort(vecStr.begin(), vecStr.end());//也不能用const iterators
print(vecStr); cout << endl;
auto rngEnd = unique(vecStr.begin(), vecStr.end());//因為unique會overwrite所以不能用「cbegin()、cend()」
print(vecStr); cout << endl;
vecStr.erase(rngEnd, vecStr.cend());
print(vecStr); cout << endl;
}
int main() {
string word; vector<string> vecStr;
while (cin >> word) {
vecStr.push_back(word);
}
elimDups(vecStr);
}
海賢老和尚 孫守真 淨空老法師 白雲老禪師 任真 常律老和尚 常照法師 悟道法師 悟行法師 黃柏霖警官 陳彩瓊總裁 孫守真
^Z
海賢老和尚,孫守真,淨空老法師,白雲老禪師,任真,常律老和尚,常照法師,悟道法師,悟行法師,黃柏霖警官,陳彩瓊總裁,孫守真,
白雲老禪師,任真,孫守真,孫守真,悟行法師,悟道法師,海賢老和尚,常律老和尚,常照法師,淨空老法師,陳彩瓊總裁,黃柏霖警官,
白雲老禪師,任真,孫守真,悟行法師,悟道法師,海賢老和尚,常律老和尚,常照法師,淨空老法師,陳彩瓊總裁,黃柏霖警官,,
白雲老禪師,任真,孫守真,悟行法師,悟道法師,海賢老和尚,常律老和尚,常照法師,淨空老法師,陳彩瓊總裁,黃柏霖警官,
練習10.10
2:15:59
Why do you think the algorithms don’t change the size of containers?
為何你認為演算法不會變更容器的大小?
您為什麼認為算法不會改變容器的大小?(google翻譯)
→你認為是為什麼演算法不去變更容器的大小?
又不是「我認為」的!
演算法若能改變容器恐怕就不易抓到正確的元素範圍,容易發生超標、溢位等嚴重的失誤
10.3. Customizing Operations
10.3自訂運算
2:23:59
客製的運算
The library also defines versions of these algorithms that let us supply our own operation to use in place of the default operator.
程式庫也定義了這些演算法的另一種版本,讓我們可以提供自己的運算來取代預設 運算子。
→程式庫也定義了這些演算法的一些版本來讓我們得以定義我們自己的運算來取代這類運算子(<,==)預設的行為
頁386
如果我們不想照原來的「<」運算子的定義來做,而是想有自己的一種定義(順序),或者說是想要比對一些型別本身並不具有「<」運算子的元素,我們就會想定義自己的「<」運算子,來賦予它新的意義。
3:35:20
override 就是overwrite
2:37:40
10.3.1. Passing a Function to an Algorithm
10.3.1傳遞函式給演算法
2:42:55
Predicates
判斷式(predicate)
多載版本的sort演算法,帶3個引數,第3個即predicate
A predicate is an expression that can be called and that returns a value that can be used as a condition.
判斷式(predicate)是一個運算式(表達式),它是可以被呼叫(調用)的,而會回傳一個可以被當作條件判斷的值
單元判斷式(unary predicate)
二元判斷式(binary predicate)
2:56:00
The version of sort that takes a binary predicate uses the given predicate in place of < to compare elements.
如果是這樣的話,可以說是改寫了「<」的定義嗎?只是遮蔽不用「<」吧?
The predicates that we supply to sort must meet the requirements that we’ll describe in § 11.2.2 (p. 425 ). For now, what we need to know is that the operation must define a consistent order for all possible elements in the input sequence. Our isShorter function from § 6.2.2 (p. 211 ) is an example of a function that meets these requirements, so we can pass isShorter to sort .
也就是把function當作一個predicate引數來傳給sort演算法
// comparison function to be used to sort by word length
bool isShorter(const string &s1, const string &s2)
{
return s1.size() < s2.size();
}
// sort on word length, shortest to longest
sort(words.begin(), words.end(), isShorter);
還是用「<」啊!可見並不沒重新定義「<」這個符號的定義,而是不用別人對它所下的定義,不照那個定義去執行罷了;而由我們自己決定看是要用哪個對「<」的定義;如這裡是用string類別對「<」定義的運算。
3:10:50
Sorting Algorithms
stable_sort演算法
穩定的排序可保持相等元素之間的原始順序。
就是原來已經(已經經過)排序過的順序不會被變動,而是在相同的順序中,再做次一階的排序
頁387
3:17:00
By calling stable_sort, we can maintain alphabetical order among those elements that have the same length:
⑧找對主詞 這裡的「maintain」講的是這些「相等」(長度)的元素,它們的排列,能夠按照字母的順序來排序。
表哥原理:能按照(照著做而不破壞規矩)自然就是「保持」「維持」了
∴ 「maintain」在這裡要翻成「根據」或「按照」才最佳
都順便在講翻譯學了
elimDups(words); // put words in alphabetical order and remove duplicates
// resort by length, maintaining alphabetical order among words of the same length
stable_sort(words.begin(), words.end(), isShorter);
for (const auto &s : words) // no need to copy the strings
cout << s << " "; // print each element separated by a space
cout << endl;
練習10.11
3:40:20
#include<vector>
#include<string>
#include <iostream>
#include<algorithm>
using namespace std;
void print(vector<string>& vec) {
for (string s : vec)
cout << s << ",";
}
inline bool isShorter(const string & s1,const string & s2) {
return s1.size() < s2.size();
};
void elimDups(vector<string>& vecStr) {
print(vecStr); cout << endl;
sort(vecStr.begin(), vecStr.end());//也不能用const iterators
print(vecStr); cout << endl;
auto rngEnd = unique(vecStr.begin(), vecStr.end());//因為unique會overwrite所以不能用「cbegin()、cend()」
print(vecStr); cout << endl;
vecStr.erase(rngEnd, vecStr.cend());
print(vecStr); cout << endl;
stable_sort(vecStr.begin(), vecStr.end(), isShorter);//通常我們呼叫函式是必須要傳引數,而在這裡卻只要調用其名稱即可!
print(vecStr); cout << endl;
}
int main() {
string word; vector<string> vecStr;
while (cin >> word) {
vecStr.push_back(word);
}
elimDups(vecStr);
}
3:49:47
練習10.12
Severity Code Description Project File
Error C2678 binary '=': no operator found which takes a left-hand operand of type 'const Sales_data' (or there is no acceptable conversion) prog1 C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.23.28105\include\algorithm
失敗,俟考(已上GitHub)
5:34:00
練習10.13
partition 演算法
5:46:40
#include<vector>
#include<string>
#include<algorithm>
#include <iostream>
using namespace std;
bool morethen5char(string s) {
return s.size() >= 5;
}
int main() {
string w;
vector<string>words;
while (cin>>w)
{
words.push_back(w);
}
auto pr=partition(words.begin(), words.end(), morethen5char);//不能用常值版本cbegin,可見是要改寫元素故
words.erase(pr, words.end());
for (string s : words)
cout << s << ",";
cout << endl;
}
6:10:10
10.3.2. Lambda Expressions
The predicates we pass to an algorithm must have exactly one or two parameters, depending on whether the algorithm takes a unary or binary predicate, respectively.
演算法所帶的predicate判斷式引數只能為一元或二元(參數)
It would be move useful to be able to partition a sequence without having to write a separate predicate for every possible size.
move當是「more」之訛,中文版已逕正
6:21:40
A sketch of this function, which we’ll name biggies, is as follows:
我們會命名為biggies的這個函式的草圖如下:
→我們姑且叫作「biggies」的函式,它大概的輪廓如下(它大概是像下面這個樣子):
頁388
6:28:00
find_if 演算法
find演算法(頁376)
However, find_if takes a unary predicate—any function we pass to find_if must have exactly one parameter that can be called with an element from the input sequence.
6:43:30
Introducing Lambdas
Lambda簡介
We can pass any kind of callable object to an algorithm. An object or expression is callable if we can apply the call operator (§ 1.5.2 , p. 23 ) to it. That is, if e is a callable expression, we can write e(args) where args is a comma-separated list of zero or more arguments.
可以將任何可以被呼叫的東西傳遞給演算法
只要能在它上面用上呼叫運算子,這個東西就是可呼叫的(callable)
可呼叫物件(callable object)
6:48:40
只要是可呼叫的,就可以這樣寫「可呼叫物件()」
可呼叫的東西我們目前僅接觸到函式和函式指標(function pointer)
還有兩種是可呼叫的:
1.重載函式呼叫運算子的類別
2.lambda表達式(運算式)
重載了函式呼叫運算子的類別(這會在§14.8中涵蓋,頁570),以及lambda expressions (lambda 運算式)。
6:57:20
一個lambda expression代表一個可呼叫的程式碼單元。
It can be thought of as an unnamed, inline function.
lambda表達式就如一個不具名的行內函式(inline function)
Like any function, a lambda has a return type, a parameter list, and a function body.
Unlike a function, lambdas may be defined inside a function.
A lamba expression has the form
[ capture list ] ( parameter list ) -> return type { function body }
where capture list is an (often empty) list of local variables defined in the enclosing function; return type , parameter list , and function body are the same as in any ordinary function. However, unlike ordinary functions, a lambda must use a trailing return (§ 6.3.3 , p. 229 ) to specify its return type.
不同於函式,lambda可以被定義在一個函式內。一個lambda expression有這種形式:
[capture list] (parameter list) -> return type { function body }
其中capture list(捕捉串列)是定義在外圍函式中的一個區域變數串列(通常是空的); return type (回傳型別)、parameter list (參數列)和function body (函式主體)就跟一般函式相同。然而,不同於一般函式,一個lambda必須使用尾端回傳(trailing return,§6.3.3) 來指定其回傳型別。
7:10:00
We can omit either or both of the parameter list and return type but must always include the capture list and function body:
頁389
auto f = [] { return 42; };
Here, we’ve defined f as a callable object that takes no arguments and returns 42.
這就是定義可呼叫物件(callable object)的方式
We call a lambda the same way we call a function by using the call operator:
cout << f() << endl; // prints 42
7:14:40
7:21:30
Note Lambdas with function bodies that contain anything other than a single return statement that do not specify a return type return void .
可見lambda與inline函式(行內函式,inline function)息息相關
7:23:17
Passing Arguments to a Lambda
傳入引數給Lambda
傳遞引數就是為了初始化參數值
lambda是不能有預設引數(default argument)的,因此,對lambda的呼叫,所用引數數量一定是和其定義的參數數量一致的
7:28:00
所以lambda和函式跑不掉關係,和行內函式、呼叫運算子更跑不掉關係:
As an example of a lambda that takes arguments, we can write a lambda that
behaves like our isShorter function:
[](const string &a, const string &b)
{ return a.size() < b.size();}
The empty capture list indicates that this lambda will not use any local variables from the surrounding function.
Using the Capture List
使用捕捉串列
7:46:01
We want an expression that will compare the length of each string in the input sequence with the value of the sz parameter in the biggies function.
我們想要一個運算式來比較輸入序列中每個string的長度和biggies函式中sz參數的值。
→來將「輸入序列中每個string的長度」和「biggies函式中sz參數的值」作比較。
7:52:30
頁390
7:55:00
原來叫「capture」的意思就是要捕捉到區域變數現有的值,來進行必要的運算:
In this case, our lambda will capture sz and will have a single string parameter.
The body of our lambda will compare the given string’s size with the captured value
of sz:
Calling find_if
留言