Найти «новые» предметы из двух контейнеров

Question

У меня есть два контейнера (фактический контейнер гибкий, несортированный и отсортированный не имеет значения для меня, поэтому все, что лучше всего ответит на мой вопрос, это то, что я буду использовать), которые содержат некоторые данные.Я хочу сравнить эти два контейнера и либо удалить все «дубликаты» из второго, либо создать новый контейнер только с «новыми» значениями.

Под дубликатом / новым я понимаю следующее: Контейнер 1 содержит:[1, 2, 4, 8, 16] Контейнер 2 содержит: [1, 2, 4, 16, 32]

После запуска алгоритма новый контейнер (или модифицированный контейнер 2) должен содержать: Контейнер3 содержит: [32]

Обратите внимание, что я НЕ хочу, чтобы '8' было в новом контейнере (или модифицированном контейнере), поскольку я хочу только найти 'новые' значения.

Я мог бы легко реализовать наивную и медленную программу, чтобы сделать это сам, однако я ищу наиболее элегантный и эффективный способ добиться этого (Boost хорошо, если STL не предоставляет все необходимые инструменты / алгоритмы без развертывания собственного,в противном случае тоже неплохо кататься).

Итак ... Какой самый лучший (читай: самый элегантный и эффективный) способ сделать это?

Заранее спасибо.

PS Если это вообще актуально, яЯ использую это, чтобы написать «diffing» инструмент для экспортируемых функций из DLL.У меня есть несколько очень больших библиотек DLL, и я хочу найти «новые» экспорты в последних сборках этих библиотек.

Answer 1

Похоже, STL set_difference может быть правильным для вас.Пример из здесь :

// set_difference example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  vector<int> v(10);                           // 0  0  0  0  0  0  0  0  0  0
  vector<int>::iterator it;

  sort (first,first+5);     //  5 10 15 20 25
  sort (second,second+5);   // 10 20 30 40 50

  it=set_difference (first, first+5, second, second+5, v.begin());
                                               // 5 15 25  0  0  0  0  0  0  0

  cout << "difference has " << int(it - v.begin()) << " elements.\n";

  return 0;
}

Answer 2

hash_table в STL может решить эту проблему.

1. Вставьте все элементы контейнера один в hash_table.
2. Для каждого элемента в контейнере два , проверьте , находится ли он в hash_table или нет;если нет, вставьте его в контейнер три .

Общая сложность времени составляет O (n) .Метод сортировки и сравнения имеет временную сложность O (nlogn) .

Answer 3

Простейшим методом, вероятно, будет сортировка, а затем итерация.Поскольку оба контейнера отсортированы, вы можете просто напрямую сравнить каждый индекс (или итератор с отсутствующими ссылками) на равенство и вставить в новый (или удалить из существующего), только если он не равен.Это O (n logn) и зависит от operator< и operator==.