Предложение по структуре данных!

Question

У меня есть следующие требования к структуре данных:

1. Прямой доступ к элементу с помощью ключа (ключ будет целым числом, диапазон также равен целому диапазону)
2. Избегать выделения памяти по частям (выделение постоянной памяти для структуры данных, включая данные)
3. Должен иметь возможность динамически увеличивать размер структуры данных

Какую структуру данных вы бы предложили?

Любые указатели в этом направлении также будут полезны.

Answer 1

звучит для меня как хеш-таблица (он же словарь)

Answer 2

1) разреженный массив
2,3) куча

В основном вам потребуется реализовать кучу и разреженный массив, которые совместно используют один большой буфер. Обычно значение, хранящееся в разреженном массиве, является указателем. В вашем случае указатель будет относиться к основанию вашей кучи, иначе известный как смещение. Куча должна быть перед разреженным массивом в большом буфере, чтобы изменение размера кучи не изменило смещения.

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