3

Given 

std::vector<double> a;
std::vector<int> ind;

where ind is 1sorted in ascending order.

I want to do the equivalent of the following:

for (auto it=ind.rbegin();it!=ind.rend();it++) a.erase(a.begin() + *it);

I came up with this:

for (auto it=ind.begin();it!=ind.end();it++) 
   a[*it] = std::numeric_limits<double>::max();
std::erase(std::remove(a.begin(),a.end(),std::numeric_limits<double>::max()),a.end());

This is very fast, but it doesn't feel right to use the std::numeric_limits::max() as a flag in this context.

Of course feelings shouldn't play too much into the equation ... clearly comparing the doubles within the std::remove is safe, and the limit will never occur in practice in this vector in a working application, so it should be ok, no?

Any thoughts on this?

1) Ref comment by the OP. – Alf

4

1 回答 1

3

让我们看看你的“基线”代码，你说你想做的“等效”：

std::vector<double> a;
std::vector<int> ind;

for (auto it = ind.rbegin(); it != ind.rend(); it++)
    a.erase(a.begin() + *it);

我们从中收集到的是应该删除ind的索引向量，并且它们是按升序排序的。a这些索引必须从a. 我假设您的目标是在空间和时间方面有效地做到这一点。

如果您根据所需的最少操作数来考虑它，则必须移动许多/大多数/所有元素a才能删除ind. 您不想erase()多次，因为这意味着不止一次地移动某些元素。一种最佳解决方案（在一般情况下，不对 中的值施加特殊要求a）如下所示：

size_t slow = 0; // where we are currently copying "to"
std::vector<int> inditer = ind.begin();
for (size_t fast = 0; fast != a.size(); ++fast) {
    if (inditer != ind.end() && *inditer == fast) {
        // "remove" this element by ignoring it
        ++inditer;
    } else {
        a[slow] = a[fast];
        ++slow;
    }
}
a.resize(slow);

现在，您可能可以使用 STL 算法和一个自定义谓词（函子）重新表述它，它会记住它在 中的“当前”位置ind，但它的代码不会少很多，而且可能更难理解。

于 2015-02-17T09:11:42.480 回答