当前位置：首页 -> 基础 -> c++编程基础

C++ 算法库(3) 划分操作(一)

2014-11-24 08:21:32 · 作者: · 浏览: 2
标签: 算法 划分 操作
划分操作：
is_partitioned C++11 检测某个范围是否按指定谓词划分过
partition 将某个范围划分为两组
partition_copy C++11 拷贝指定范围的划分结果
partition_point C++11 返回被划分范围的划分点
stable_partition 稳定划分，两组元素各维持相对顺序

is_partitioned

检测某个范围是否按指定谓词划分过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// is_partitioned example
#include // std::cout
#include // std::is_partitioned
#include // std::array

bool IsOdd (int i) { return (i%2)==1; }

int main () {
std::array foo {1,2,3,4,5,6,7};

// print contents:
std::cout << "foo:"; for (int& x:foo) std::cout << ' ' << x;
if ( std::is_partitioned(foo.begin(),foo.end(),IsOdd) )
std::cout << " (partitioned)\n";
else
std::cout << " (not partitioned)\n";

// partition array:
std::partition (foo.begin(),foo.end(),IsOdd);

// print contents again:
std::cout << "foo:"; for (int& x:foo) std::cout << ' ' << x;
if ( std::is_partitioned(foo.begin(),foo.end(),IsOdd) )
std::cout << " (partitioned)\n";
else
std::cout << " (not partitioned)\n";

return 0;
}

输出：

1
2
foo: 1 2 3 4 5 6 7 (not partitioned)
foo: 1 7 3 5 4 6 2 (partitioned)

partition

将某个范围划分为两组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// partition algorithm example
#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';

return 0;
}

输出：

1
2
odd elements: 1 9 3 7 5
even elements: 6 4 8 2

partition_copy

拷贝指定范围的划分结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// partition_copy example
#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;
}

输出：

1
2
odd: 1 3 5 7 9
even: 2 4 6 8

partition_point

返回被划分范围的划分点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// partition_point example
#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 odd;

std::partition (foo.begin(),foo.end(),IsOdd);

auto it = std::partition_point(foo.begin(),foo.end(),IsOdd);
odd.assign (foo.begin(),it);

// print contents of odd:
std::cout << "odd:";
for (int& x:odd) std::cout << ' ' << x;
std::cout << '\n';

return 0;
}

输出：

1
odd: 1 3 5 7 9

stable_partition

稳定划分，两组元素各维持相对顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// stable_partition example
#include // std::cout
#include // std::stable_partition
#include // std::vector

bool IsOdd (int i) { return (i%2)==1; }

int main () {
std::vector myvector;

// set so