Я знаю, что эти команды предназначены для двух наборов.Set_union/Set_intersect для более чем двух наборов в C++
Есть ли простой и быстрый способ сделать это для более чем двух наборов.
Я думаю, что я могу использовать какой-то цикл для этого, но, возможно, есть лучший способ.
Спасибо
Для объединения в набор, если вы увидите, какой из M-наборов имеет наименьшее значение, которое будет принимать сравнения M-1. и повторите попытку. Если N - это общее число элементов во всех наборах, наш алгоритм таким образом равен O (NM) (игнорируйте, что это M-1 для обозначения Big-O).
Где мы можем оптимизировать следующим образом: если мы отсортируем наименьших элементов t каждого набора: теперь мы выходим с фронта, но из этого набора нам просто нужна вставка O (logM) в наши новые отсортированные фронты. Мы делаем это для каждого элемента, поэтому наш алгоритм O (N logM).
Обратите внимание, что если у вас есть 3, вы, вероятно, ничего не получите. Если у вас есть 8 таких наборов, это, безусловно, может показать выигрыш.
Для пересечения множеств мы ищем только значения, которые появляются во всех наших множествах. Мы знаем, что они одинаковы, если минимум совпадает с максимальным. Мы можем выскочить и отбросить меньшие значения, если они не будут потом снова вставляться каждый раз, когда следующий. Если это так, мы добавляем к нашему результату, затем поп из каждого списка. В любом случае у нас все еще будет O (N logM)
О set_union:
Если контейнеры действительно станд :: набор, вы могли бы сделать петлю через все наборы, но не с помощью set_union, вы можете выбрать один из наборов и (используя begin() и end() итераторы других наборов). Таким образом, вы будете не создать много копий, потому что set_union возвращает (итератор) копию вновь созданного набора. Если вы не хотите изменять какой-либо набор, вы можете создать новый, пустой и начать вставлять все элементы из всех наборов.
Если вы не используете наборы, вы можете временно создать std :: set, использовать вставку, а затем вставить все элементы в новый контейнер из вашего типа.
О set_intersect: вы можете использовать стирание, но не используя итераторы, просто просматривая все наборы и все элементы, которые они содержат. Но я не уверен, будет ли это быстрее, если использовать set_intersect. Зависит от того, сколько у вас наборов.
Надежда, что помогло (:
Если вы используете отсортированные наборы (например, наборы STL), вы можете сделать объединение/пересечение на всех из них сразу за один проход Если они простые наборы, я не знаю. подумайте, что вы можете сделать это лучше, чем комбинировать их по одному.