C ++, быстрое удаление элементов из вектора, уникального для другого вектора - PullRequest
Новая
       20

C ++, быстрое удаление элементов из вектора, уникального для другого вектора

3 голосов
/ 24 января 2012

Есть 2 несортированных вектора int и вектор пар int, int 

std::vector <int> v1;
std::vector <std::pair<int, float> > v2;

содержит миллионы предметов.

Как максимально быстро удалить из v1 такие элементы, которые являются уникальными для v2.first (т.е. не включены в v2.first)?

Пример: 

v1:  5 3 2 4 7 8
v2: {2,8} {7,10} {5,0} {8,9}
----------------------------
v1: 3 4

Ответы [ 2 ]

6 голосов
/ 24 января 2012

Есть два трюка, которые я бы использовал, чтобы сделать это как можно быстрее:

  1. Использовать некоторый ассоциативный контейнер (вероятно, std::unordered_set) для хранения всех целых чисел ввторой вектор, чтобы значительно повысить эффективность поиска целого числа в первом векторе.

  2. Оптимизировать способ удаления элементов из исходного вектора.

Более конкретно, я бы сделал следующее.Начните с создания 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).

Надеюсь, это поможет!

1 голос
/ 24 января 2012

Предполагается, что ни один контейнер не отсортирован, и что сортировка на самом деле слишком дорогая или недостаточно памяти: 

v1.erase(std::remove_if(v1.begin(), v1.end(), 
                        [&v2](int i) { 
                         return std::find_if(v2.begin(), v2.end(), 
                                             [](const std::pair<int, float>& p) { 
                                                return p.first == i; }) 
                                != v2.end() }), v1.end());

В качестве альтернативы можно отсортировать v2 на first и использовать вместо этого бинарный поиск. Если памяти достаточно, используйте unordered_set для сортировки first из v2.

Полная версия C ++ 03: 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

struct find_func {
  find_func(int i) : i(i) {}

  int i;
  bool operator()(const std::pair<int, float>& p) {
    return p.first == i;
  }
};

struct remove_func {
  remove_func(std::vector< std::pair<int, float> >* v2) 
  : v2(v2) {}
  std::vector< std::pair<int, float> >* v2;
  bool operator()(int i) {
    return std::find_if(v2->begin(), v2->end(), find_func(i)) != v2->end();
  }
};


int main()
{
  // c++11 here
  std::vector<int> v1 = {5, 3, 2, 4, 7, 8};
  std::vector< std::pair<int, float> > v2 = {{2,8}, {7,10}, {5,0}, {8,9}};
  v1.erase(std::remove_if(v1.begin(), v1.end(), remove_func(&v2)), v1.end());

  // and here
  for(auto x : v1) {
    std::cout << x << std::endl;
  }

  return 0;
}
...