Подсчет длины последовательности Коллатца - пользовательский итератор замедляет работу?

Я решал задачу UVA №100 — "The 3n + 1 проблема". Это их «примерная» задача с очень щадящим ограничением по времени (ограничение в 3 секунды, их пример решения вообще без кэширования выполняется за 0,738 с, мое лучшее решение на данный момент работает за 0,016 с), поэтому я подумал, что, как бы я ни экспериментировал с кодом, я всегда должен укладываться в лимит. Что ж, я ошибся.

Спецификация задачи проста: каждая строка ввода содержит два числа i и j, а вывод должен вывести эти числа, за которыми следует максимальная длина последовательности Коллатца, начало которой находится между i и j включительно.

Я подготовил четыре решения. Они очень похожи, и все дают хорошие ответы.

Первое решение кэширует последовательности до 0x100000 длин в vector. Длина 0 означает, что длина последовательности, начинающейся с этого конкретного числа, еще не рассчитана. Работает достаточно быстро - 0,03 сек.

Второе решение очень похоже, только оно кэширует каждую отдельную длину в разреженном массиве, реализованном с помощью unordered_map. Оно работает довольно медленнее, чем предыдущее решение, но все же хорошо укладывается в ограничение: 0,28 с.

В качестве упражнения я также написал третье решение, основанное на втором. Цель состояла в том, чтобы использовать функцию max_element, которая принимает только итераторы. Я не мог использовать unordered_map::iterator, для увеличения такого итератора, AFAIK, линейно по размеру карты; поэтому я написал собственный итератор, работающий с абстрактным «контейнером», который «держит» длину последовательности всех возможных чисел (но на самом деле вычисляет их и кэширует только по мере необходимости). По сути, это то же самое решение unordered_map, только сверху добавлен дополнительный уровень итераторов. Решение не укладывалось в 3 сек. предел.

И теперь приходит то, что я не могу понять. Хотя очевидно, что третье решение намеренно усложнено, я с трудом мог поверить, что дополнительный слой итераторов может привести к такому замедлению. Чтобы проверить это, я добавил тот же слой итератора в решение vector. Это моё четвертое решение. Судя по тому, как эта идея с итератором повлияла на мое решение unordered_map, здесь я тоже ожидал значительного замедления; но как ни странно, этого не произошло вовсе. Это решение работает почти так же быстро, как и обычное vector, за 0,035 с.

Как это возможно? Что именно отвечает за замедление в третьем решении? Как возможно, что чрезмерное усложнение двух одинаковых решений совершенно одинаковым образом очень сильно замедляет одно из них и почти не вредит другому? Почему добавление слоя итератора к решению unordered_map привело к тому, что оно не подошло по времени, а то же самое к решению vector почти не замедлило его?

РЕДАКТИРОВАТЬ:

Я обнаружил, что проблема кажется наиболее заметной, если ввод содержит много повторяющихся строк. Я протестировал все четыре решения на своей машине против ввода 1 1000000, повторив 200 раз. Решение с простым вектором обработало их все за 1,531 с. Решение с вектором и дополнительным слоем итератора заняло 3,087 сек. Решение с простой неупорядоченной картой заняло 33,821 с. А решение с неупорядоченной картой и дополнительным слоем итератора заняло более полчаса — я остановил его через 31 минуту 0,482 секунды! Я протестировал его на Linux mint 17.2 64 бит, версия g++ Ubuntu 4.8.4-2ubuntu1~14.04 с флагами -std=c++11 -O2, процессор Celeron 2955U @1,4 ГГц x 2