Я пытаюсь создать хэш-карту, которая использует шаблон. Шаблон будет принимать хеш-функцию (в форме хэша (ключ int, размер int)) и функцию зондирования (в форме зондирования (int i) в случае зондирования и зондирования (ключ int, размер int) в случае двойного хэша. Я надеюсь, вы понимаете, о чем я говорю. Вот мое главное:
#include "generic_map.h"
inline int hash( int key, std::size_t M ) { return key % M; }
inline int hash2( int key, std::size_t M ) { return key % (M-1) + 1; }
inline int linear_probe( int i ) { return i; }
inline int quadratic_probe( int i ) { return i*i; }int main() {
generic_map<int, char, int(*)(int,std::size_t), hash, int(*)(int), quadratic_probe, false> map1( 20);
generic_map<int, char, int(*)(int,std::size_t), hash, int(*)(int, std::size_t), hash2, true> map2( 20);
}
Как вы можете видеть, я передаю два разных типа функций указателя в качестве функции зонда. «Hash2» будет передан как функция зонда в случае двойного хеширования. Вот фрагмент из моего файла заголовка (а именно, объявление моего класса, объявление узла и метод вставки:
template <class KEY, class VALUE, class HASH_FUNC, HASH_FUNC hash, class PROBE_FUNC, PROBE_FUNC probe, bool double_hash>
//Hashmap Class
class generic_map {
private:
//Node Class
struct hashNode {
KEY key; //Stores the key of node
VALUE value; //Stores the value that associates to key
hashNode(KEY key, VALUE &value) : key(key), value (value) {} //hashNode constructor
};
public:
//Creates a new backing array with user inserted capacity
generic_map( int capacity ) {
M = capacity;
map = new hashNode * [capacity];
for(int i = 0; i < M; ++i) {
map[i] = NULL;
}
}
//Deletes the hashNodes in the list and the map
~generic_map() {
clear();
}
//If index that key hashes to is empty, insert. Else, replace value at hashed index.
int insert( KEY key, VALUE value ) {
int f = hash( key, M );
int p = 0;
int h = f;
while( map[h] != NULL ) {
if( p == M )
return -1 * p;
if( map[h]->key == key ) {
map[h]->value = value;
return p;
}
else {
++p;
if(double_hash) {
h = f + (p * probe(key, M)) % M;
}
else {
h = f + (probe( p )) % M; //This is throwing an error and will not compile,
} //saying, "too few arguments to function call.
}
}
Часть «else» условия «double_hash_» в моем методе вставки помечает ошибку, потому что я, конечно, вызываю один и тот же зонд, функцию шаблона с двумя разными номерами аргументов. Я не спрашиваю, ПОЧЕМУ она выдает ошибку, так как я уже знаю почему. Я прошу решение этого — или обойти. Спасибо.
Вот несколько решений, о которых я могу подумать:
Быстрое и грязное исправление состоит в том, чтобы объявить фиктивный второй параметр по умолчанию, который не будет использоваться, для функций зонда с одним параметром, таких как
inline int linear_probe( int i, int dummy = 0 ) { return i; }
Теперь у linear_probe фактически 2 параметра, но один инициализируется по умолчанию, так что вы сможете использовать двухпараметрический указатель на функцию для указания на него. Но это решение не самое элегантное, наверное, стоит подумать об изменении своего дизайна. Почему бы не создать 2 отдельных класса, один для простого хеширования, другой для двойного? Или возможно сделать двойное хеширование наследованным от простого хеширования.
Используйте шаблонную специализацию
Вам нужно специализировать класс generic_map
за true
а также false
, Сохраните свое общее определение, но просто специализируйте 2 версии как template<typename types (omit bool here as we specialize)> generic_map<types, true>
, Посмотрите здесь, например: http://cprogramming.com/tutorial/template_specialization.html