Хотелось бы иметь вектор, из которого максимально дёшево можно удалять элементы и при этом иметь индексный доступ к элементам, скорость которого (почти) не зависит от собственно индекса.
Проблема в том, что из ассоциативных массивов элементы удаляются легко и просто, но при этом ассоциативные массивы нормально не итерируются по значению ключа, и в этом есть некая проблема на фоне того, что сам по себе доступ к элементам АМ осуществляется вычислением дорогостоящей хеш-функции.
Как себе представляю попытку решения проблемы созданием двухсвязного списка и к чему в итоге прихожу:
=== Есть служебная структура данных - перечислитель ===
Перечислитель представляет собой динамический массив смещений до элементов списка для быстрого поиска элемента за номером N.
Перечислитель скорее всего реализуется «на стеке», хотя мне ближе подход с malloc'ами статичных чанков и связыванием этих чанков через ещё одну надстроечную структуру. Проще говоря, такой вектор сам по себе должен быть динамически расширяемым. А как? Ну вот либо malloc'ом выделять чанк, а потом когда закончится - выделять новый и связывать со старым, либо... на этом мысль останавливается, потому что таки да, стек - это не абстракция, а тот же чанк в памяти и у стека тоже есть границы.
=== Есть собственно элементы двухсвязного списка ===
Каждый элемент списка содержит в себе: смещение предыдущего элемента, смещение до полезных данных элемента (payload), размер полезных данных, смещение последующего элемента, индекс текущего элемента.
=== Поиск элемента списка за номером N=3937 ===
Идём в служебную структуру данных - перечислитель, смотрим её заголовок:
ага, элементы с 0 по 2048-й - ищи по смещению такому-то. Не подходит, у нас 3937
следующая запись: элементы с 2048 до 4096 - ищи по смещению AUX_OFFSET
OK, нам подходит, у нас как раз N>2048 && N<4096
Вычисляем смещение до элемента перечислителя, содержащего указатель на элемент списка.
DLL_EL_OFFSET=QWORD(AUX_OFFSET+(3937-2048)*8)
Получили смещение до элемента списка - взяли данные, считав смещение до payload.
=== Удаление элемента из списка ===
Вот здесь мне нужно радостно удалить указатель на элемент списка из служебной структуры - и это становится некоторой проблемой, потому что для этого мне нужно циклически перекопировать всё содержимое вектора смещений до элементов списка, сдвинув всё его содержимое после удалённого значения несуществующего элемента вправо (в сторону меньших адресов). А это, мягко говоря, геморройноё занятие, потому что копирование памяти само по себе небыстрое, а тут мы имеем дело ещё и по сути со служебным списком - «динамическим массивом».
После непродолжительных раздумий напрашивается вывод о том, что дуализм двухсвязного списка, позволяющий представлять его и как просто вектор, и как список - невозможен без тупого перебора всех элементов списка вплоть до того. как будет найден нужный нам в рамках «парадигмы вектора» элемент N.
Т.е. списки хорошо итерируются влево-вправо, но вот как сделать так, чтобы можно было всё-таки находить просто элемент за номером N со скоростью O(1) (говоря не на птичьем языке - за время, «почти независящее» от этого самого N) ?
В общем, интересно есть ли библиотечные реализации двухсвязных списков, элементы которых можно быстро адресовать по индексу, делая минмальное количество телодвижений и уж точно не делая интенсивных переборов? Безусловно, поиск элемента N может быть более трудоёмким, нежели поиск 0-го, но хотелось, чтобы разница была минимальной, а не «равно максимизированной для всех», как это имеет место быть в случае ассоциативного массива.
P.S. И где-то там за горизонтом сам собой встаёт вопрос о том, а можно ли кешировать результат выполнения хеш-функции? Префиксным деревом, быть может?
