C++ 标准库方法删除列表中满足条件的一对项目中的一个

Question

假设您有一个 std::list其中包含一组值。为了演示起见，我们会说它只是 std::list<int> ，但在我的例子中，它们实际上是二维点。无论如何，我想删除一对中的一个 int满足某种距离标准的 s(或点)。我的问题是如何将其作为不超过 O(N^2) 操作的迭代来处理。

示例

源是int的列表包含:

{ 16, 2, 5, 10, 15, 1, 20 }

如果我给它一个距离标准 1 (即列表中的任何项目都不应在任何其他项目的 1 范围内)，我想生成以下输出:

{ 16, 2, 5, 10, 20 }如果我向前迭代或

{ 20, 1, 15, 10, 5 }如果我向后迭代

我觉得一定有一些很棒的方法可以做到这一点，但我被这个迭代器的双循环困住了，并试图在遍历列表时删除项目。

Answer 1

制作“区域” map ，基本上是 std::map<coordinates/len, std::vector<point>> . 将每个点添加到它的区域，以及 8 个相邻区域中的每一个 O(N*logN) .在每个较小的列表上运行“nieve”算法(技术上 O(N^2) 除非有最大密度，否则它变为 O(N*density) )。最后:在您的原始列表中，遍历每个 point , 如果它已从 任何 它被放入的 8 个迷你列表中删除，则将其从列表中删除。 O(n)

没有密度限制，这是O(N^2) ，而且很慢。但是，点分布得越多，这种情况就会变得越来越快。如果这些点在已知边界内稍微均匀分布，您可以切换到二维数组，从而显着更快，并且如果密度有恒定限制，技术上 em> 使它成为 O(N)算法。

顺便说一句，这就是您对两个变量的列表进行排序的方式。 grid/map/2dvector 的东西。

[编辑] 你提到你在使用“nieve”方法时也遇到了麻烦，所以就是这样:

template<class iterator, class criterion>
iterator RemoveCriterion(iterator begin, iterator end, criterion criter) {
    iterator actend = end;
    for(iterator L=begin; L != actend; ++L) {
        iterator R(L);
        for(++R; R != actend;) {
            if (criter(*L, *R) {
                iterator N(R); 
                std::rotate(R, ++N, actend);
                --actend;
            } else
                ++R;
        }
    }
    return actend;
}

这应该适用于链表、 vector 和类似的容器，反之亦然。不幸的是，由于没有考虑链表的属性，它有点慢。有可能制作出只在特定方向的链表上运行的更快的版本。很多。请注意，返回值很重要，就像其他变异算法一样。它只能更改容器的内容，不能更改容器本身，因此您必须在完成时清除返回值之后的所有元素。