Краткий ответ

std::distance работает за O(1) для итераторов произвольного доступа и за O(n) для обычных входных, прямых и двунаправленных итераторов. Причина в доступных операциях: итераторы произвольного доступа поддерживают вычисление разности, а остальные позволяют узнать расстояние только последовательным продвижением от начала к концу.

Исторический контекст

Итераторы STL создавались как единый интерфейс обхода разных контейнеров. Алгоритм должен работать с std::vector, std::list и другими структурами, не зная их внутреннего устройства.

Чтобы сохранить универсальность и при этом использовать доступные оптимизации, итераторы разделили на категории. Категория описывает не только допустимые операции, но и гарантии их сложности.

Постановка проблемы

Внешне вызовы std::distance для разных контейнеров выглядят одинаково, но стоимость может различаться радикально. Ошибочное предположение, что любой такой вызов константный, способно превратить линейный алгоритм обработки списка в квадратичный.

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

Подробное решение

Для итераторов произвольного доступа доступны операции вроде прибавления смещения и вычитания итераторов. Поэтому расстояние между двумя позициями вычисляется напрямую, без обхода элементов, и имеет сложность O(1).

Для входных, прямых и двунаправленных итераторов стандартная операция продвижения — переход к следующему элементу. Реализация std::distance последовательно увеличивает первый итератор, пока он не достигнет второго, поэтому сложность составляет O(n).

Категория двунаправленного итератора сама по себе не делает расстояние константным: возможность двигаться назад не означает наличие операции вычисления разности. Для корректного вызова второй итератор должен быть достижим из первого в соответствии с требованиями конкретной категории; нарушение этого условия приводит к неопределённому поведению или нарушению предусловий алгоритма.

#include <iostream>
#include <iterator>
#include <list>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4};
    std::list<int> l{1, 2, 3, 4};

    std::cout << std::distance(v.begin(), v.end()) << '
';
    std::cout << std::distance(l.begin(), l.end()) << '
';
}

Числовой результат одинаков, но асимптотическая стоимость различается: для vector расстояние вычисляется за O(1), а для list — за O(n). Наличие у контейнера собственного метода size() не меняет сложность std::distance для его итераторов: алгоритм получает только итераторы и обязан ориентироваться на их возможности.

В современном C++ у диапазонных алгоритмов есть дополнительный механизм sized sentinel: если типы конца и начала поддерживают вычисление расстояния, std::ranges::distance может использовать его. Это не отменяет общего правила для обычных итераторов и не делает std::distance константным для любого контейнера.

Ситуация из практики

В обработчике большого std::list разработчик в каждой итерации цикла вычислял позицию элемента через std::distance от begin(). Формально тело цикла выполняло линейную работу, но суммарная сложность стала O(n²).

Рассматривались три варианта:

заменить контейнер на std::vector: быстрый произвольный доступ и константное вычисление расстояния, но дорогие вставки в середину и возможная инвалидизация итераторов;
сохранять числовой индекс отдельным счётчиком: линейный общий обход и отсутствие повторных проходов, но индекс нужно вручную поддерживать при сложной логике переходов;
оставить std::list и вызывать std::distance только после завершения обхода: сохраняется эффективная вставка в середину, но позиция доступна не в каждый момент.

Выбрали отдельный счётчик, поскольку порядок обхода уже был линейным, а контейнер требовался для частых вставок. Итоговая сложность снизилась с O(n²) до O(n) без изменения структуры данных.

Что кандидаты часто упускают

Делает ли двунаправленная категория вычисление расстояния константным?

Нет. Двунаправленный итератор умеет переходить к предыдущему элементу, но стандартная модель не предоставляет операции вычитания двух итераторов. Поэтому std::distance обычно последовательно увеличивает или уменьшает итератор и работает за O(n).
Почему std::distance нельзя автоматически заменить вызовом container.size()?

Функция принимает пару итераторов, которые могут обозначать только часть контейнера, диапазон из другого источника или вообще не принадлежать контейнеру с доступным size(). Универсальный алгоритм не должен знать владельца итераторов, поэтому он использует только операции, гарантированные их категорией.
Чем в этом отношении может отличаться std::ranges::distance?

std::ranges::distance умеет использовать разность между началом и концом, если диапазон предоставляет совместимый sized sentinel. В таком случае расстояние может вычисляться за O(1) даже без классической проверки категории итератора. Если такой операции нет, функция возвращается к последовательному продвижению и имеет линейную сложность.