Здравствуйте, niXman, Вы писали:

X>Здравствуйте, Кузнец, Вы писали:

R>>>разные O-большие

К>>Да, std::set имеет логарифмическое время вставки, а unordered_set константу в среднем. Взамен std::set упорядочен, а другой порядок не гарантирует, в нашем же случае упорядоченность никак не помогает, но критично время обработки.

X>это все понятно. но что-то мой опыт подсказывает мне, что все эти моменты на этом наборе данных с учетом что данные — интегралы — не имеют большого значения...

Эти данные не интегралы, это индексы. Наш алгоритм следует статье , каждому вновь найденному объекту присваивается индекс, иногда индексы приходится отождествить, при этом остаётся один из них (какой именно — определяет алгоритм отождествления, у нас там работает disjoint-set-union, поэтому нельзя сказать, например, что всегда выбирается меньший из двух). Эти индексы потом в QSet и были сложены, причём каждый клался столько раз, сколько других индексов было отождествлено, поэтому и пришлось испольховать хеш-множество, чтобы не заниматься каждый раз поиском по уже набранным индексам (можно было бы сложить в std::vector, но тогда мы бы имели много повторяющихся чисел, что сломает алгоритм)