шаблоны — реализовать линейное зондирование в c ++ для универсального типа

Question

шаблоны — реализовать линейное зондирование в c ++ для универсального типа

Я хотел реализовать линейное зондирование для хэштега в C ++, но ключ, значение
Пара будет иметь общий тип, как: вектор< пара< ключ, значение>>(где ключ, значение имеет универсальный тип).

Теперь, при линейном исследовании, если клетка занята, мы пересекаем вектор, пока не найдем пустую ячейку, а затем поместим новую пару в эту ячейку.

Проблема в том, что в общем типе, как я могу проверить, занята ли конкретная ячейка или нет?
Я не могу использовать эти условия:

if(key == '\0')//As key is not of type string

ИЛИ ЖЕ

if(key == 0)//As key is not of type int

Итак, как можно будет проверить, пуста ли конкретная ячейка в векторе или нет?
Пожалуйста, поправьте меня, если я неправильно понял концепцию.

0

c++hashtable linear-probing templates

Решение

Другие решения

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

Например.

template<typename T>
bool isEmpty(const T &t) {
return !t;
}

bool isEmpty(const std::string &s) {
return s.length() == 0;
}

bool isEmpty(double d) {
return d < 0;
}

isEmpty(0); // true
isEmpty(1); // false
isEmpty(std::string()); // true
isEmpty(std::string("not empty")); // false
isEmpty(1.0); // false
isEmpty(-1.0); // true

Вам нужно только специализироваться на ключевых типах, которые не имеют operator ! или где требуется другая логика для проверки

0

В случае, если вы не хотите исключать возможность иметь в своем хэше элементы «по умолчанию», вы можете построить параллельную структуру данных, например std::bitset (если вы заранее знаете максимальный размер вашей структуры данных) или std::vector<bool>, что в следующем я буду называть has, has[i] будет правдой, если vector[i] содержит действительный, фактически вставленный элемент.

Поэтому операции должны быть изменены следующим образом:

вставить: продолжайте сканировать вектор, пока не найдете позицию i такой, что has[i] == false
удалить элемент в положении я: задавать has[i] в false

Надеюсь это поможет

0

Источник

Accepted Answer

Я думаю, вы можете просто проверить, имеет ли элемент вектора значимый ключ и значение:

if(vector[i] == std::pair<key, value>())
//empty

или, если вы заботитесь только о ключах

if(vector[i].first == key())
//empty

Этот подход предполагает, что конструктор по умолчанию key Тип создает объект, который будет считаться «пустым» или «недействительным» ключом.

2