上次提到過為容器生成數(shù)據(jù)的問題，我給出的用 boost.lambda 的方法是

上次提到過為容器生成數(shù)據(jù)的問題，我給出的用 boost.lambda 的方法是：

? std::vector<int> vect(10);
? int i = 0;
? std::for_each( vect.begin(), vect.end(), _1 = ++var(i) );

不錯，這樣可以生成連續(xù)的數(shù)字，也還算比較簡潔，因為代碼量不會隨著容器的大小而變化，不過，如果要在容器內(nèi)填入隨機數(shù)呢？其實比上面更簡單，因為 STL 的 generate 算法就是設計來做這個的：

? std::vector<int> vect(10);
? std::generate(vect.begin(), vect.end(), rand);

rand 是我們熟悉的標準 C 庫函數(shù)，這樣我們可以生成任意數(shù)量的隨機數(shù)了，不過還是有點不好的地方：每次生成的序列都是一樣的，因為 rand 生成的是偽隨機數(shù)。這個容易解決，我們必須先 seed 一下：

? std::vector<int> vect(10);
? srand(time(NULL));
? std::generate(vect.begin(), vect.end(), rand);

好了，我們終于還是用了三行（其實是兩行，聲明 vector 總是必需的吧！），但是好歹是有了一個可用的方案。回頭看看，前面的連續(xù)整數(shù)問題也可以用 generate 來做，方法不言而喻：

? std::vector<int> vect(10);
? int i = 0;
? std::generate(vect.begin(), vect.end(), ++var(i));

好處是 generate 本身更能說明這句話的用途，當然這個可能因人而異。

我知道有人一定在問：一定要兩行么？一定要有一個初始變量么？答案是可以沒有，但是要用到另外的算法，再加上 boost.lambda 的協(xié)助。看看下面：

? std::vector<int> vect(10);
? std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = _1 + 1);

如果你現(xiàn)在把 vect 輸出，你會得到：

0 1 2 3 4 5 6 7 8 9

乍看起來不太好理解，我來慢慢解釋。
partial_sum 的第4個參數(shù)是一個雙參數(shù)的 functor ，在這里，lambda 表達式 _2 = _1 + 1 充當了這個角色，它相當于

f(x, y)? {? y? =? x? +? 1;? }

而 partial_sum 呢？它把一個序列的 partial sum 送到結(jié)果序列中去，例如如果輸入一個數(shù)組 v[10] ，而輸出是 r[10] ，那么它的計算就是

r[0] = v[0]????????????
r[1] = f( r[0], r[1] )
r[2] = f( r[1], r[2] )
......
r[9] = f( r[8], r[9] )

而當我們把 partial_sum 作用于 vect 本身，結(jié)果就成了

vect[0] = vect[0]??????????????????????????? // vect[0] = 0
vect[1] = (vect[1] = vect[0] + 1)?? // vect[1] = 1
vect[2] = (vect[2] = vect[1] + 1)?? // vect[2] = 2
......
vect[9] = (vect[9] = vect[8] + 1)?? // vect[9] = 9

你一定發(fā)現(xiàn)其中的問題所在了：首先，我們必須依賴于編譯器把 vect[0] 初始化為0，其次，vect[0] = vect[0] 是不可回避的。以我當前所想到的，也只能這樣了。

推廣一下，如果把 _2 = _1 + 1 中的常數(shù) 1 換成另外的數(shù)字，我們就可以用一句話得到從 0 開始的等差數(shù)列，例如

? std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = _1 + 3);

得到的是

0 3 6 9 12 15 18 21 24 27

如果再發(fā)揮一點想象力，你就可以構(gòu)造出更復雜的 lambda 表達式，從而得到更復雜的數(shù)組（也許這里叫數(shù)列更好吧），例如

? std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = 2 * _1 + 1);

得到的是 2 的 n 次方 - 1 數(shù)列

0 1 3 7 15 31 63 127 255 511

在 STL 算法中，adjacent_difference 和 partial_sum 是逆運算，因此，上面的事情也可以用 adjacent_difference 來做，只不過要把 lambda 表達式中的參數(shù)位置換一下，例如要得到 0, 3, 6... 的等差數(shù)列，只需要

