CODEWITHSUNDEEP
c++visual-c++stl
daiyue
daiyue

Reputation: 7448

remove elements of a vector from another vector

I have two vectors of XML DOM nodes:

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

B is a subset of A. I want to remove B from A and I also want to preserve the order of A, so that if an element in A is removed it is replaced with a blank element. It would look like this:

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

The remove_if function from <algorithm> may do the job, but i don't know how to code the predicate function here. Does anyone know what the predicate function should look like?

update:

I tried the following code:

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 and vecTempItemSet are all of vectors of IXMLDOMNodePtr but i got the following errors:

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>          ]

Upvotes: 1

Views: 4025

Answers (2)

memetech
memetech

Reputation: 1049

I doubt there is a perfect algorithm for you in the standard library. The amount of work depends on whether the two vectors are pre-sorted or not, or if you can sort them.

If you cannot sort your vectors, then you are left in O(n^2) territory, since for each element in B to be removed from A, you have to search A once over to find it.

A good sort is O(n lg n), so pre-sorting is faster than not sorting them, in general.

If performance is not an issue, the brute force approach is 

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

If the two vectors are sorted, perhaps better to iterate through them in parallel

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;
}

In this loop, we hold two iterators into B and A. We move A forward while it is less than B - therefore we know there are no elements before this in A that exist in B, because they are sorted. We move B forward if the inverse is true. If they match, we zero the element per your question.

Upvotes: 2

Kerrek SB
Kerrek SB

Reputation: 477060

If you guarantee that B is an ordered subsequence of A, you could write this yourself:

auto j = B.begin();
for (auto i = A.cbegin(); i != A.cend(); ++i)
{
  if (*i == *j) { *i = blank; ++j; }
}
assert(j == B.end());

OK, for the general case, where B isn't necessarily in the correct order. Using predicates is no good, because the predicate must have a const call, and we need to manipulate the object (or some other state variable). So let's try a variation of the above instead:

auto j = B.begin();

std::set<size_t> Bindices;
for (size_t i = 0; i < B.size(); ++i) { Bindices.insert(Bindices.end(), i); }

for (auto i = A.cbegin(); i != A.cend(); ++i)
{
  for (auto k = Bindices.begin(); k != Bindices.end(); ++k)
  {
    if (*i == B[*k]) { *i = blank; Bindices.erase(k); break; }
  }
}

assert(Bindices.empty());

Upvotes: 1

Related Questions