Так что я действительно устала от своего C ++ и пытаюсь реализовать компактный контейнер отображения в качестве упражнения.Я пытаюсь найти лучший способ позволить моему классу выбрать лучший / наименьший тип для динамически размещаемого массива.Кроме того, этот тип может измениться в течение срока службы объекта.
Идея состоит в том, что вы разбиваете хэш-таблицу на таблицу и данные:
table: [-1, -1, 2, -1, 1, 0]
data: [ [h0, key0, value0], [h1, key1, value1], [h2, key2, value2] ]
При предварительном поиске вы хешируете ключ% размера таблицы и получаете соответствующий индекс в массиве данных.Сохраняя фактическую хеш-таблицу разреженной и как можно меньшей и легкой, вы можете получить хорошую скорость кеширования и т. Д. Кроме того, элементы можно перебирать по порядку.
Чтобы таблица была маленькой, я хочу, чтобы она использовала наименьший возможный тип данных для хранения индексов (с запасом для минимизации коллизий):
- char до 127 элементов
- short до 2 ** 15
- int до 2 ** 31
- longs впоследствии
По мере добавления новых записей массив таблиц будетнеобходимо изменить размер и в конечном итоге изменить тип.Я пытаюсь найти лучший способ сделать это в моем контейнере.
Поскольку в моих определениях мне придется использовать тип массива таблиц, мне придется использовать некоторыевид полиморфизма.Я не думаю, что шаблон будет работать, так как тип может измениться и не будет известен во время выполнения.
Я немного читал об объединениях и вариантах, но из того, что я понимаю о них, я не понимаюНе думаю, что они будут работать.
Я немного знаю C, но я знаю, что использование указателей void недовольно в C ++.
Лучшее, что я придумал, - это какой-то базовый класс, чтобы сообщить моему контейнеручто все массивы table поддерживают один и тот же интерфейс.Но похоже, что я буду дублировать большой объем кода и вставлять некоторые виртуальные функции поиска для чего-то, что я хочу сделать простым и быстрым, насколько это возможно.
template <typename K, typename V>
struct Entry {
int hash;
V value;
K key;
};
class Table {
public:
virtual int operator[](int) =0;
}
class CharTable: public Table {
public:
CharTable(int s) :t{new char[s]}{}
int operator[](int i) { return t[i]; }
~CharTable() {delete t[];}
private:
char* t;
}
// short table etc...
template <typename K, typename V>
class CompactMapping {
public:
CompactMapping();
V& operator[](const K&);
unsigned int size() const {return sz;}
void resize(unsigned int);
private:
vector<Entry<K,V>> entries;
unsigned int sz;
Table* table;
int allocated;
}
template <typename K, typename V>
V& CompactMapping<K, V>::operator[](const K& key){
//simplified
int index = table[hash(key) % allocated];
if (entries[index].key == key){
return entries[index].value;
}
}
template <typename K, typename V>
void CompactMapping<K, V>::resize(unsigned int s){
if (s <= 2**7)
CharTable* t = new CharTable(s);
if (s <= 2**15)
ShortTable* t = new ShortTable(s);
//... maybe a switch statement instead
for (int i=0; i!=sz; ++i)
t[entries[i].hash %s] = i;
delete *table;
table = t;
allocated = s;
}
Полное раскрытие Я фактически не проверял это,поэтому реализация может быть отключена.Прежде чем идти по этому пути, я просто хочу знать, в порядке ли мое мышление или есть лучшее решение.
Я также был бы признателен за любые другие советы, которые вы, ребята, могли бы дать мне.