使用remove_if从C++向量中按索引删除

Question

在C++中，我们可以使用remove_if函数根据一个操作元素的谓词，在线性时间内从向量中移除元素。

bool condition(double d) {...}

vector<double> data = ...
std::remove_if (data.begin(), data.end(), condition);

如果我的条件不依赖于值，而是依赖于索引呢？换句话说，如果我想删除所有奇数索引元素，或一些任意的索引集合等等？

bool condition(int index) {//returns whether this index should be removed}

vector<double> data = ...
std::remove_if (data.begin(), data.end(), ???);

- donnyton

---

可能是根据索引删除向量元素的重复问题。 - user657267

Answer 1

你可以使用指针算术运算来找到谓词函数传递给std::remove_if的特定元素的索引：

std::remove_if(data.begin(), data.end(),
               [&data](const double& d) { return (&d - &*data.begin()) % 2); });

请注意，remove_if函数传递的是迭代器所指对象的引用（通过解引用迭代器获取），这在标准库的表106-迭代器要求中已经得到了保证。

- Tony Delroy

---

谢谢。你能解释一下为什么要使用&*data.begin()而不是只使用data.begin()吗？ - donnyton

@donnyton 因为 begin() 返回一个迭代器，但我们想将其与参数的地址（即指针）进行比较，因此需要进行 &* 转换。 - Tony Delroy

我认为标准并不保证这个方法会成功，因为它假设在谓词被应用之前，元素没有被移动或交换。标准只保证谓词正好被应用“last - first”次。据我所知，实现可以在应用谓词之前移动/交换元素，这样做很愚蠢，但符合标准。 - D Drmmr

@DDrmmr：还有一条规定是“为了确定数据竞争的存在，除非规范要求这样做，算法不得修改通过迭代器参数引用的对象。”- 为了最小化数据竞争，这种规定也应该禁止在谓词应用之前进行不必要的移动/交换（至少与容器的其他成员）。 - Tony Delroy

这仅适用于ContiguousIterator，而std::remove_if只需要ForwardIterator。 - Caleth

@Caleth：这是一个很好的观点，但问题非常明确地涉及向量。 - Tony Delroy

Answer 2

我其实只是为了这个问题注册了一个账号。使用awesomeyi的回答更加简洁明了。

int count = 0;
auto final = std::remove_if (data.begin(), data.end(), [&count](const double d) {
    return (count++) % 2;
});

标准确实指出谓词应该被精确地应用last - first次。remove_if与ForwardIterators一起工作。

这意味着谓词只能按照它们在序列中最初出现的顺序应用一次。

除非库在保留ForwardIterator的内部副本方面愚弄你。

- jonas simple

---

我相信实现允许做一些像遍历保留元素地址，然后在线程中应用谓词或使用一些并行指令之类的事情，所以我认为这不是特别安全的。 - Tony Delroy

Answer 3

利用 lambas 可以捕获变量的特性。以下是一个快速示例：

vector<double> data = {5, 3, 6, 7, 8};

int count = 0;
auto final = std::remove_if (data.begin(), data.end(), [&](const double d) {
    bool b = false;
    if(count % 2) b = true;
    ++count;
    return b;
});

for(auto beg = data.begin(); beg != final; ++beg)
    cout << *beg << endl;

代码将会输出：5 6 8

- yizzlez

---

这对 remove_if 应用谓词的顺序进行了假设，但标准文本并未保证这一点。 - Benjamin Lindley

Answer 4

一个类似于`std::remove_if`的算法，但是它的谓词函数接受索引作为参数。

template<class ForwardIt, class UnaryPredicate>
ForwardIt remove_indexes_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    ForwardIt dest = first;
    for(ForwardIt i = first; i != last; ++i)
        if (!p(std::distance(first, i)))
            *dest++ = std::move(*i);
    return dest;
}

- Caleth