Быстрое перемещение по списку

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

Сделай и проверь на сколько это ускорит твою задачу.

Может проще сделать индексацию: завести массив ссылок на элементы?

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

> с очень большим количеством элементов, к которой новые элементы добавляются редко, а перемещение должно выполняться быстро.

А почему тогда не использовать простой массив?

Если элементов очень много, такой массив просто может не поместиться в памяти.

> Если элементов очень много, такой массив просто может не поместиться в памяти.

видится мне каша в твоих представлениях о мире..

>видится мне каша в твоих представлениях о мире..

Этого я не отрицаю. Но массив действительно может не влезть в адресное пространство процесса, если оно сильно фрагментированно.

> Этого я не отрицаю. Но массив действительно может не влезть в адресное пространство процесса, если оно сильно фрагментированно.

а) весь мир уже давно ползет на 64 бита, по крайней мере на десктопах и серверах. Там сия проблема отсутсвует

б) если вы не будете аллоцировать списки из миллионов элементов - то у вас не будет такой жуткой фрагментации памяти ;)

в) используйте правильные аллокаторы

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

есть такая структура данных -- список массивов. Готовая реальзация -- CvSeq в opencv

>Но массив действительно может не влезть в адресное пространство процесса, если оно сильно фрагментированно.

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

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

Что мешает к текущему указателю прибавить нужное значение?

Вероятно то, что это - список. =)