Как проверить, является ли один вектор подмножеством другого?

В настоящее время я считаю, что мой лучший вариант - использовать std:: set_intersection, а затем проверить, совпадает ли размер меньшего ввода с количеством элементов, заполненных set_intersection.

Есть ли лучшее решение?

Ответы

Ответ 1

Попробуйте следующее:

if (std::includes(set_one.begin(), set_one.end(),
                  set_two.begin(), set_two.end()))
{
// ...
}

О включает().

Алгоритм includes() сравнивает два отсортированные последовательности и возвращает true, если каждый элемент в диапазоне [start2, finish2) содержится в диапазоне [старт1, отделка1). Он возвращает false в противном случае. включает() предполагает, что последовательности сортируются с использованием operator <() или используя предикат сост.

работает в

Не более ((finish1 - start1) + (finish2 - start2)) * Выполняется сравнение 2 - 1.

Плюс O (nlog (n)) для сортировки векторов. Вы не получите его быстрее, чем это.