稳定分区std::vector按元素原位置的奇偶校验

Question

我想根据元素在容器中的原始索引的奇偶性对 std::vector 进行分区。换句话说，我想把它分成两半：第一部分包含所有偶数索引元素，第二部分包含所有奇数索引元素。

元素之间的顺序关系无关紧要，重要的是在原始向量中的位置。

我想用 标准算法 和 lambda 实现这种效果，最好是在原位。我可以用常规的 for 循环来完成。

例子

让我们假设我们有一个元素向量 a b c d e f。所需的分区是 a c e b d f。第一个（a）、第三个（c）和第五个（e）元素移到前面，而第二个（b）、第四个（d) 和第六 (f) 个元素移到后面。

我的尝试

我有一个类似这个的对象：

struct T {
    int x;
};

我能够按这样的字段值对其进行分区：

std::vector<T> ts {{1}, {2}, {4}, {3}, {6}, {5}};
auto predicate = [](const T& t) {
    return t.x % 2 == 1;
};
std::stable_partition(ts.begin(), ts.end(), predicate);

结果是1 3 5 2 4 6。我想要分区 return 1 4 6 2 3 5.

我试图将 predicate 定义为

auto predicate = [](const std::vector<T>::const_iterator& t)
    return t->x % 2 == 1;
};

但它不编译，显然没有任何意义。

为了说明我的问题，我编写了一个 for 循环来执行此分区，尽管不是以稳定的方式进行。

for (auto i = ts.begin() + 1, j = ts.begin() + 2; j != ts.end(); i += 1, j += 2) {
    std::swap(*i, *j);
}

总结

是否可以使用 std 算法来实现，或者我是否需要求助于标准循环？

Answer 1

在c++11中，使用一个计数器作为索引来验证它是偶数还是奇数。

#include <iostream>
#include <vector>

struct T {
    int x;
};

int main()
{
    std::vector<T> ts {{1}, {2}, {4}, {3}, {6}, {5}};
    int counter =0;
    auto predicate = [&counter]() {
        ++counter;
        return (counter % 2 == 1);
    };
    std::stable_partition(ts.begin(), ts.end(), predicate);

    for(auto i: ts)
        std::cout << i.x << ", ";

}

Answer 2

向量将其数据存储在线性数组中。你可以利用这些知识。

将 lambda 作为捕获指向向量第一项的指针的谓词，并通过对 T 的引用获取其参数 ，以引用向量的原始存储元素。然后你可以通过简单的指针运算找出索引是否为even/odd：

struct T { int x; }; int main() { std::vector<T> ts {{1}, {2}, {4}, {3}, {6}, {5}}; auto pred = [beg = &(*ts.begin())](T& elem) { return (&elem-beg) % 2 == 0; }; std::stable_partition(ts.begin(), ts.end(), pred); for (T t : ts) std::cout << t.x << std::endl; // 1,4,6,2,3,5 }

稳定分区std::vector按元素原位置的奇偶校验

Stable partition std::vector by the parity of the element's original position

c++

algorithm

functional-programming

std

例子

我的尝试

总结