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

Question

想象一下,你有std::list一组值.为了示范,我们会说它只是std::list<int>,但就我而言,它们实际上是2D点.无论如何,我想删除满足某种距离标准的一对 int s(或点)中的一个.我的问题是如何将此作为迭代,而不是O(N ^ 2)操作.

例

Source是一个int包含以下内容的列表:

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

如果我给出了这个距离标准1(即列表中的项目不应该在1任何其他项目中),我想产生以下输出:

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

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

我觉得必须有一些很棒的方法来做到这一点,但我坚持使用这个迭代器的双循环并尝试在迭代列表时擦除项目.

Answer 1

制作“区域”地图，基本上是一个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)，而且很慢。但点越分散，这个速度就会变得越来越快。如果这些点在已知边界上稍微均匀地分布，您可以切换到二维数组，从而显着加快速度，并且如果密度有恒定的限制，从技术上讲，这使其成为一种O(N)算法。

顺便说一下，这就是对两个变量的列表进行排序的方法。网格/地图/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;
}

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