C++ Разница между двумя векторами <MyType*> A и B

Question

У меня есть два объекта vector<MyType*> под названием A и B. Класс MyType имеет поле ID, и я хочу получить MyType*, которые находятся в A, но не в B. Я работаю над приложением для анализа изображений, и я надеялся найти быстрое/оптимизированное решение.

С наилучшими пожеланиями, Поллукс

Answer 1

Неупорядоченный подход, как правило, имеют квадратичную сложность, если данные не сортируется заранее (ваш ID поля), в этом случае его будет линейными и не требуют повторных запросов через B.

struct CompareId 
{ 
    bool operator()(const MyType* a, const MyType* b) const 
    { 
     return a>ID < b->ID; 
    } 
}; 
... 
sort(A.begin(), A.end(), CompareId()); 
sort(B.begin(), B.end(), CompareId()); 

vector<MyType*> C; 
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C)); 

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

Предупреждение: переход на несколько сложную территорию.

Есть еще одно решение, которое вы можете рассмотреть, которое может быть очень быстрым, если это применимо, и вам никогда не придется беспокоиться о сортировке данных. В принципе, создайте любую группу объектов MyType, которые имеют один и тот же ID-хранилище общий счетчик (ex: указатель на unsigned int).

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

В дополнение к этому, есть глобальный счетчик «обхода», который получает приращение каждый раз, когда он извлекается.

static unsigned int counter = 0; 
unsigned int traversal_counter() 
{ 
    // make this atomic for multithreaded applications and 
    // needs to be modified to set all existing ID-associated 
    // counters to 0 on overflow (see below) 
    return ++counter; 
} 

Теперь вернемся к тому, где у вас есть векторы A и B, хранящие MyType *. Чтобы получить элементы из A, которые не находятся в B, мы сначала вызываем traversal_counter(). Предполагая, что это первый раз, когда мы его назовем, это даст нам обходное значение 1.

Теперь перебираем каждый объект MyType * в B и устанавливаем общий счетчик для каждого объекта от 0 до значения обхода, 1.

Теперь перебирать все MyType * объект А. те, которые имеют значение счетчика, которое не соответствует текущему значению обхода (1) являются элементами а, которые не содержится в B.

что происходит когда вы переполняете счетчик обхода? В этом случае мы перебираем все счетчики, хранящиеся в ID-карте, и устанавливаем их обратно на ноль вместе с самим счетчиком обхода. Это нужно будет только раз в 4 миллиарда обходов, если это 32-битный беззнаковый int.

Речь идет о самом быстром решении, которое вы можете применить к данной проблеме. Он может выполнять любую заданную операцию с линейной сложностью на несортированных данных (и всегда, а не только в лучших сценариях, таких как хеш-таблица), но она вводит некоторую сложность, поэтому учитывайте ее только в том случае, если она вам действительно нужна.

Answer 2

Сортировка оба вектора (std::sort) в соответствии с ID, а затем использовать std::set_difference. Вам нужно будет определить пользовательский компаратор перейти на оба этих алгоритмов, например

struct comp 
{ 
    bool operator()(MyType * lhs, MyType * rhs) const 
    { 
     return lhs->id < rhs->id; 
    } 
}; 

Answer 3

Сначала рассмотрите проблему. Вы хотите «все в A не в B». Это означает, что вам придется посетить «все в А». Вам также нужно будет посетить все в B, чтобы знать, что есть и не находится в B. Таким образом, это предполагает, что должно быть решение O(n) + O(m) или взять на себя смелость преодолеть разницу между n и m, O(2n).

Давайте рассмотрим подход std::set_difference. Каждый вид - O(n log n), а set_difference - O(n). Таким образом, метод sort-sort-set_difference равен O(n + 2n log n). Назовем это O(4n).

Другим подходом было бы сначала разместить элементы B в наборе (или карте). Итерация по B для создания набора - O(n) плюс вставка O(log n) каждого элемента, за которым следует итерация по A O (n), с поиском для каждого элемента A (log n), дает общее количество: O(2n log n). Назовем это O(3n), что немного лучше.

Наконец, используя unordered_set (или unordered_map), и предполагая, что мы получаем средний случай O(1) вставки и O(1) поиска, мы имеем подход, который O(2n). Ага!

Настоящая победа здесь в том, что unordered_set (или карта) , вероятно, - самый естественный выбор для представления ваших данных в первую очередь, то есть правильный дизайн дает оптимизированную реализацию. Это не всегда происходит, но приятно, когда это происходит!

Answer 4

Если B предвещает A, то при заполнении A вы можете бронировать в векторе C.