#c #algorithm #boost #stl
#c #алгоритм #повышение #stl
Вопрос:
У меня есть два контейнера (фактический контейнер гибкий, для меня не имеет значения, какой из них не отсортирован, поэтому я буду использовать то, что лучше всего подходит для ответа на мой вопрос), которые содержат некоторые данные. Я хочу сравнить эти два контейнера и либо удалить все «дубликаты» из второго, либо создать новый контейнер только с «новыми» значениями.
Под дублированием / новым я подразумеваю следующее: Контейнер 1 содержит: [1, 2, 4, 8, 16] Контейнер 2 содержит: [1, 2, 4, 16, 32]
После запуска алгоритма новый контейнер (или модифицированный контейнер 2) должен содержать: Контейнер 3 содержит: [32]
Обратите внимание, что я не хочу, чтобы «8» было в новом контейнере (или измененном контейнере), поскольку я хочу только найти «новые» значения.
Я мог бы легко реализовать наивную и медленную программу, чтобы сделать это самостоятельно, однако я ищу наиболее элегантный и эффективный способ добиться этого (Boost подойдет, если STL не предоставляет все необходимые инструменты / алгоритмы без использования ваших собственных, в противном случае также подойдет использование ваших собственных).
Итак… Какой был бы «лучший» (читай: самый элегантный и эффективный) способ сделать это?
Заранее спасибо.
P.S. Если это вообще уместно, я использую это, чтобы написать инструмент ‘diffing’ для экспортированных функций из библиотеки DLL. У меня есть несколько очень больших библиотек DLL, и я хочу найти «новые» экспортированные файлы в последних сборках этих библиотек DLL.
Ответ №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;
}
Комментарии:
1. Erase принимает итераторы в свой собственный контейнер и удаляет их, он не сравнивает значения из другого контейнера, как вы предлагаете.
2. Вы полностью правы, мой STL немного заржавел, это моя ошибка. Я изменил ответ, надеюсь, на этот раз я все понял правильно =)
3. set_difference — это алгоритм, которого мне не хватало. Спасибо!
4.
set_differenceэто алгоритм, но здесь, чтобы достичь того, чего хотел OP, нам нужно изменить порядок передаваемых контейнеров. Вместо этого должно бытьit=set_difference (second, second 5, first, first 5, v.begin());.Notice that I do NOT want '8' to be in the new container (or modified container) as I only want to find the 'new' values.
Ответ №2:
Самым простым методом, вероятно, была бы сортировка с последующим повторением. Поскольку оба контейнера отсортированы, вы можете просто напрямую сравнить каждый индекс (или итератор без ссылок) на предмет равенства и вставить в новый (или удалить из существующего), только если они не равны. Это O (n logn) и зависит от operator< и operator== .
Комментарии:
1. Вопрос разрешает выбор отсортированных входных контейнеров, поэтому с учетом предварительно отсортированных входных данных это всего лишь O (max (M, N)) — M и N — количество элементов в каждом из входных контейнеров….
Ответ №3:
hash_table в STL может решить эту проблему.
- Вставьте все элементы из первого контейнера в hash_table.
- Для каждого элемента в контейнере номер два проверьте, есть ли он в hash_table или нет; если нет, поместите его в контейнер номер три.
Общая временная сложность составляет O (n). Метод сортировки и сравнения имеет временную сложность O(nlogn).