Реализовать линейное зондирование в C++ для универсального типа

Question

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

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

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

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

ИЛИ ЖЕ

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

Вы можете использовать бесплатную функцию 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 ! или где требуется другая логика для проверки