Set_union / Set_intersect для более чем двух наборов в C ++

Question

Я знаю, что эти команды предназначены для двух наборов.

Существует ли простой и быстрый способ сделать это для более чем двух наборов.это, но может быть, есть лучший способ.

Спасибо

Answer 1

Если вы используете отсортированные наборы (например, наборы STL), вы можете выполнить объединение / пересечение для всех них одновременно за один проход.Если они простые наборы, я не думаю, что вы можете добиться большего успеха, чем объединять их по одному.

Answer 2

Для объединения наборов, если вы собираетесь увидеть, какой из M наборов имеет наименьшее значение, которое будет принимать сравнения M-1. Так что теперь мы выталкиваем это значение и идем снова. Если N - общее количество элементов во всех наборах, наш алгоритм таким образом будет O (NM) (игнорируйте, что это - M-1 для записи Big-O).

То, где мы могли бы оптимизировать, выглядит следующим образом: если мы сортируем самый низкий элемент каждого набора: теперь мы выталкиваем один спереди, но из этого набора нам просто нужна вставка O (logM) в наши новые отсортированные фронты , Мы делаем это для каждого элемента, поэтому наш алгоритм O (N logM).

Обратите внимание, что если у вас есть 3, вы, вероятно, ничего не получите. Если у вас есть 8 таких наборов, это, безусловно, может показать усиление.

Для пересечения наборов мы ищем только значения, которые появляются во всех наших наборах. Мы знаем, что они все одинаковы, если минимум совпадает с максимумом. Мы можем выскочить и отбросить меньшие значения, если они не будут, тогда снова вставлять каждый раз следующее. Если это так, мы добавляем в наш результат, а затем поп из каждого списка. В любом случае у нас все еще будет O (N logM)

Answer 3

О set_union :
Если ваши контейнеры действительно std :: set, вы можете сделать цикл по всем наборам, но не используя set_union, вы можете выбрать один из наборов и использовать insert(используя итераторы begin () и end () других множеств).Таким образом, вы не создадите много копий, потому что set_union возвращает (итератор) копию только что созданного набора.Если вы не хотите изменять какой-либо из наборов, вы можете создать новый, пустой, и начать вставлять все элементы из всех наборов.
Если вы не используете наборы, вы можете временно создать std:: установить, использовать вставку, а затем вставить все элементы в новый контейнер вашего типа.
О set_intersect : вы можете использовать стирание, но без использования итераторов, просто просматривая все множества и все элементы,что они содержат.Но я не уверен, будет ли это быстрее, чем при использовании set_intersect.Зависит от того, сколько у вас комплектов.
Надеюсь, что помогло (: