удалить элементы вектора из другого вектора

Question

У меня есть два вектора узлов XML DOM:

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

B - это подмножество A. Я хочу удалить B из A, а также сохранить порядок 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 но я получил следующие ошибки:

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

Я сомневаюсь, что в стандартной библиотеке для вас есть идеальный алгоритм. Объем работы зависит от того, предварительно отсортированы два вектора или нет, или вы можете отсортировать их.

Если вы не можете отсортировать свои векторы, то вы остаетесь на территории O (n ^ 2), поскольку для удаления каждого элемента в B из A вам придется искать 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);

Если два вектора отсортированы, возможно, лучше перебрать их параллельно

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 нет элементов, которые существуют в B, потому что они отсортированы. Мы перемещаем B вперед, если верно обратное. Если они совпадают, мы обнуляем элемент по вашему вопросу.

Answer 2

Если вы гарантируете, что B является упорядоченной подпоследовательностью A, вы можете написать это самостоятельно:

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

---

ОК, для общего случая, где B не обязательно в правильном порядке. Использование предикатов бесполезно, потому что предикат должен иметь вызов const , и нам нужно манипулировать объектом (или некоторой другой переменной состояния). Итак, давайте попробуем вариант выше:

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());