Сообщение Re: set/map в одном куске памяти от 17.10.2020 3:55
Изменено 17.10.2020 4:03 Артём
Re: set/map в одном куске памяти
Здравствуйте, Marty, Вы писали:
M>Хочу иметь что-то типа std::set, или возможно, std::map, ключом выступает строка (голый указатель char), и чтобы всё хранилось в одном куске памяти, который статически задается, и никогда не происходит перевыделений. Если места не хватило — просто падаем.
M>Хочется максимально быстро искать, добавление будет производится при отсутствии ключа наверное на пару десятичных порядков реже.
M>Пока придумал строки класть в один кусок памяти, указатели на них (на пару с индексом/указателем полезной нагрузки) — в другой кусок памяти, полезную нагрузку — в третий кусок памяти.
M>При добавлении нам нужно только найти место для вставки и раздвинуть один массив с указателем-ключом или { ключ, индекс } (для мапа).
M>Возможно есть готовые алгоритмы/реализации получше для заданных условий?
Хеш таблица
Поставь лимит на длину ключа, и выделяй память на, скажем, 2x(длина ключа + длина полезной нагрузки) максимально планируемое количество ключей. Если ключ 2 раза в коллизию попал- падай. Никаких реаллокаций не делай.
M>Хочу иметь что-то типа std::set, или возможно, std::map, ключом выступает строка (голый указатель char), и чтобы всё хранилось в одном куске памяти, который статически задается, и никогда не происходит перевыделений. Если места не хватило — просто падаем.
M>Хочется максимально быстро искать, добавление будет производится при отсутствии ключа наверное на пару десятичных порядков реже.
M>Пока придумал строки класть в один кусок памяти, указатели на них (на пару с индексом/указателем полезной нагрузки) — в другой кусок памяти, полезную нагрузку — в третий кусок памяти.
M>При добавлении нам нужно только найти место для вставки и раздвинуть один массив с указателем-ключом или { ключ, индекс } (для мапа).
M>Возможно есть готовые алгоритмы/реализации получше для заданных условий?
Хеш таблица
Поставь лимит на длину ключа, и выделяй память на, скажем, 2x(длина ключа + длина полезной нагрузки) максимально планируемое количество ключей. Если ключ 2 раза в коллизию попал- падай. Никаких реаллокаций не делай.
Re: set/map в одном куске памяти
Здравствуйте, Marty, Вы писали:
M>Хочу иметь что-то типа std::set, или возможно, std::map, ключом выступает строка (голый указатель char), и чтобы всё хранилось в одном куске памяти, который статически задается, и никогда не происходит перевыделений. Если места не хватило — просто падаем.
M>Хочется максимально быстро искать, добавление будет производится при отсутствии ключа наверное на пару десятичных порядков реже.
M>Пока придумал строки класть в один кусок памяти, указатели на них (на пару с индексом/указателем полезной нагрузки) — в другой кусок памяти, полезную нагрузку — в третий кусок памяти.
M>При добавлении нам нужно только найти место для вставки и раздвинуть один массив с указателем-ключом или { ключ, индекс } (для мапа).
M>Возможно есть готовые алгоритмы/реализации получше для заданных условий?
Хеш таблица
Поставь лимит на длину ключа, и выделяй память на, скажем, 2x(длина ключа + длина полезной нагрузки) максимально планируемое количество ключей. Если ключ в коллизию попал- падай. Никаких реаллокаций не делай.
M>Хочу иметь что-то типа std::set, или возможно, std::map, ключом выступает строка (голый указатель char), и чтобы всё хранилось в одном куске памяти, который статически задается, и никогда не происходит перевыделений. Если места не хватило — просто падаем.
M>Хочется максимально быстро искать, добавление будет производится при отсутствии ключа наверное на пару десятичных порядков реже.
M>Пока придумал строки класть в один кусок памяти, указатели на них (на пару с индексом/указателем полезной нагрузки) — в другой кусок памяти, полезную нагрузку — в третий кусок памяти.
M>При добавлении нам нужно только найти место для вставки и раздвинуть один массив с указателем-ключом или { ключ, индекс } (для мапа).
M>Возможно есть готовые алгоритмы/реализации получше для заданных условий?
Хеш таблица
Поставь лимит на длину ключа, и выделяй память на, скажем, 2x(длина ключа + длина полезной нагрузки) максимально планируемое количество ключей. Если ключ в коллизию попал- падай. Никаких реаллокаций не делай.