CODEWITHSUNDEEP
c++templateshashtable
tul1
tul1

Reputation: 414

Template HashTable

I'm trying to write a code for a template HashTable but I'm blocked with some compilation errors.

Class 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;
};

The data type lista I'm using is linked list already tested.

To use several hash function depending on the key's type y develop the following class:

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;
};

Every function on hashes for a different data type.

The errors I'm getting from gcc compiler are:

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)))’

It seems to be having a problem every time I ask for dynamic memory:

new lista<HashElement*>()

I don't really know how to solve the problem.

These are the methods: 

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;
}

Upvotes: 0

Views: 2372

Answers (1)

Alan Stokes
Alan Stokes

Reputation: 18972

You don't need (and mustn't have) the typename in typename lista<HashElement*>* temp = ... or in typename HashTable<Key,Value> * aux(bucket_num_*INCREASE_FACTOR);.

Its purpose is to clarify whether a nested name of a template specialization is a type or not; you don't have a nested name (i.e. one with a :: in it) there.

But you do need it in typename lista<HashElement*>::iterador it; - here it's needed to tell the compiler that the iterador you are referring to is a type.

Upvotes: 1

Related Questions