Итерация по unordered_set быстрее чем по vector?

дык оригинальный тест ваще к задаче с псевдоалгокачки чисто понимание ТС чё

в самой задачке(как оказалось с фигой в кармане) тесты более чтоли равновероятные

но на практике

O(nlogn) алгоритм с сортировкой проходит тест на O(n).

И у меня свой интерес и своя практика, чужими практиками пусть занимаются чужие

boost::unordered_flat_set

и раздвинул бы табличку 2x - 4x

Медленнее, чем просто инициализация.

И у меня свой интерес и своя практика

Дык, а толку то гонять на входе без дупликатов? Когда вы в миллиарды уходите дырок в вас практически не остаётся. Это очень и очень вырожденный случай. Я даже не до конца понимаю какую практическую пользу из этого извлечь можно.

Медленнее, чем просто инициализация.

Вот здесь не понял. Что значит «просто инициализация»?

Я даже не до конца понимаю какую практическую пользу из этого извлечь можно.

Практическое значение «идеального» хеша. Превращение О(1) в O(logn), там где не ждали.

boost::unordered_flat_set(arr.begin(), arr.end());

против

boost::unordered_flat_set(arr.begin(), arr.end(), 2*arr.size());

https://en.wikipedia.org/wiki/Van_Emde_Boas_tree

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

вроде бы верно зарефакторил:
https://godbolt.org/z/xEbYK3dvz

#include <vector>
#include <unordered_set>
#include <algorithm>
#include <ranges>
#include <functional>
#include <string>

int longestConsecutive(const std::vector<int>& nums) {
    std::unordered_set<int> set(std::from_range_t(), nums);
    
    auto comparatorFn = [&]( auto v  ){ return set.contains( v - 1 ); };
    auto transformToCountFn  = [&]( auto el ){
                            int length = 0;
                            while ( set.contains( el + length ) )
                                length++;
                            return length;
                        };
    auto counts = set   | std::views::filter(comparatorFn)
                        | std::views::transform(transformToCountFn)
                        | std::ranges::to<std::vector>();

    return std::ranges::max(counts);
}

это же асимптотическая сложность — не отражающая относительность реальной скорости — O(1) может занимать больше времени чем O(n) в каких то примерах.

Не вникал особо в суть постов.
Не проще ли отсотировать набор элементов?

std::ranges::sort
Complexity
𝓞(N·log(N)) comparisons and projections, where N = ranges::distance(first, last)
-- в условиях задачи

You must write an algorithm that runs in O(n) time.

тут имеется ошибка — в ретурне нужно +1 сделать поскольку тут не учитывается один инкремент для каждой из последовательностей...

std::unordered_set<Key,Hash,KeyEqual,Allocator>::erase

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

и https://eel.is/c draft/stmt.ranged#1
иными словами короче — это UB

vector<byte> buf(2 * sizeof(void*) * nums.size());
pmr::monotonic_buffer_resource mbr{buf.data(), buf.size()};;
pmr::polymorphic_allocator<int> pa{&mbr};
pmr::set<int> set(nums.begin(), nums.end(), pa);

это ты https://en.cppreference.com/w/cpp/container/flat_set.html изобрёл?

тут даже не с range-based-for-loop UB — модифицируется контейнер, по которому итерация идёт, и инвалидируется как минимум итератор, по которому эрейзится.

Нет, не я

Инициализировать надо уникальными значениями, union-find - это лес непересекающихся множеств, по началу единичных множеств из уникальных элементов. Также придется создать map числа на элемент-ноду union-find, возможно также обратный map. И всё это - не линейная сложность

во-первых линейная при условии нормальной реализации хэш-таблицы и/или валидации входных данных. Во-вторых это задача для собеседования, придуманная специально для того чтобы проверить твои знания в нескольких вопросах и поставить не просто «решил/не решил», а более детальный грейд.

Т.е. типичный сценарий собеседования - кандидат реализует что-то с помощью сортировки, если там не ошибок - то у него спрашивают «а можешь придумать алгоритм быстрее», если он не додумывается до системы непересекающихся множеств - то ему попытаются повысить грейд вопросами про хэш-таблицы.

Если ты правильно реализовываешь СНМ, то получаешь оффер программистом в гугл; если нет, но справляешься с сортировкой и отлично рассказываешь про хэш-таблицы - то тебе могут попытаться подобрать другую позицию (например SRE вместо SWE); во всех остальных случаях - отказ.

По крайней мере так было до ковида. Сейчас все наверняка сложнее, а если ты из России, то думаю вообще не пригласят на собес))

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

лучше бы исследовали знания в части использования памяти, кастов, юнионов и подобного, что как раз может сделать качественную оценку для того, как может тот или иной разработчик сделать код, — поскольку в случае незнания (непонимания) такового и происходят все эти «запинки» с багами в коде, которые очень сложно отследить (хотя бывает и достаточно тривиально, если нормально поиском по кодовой базе пройтись по очевидным сценариям частых ошибок).

ну и лично моё мнение — что попросту наоборот на счёт использования явных «реализаций» в коде нужно «ругать», что бы использовали уже написанное — иначе кодовые базы вот и превращаются в многомиллионные строки вместо использования до сотен раз меньшего количества.

все эти «олимпиадовские» «замашки» должны пресекаться на отборе — ну и во время отслеживания возделанного кода тимлидами. — А тут я порой читаю что как раз «тимлид-подобные» лица наоборот поощрают написание «встроенного явного цикла», вместо использования уже готового алгоритма. Да и даже на олимпиадах я считаю необходимо снижать оценки сильно для неспособных применять уже имеющийся код (как минимум в стандартной либе).