使用一个东西，不明白它的道理，不高明
——侯捷老师
1. partition()函数
将输入序列转换划分成两个部分,函数返回值是第二个部分的第一个元素的迭代器。
1.1. 函数声明
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition (ForwardIterator first,
ForwardIterator last,
UnaryPredicate pred);
1.2. 等价操作实现
template<class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition(BidirectionalIterator first,
BidirectionalIterator last,
UnaryPredicate pred)
{
while (first != last) {
while (pred(*first)) {
++first;
if (first == last) return first;
}
}
do {
--last;
if (first == last)
} while (!pred(*last));
swap(*first, *last);
++first;
}
return first;
}
1.3. 源码探究
partition()->std::__partition()->iter_swap()
partition()函数:
template<typename _ForwardIterator, typename _Predicate>
inline _ForwardIterator
partition(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred)
{
// concept requirements
__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
_ForwardIterator>)
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
return std::__partition(__first, __last, __pred,
std::__iterator_category(__first));
}
std::__partition()函数:
template<typename _BidirectionalIterator, typename _Predicate>
_BidirectionalIterator
__partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
_Predicate __pred, bidirectional_iterator_tag)
{
while (true)
{
while (true)
if (__first == __last)
return __first;
else if (__pred(*__first))
++__first;
else
break;
--__last;
while (true)
if (__first == __last)
return __first;
else if (!bool(__pred(*__last)))
--__last;
else
break;
std::iter_swap(__first, __last);
++__first;
}
}
iter_swap()函数:
template<typename _FIter1, typename _FIter2>
void
iter_swap(_FIter1, _FIter2);
1.4. 示例程式
void test_partition() {
vector<int> vec;
for (int i = 1; i <= 10; i++) {
vec.push_back(i);
}
vector<int>::iterator bound;
bound = std::partition(vec.begin(), vec.end(), [](int i) {
return i % 2 == 1;
});
cout << "Odd elements: ";
for (auto it = vec.begin(); it != bound; it++) {
cout << *it << " ";
}
cout << endl;
cout << "Even elements: ";
for (auto it = bound; it != vec.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
1.5 输出结果
image.png
参考链接：http://www.cplusplus.com/reference/algorithm/partition/
2. partition_copy()函数
将[first,last)区间里满足/不满足pred的分别拷贝到对应的区间
2.1 函数声明
template<class InputIterator, class OutputIterator1,
class OutputIterator2, class UnaryPredicate pred>
pair<OutputIterator1, OutputIterator2>
partition_copy(InputItertor first, InputIterator last,
OutputIterator1 result_true, OutputIterator2 result_false,
UnaryPredicate pred);
2.2 等价操作实现
template <class InputIterator, class OutputIterator1,
class OutputIterator2, class UnaryPredicate pred>
pair<OutputIterator1,OutputIterator2>
partition_copy (InputIterator first, InputIterator last,
OutputIterator1 result_true, OutputIterator2 result_false,
UnaryPredicate pred)
{
while (first!=last) {
if (pred(*first)) {
*result_true = *first;
++result_true;
}
else {
*result_false = *first;
++result_false;
}
++first;
}
return std::make_pair (result_true,result_false);
}
2.3 源码探究
template<typename _InputIterator, typename _OutputIterator1,
typename _OutputIterator2, typename _Predicate>
pair<_OutputIterator1, _OutputIterator2>
partition_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator1 __out_true, _OutputIterator2 __out_false,
_Predicate __pred)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
for (; __first != __last; ++__first)
if (__pred(*__first))
{
*__out_true = *__first;
++__out_true;
}
else
{
*__out_false = *__first;
++__out_false;
}
return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
}
2.4 示例程式
void test_partition_copy() {
vector<int> foo {1,2,3,4,5,6,7,8,9};
vector<int> odd, even;
int n = std::count_if(foo.begin(), foo.end(), [](int i) {
return i % 2 == 1;
});
odd.resize(n);
even.resize(foo.size() - n);
std::partition_copy(foo.begin(), foo.end(), odd.begin(), even.begin(), [](int i) {
return i % 2 == 1;
});
cout << "odd: ";
for (auto& x : odd) {
cout << x << " ";
}
cout <<endl;
cout << "even: ";
for (auto& x : even) {
cout << x << " ";
}
cout << endl;
}
2.5 输出结果
image.png
2.6 参考链接
http://www.cplusplus.com/reference/algorithm/partition_copy/
3. partition_point()函数
功能：返回指向第一个不是属于第一类序列的元素的迭代器
3.1 函数声明
template<class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point(ForwardIterator first, ForwardIteartor last,
UnaryPredicate pred);
3.2 等价操作实现
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred)
{
auto n = distance(first,last);
while (n>0)
{
ForwardIterator it = first;
auto step = n/2;
std::advance (it,step);
if (pred(*it)) { first=++it; n-=step+1; }
else n=step;
}
return first;
}
3.3 源码探究
template<typename _ForwardIterator, typename _Predicate>
_ForwardIterator
partition_point(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred)
{
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_ForwardIterator>::value_type>)
// A specific debug-mode test will be necessary...
__glibcxx_requires_valid_range(__first, __last);
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
_DistanceType __len = std::distance(__first, __last);
_DistanceType __half;
_ForwardIterator __middle;
while (__len > 0)
{
__half = __len >> 1;
__middle = __first;
std::advance(__middle, __half);
if (__pred(*__middle))
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
3.4 示例程式
void test_partition_point() {
vector<int> vec = {1,2,3,4,5,6,7,8,9};
std::vector<int> odd;
std::partition(vec.begin(), vec.end(), [](int i) {
return i % 2 == 1;
});
auto it = std::partition_point(vec.begin(), vec.end(), [](int i) {
return i % 2 == 1;
});
odd.assign(vec.begin(), it);
cout << "odd contains: ";
for (auto& x : odd) {
cout << x << " ";
}
cout << endl;
}
输出结果：
image.png
为何不是有序的？
3.5 参考链接
http://www.cplusplus.com/reference/algorithm/partition_point/
4. is_partitioned()函数
4.1 函数声明
template<class InputIterator, class UnaryPredicate>
bool is_partitioned(InputIterator first, InputIterator last, UnaryPredicate pred)
4.2 等价操作实现
template <class InputIterator, class UnaryPredicate>
bool is_partitioned (InputIterator first, InputIterator last, UnaryPredicate pred)
{
while (first!=last && pred(*first)) {
++first;
}
while (first!=last) {
if (pred(*first)) return false;
++first;
}
return true;
}
4.3 源码探究
template<typename _InputIterator, typename _Predicate>
inline bool
is_partitioned(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
{
__first = std::find_if_not(__first, __last, __pred);
return std::none_of(__first, __last, __pred);
}
none_of()函数：
template<typename _InputIterator, typename _Predicate>
inline bool
none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{ return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
find_if()函数
template<typename _InputIterator, typename _Predicate>
inline _InputIterator
find_if(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
return std::__find_if(__first, __last,
__gnu_cxx::__ops::__pred_iter(__pred));
}
4.4 示例程式
/**
template<class InputIterator, class UnaryPredicate>
bool is_partitioned(InputIterator first, InputIterator last, UnaryPredicate pred);
*/
bool IsOdd (int i) { return (i%2)==1; }
void test_is_partitioned() {
std::array<int,7> 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";
}
输出结果:
image.png
