Любому программисту будет полезно понимание различных структур данных и способов анализа их производительности. Но на практике мне ни разу не пригождались АВЛ-деревья, красно-чёрные деревья, префиксные деревья, списки с пропусками, и т.д. Некоторые структуры данных я использую только для одного конкретного алгоритма и ни для чего больше (например, кучи для реализации очереди с приоритетом в алгоритме поиска пути A*).
В повседневной работе я обычно обхожусь на удивление малым количеством структур данных. Чаще всего мне пригождаются:
- Общие массивы данных (Bulk data) — способ эффективного хранения большого количества объектов.
- Слабые ссылки (Weak reference) (или дескрипторы (handle)) — способ обращения к объектам в bulk data без сбоев программы в случае, если объект удалён.
- Индексы — способ быстрого доступа к отдельным подмножествам в bulk data.
- Массивы массивов — способ хранения объектов bulk data с динамическими размерами.
Я посвящу несколько статей тому, как я обычно реализую все эти структуры. Давайте начнём с простейшей и самой полезной — bulk data.