? std::adjacent_difference(vect.begin(), vect.end(), vect.begin(), _1 = _2 + 3);

而 2 的 n 次方 - 1 數(shù)列也是同樣道理

? std::adjacent_difference(vect.begin(), vect.end(), vect.begin(), _1 = 2*_2 + 1);

如果你要生成倒序的數(shù)列呢？當然，STL 算法 reverse 可以派上用場，不過也不要忘了 STL 還有 reverse_iterator 這回事，用它就無需另外調(diào)用 reverse 了：

? std::partial_sum(vect.rbegin(), vect.rend(), vect.rbegin(), _2 = 2*_1 + 1);

得到

511 255 127 63 31 15 7 3 1 0

最后還要提醒大家不要忘了一個很有用的 STL 算法： random_shuffle 。它可以把 Random access container 里面的值打亂，配合上面的數(shù)列生成，在很多場合是進行測試 （例如測試排序算法） 的好工具。在我的機器上，下面兩行

? std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = 2*_1 + 1);
? std::random_shuffle(vect.begin(), vect.end());

得到打亂以后的數(shù)列：

255 1 511 3 0 31 127 7 15 63

=================================================================================

有了強大的生成機制作基礎，下面的實驗也更加容易了。STL 的 count_if 和 find_if 都接受一個 predicate 作為比較的依據(jù)，而這個 predicate 往往非常簡單，以至于為它專門寫一個 functor 簡直不可接受。在第一篇里面已經(jīng)展示了用 boost.lambda 生成臨時的無名 functor 的能力，這里再多說一點。

下面先生成 2^n - 1 的數(shù)組，然后找出其中第一個大于100的數(shù)

? std::vector<int> vect(10);
? std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = 2*_1 + 1);
?
? std::cout << *std::find_if(vect.begin(), vect.end(), _1 > 100);

輸出為 127 ，如我們所料。同樣道理，如果是 count_if ，則會得到大于100的數(shù)的個數(shù)

? std::cout << std::count_if(vect.begin(), vect.end(), _1 > 100);

輸出是 3 。注意細節(jié)：find_if 返回一個 iterator ，所以在它之前有 * 解引用，而 count_if 直接返回一個數(shù)字，無需解引用。

與之類似的還有 STL 的 partition 算法，它根據(jù)傳入的 predicate 對一個序列進行劃分，predicate 得到 true 的將放在前面，其余的放在后面，返回的是那些“ 放在 后面”的元素中的第一個，換言之就是分界點。下面的代碼

? std::vector<int> vect(10);
? std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = 2*_1 + 1);
?
? std::cout << *std::partition(vect.begin(), vect.end(), _1 > 100) << std::endl;
?
? std::for_each(vect.begin(), vect.end(), std::cout << _1 << " ");

輸出為

7
511 255 127 7 15 31 63 3 1 0

如果仔細觀察，還可以發(fā)現(xiàn)上面的輸出有點問題：數(shù)列中原有的順序（0, 1, 3, 7...）不復存在，這是因為 partition 并不是一個穩(wěn)定排序的算法，它不保證排序結(jié)果保有原來的順序。如果需要穩(wěn)定排序，可以使用 stable_partition 。只需要更改排序的那一句代碼為

? std::cout << *std::stable_partition(vect.begin(), vect.end(), _1 > 100) << std::endl;

結(jié)果是

0
127 255 511 0 1 3 7 15 31 63

當然，如果你還記得大學里的算法理論，就知道它們在效率上是有點區(qū)別的，partition 的復雜度保證為 O(n) ，具體地說是保證不超過 n/2 次交換；而 stable_partition 在最好情況下為 O(n) ，最差情況則達到 O(n*log(n)) 。

順便說一下，上面的幾件簡單的事情，用標準的 STL 算法都可以辦到，只不過實在是……面目可憎：

? std::cout << *std::partition(vect.begin(), vect.end(),
??? std::bind2nd(std::greater<int>(), 100)) << std::endl;

這句代碼做的事情和前面的 partition 一模一樣，但是孰優(yōu)孰劣，大家自有公斷。