Хочу иметь что-то типа std::set, или возможно, std::map, ключом выступает строка (голый указатель char), и чтобы всё хранилось в одном куске памяти, который статически задается, и никогда не происходит перевыделений. Если места не хватило — просто падаем.
Хочется максимально быстро искать, добавление будет производится при отсутствии ключа наверное на пару десятичных порядков реже.
Пока придумал строки класть в один кусок памяти, указатели на них (на пару с индексом/указателем полезной нагрузки) — в другой кусок памяти, полезную нагрузку — в третий кусок памяти.
При добавлении нам нужно только найти место для вставки и раздвинуть один массив с указателем-ключом или { ключ, индекс } (для мапа).
Возможно есть готовые алгоритмы/реализации получше для заданных условий?
Здравствуйте, Marty, Вы писали:
M>Здравствуйте!
M>Хочу иметь что-то типа std::set, или возможно, std::map, ключом выступает строка (голый указатель char), и чтобы всё хранилось в одном куске памяти, который статически задается, и никогда не происходит перевыделений. Если места не хватило — просто падаем.
А может взять готовый контейнер и к нем добавить аллокатор, который будет с твоим куском памяти работать? Мне думается это будет проще, чем не только памятью управлять, но еще и логику set/map реализовывать.
Здравствуйте, kaa.python, Вы писали:
M>>Хочу иметь что-то типа std::set, или возможно, std::map, ключом выступает строка (голый указатель char), и чтобы всё хранилось в одном куске памяти, который статически задается, и никогда не происходит перевыделений. Если места не хватило — просто падаем.
KP>А может взять готовый контейнер и к нем добавить аллокатор, который будет с твоим куском памяти работать? Мне думается это будет проще, чем не только памятью управлять, но еще и логику set/map реализовывать.
Теоретически можно, но тут ещё нюанс — std::map/set — это дерево, как минимум — это пара, а то и тройка указателей дополнительно. Для MCU — жирновато, хочется подешевле по памяти.
Здравствуйте, Marty, Вы писали:
M>Хочу иметь что-то типа std::set, или возможно, std::map, ключом выступает строка (голый указатель char), и чтобы всё хранилось в одном куске памяти, который статически задается, и никогда не происходит перевыделений. Если места не хватило — просто падаем.
Может быть boost::flat_map/set подойдет, если создать его с собственным аллокатором фиксированного размера, ну или посмотреть что там в boost::pool есть.
Здравствуйте, Marty, Вы писали:
M>Хочу иметь что-то типа std::set, или возможно, std::map, ключом выступает строка (голый указатель char), и чтобы всё хранилось в одном куске памяти, который статически задается, и никогда не происходит перевыделений. Если места не хватило — просто падаем.
M>Хочется максимально быстро искать, добавление будет производится при отсутствии ключа наверное на пару десятичных порядков реже.
M>Пока придумал строки класть в один кусок памяти, указатели на них (на пару с индексом/указателем полезной нагрузки) — в другой кусок памяти, полезную нагрузку — в третий кусок памяти. M>При добавлении нам нужно только найти место для вставки и раздвинуть один массив с указателем-ключом или { ключ, индекс } (для мапа).
M>Возможно есть готовые алгоритмы/реализации получше для заданных условий?
Хеш таблица
Поставь лимит на длину ключа, и выделяй память на, скажем, 2x(длина ключа + длина полезной нагрузки) максимально планируемое количество ключей. Если ключ в коллизию попал- падай. Никаких реаллокаций не делай.
Здравствуйте, Marty, Вы писали:
M>Теоретически можно, но тут ещё нюанс — std::map/set — это дерево, как минимум — это пара, а то и тройка указателей дополнительно.
На одном куске памяти это делается элементарно.
Вместо указателей в структурах нод — индексы в этом самом массиве нод.
M>При добавлении нам нужно только найти место для вставки и раздвинуть один массив с указателем-ключом или { ключ, индекс } (для мапа).
Ничего раздвигать не надо.
Ноды фиксированного размера.
Свободное место "ищется" за O(1) (https://en.wikipedia.org/wiki/Free_list).
