Ковыряю алгоритмы на Leetcode. Преобразую vector в unordered_set для кеширования и поиска элементов, ничего сложного. Далее собственно итератор по vector, и проверка есть ли каждый элемент в unordered_set и далее логика если есть.
Запуск кода вываливается на платформе с ошибкой мол алгоритм отработал слишком медленно.
Барабанная дробь - меняем итерацию по массиву на итерацию по unordered_set - алгоритм укладывается во временные рамки. Что за? Есть разумное объяснение? А то все говорят что итерации по массиву быстрее быть не может за счёт кеширования в CPU и предвыборки элементов массива загодя в кеш. Оказывается может.
int func(vector<int>& nums) {
unordered_set<int> set;
for (auto n : nums) {
set.insert(n);
}
// Итерация по nums медленнее чем по 'set' !!!
for (auto n : nums) {
...
