std::
partition
函数模板 <algorithm>
C++98 |
template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first,
BidirectionalIterator last, UnaryPredicate pred); |
C++11 |
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition (ForwardIterator first,
ForwardIterator last, UnaryPredicate pred); |
范围分区为二
随机重新排列[first,last)范围内的元素。
重新排列范围[first,last]中的元素,使pred返回true的所有元素先于返回false的所有元素。
迭代器返回指向第二组的第一个元素的点。
每个组中的相对顺序不一定与调用之前相同。
请参阅stable_partition查看具有类似行为但在每个组中具有稳定顺序的函数。
这个函数模板 (C++98)的行为相当于:
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) return first;
} while (!pred(*last));
swap (*first,*last);
++first;
}
return first;
} |
☲ 参数
-
first, last
-
C++98: 指向分区序列的初始和最终位置的双向迭代器。使用的范围是[first,last),
它包含first和last1之间的所有元素,包括first指向的元素,但不包括last指向的元素。
C++11: 指向分区序列的初始和最终位置的前向迭代器.使用的范围是[first,last),
它包含first和last之间的所有元素,包括first指向的元素,但不包括last指向的元素。
前向迭代器(ForwardIterator)必须指向一个定义了swap的类型,并交换其实参的值。
-
pred
-
一个一元函数,它接受范围中的一个元素作为参数,并返回一个可转换为bool的值。
返回的值指示是否将该元素放在前面(如果为真,则将其放在所有返回false的元素之前)。
函数不应修改其参数。
它可以是函数指针,也可以是函数对象。
☉ 返回值
指向第二组元素(pred返回false的元素)的第一个元素的迭代器,如果这组元素为空,则指向最后一个元素。
☣ 示例
// partition algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::partition
#include <vector> // std::vector
bool IsOdd (int i) { return (i%2)==1; }
int main () {
std::vector<int> 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<int>::iterator bound;
bound = std::partition (myvector.begin(), myvector.end(), IsOdd);
// print out content:
std::cout << "odd elements:";
for (std::vector<int>::iterator it=myvector.begin(); it!=bound; ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "even elements:";
for (std::vector<int>::iterator it=bound; it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
} |
可能输出:
odd elements: 1 9 3 7 5
even elements: 6 4 8 2
✥ 复杂度
first and last 之间的距离线性: 对每个元素应用pred,并可能交换其中一些元素
(如果迭代器类型是双向的,最多交换量的一半)。
⇄ 数据竞争
在[first,last)范围内的对象被修改。
☂ 异常安全性
如果元素交换或迭代器上的操作抛出,则抛出。
注意,无效的参数会导致未定义的行为。
🍄 另请参阅
rotate |
旋转元素(函数模板) |
reverse |
反转元素(函数模板) |
find_if |
在范围内查找元素(函数模板) |
swap |
交换两个对象的值(函数模板) |