c++ - 从一个 vector 中移除另一个 vector 的元素

Question

我有两个 XML DOM 节点 vector :

vector<IXMLDOMNodePtr> A; //filled in somehow
vector<IXMLDOMNodePtr> B; //filled in somehow

B 是 A 的子集。我想从 A 中删除 B，并且我还想保留 A 的顺序，这样如果删除 A 中的元素，它就会被替换为空白元素。它看起来像这样:

node1||blank||node2||...

remove_if来自 <algorithm> 的函数可以完成这项工作，但我不知道如何在这里编写谓词函数。有谁知道谓词函数应该是什么样子？

更新:

我尝试了以下代码:

static MSXML2::IXMLDOMNodePtr transformIfInB(const vector<MSXML2::IXMLDOMNodePtr>& B,     MSXML2::IXMLDOMNodePtr ptr){return find(B.begin(), B.end(), ptr) != B.end() ? 0 : ptr;
}};

std::transform(vecCurRowItemSet.begin(),vecCurRowItemSet.end(),vecCurRowItemSet.begin(),std::bind1st(transformIfInB, vecTempItemSet));

vecCurRowItemSet 和 vecTempItemSet 都是 IXMLDOMNodePtr 的 vector 但我收到以下错误:

c:\Program Files\Microsoft Visual Studio 10.0\VC\include\xfunctional(278): error C2825:     '_Fn2': must be a class or namespace when followed by '::'
1>          XMLDOMFromVCDlg.cpp(4161) : see reference to class template instantiation     'std::binder1st<_Fn2>' being compiled
1>          with
1>          [
1>              _Fn2=MSXML2::IXMLDOMNodePtr (const std::vector<MSXML2::IXMLDOMNodePtr>     &,MSXML2::IXMLDOMNodePtr)
1>          ]

Answer 1

我怀疑标准库中是否有适合您的完美算法。工作量取决于这两个 vector 是否已预先排序，或者您是否可以对它们进行排序。

如果您无法对 vector 进行排序，那么您将处于 O(n^2) 范围内，因为要从 A 中删除 B 中的每个元素，您必须对 A 进行一次搜索才能找到它。

一个好的排序是 O(n lg n)，所以一般来说，预排序比不排序要快。

如果性能不是问题，那么蛮力方法就是

IXMLDOMNodePtr transformIfInB(IXMLDOMNodePtr ptr) { return find(B.begin(),B.end(), ptr) != B.end() ? 0 : ptr; }
...
std::transform(A.begin(),A.end(),A.begin(),transformIfInB);

如果这两个 vector 已排序，或许最好并行遍历它们

typedef std::vector<IXMLDOMNodePtr>::iterator vecIt;
vecIt itA, itB;
std::sort(A.begin(),A.end()); 
std::sort(B.begin(),B.end());
for(itA = A.begin(), itB = B.begin(); itB != B.end() && itA != A.end(); )
{
  if(*itA < *itB) ++itA; 
  else if(*itA == *itB) *itA++ == 0;
  else if(*itA > *itB ) ++itB;
}

在这个循环中，我们持有 B 和 A 中的两个迭代器。当 A 小于 B 时，我们将 A 向前移动 - 因此我们知道 A 之前的元素不存在于 B 中，因为它们已排序。如果反转为真，我们将 B 向前移动。如果它们匹配，我们会根据您的问题将元素归零。