Разница между двумя std :: векторами без естественного порядка сортировки
Я ищу эффективный способ получить разницу между двумя std::vectors, Объекты, которые они содержат, не имеют естественного порядка; лучшее, что я могу сделать, это проверить на равенство. Кажется, это исключает std::set_difference вариант.
Есть ли лучшее решение, чем сравнивать объекты внутри двух вложенных итераторов?
Решение
Цель состоит в том, чтобы уменьшить количество тестов на равенство, группируя возможные положительные совпадения вместе.
Лучшее, что я могу придумать, — это создать хеш-карту с первым вектором, а затем вычесть все элементы второго вектора из хеш-карты. Это означает, что вам нужно придумать достойную хеш-функцию для ваших элементов.
Обычно, если вы храните указатели и ваш предикат равенства основан на них, вы также можете основывать свой хэш на этом интегральном значении указателя.
Увидеть Что такое хорошая хеш-функция?.
Как упомянуто в комментариях, альтернативная возможность состоит в том, чтобы установить порядок на определенных атрибутах элементов и использовать это, чтобы уменьшить возможности равенства. Возможно, вам придется сначала отсортировать оба вектора.
Другие решения
Вы можете воспользоваться свойством векторов, у них есть непрерывное выделение памяти, что означает, что у вектора есть одно большое зарезервированное пространство памяти (больше, чем обычно используется), и без излишней оптимизации вы можете сравнивать непосредственно пространства памяти.
В C ++ 0x у вас есть метод data (), который дает вам прямой доступ к началу этого пространства памяти. И вы можете использовать memcmp сравнить все данные внутри векторов.
std::vector<char> vector_1;
std::vector<char> vector_2;
// data in to vector_1
// data in to vector_2
if(!memcmp(vector1.data(),vector_2.data(),SIZE_OF_BUFFER_TO_COMPARE))
{
std::cout <<< "equal vectors" << std::endl;
}