Как правильно слить/объеденить несколько множеств в одно?

Возник вопрос: что будет быстрее слить множества и пробежаться по одном find'ом или несколько раз пробежаться find'ом?

Проверка на вхождение элемента в дерево: O(log N) от количества элементов. Проверка на вхождение в N множеств по N элементов: O(N log N).

Объединение двух множеств: это N вставок. То есть O(N log N). Объединение N множеств: N вставок по N элементов. То есть O(N^2 log N).

То есть в пределе получается O(N log N) для прохода по всем множестам против O(N^2 log N) для объединения всех и прохода. Так что если искать надо часто, то лучше объединить. Если изредка, лучше не париться.

Ну и как всегда, дьявол в константах.

Для однократного поиска конечно лучше не сливать, а обойти множества. А для многократного при неизменных множествах может заиметь смысл сливать. Поиск имеет сложность O(log N), поиск в эквивалентных K раздельных непересекающихся множеств - O(K * log N/K) (т.е. конечно больше). Стоимость слияния двух множеств размером N - не меньше O(N * log N).

И вообще. Если это set<char> то это всего 256 разнообразных элементов. Можно быстро схлопнуть их std::array<bool, 256> и проверять вхождение сколько влезет со скоростью света.

А char[8] уже не в моде?

std::bitset тогда уж.

Блин, я конечно же имел ввиду char[32].

bitset не так просто объединяется. Это не «|» для uin64_t или char.

bitset не так просто объединяется. Это не «|» для uin64_t или char.

Но для него же определён operator|() и компания :\

Блин, пора спать... Сори, у меня были какие-то куевые маны.

Помимо того, что посоветовали выше, можешь попробовать вместо std::set заюзать std::unordered_set (или std::tr1::unordered_set, если относительно старый компилятор).

Проверка на вхождение в N множеств по N элементов: O(N log N).

А с чего ты, собственно, взял, что количество множеств и количество элементов в этих множествах - это одно и то же N? Гораздо вероятнее, что набор множеств фиксирован или, по крайней мере, меняется слабо

Я set_union никогда не пользовался, но в документации вроде написано, что set_union для отсортированных данных.

А ещё в документации должно быть написано, что set хранит данные в отсортированном виде

А ещё в документации должно быть написано, что set хранит данные в отсортированном виде

Кхм, действительно.

Посмотрел я на set_union. Он очень медленно работает. Сделай лучше несколько find-ов.

если у тебя есть заранее выделенный пул потоков, то можно паралелльно запустить find на всех сетах не сливая их в один