模板HashTable

Question

我试图为模板HashTable编写代码，但由于一些编译错误而受阻。

HashTable类：

template<typename Key, typename Value>
class HashTable{
        class HashElement{
            friend class HashTable;
            Key k_;
            Value v_;
        public:
            HashElement();
            HashElement(const Key&, const Value&);
            ~HashElement();
        };
        unsigned int bucket_num_;
        unsigned int size_;
        std::vector<lista<HashElement*>*>* table_;
        HashFunction h_;    

        unsigned int hash(const Key&)const;
        int rehash();
    public:
        HashTable();
        HashTable(const unsigned int);
        HashTable(const HashTable &);
        ~HashTable();
        unsigned int HashTableGetSize(){return size_;};
        unsigned int HashTableGetBucketNumber(){return bucket_num_;};
        int HashTableInsert(const Key&, const Value&);
        bool IsInHashTable(const Key&, const Value&) const;
        bool IsEmptyBucket(const unsigned int) const;
};

我使用的数据类型lista已经被测试过了。

若要根据键的类型y使用几个散列函数，请开发以下类：

class HashFunction{
    public://son todos metodos de sobrecarga
        unsigned int on(const int&) const;
        unsigned int on(const std::string&) const;
        unsigned int on(const float&) const;
};

散列上的每个函数都针对不同的数据类型。

我从gcc编译器那里得到的错误是：

HashTable.hpp: In constructor ‘HashTable<Key, Value>::HashTable()’:
HashTable.hpp:118:12: error: expected nested-name-specifier
HashTable.hpp:118:12: error: expected ‘(’
HashTable.hpp:118:12: error: expected ‘;’
HashTable.hpp:119:16: error: ‘temp’ was not declared in this scope
HashTable.hpp: In constructor ‘HashTable<Key, Value>::HashTable(unsigned int)’:
HashTable.hpp:130:12: error: expected nested-name-specifier
HashTable.hpp:130:12: error: expected ‘(’
HashTable.hpp:130:12: error: expected ‘;’
HashTable.hpp:131:16: error: ‘temp’ was not declared in this scope
HashTable.hpp: In member function ‘int HashTable<Key, Value>::rehash()’:
HashTable.hpp:164:11: error: expected nested-name-specifier
HashTable.hpp:164:11: error: expected ‘(’
HashTable.hpp:164:11: error: expected ‘;’
HashTable.hpp:171:8: error: ‘aux’ was not declared in this scope
HashTable.hpp:175:11: error: ‘aux’ was not declared in this scope
HashTable.hpp: In instantiation of ‘HashTable<Key, Value>::HashTable() [with Key = std::basic_string<char>; Value = int]’:
Hashtest.cpp:10:29:   required from here
HashTable.hpp:119:3: error: no match for ‘operator*’ in ‘**(((HashTable<std::basic_string<char>, int>*)this)->HashTable<std::basic_string<char>, int>::table_ + ((sizetype)(i * 12u)))’
HashTable.hpp: In instantiation of ‘HashTable<Key, Value>::~HashTable() [with Key = std::basic_string<char>; Value = int]’:
Hashtest.cpp:10:29:   required from here
HashTable.hpp:149:3: error: no match for ‘operator*’ in ‘**(((HashTable<std::basic_string<char>, int>*)this)->HashTable<std::basic_string<char>, int>::table_ + ((sizetype)(i * 12u)))’

每次我请求动态记忆时，似乎都有问题：

new lista<HashElement*>()

我真的不知道怎么解决这个问题。

以下是这些方法：

template<typename Key, typename Value>
HashTable<Key,Value>::HashElement::HashElement()
{
}

template<typename Key, typename Value>
HashTable<Key,Value>::HashElement::HashElement(const Key &k, const Value &v) : k_(k),v_(v)
{
}

template<typename Key, typename Value>
HashTable<Key,Value>::HashElement::~HashElement()
{
}

template<typename Key, typename Value>
HashTable<Key,Value>::HashTable() : bucket_num_(BUCKET_INIT_NUM), size_(0)
{
    this->h_=HashFunction();
    table_ = new std::vector<lista<HashElement*>*>(BUCKET_INIT_NUM);
    for(unsigned int i=0; i < bucket_num_; i++)
    {
        typename lista<HashElement*>* temp = new lista<HashElement*>();
        *table_[i] = temp;
    }
}

template<typename Key, typename Value>
HashTable<Key,Value>::HashTable(const unsigned int b) : bucket_num_(b), size_(0)
{
    this->h_=HashFunction();
    table_ = new std::vector<lista<HashElement*>*>(BUCKET_INIT_NUM);
    for(unsigned int i=0; i < bucket_num_; i++)
    {
        typename lista<HashElement*>* temp = new lista<HashElement*>();
        *table_[i] = temp;
    }
}

template<typename Key, typename Value >
HashTable<Key,Value>::HashTable(const HashTable &orig)
{
    table_ = new std::vector<lista<HashElement*>*>(orig);
    h_=HashFunction();
    h_=orig.h_;
    size_=orig.size_;
    bucket_num_=orig.bucket_num_;
}

template<typename Key, typename Value>
HashTable<Key,Value>::~HashTable()
{
    for(unsigned int i=0; i < bucket_num_ ; i++)
        delete *table_[i];
    delete table_;
    bucket_num_=0;
    size_=0;
}

template<typename Key, typename Value>
unsigned int HashTable<Key,Value>::hash(const Key &k) const
{
    return this->h_.on(k);
}

template<typename Key, typename Value>
int HashTable<Key,Value>::rehash()
{
    typename HashTable<Key,Value> * aux(bucket_num_*INCREASE_FACTOR);
    bucket_num_ = bucket_num_*INCREASE_FACTOR;
    for(unsigned int i=0; i<bucket_num_; i++)
    {
        typename lista<HashElement*>::iterador it;
        for(it=table_[i]->primero(); !it.extremo(); it.avanzar())
        {
            if( aux->HashTableInsert(it.dato()->k_ ,it.dato()->v_) == -1 )
                return -1;
        }
    }
    table_ = aux->table_;
}

template<typename Key, typename Value>
int HashTable<Key,Value>::HashTableInsert(const Key &k, const Value &v)
{
    if(IsInHashTable(k,v)==true)
        return -1;

    unsigned int bucket = hash(k) % bucket_num_;
    HashElement *e(k,v); 
    table_[bucket]->insertar(e);
    return 0;
}

template<typename Key, typename Value>
bool HashTable<Key,Value>::IsEmptyBucket(const unsigned int pos) const
{
    if(pos>bucket_num_) return false;
    return (table_[pos]->vacia()==true)?true:false;
}

template<typename Key, typename Value>
bool HashTable<Key,Value>::IsInHashTable(const Key & k, const Value & v) const
{
    unsigned int bucket=hash(k)%bucket_num_;
    typename lista<HashElement*>::iterador it;
    for(it=table_[bucket]->primero(); !it.extremo(); it.avanzar())
    {
        if(it.dato()->v_ == v) return true;
    }
    return false;
}

Answer 1

您不需要(也不一定不需要) typename在typename lista<HashElement*>* temp = ...或typename HashTable<Key,Value> * aux(bucket_num_*INCREASE_FACTOR);中。

它的目的是澄清模板专门化的嵌套名称是否是一种类型；您没有嵌套名称(即其中包含::的名称)。

但是在typename lista<HashElement*>::iterador it;中确实需要它--这里需要告诉编译器，您所指的iterador是一种类型。