我想迭代 vector 的所有元素，并为每个元素检查 vector 的所有其他元素的条件。

逻辑:

Precondition: q is not in vector

for every x,y in vector
    if d(x, y) <= d(x, q) && d(x, q) <= d(y, q) then
        eliminate x, y

一种方法:

for(vector<Point_d>::iterator it = candidates.begin(); it != candidates.end(); ++it){

    for (vector<Point_d>::iterator it2 = candidates.begin(); it2 != candidates.end(); ++it2) {

        if(dist.transformed_distance(*it, *it2) <=  dist.transformed_distance(*it, q)
                && dist.transformed_distance(*it, q) <= dist.transformed_distance(*it2, q)){

            /* Remove x,y without invalidate the iterators */
        }
    }

}

我知道如果我在循环中删除一个元素，迭代器将失效。有没有什么方法可以用 Erase-Remove Idiom 来做到这一点，或者有没有其他方法可以做到这一点？我搜索了很多，找到了各种我可以组合起来使其工作的部分，即通过从 for 循环中删除迭代器并使用 erase 和 remove_if，但我无法弄清楚，而且因为我是新手c++ 和 STL 我想听听更好的方法。

编辑

此外，如果可能的话，我不想为相同的元素做条件，即 d(x, x) <= d(x, q) .

最佳答案

如果您按照以下代码改用索引，您的工作可能会更容易。我有一个稍微修改过的 live demo这表明这是有效的。 (我将 dist 函数替换为仅返回 abs(x-y) 整数的函数)。

for(size_t i=0; i<candidates.size();){

    bool deleted = false;

    for (size_t j = 0; j < candidates.size();) {

        if(i==j) {
             ++j;
             continue;
        }

        if(dist.transformed_distance(candidates[i], candidates[j]) <=  dist.transformed_distance(candidates[i], q)
                && dist.transformed_distance(candidates[i], q) <= dist.transformed_distance(candidates[j], q)){

            bool dec_i = false;

            if(i < j) --j;
            else dec_i = true;

            candidates.erase(std::next(candidates.begin(), i));                
            candidates.erase(std::next(candidates.begin(), j));            

            if(dec_i) --i;
            deleted = true;
            break;
        }
        else 
            ++j;
    }
    if(!deleted)
        ++i;
}

请注意，您可以有一个替代实现，在第一遍中标记要删除的元素，然后删除它们。在这种情况下，行为是不同的:因为元素没有被删除，它们仍然被考虑用于以后的对匹配。因此，单个元素可以与多个其他元素配对以进行删除，最终可能会删除比上述更多的元素。这次成本是 O(n^2) 而不是 O(n^3)。现场演示 here :

std::vector<int> deleteIndices;
deleteIndices.reserve(candidates.size());

for(size_t i=0; i<candidates.size(); ++i){

    for (size_t j = 0; j < candidates.size(); ++j) {

        if(i==j) {
             continue;
        }

        if(dist.transformed_distance(candidates[i], candidates[j]) <=  dist.transformed_distance(candidates[i], q)
                && dist.transformed_distance(candidates[i], q) <= dist.transformed_distance(candidates[j], q)){
            deleteIndices.push_back(i);
            deleteIndices.push_back(j);    
        }
    }
}

std::sort(deleteIndices.begin(), deleteIndices.end());
auto unique_end = std::unique(deleteIndices.begin(), deleteIndices.end());

//I'm using this complicated thing as the template param just because I don't know what your element type is
std::vector<std::remove_reference_t<decltype(candidates[0])>> output;
output.reserve(candidates.size() - deleteIndices.size());

auto it = deleteIndices.begin();
auto i = 0;
std::copy_if(candidates.begin(), candidates.end(), std::back_inserter(output), [&it,&i,unique_end](int elem)
    { 
        if(it==unique_end) { 
            ++i; 
            return true; 
        } 
        if(i == *it) { 
            ++i; 
            ++it; 
            return false; 
        } 
        ++i; 
        return true; 
    });

关于c++ - Nested loop of same vector - Erase–remove 成语，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37830190/