std::partition
来自cppreference.com
 |
该页由英文版wiki使用Google Translate机器翻译而来。
该翻译可能存在错误或用词不当。鼠标停留在文本上可以看到原版本。你可以帮助我们修正错误或改进翻译。参见说明请点击这里. |
| 定义于头文件 <algorithm>
|
||
| template< class BidirIt, class UnaryPredicate > BidirectionalIterator partition( BidirIt first, BidirIt last, |
(C++11 前) (C++11 起) |
|
重排[first, last)区间内的元素，使得对于谓词p返回true的元素排在返回false的元素之前。这个重排是不稳定的。
目录 |
[编辑] 参数
| first, last | - | 要重排的元素的区间 |
| p | - | 如果当前元素排在其他元素之前则返回 true 的一元谓词。 谓词函数签名应等价于如下者： bool pred(const Type &a); 签名不必拥有 const & ，但函数必须不修改传递给它的对象。 |
| 类型要求 | ||
-BidirIt 必须满足 BidirectionalIterator 的要求。
| ||
-ForwardIt 必须满足 ValueSwappable 和 ForwardIterator 的要求。However, the operation is more efficient if ForwardIt also satisfies the requirements of BidirectionalIterator
| ||
[编辑] 返回值
指向第二组（返回false的那组）的第一个元素的迭代器
[编辑] 复杂度
last-first次谓词调用，以及最多last-first次交换。如果ForwardIt还满足BidirectionalIterator的要求，那么最多只要(last-first)/2次交换。
[编辑] 可能的实现
template<class BidirIt, class UnaryPredicate> BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p) { while (1) { while ((first != last) && p(*first)) { ++first; } if (first == last--) break; while ((first != last) && !p(*last)) { --last; } if (first == last) break; std::swap(*first++, *last); } return first; } |
[编辑] 示例
运行此代码
#include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <vector> bool is_even(int i) { return i % 2 == 0; } int main() { std::vector<int> v; for (int i = 0; i < 10; ++i) v.push_back(i); std::cout << "Original vector:\n "; std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); // Partition the vector std::vector<int>::iterator p = std::partition(v.begin(), v.end(), std::ptr_fun(is_even)); std::cout << "\nPartitioned vector:\n "; std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << "\nBefore partition:\n "; std::copy(v.begin(), p, std::ostream_iterator<int>(std::cout, " ")); std::cout << "\nAfter partition:\n "; std::copy(p, v.end(), std::ostream_iterator<int>(std::cout, " ")); }
可能的输出：
Original vector:
0 1 2 3 4 5 6 7 8 9
Partitioned vector:
0 8 2 6 4 5 3 7 1 9
Before partition:
0 8 2 6 4
After partition:
5 3 7 1 9[编辑] 另请参阅
| (C++11) |
判断区间是否被给定的谓词划分 (函数模板) |
| 将元素分为两组，同时保留其相对顺序 (函数模板) |
