Объединение множеств/набор пересекаются более двух комплектов в C++

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

Есть ли простой и быстрый способ сделать это для более чем двух наборов.

Я думаю, что могу использовать какой-то цикл для этого, но, возможно, есть лучший способ.

Спасибо

3 2
c++ algorithm intersection

3 ответа:

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

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

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

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

1

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

1

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

1