Если длина исходной строки — N, то я выполняю сначала N операций, чтобы построить свою структуру, а потом ещё log(N)  каждый раз, когда мне нужно найти номер строки для оффсета

Так String где ты делаешь поиск имутабельная, как я понял. Значит не нужно тебе считать там строки каждый раз

Ну, я один раз ищу все ньюлайны и бью по ним строку

А потом бинпоиском ищу ту line, в которой находится нужный оффсет

Спасибо стандартной библиотеке Rust за то, что там есть бинпоиск

А, ну и норм. По идее быстрее и не получится

Можно быстрее и быстрее, но гораздо дороже по памяти

Можно все номера байтов сложить в хешмапу из номера байта в номер строки

Тогда определить строку по оффсету можно мгновенно

Но это оверкилл

Я, собственно, этот итератор долго составлял, дальше всё просто

Ага, сильно оверкилл.

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

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

И тогда уже не в хешмапу а в массив просто. Ключи не имеют смысла, если они просто от нуля до длины string.len()

Логично, да

Ну типа бинпоиск заглянет сразу в середину, а ты можешь по средней длине строки прикинуть куда нужно глянуть чтоб не в середину, а если пропамзал, скорректировать на сколько промазал опять отталкиваясь на среднюю длину строки.. ну это я к примеру. Так то я не знаю как оно будет быстрее или медленнее. Знаю что сравнения дешевле чем вычисления. Так что я бы не заморачивайся над своим поисковым велосипедом))) Наверное.

А. Ну технически можно, да, особенно с учётом того, что среднюю длину строки я знаю.

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

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