c++ - 在 CPP 中删除重叠对象

Question

我有一个名为 shape1->overlaps(shape2) 的方法和一个形状 vector 。

我必须删除在我的形状 vector 内重叠的所有形状。我目前不知道该怎么做，我不确定为什么这段代码不起作用。

for (vector<Shape *>::iterator it = shapes->begin(); it != shapes->end();){
        for (vector<Shape *>::iterator jt = it + 1; jt != shapes->end();){
            // If the shapes are not the same
            if (*it != *jt){
                // Check if they overlap, if they do remove them.
                if ((*it)->overlaps(*jt)){
                    // Print the overlapping shapes
                    printShapeInfo(*jt);
                    jt = shapes->erase(jt);
                } else {
                    ++jt;
                }
            } else {
                ++jt;
            }

        }
        printShapeInfo(*it);
        it = shapes->erase(it);
        ++it;
    }

我得到的错误是: vector 迭代器在运行时在 Visual Studio 中不可递增。

Answer 1

一些建议:

首先，对于外部循环，使用常规循环索引，而不是迭代器。

原因是您在循环时更改了 vector 的内容和大小。更改内容意味着您现在用来循环的迭代器将失效。在这方面使用普通索引要容易得多。

其次，对于内部循环，摆脱它并使用一个(或两个)算法函数来找出被删除的内容。所以基本上，你有一个循环。

这里有一个版本(未测试)可能会模仿您正在尝试做的事情。请注意，我不得不模拟你的类(class)以试图展示正在发生的事情:

#include <vector>
#include <algorithm>
//...
class Shape
{
    public:
        bool overlaps(Shape *s) { return true; }
        bool operator==(const Shape& s) { return true; }
        bool operator!=(const Shape& s) { return false; }
};

void printShapeInfo(Shape& s) {}

void foo(std::vector<Shape*>* shapes)
{
    // use a regular index here
    for (size_t i = 0; i < shapes->size(); ++i)
    {
        // get our starting point     
        auto it = shapes->begin() + i;

        // point to the next item after the i'th item.
        auto it2 = shapes->begin() + i + 1;

        // partition the objects.  Collided ones go on the left of the partition,
        // others go to the right of the partition.
        auto div = 
              std::stable_partition(it2, shapes->end(), 
               [&](Shape* s){ return (*s != *(*it2))?s->overlaps(*it2):false;});

        // check if there is anything on left side of partition
        if ( it2 != div ) 
        {
            // for each of the collided ones, print stuff out
              std::for_each(it2, div, [&](Shape *s){ printShapeInfo(*s); });

            // we're done with them, now erase them.
              shapes->erase(it2, div);

            // also erase the iterator we collided with
              shapes->erase(it);
         }
    }
}

做了什么？我们使用了 std::stable_partition将碰撞的元素移动到 vector 的一侧，其中 div 是碰撞和非碰撞项目之间的分界线。

这让我们有机会为每个项目调用 printShapeInfo。然后我们最终使用 vector::erase 从 vector 中删除它们。

请注意，此实现消除了(希望如此)迭代器失效错误。当给定正确的参数时，算法功能只是“工作”。您也看不到试图重新安装迭代器的棘手代码。对于序列容器，几乎没有理由编写遍历容器并同时从容器中删除的循环。

同样，这没有经过测试，但您应该了解所做的事情的要点。