Хочу структуру данных удовлетворяющую следующим условиям:
- Хранит в себе пары ключ-значение. Ключи - числа от 0 до 4095. Значения - uint32_t, но в целом вряд ли принципиально для алгоритма.
- Элементы отсортированы по возрастанию ключа - имея в каком-то виде указатель на элемент можно со сложностью O(1) получить указатель на следующий или на предыдущий (то есть возможна дешёвая итерация в обе стороны, полный обход списка в порядке сортировки и обратном имеет сложность O(N) - просто выполнить O(1) для каждого элемента) в порядке сортировки ключей.
- Существует операция поиска элемента по ключу со сложностью не более O(logN). При этом если элемента с таким ключом нет, должен находиться элемент с максимальным ключом меньше запрошенного. Функция поиска возвращает в каком-то виде указатель на элемент, который позволяет не только узнать его значение, но и выполнять итерирование, а также вставку и удаление элементов перед или после него.
- Операции добавления и удаления элементов - дешёвые, но выполняются значительно реже итерирования. Сложность не более O(logN).
- Эффективность по памяти. Требуется добавлять необходимый минимум служебной информации к элементам (так как сами элементы всего лишь 6 байт). Ну и само собой нельзя взять и выделить память сразу под 4096 возможных элементов, когда в реальности может лежать лишь пара сотен.
- Операции итерирования и поиска элементов не должны приводить к модификации структуры данных, чтобы можно было использовать RW блокировки и несколько потоков могли одновременно читать одну и ту же структуру (невозможность записи без эксклюзивной блокировки это нормально).
- Здорово если бы добавление-удаление элементов не инвалидировало указатели на не затронутые элементы, но это опциональное требование.
Как я понимаю, разумно использовать какой-нибудь std::vector, в который запихнуть элементы с обвязкой, а указатели между элементами (для построения какого-нибудь двоичного дерева) делать в виде 16-битных индексов (ведь максимальное число уникальных ключей всего 4096). Вопрос в том какую структуру данных построить поверх вектора.
