Есть два трюка, которые я бы использовал, чтобы сделать это как можно быстрее:
Использовать некоторый ассоциативный контейнер (вероятно, std::unordered_set
) для хранения всех целых чисел ввторой вектор, чтобы значительно повысить эффективность поиска целого числа в первом векторе.
Оптимизировать способ удаления элементов из исходного вектора.
Более конкретно, я бы сделал следующее.Начните с создания std::unordered_set
и добавления всех целых чисел, являющихся первым целым числом в паре, из второго вектора.Это дает (ожидаемое) O (1) время поиска, чтобы проверить, существует ли конкретный int
в наборе.
Теперь, когда вы сделали это, используйте алгоритм std::remove_if
, чтобы удалить все изоригинал vector
, который существует в хеш-таблице.Вы можете использовать лямбду для этого:
std::unordered_set<int> toRemove = /* ... */
v1.erase(std::remove_if(v1.begin(), v1.end(), [&toRemove] (int x) -> bool {
return toRemove.find(x) != toRemove.end();
}, v1.end());
Этот первый шаг сохранения всего в unordered_set
занимает ожидаемое O (n) время.Второй шаг выполняет ожидаемую работу O (n), объединяя все удаления до конца и заставляя поиск занимать небольшое время.Это дает общее ожидаемое время O (n), O (n) для всего процесса.
Если вам разрешено сортировать второй вектор (пары), то вы можете сделать это вO (n log n) время наихудшего случая, O (log n) пространство наихудшего случая путем сортировки вектора по ключу с последующим использованием std::binary_search
, чтобы проверить, следует ли исключить конкретный int
из первого vector
или нет.Каждый двоичный поиск занимает O (log n) времени, поэтому общее время, необходимое для сортировки, составляет O (n log n), O (log n) время на элемент в первом векторе (всего O (n log n)) и O (n) время для удаления, что в сумме дает O (n log n).
Надеюсь, это поможет!