В настоящее время я считаю, что мой лучший вариант - использовать std :: set_intersection, а затем проверить, совпадает ли размер меньшего ввода с количеством элементов, заполненных set_intersection.Как проверить, является ли один вектор подмножеством другого?
Есть ли лучшее решение?
Попробуйте это:
if (std::includes(set_one.begin(), set_one.end(),
set_two.begin(), set_two.end()))
{
// ...
}
О includes().
включает в себя() Алгоритм сравнивает два упорядоченные последовательности и возвращает истину, если каждый элемент в диапазоне [start2, finish2) содержится в диапазоне [Начало1, finish1). В противном случае он возвращает false . includes() предполагает, что последовательности сортируются с использованием оператора <() или с использованием предиката comp.
работает в
В лучшем случае ((finish1 - start1) + (finish2 - start2)) * 2 - 1 сравнения выполняются.
Plus O (nlog (n)) для сортировки векторов. Вы не получите его быстрее.
Я считаю, что std :: set_intersection будет выполнять те же действия, что и выше (т. Е. (2 * (count1 + count2)) - 1 операция) – Nim
В худшем случае тот же, но если результат ложный, то включит его работу намного быстрее. И вы также используете еще один вектор в пересечении. Поскольку имена предполагают, что set_intersection следует использовать для нахождения этого пересечения и включает в себя для проверки того, является ли один набор подмножеством другого. – Klark
если ваши данные находятся в 'std :: set', вы можете использовать' std :: set_difference' –