Какой контейнер использовать для String-Interning
Моя цель — сделать интернирование строк. Для этого я ищу хеш
контейнерный класс, который может делать следующее:
- выделить только один блок памяти на узел
- разный размер пользовательских данных на узел
Тип значения выглядит так:
struct String
{
size_t refcnt;
size_t len;
char data[];
};
Каждый объект String будет иметь разный размер. Это будет достигнуто с
Оператор новый + размещение нового.
Так что, в основном, я хочу выделить Node сам и вставить его в контейнер позже.
Следующие контейнеры не подходят:
- станд :: unordored_set
-
повышение :: multi_index :: *
Невозможно выделить узлы разных размеров
-
повышение :: навязчивый :: unordered_set
Кажется, работает на первых порах. Но имеет некоторые недостатки. Прежде всего, вы должны выделить
массив ковшей и поддерживайте коэффициент загрузки самостоятельно. Это просто ненужно
и подвержен ошибкам.Но сложнее решить еще одну проблему: вы можете искать только те объекты, которые имеют
введите String. Но неэффективно выделять строку каждый раз, когда вы ищете запись
и у вас есть только то есть std :: string в качестве входных данных.
Есть ли другие хешированные контейнеры, которые можно использовать для этой задачи?
Решение
Я не думаю, что вы можете сделать это с любым из стандартных контейнеров.
Что вы можете сделать, это сохранить указатель на String и предоставить пользовательские хеш-функции и cmp-функторы
struct StringHash
{
size_t operator() (String* str)
{
// calc hash
}
};
struct StringCmp
{
bool operator() (String* str1, String* str2)
{
// compare
}
};
std::unordered_set<String*, StringHash, StringCmp> my_set;
Другие решения
Ваше определение для String не будет компилироваться в C ++; очевидное
Решение состоит в том, чтобы заменить data поле с указателем (в котором
случай, вы можете поместить сами структуры в
std::unordered_set).
Можно создать открытую структуру в C ++ с
что-то вроде следующего:
struct String
{
int refcnt;
int len;
char* data()
{
return reinterpret_cast<char*>(this + 1);
}
};
Вы катаетесь на тонком льду, если вы делаете, однако; для других типов
чем charесть риск, что this + не будет
соответствующим образом выровнен.
Если вы сделаете это, то ваш std::unordered_set придется
содержат указатели, а не элементы, поэтому я сомневаюсь, что вы
получить что-нибудь для усилий.