Разница векторов при сохранении порядка

Question

Разница векторов при сохранении порядка

У меня два char векторы говорят {'G', 'K', 'A', 'L', 'P'} а также {'K', 'P', 'T', 'M'}, Я должен получить разницу между этими двумя векторами, сохраняя порядок, т.е. {'G', 'A', 'L'},

Я в курсе std::set_difference функция, но это не может быть использовано, так как это потребует сортировки векторов. Есть ли оптимизированный способ сделать это в C ++?

4

c++c++11 set-difference string vector

Решение

Другие решения

Ручное решение:

std::vector<char> a{'G','K','A','L','P'};
std::vector<char> b{'K','P','T','M'};
std::vector<char> result;

for(auto const& item:a){
if(std::find(std::begin(b),end(b),item)==std::end(b)){
result.push_back(item)
}
}

0

Источник

Accepted Answer

Вы можете сделать std::set только из второго вектора, чтобы получить сложность логарифмического поиска, затем выполнить итерацию по первому вектору, нажав на результирующий вектор, если элемент не найдено в комплекте:

#include <iostream>
#include <vector>
#include <set>
#include <iterator>
#include <algorithm>

int main()
{
std::vector<char> a = {'G', 'K', 'A', 'L', 'P'};
std::vector<char> b = {'K', 'P', 'T', 'M'};
std::vector<char> result;

std::set<char> s(b.begin(), b.end());

std::copy_if(a.begin(), a.end(), std::back_inserter(result),
[&s](char elem) { return s.find(elem) == s.end(); });

for(auto elem : result)
std::cout << elem << ", ";

return 0;
}

Жить на Колиру

Если хотите вычесть только количество значений, найденных во втором векторе, переделать это с std::multisetгде вы также erase элемент в наборе, если найден:

std::copy_if(a.begin(), a.end(), std::back_inserter(result), [&s](char elem)
{
auto it = s.find(elem);

if(it == s.end())
return true;

s.erase(it);
return false;
});

Обратите внимание, что приведенное выше удалит первые вхождения и сохранит последующие.

std::copy_if(a.rbegin(), a.rend(), ...

будет делать обратное, но это также даст вам обратный вывод.

8