Блог

Главная - Вопросы по программированию - реализация линейного поиска в c для универсального типа

реализация линейного поиска в c для универсального типа

#c #templates #hashtable #linear-probing

#c #шаблоны #хеш-таблица #линейное зондирование

Вопрос:

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

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

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

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

или

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

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

Комментарии:

1. Вы можете специализировать функцию, содержащую этот код.

2. Вам может понадобиться другая структура данных, которая знает, является ли она «пустой» или нет.

3. Но как я могу специализировать функцию?

4. Свяжите дополнительный флаг с ячейками, предпочтительно в виде упакованного массива битов.

5. Вы не можете. Есть некоторые вещи, которые C не позволяет вам делать. Вы, конечно, можете создать параллельный массив флагов, но это на самом деле не отвечает на вопрос. Вы можете потребовать, чтобы ваш шаблонный тип поддерживал только метод «isnull» некоторого описания, и тогда код не является универсальным.

Ответ №1:

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

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

или, если вас интересуют только ключи

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

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

Комментарии:

1. Что произойдет, если key or value не имеет значения по умолчанию? int Например?

2. @FatihBAKIR, почему бы и нет? В этом случае int будет инициализирован с 0 . Конечно, этот подход предполагает, что конструктор key типа по умолчанию создает объект, который считается empty invalid ключом или. Отредактировал ответ, чтобы подчеркнуть это.

3. @SingerOfTheFall, должен ли я создать пустую пару (в конструкторе) для каждого индекса вектора? Разве это не наложило бы ограничение на то, что размер вектора должен быть известен заранее.

4. @Saurabh, не обязательно. Вам просто нужно убедиться, что при удалении элемента в векторе вы либо 1) действительно удаляете его из вектора, либо 2) заменяете на пустую пару. Таким образом, когда вы позже пройдете вектор, вы либо найдете где-нибудь пустую пару и используете эту ячейку, либо дойдете до конца вектора и добавите к нему.

5. @SingerOfTheFall, еще кое-что. Я написал соответствующий код, пожалуйста, смотрите ссылку: ( gist.github.com/Sharma96/f312af6b3219c992dd1519a572dfddf3 ) . В коде происходит странная вещь, если вы запустите код, вы обнаружите, что когда значение y(в функции ch) равно 5, оно печатает 135057 для значения v[y]. во-первых, как он инициализирует значение для пары на 5-миндекс (и только 5-й индекс), в то время как я вызываю функцию добавления только 4 раза.

Ответ №2:

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

Например.

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

bool isEmpty(const std::string amp;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 ! или где для проверки требуется другая логика

Ответ №3:

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

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

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

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