Структура данных в c для быстрого поиска / вставки / удаления целых чисел (из известного конечного домена)

Question

Я пишу игру для мобильного телефона в c. Меня интересует структура данных, которая поддерживает быструю (по возможности, амортизированную O (1)) вставку, поиск и удаление. В структуре данных будут храниться целые числа из области [0, n], где n известно заранее (это константа), а n относительно мало (порядка 100000).

До сих пор я рассматривал массив целых чисел, в котором установлен бит "ih", если в наборе содержится целое число "ih" (поэтому [0] - это целые числа от 0 до 31, а [1] - целые числа С 32 по 63 и т. Д.).

Есть ли более простой способ сделать это в c?

Answer 1

Ваша идея проста и эффективна - при условии, что у вас есть 100000/8 = 12,5 КБ для игры, я не вижу смысла искать другие решения.

Answer 2

Будет работать плоский массив, но он будет стоить 100 000 бит. Другая возможность - это «хэш-набор».