C++ partition(STL partition)演算法使用詳解

在序列中分割區元素會重新對元素進行排列，所有使給定謂詞返回 true 的元素會被放在所有使謂詞返回 false 的元素的前面。這就是 partition() 演算法所做的事。

partition 的前兩個引數是定義被分割區序列範圍的正向疊代器，第三個引數是一個謂詞。下面展示如何使用 partition() 來重新排列序列中的值，所有小於平均值的元素會被放在所有大於平均值的元素的後面：

std::vector<double> temperatures {65, 75, 56, 48, 31, 28, 32, 29, 40, 41, 44, 50};
std::copy(std::begin(temperatures), std::end(temperatures), //List the values
std::ostream_iterator<double>{std::cout, " "});
std::cout << std::endl;
auto average = std::accumulate(std::begin(temperatures),std::end(temperatures), 0.0)/temperatures.size();
std::cout << "Average temperature: "<< average << std::endl;
std::partition(std::begin(temperatures), std::end(temperatures),[average](double t) { return t < average; });
std::copy(std::begin(temperatures), std::end(temperatures),std::ostream_iterator<doiible>{std::cout, " "});
std::cout << std::endl;

這段程式碼會輸出下面這些內容：

65 75 56 48 31 28 32 29 40 41 44 50
Average temperature: 44.9167
44 41 40 29 31 28 32 48 56 75 65 50

通過 accumulate() 演算法建立的元素之和除以元素個數，計算出 temperatures 容器中元素的平均值。在前面，我們已經介紹了 accumulate() 演算法，所以，我們記得它的第三個引數就是和的初始值。執行 partition() 演算法後，可以看到所有小於平均值的溫度值都在大於平均值的溫度值之前。

這個謂詞可以不必是用來處理順序關係的一它可以是我們喜歡的任何樣子。例如，可以對表示個體的 Person 物件進行分割區，將所有女性放在男性的前面，或者將有大學學歷的放在沒有大學學歷的前面。下面是一個對 tuple 物件的序列進行分割區的範例，這個元組物件用來表示人和標識他們的性別：

using gender = char;
using first = string;
using second= string;
using Name = std::tuple<first, second, gender>;
std:: vector<Name> names {std::make_tuple ("Dan", "old", 'm'),std::make_tuple("Ann", "old", 'f'),std::make_tuple ("Ed", "old",'m'),std::make_tuple ("Jan", "old", 'f'), std::make_tuple ("Edna", "old", 'f')};
std::partition(std::begin(names), std::end(names),[](const Names name) { return std::get<2>(name) == 'f'; });

for(const auto& name : names)
    std:: cout << std::get<0> (name) << " "<< std::get<1> (name) << std::endl;

這裡使用 using 宣告來解釋 tuple 物件成員變數的意義。當 tuple 物件的最後一個成員變數是“f”時，這個謂詞會返回 true，所以輸出中會出現 Edna、Ann 以及處在 Ed 和 Dan 之前的 Jan。在這個謂詞中，可以用表示式 std::get<gender>(name) 來參照 tuple 的第三個成員變數。這樣做是可行的，因為第三個成員是唯一的，這就允許用它的型別來識別這個成員。

partition() 演算法並不保證維持這個序列原始元素的相對順序。在上面的範例中，對於原 始序列，元素 44 和 41 在 40 的後面。但在進行這項操作之後，它們就不是那樣了。為了維持元素的相對順序，可以使用 stable_partition() 演算法。它的引數和 partition() 一樣，可以用下面這些語句來代替前一段程式碼中的 partition() 呼叫：

std::stable_partition(std::begin(temperatures), std::end(temperatures),[average](double t) { return t < average; });

做出這些修改後，對應的輸出如下：

65 75 56 48 31 28 32 29 40 41 44 50
Average temperature: 44.9167
31 28 32 29 40 41 44 65 75 56 48 50

可以看到，重排序時並不一定要對序列進行分割區，元素的相對順序被保留了。所有小於平均值的元素的相對順序都沒有被改變，所有大於平均值的元素也是如此。