C++ 删除 vector 的某些元素

Question

我是 C++ 的新手，想做 vector 元素消除。

我的载体是这样的:

<vector<vector>> objPoints;
<vector<vector>> delPoints;
<vector<vector>> objPoints2;

每个 objPoints 的大小为 1000x3，并且包含所有点。我想从 objPoints 中删除 delPoints，即每行中的 (X,Y,Z) 值。

谁能告诉我语法？

Answer 1

我对您的问题的解释如下:您有两个 vector objPoints和 delPoints其中包含 1000 个三维点。我会将其编码为

std::vector<std::array<int,3> > objPoints;

我假设你有一些光栅，这样你就可以通过 int 描述你的点值(否则，对于 double 条目，比较并不那么容易)。

使用 std::array<int,3> 的一个好处是您自动获得点的字典顺序(这意味着 std::less 和 std::equal_to 的特化可以直接使用而无需进一步创建一些)。

---

算法:

首先对数组进行排序。可能存在并非真正必要的算法(请参阅@AshwaniDausodia 的其他答案)，但以下假设是这样。此外，通常通过使用排序的 vector 可以获得更好的性能(至少在 big-O 中:对于未排序的容器，它大约是 O(size1*size2) ，而对于以下算法则更低)。排序首先需要努力 O(size1 log(size1)) + O(size2 log(size2))

接下来，同时遍历两个数组，每次找到一个共同元素时，将其从其中一个 vector 中删除。当你遍历排序数组时，你总是只能增加指向较小元素的迭代器，这一步需要 O(size1+size2) .

---

实现:

// deletes the elements from container c1 which are also present in c2
// requires sorted containers c1 and c2
//
template< class ContainerType1, class ContainerType2 >
void delete_common_elements(ContainerType1& c1, ContainerType2 const& c2 )
{
    for(auto it1=c1.begin(), it2=c2.begin()
       ; it1!=c1.end() && it2!=c2.end(); )
    {
        if(*it1==*it2)  // eventually change here if your points are not int's
                        // but are of floating-point type
        {
             it1 = c1.erase(it1);  //it1 is increased here
        }
        else
        {
             *it1<*it2 ? ++it1 : ++it2;
        }
    }
}   

DEMO

总而言之，这需要 O(c1.size()) + O(c1.size() * log(c1.size()) 的努力(自然假设 c1.size()>=c2.size() )。

可以很容易地扩展它来采用任意比较运算符而不是 operator== .