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

RandomAccessCollection обязуется вычислять distance(from:to:) за O(1), то есть за постоянное время, независимо от количества элементов между индексами. Аналогичная гарантия действует для перемещения индекса на заданное смещение через index(_:offsetBy:).

Это не означает, что коллекция непрерывно хранится в памяти или использует целочисленные индексы. Гарантия относится именно к операциям над индексами.

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

Протоколы коллекций Swift разделяют возможности типов: базовый Collection описывает обход и работу с индексами, BidirectionalCollection добавляет движение назад, а RandomAccessCollection — эффективное произвольное перемещение по индексам.

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

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

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

Если разработчик ошибочно предполагает произвольный доступ за O(1) для любой коллекции, производительность будет зависеть от конкретного типа. Например, алгоритм, эффективный для массива, может оказаться существенно медленнее для другой Collection.

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

RandomAccessCollection уточняет контракт Collection: переход индекса на смещение и вычисление расстояния между индексами должны выполняться за постоянное время. Поэтому алгоритм может безопасно использовать такие операции многократно, не проходя все промежуточные элементы.

func span<C: RandomAccessCollection>(_ collection: C) -> Int {
    collection.distance(
        from: collection.startIndex,
        to: collection.endIndex
    )
}

let values = [10, 20, 30, 40]
print(span(values)) // 4

Индексы в Swift являются абстрактными значениями: нельзя предполагать, что индекс — это Int или что его можно складывать обычным оператором. Доступ выполняется через методы коллекции, а требование RandomAccessCollection гарантирует для них нужную сложность.

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

Цена гарантии — более строгие требования к реализации коллекции. Типы, у которых индекс можно перемещать только последовательным обходом, не должны объявлять соответствие RandomAccessCollection. Для них корректнее использовать более общий Collection, даже если это приводит к более высокой сложности отдельных операций.

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

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

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

Если алгоритм действительно зависит от частых произвольных переходов, выбранное решение — принять RandomAccessCollection. Если же нужен только однократный подсчёт обработанных элементов, лучше вести счётчик во время обхода и не требовать более строгий протокол без необходимости.

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

Означает ли RandomAccessCollection, что индексы имеют тип Int?

Нет. Индексы остаются абстрактным Index конкретной коллекции. Гарантируется эффективное перемещение через API коллекции, а не числовая природа индекса. Поэтому обобщённый код должен использовать startIndex, endIndex, index(_:offsetBy:) и distance(from:to:).
Гарантирует ли Collection постоянную сложность distance(from:to:)?

Нет. Для общего Collection сложность может быть линейной относительно расстояния между индексами. Это особенно важно, если вызов находится внутри цикла: повторное вычисление расстояния от начала может привести к квадратичному числу операций.
Достаточно ли соответствия RandomAccessCollection, чтобы безопасно обращаться к элементам через указатели?

Нет. RandomAccessCollection гарантирует только свойства индексов и сложность навигации по ним. Непрерывное хранение элементов — отдельная характеристика; коллекция может предоставлять быстрый произвольный доступ без возможности безопасно представить её содержимое одним непрерывным буфером.