今天繼續。
C++11新增的關於Non-modifying sequence operations和Modifying sequence operations的算法已經寫了，詳細信息見之前的博客。
下面開始C++11新增的關於Partitions的算法：
Partitions:即分區的意思。
很多人可能還不熟悉partition，所以先說一說partition算法，需要說明的是這不是C++11新增的內容。但為了更方便大家理解，還是先寫一寫std::partition。
std::partition
原型：
template
ForwardIterator partition (ForwardIterator first,
ForwardIterator last, UnaryPredicate pred);
作用：
Rearranges the elements from the range [first,last), in such a way that all the elements for which pred returns true precede all those for which it returns false. The iterator returned points to the first element of the second group.
需要注意一下返回值：
An iterator that points to the first element of the second group of elements (those for which pred returns false), or last if this group is empty
返回的迭代器是指向第二個區間的第一個元素！！！
應用：
#include // std::cout
#include // std::partition
#include // std::vector
bool IsOdd(int i) { return (i % 2) == 1; }
int main() {
std::vector myvector;
// set some values:
for (int i = 1; i<10; ++i)
myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
std::vector::iterator bound;
bound = std::partition(myvector.begin(), myvector.end(), IsOdd);
// print out content:
std::cout << "odd elements:";
for (std::vector::iterator it = myvector.begin(); it != bound; ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "even elements:";
for (std::vector::iterator it = bound; it != myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "Now myvector is: ";
for (auto it = myvector.begin(); it != myvector.end(); it++)
{
std::cout << ' ' << *it;
}
std::cout << std::endl;
return 0;
}
//輸出：
//odd elements : 1 9 3 7 5
//even elements : 6 4 8 2
//Now myvector is : 1 9 3 7 5 6 4 8 2
我們是想按照奇數偶數進行分組，目的達到了。但是還不夠完美，因為每個分區部分的元素與之前相比，相對位置變化了。
這個時候，就需要更穩定的算法了，直接上代碼了，運行結果對比的非常明顯：
stable_partition
#include // std::cout
#include // std::partition
#include // std::vector
bool IsOdd(int i) { return (i % 2) == 1; }
int main() {
std::vector myvector;
// set some values:
for (int i = 1; i<10; ++i)
myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
std::vector::iterator bound;
bound = std::partition(myvector.begin(), myvector.end(), IsOdd);
// print out content:
std::cout << "odd elements:";
for (std::vector::iterator it = myvector.begin(); it != bound; ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "even elements:";
for (std::vector::iterator it = bound; it != myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "Now myvector is: ";
for (auto it = myvector.begin(); it != myvector.end(); it++)
{
std::cout << ' ' << *it;
}
std::cout << std::endl;
std::cout << "Now let us " << std::endl;
std::vector myvector2;
// set some values:
for (int i = 1; i<10; ++i)
myvector2.push_back(i); // 1 2 3 4 5 6 7 8 9
std::vector::iterator bound2;
bound2 = std::stable_partition(myvector2.begin(), myvector2.end(), IsOdd);
// print out content:
std::cout << "odd elements:";
for (std::vector::iterator it = myvector2.begin(); it != bound2; ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "even elements:";
for (std::vector::iterator it = bound2; it != myvector2.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "Now myvector is: ";
for (auto it = myvector2.begin(); it != myvector2.end(); it++)
{
std::cout << ' ' << *it;
}
std::cout << std::endl;
return 0;
}
//輸出：
//odd elements : 1 9 3 7 5
//even elements : 6 4 8 2
//Now myvector is : 1 9 3 7 5 6 4 8 2
//Now let us
//odd elements : 1 3 5 7 9
//even elements : 2 4 6 8
//Now myvector is : 1 3 5 7 9 2 4 6 8
現在開始介紹C++11新增的。
is_partitioned
原型：
template
bool is_partitioned (InputIterator first, InputIterator last, UnaryPredicate pred);
作用：
Test whether range is partitioned
Returns true if all the elements in the range [first,last) for which pred returns true precede those for which it returns false.
應用：
#include // std::cout
#include // std::partition
#include // std::vector
bool IsOdd(int i) { return (i % 2) == 1; }
int main() {
std::vector myvector;
// set some values:
for (int i = 1; i<10; ++i)
myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
std::vector::iterator bound;
bound = std::partition(myvector.begin(), myvector.end(), IsOdd);
// print out content:
std::cout << "odd elements:";
for (std::vector::iterator it = myvector.begin(); it != bound; ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "even elements:";
for (std::vector::iterator it = bound; it != myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "Now myvector is: ";
for (auto it = myvector.begin(); it != myvector.end(); it++)
{
std::cout << ' ' << *it;
}
std::cout << std::endl;
std::cout << "Now let us use stable_partition:" << std::endl;
std::vector myvector2;
// set some values:
for (int i = 1; i<10; ++i)
myvector2.push_back(i); // 1 2 3 4 5 6 7 8 9
std::vector::iterator bound2;
bound2 = std::stable_partition(myvector2.begin(), myvector2.end(), IsOdd);
// print out content:
std::cout << "odd elements:";
for (std::vector::iterator it = myvector2.begin(); it != bound2; ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "even elements:";
for (std::vector::iterator it = bound2; it != myvector2.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "Now myvector is: ";
for (auto it = myvector2.begin(); it != myvector2.end(); it++)
{
std::cout << ' ' << *it;
}
std::cout << std::endl;
std::cout << "Now, let us use is_partitioned on myvector2:" << std::endl;
if (std::is_partitioned(myvector2.begin(), myvector2.end(), IsOdd))
std::cout << " (partitioned)\n";
else
std::cout << " (not partitioned)\n";
std::cout << "Now, let us use is_partitioned on en empty vector:" << std::endl;
std::vector myvector3;
if (std::is_partitioned(myvector3.begin(), myvector3.end(), IsOdd))
std::cout << " (partitioned)\n";
else
std::cout << " (not partitioned)\n";
return 0;
}
//輸出：
odd elements : 1 9 3 7 5
even elements : 6 4 8 2
Now myvector is : 1 9 3 7 5 6 4 8 2
Now let us use stable_partition :
odd elements : 1 3 5 7 9
even elements : 2 4 6 8
Now myvector is : 1 3 5 7 9 2 4 6 8
Now, let us use is_partitioned on myvector2 :
(partitioned)
Now, let us use is_partitioned on en empty vector :
(partitioned)
從輸出結果看，我們需要明確：
If the range is empty, the function returns true.
上面的幾個算法，不管如何折騰，都是在一個vector進行的，結果也還是在一個vector中，於是C++11新增了這個：
partition_copy
原型：
template
pair
partition_copy (InputIterator first, InputIterator last,
OutputIterator1 result_true, OutputIterator2 result_false,
UnaryPredicate pred);
作用：
Copies the elements in the range [first,last) for which pred returns true into the range pointed by result_true, and those for which it does not into the range pointed by result_false.
應用：
#include // std::cout
#include // std::partition_copy, std::count_if
#include // std::vector
bool IsOdd(int i) { return (i % 2) == 1; }
int main() {
std::vector foo{ 1,2,3,4,5,6,7,8,9 };
std::vector odd, even;
// resize vectors to proper size:
unsigned n = std::count_if(foo.begin(), foo.end(), IsOdd);
odd.resize(n); even.resize(foo.size() - n);
// partition:
std::partition_copy(foo.begin(), foo.end(), odd.begin(), even.begin(), IsOdd);
// print contents:
std::cout << "odd: "; for (int& x : odd) std::cout << ' ' << x; std::cout << '\n';
std::cout << "even: "; for (int& x : even) std::cout << ' ' << x; std::cout << '\n';
return 0;
}
//輸出：
//odd: 1 3 5 7 9
//even : 2 4 6 8
接下來剩最後一個：
partition_point
從算法名字就能略知一二，於是直接上代碼示例：
#include // std::cout
#include // std::partition, std::partition_point
#include // std::vector
bool IsOdd(int i) { return (i % 2) == 1; }
int main() {
std::vector foo{ 1,2,3,4,5,6,7,8,9 };
std::vector foo2{ 1,2,3,4,5,6,7,8,9 };
std::vector odd;
std::vector odd2;
std::partition(foo.begin(), foo.end(), IsOdd);
auto it = std::partition_point(foo.begin(), foo.end(), IsOdd);
odd.assign(foo.begin(), it);
auto bound = std::partition(foo2.begin(), foo2.end(), IsOdd);
for (std::vector::iterator it = foo2.begin(); it != bound; ++it)
odd2.push_back(*it);
//odd2.assign(foo.begin(), bound);
// print contents of odd:
std::cout << "odd:";
for (int& x : odd) std::cout << ' ' << x;
std::cout << '\n';
std::cout << "odd2:";
for (int& x : odd2) std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
因此：
partition_point
Returns an iterator to the first element in the partitioned range [first,last) for which pred is not true, indicating its partition point.
個人覺得這個算法用處不大。
個人覺得主要應用於已經partition的range上還算有優勢！
