mmap-загружаемая библиотека структуры данных для C ++ (или C)

Question

У меня есть некоторая большая структура данных (N> 10000), которую обычно нужно создавать только один раз (во время выполнения), и впоследствии можно многократно использовать, но ее нужно загружать очень быстро. (Он используется для обработки пользовательского ввода на iPhoneOS.) mmap -ing файл кажется лучшим выбором.

Существуют ли библиотеки структур данных для C ++ (или C)? Что-то по линии

ReadOnlyHashTable<char, int> table ("filename.hash");
// mmap(...) inside the c'tor
...
int freq = table.get('a');
...
// munmap(...); inside the d'tor.

Спасибо!

---

подробности:

Я сам написал аналогичный класс для хеш-таблицы, но мне трудно поддерживать его, поэтому я хотел бы посмотреть, существуют ли уже существующие решения. Библиотека должна

• Содержит подпрограмму создания , которая сериализует структуру данных в файл. Эта часть не должна быть быстрой.
• Содержит подпрограмму загрузки , которая отображает файл в структуру данных только для чтения (или чтения-записи), которую можно использовать на O (1) этапах обработки.
• Используйте O (N) объем дискового пространства / памяти с небольшим постоянным коэффициентом. (Устройство имеет серьезные ограничения памяти.)
• Небольшие накладные расходы на средства доступа. (т.е. сложность не изменена.)

Предположения:

• Битовое представление данных (например, порядковый номер, кодировка float и т. Д.) Не имеет значения, поскольку оно используется только локально.
• Пока что мне нужны возможные типы данных: целые числа, строки и struct из них. Указатели не появляются.

P.S. Может ли Boost.intrusive помочь?

Answer 1

Вы можете попытаться создать файл отображения памяти, а затем создать структуру карты STL с распределителем клиентов. Затем ваш клиентский распределитель просто берет начало памяти отображенного файла памяти, а затем увеличивает его указатель в соответствии с запрошенным размером. В конце концов вся выделенная память должна быть в памяти отображенного в памяти файла и должна быть перезагружена позже.

Вам нужно проверить, свободна ли память по карте STL. Если это так, ваш клиентский распределитель потеряет часть памяти отображенного в памяти файла, но если он ограничен, вы, вероятно, можете жить с ним.

Answer 2

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

CMPH утверждает, что справляется с большим количеством ключей. Тем не менее, я никогда не использовал его.

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

Answer 3

GVDB (База данных GVariant), ядро ​​Dconf именно это.

См. git.gnome.org / browse / gvdb , dconf и bv
и developer.gnome.org / glib / 2.30 / glib-GVariant.html

Answer 4

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

Вероятно, лучший вариант - использовать sparse_hash_map от Google. У него очень низкие накладные расходы, а также есть нужные вам крючки сериализации.

http://google -sparsehash.googlecode.com / SVN / багажник / док / sparse_hash_map.html # ИО

Answer 5

WRT boost.intrusive, я только что посмотрел. Это интересно. И раздражает, потому что одна из моих собственных библиотек выглядит немного бессмысленно.

Я думал этот раздел выглядел особенно актуально.

Если вы можете использовать «умные указатели» для ссылок, предположительно, умный тип указателя может быть реализован с использованием простого целого числа смещения от базового адреса (и я думаю, что в этом пример). Индекс массива может быть одинаково действительным.

Конечно, есть неупорядоченная поддержка множеств / множеств (код C ++ для хеш-таблиц).

Answer 6

Просто подумал о другом варианте - Datadraw . Опять же, я не использовал это, так что никаких гарантий, но он претендует на то, чтобы быть быстрым постоянным генератором кода базы данных.