Help! Hashtable using C++

Discussion in 'OT Technology' started by fifidong, Dec 19, 2004.

  1. fifidong

    fifidong Active Member

    Joined:
    May 27, 2003
    Messages:
    2,056
    Likes Received:
    0
    Location:
    Colorado
    Code:
    --------------------Configuration: hashtable - Win32 Debug--------------------
    Compiling...
    main.cpp
    Linking...
    main.obj : error LNK2001: unresolved external symbol "public: __thiscall hashtable<int>::~hashtable<int>(void)" ([email protected]@@[email protected])
    main.obj : error LNK2001: unresolved external symbol "public: __thiscall hashtable<int>::hashtable<int>(int)" ([email protected]@@[email protected]@Z)
    Debug/hashtable.exe : fatal error LNK1120: 2 unresolved externals
    Error executing link.exe.
    How do I fix this error?

    cpp file.
    Code:
    #include <iostream>
    using namespace std;
    
    #include "hashtable.h"
    
    template <class TYPE>
    hashtable<TYPE>::hashtable(int size)
    {
    	// set maxsize
    	maxsize = size;
    
    	// create dynamic spaces
    	Table = new TYPE [maxsize];
    	filled = new bool [maxsize];
    
    	// initialize filled to false
    	for (int i=0; i<maxsize; i++) filled[i]=false;
    }
    
    template <class TYPE>
    hashtable<TYPE>::hashtable(const hashtable<TYPE> & original)
    {
    	maxsize = original.maxsize;
    	
    	Table = new TYPE [maxsize];
    	filled = new bool [maxsize];
    
    	for (int i=0; i<maxsize; i++)
    	{
    		Table[i]=original.Table[i];
    		filled[i]=original.filled[i];
    	}
    }
    
    template <class TYPE>
    hashtable<TYPE>::~hashtable()
    {
    	// if dynamic storage exists delete it
    	if (Table)
    	{
    		delete [] Table;
    		delete [] filled;
    	}
    	// ... and set their pointers to 0
    	Table=0;
    	filled=0;
    }
    
    template <class TYPE>
    int hashtable<TYPE>::Insert(TYPE item)
    {
    	int hashed = hash(item);
    	if (!filled[hashed])
    	{
    		// no collision then.. input
    		Table[hashed] = item;
    		filled[hashed] = true;
    		// return the location of input
    		return hashed;
    	}
    	// return -1 when collision occured
    	return -1;
    }
    
    template <class TYPE>
    bool hashtable<TYPE>::Delete(TYPE item)
    {
    	int hashed = hash(item);
    	// if found at the address, set filled to false.
    	if (filled[hashed] && Table[hashed]==item) 
    	{
    		filled[hashed] = false;
    		return true;
    	}
    	return false;
    }
    
    template <class TYPE>
    int hashtable<TYPE>::Search(TYPE item)
    {
    	int hashed = hash(item);
    	if (filled[hashed] && Table[hashed]==item)
    		return hashed;	// found, returning position
    	else return -1;		// not found
    }
    
    template <class TYPE>
    void hashtable<TYPE>::Print(ostream &out)
    {
    	for (int i=0; i<maxsize; i++)
    	{
    		// if filled, output as needed
    		if (filled[i])	out << "Table " << i << " - " << Table[i] << endl;
    	}
    }
    
    template <class TYPE>
    int hashtable<TYPE>::hash(int/*TYPE*/ item)
    {
    	const int MULTIPLIER = 25173;
    	const int ADDEND =13849;
    	int MODULUS = maxsize;
    
    	return ((MULTIPLIER * static_cast<int>(item)) + ADDEND) % MODULUS;
    }
    
    h file
    Code:
    #ifndef HASHTABLE_H
    #define	HASHTABLE_H
    
    #include <iostream>
    using namespace std;
    
    template <class TYPE>
    class hashtable
    {
    public:
    	hashtable( int );
    	hashtable( const hashtable<TYPE> & original );
    	~hashtable();
    
    	int Insert( TYPE );
    	bool Delete( TYPE );
    	int Search( TYPE );
    	void Print( ostream & );
    private:
    	int hash( int );
    	TYPE * Table;
    	bool * filled;
    	int maxsize;
    };
    
    #endif
    
    main file
    Code:
    #include "hashtable.h"
    
    void main()
    {
    	hashtable<int> T(10);
    }
    
     
  2. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Is main.cpp the main file?
    If the first cpp file is separate from the main file, then it doesn't look like it's being compiled and linked into the exe. Make sure it's included in your project.
     
  3. fifidong

    fifidong Active Member

    Joined:
    May 27, 2003
    Messages:
    2,056
    Likes Received:
    0
    Location:
    Colorado
    (1st) implementation cpp
    (2nd) implementation h
    (3rd) main.cpp is the main file
    it's being compiled. it's template issue.

    not sure what though
     
  4. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    I see main.cpp, but I don't see implementation.cpp
     
  5. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Nevermind. The problem has to do with how templates are compiled. When implementation.cpp is compiled, an instance of the functions for hashtable<int> is not created because hashtable<int> is not being used in that file.

    You can do one of two things:
    1) Move the contents of implementation.cpp into hashtable.h and get rid of implementation.cpp. This will include the function bodies in every translation unit in which hashtable is used, and ensure that correct instances of the functions are created.

    2) Add a dummy static global instance of hastable<int> in implementation.cpp. Since an instance of hastable<int> is created while the function bodies are compiled, the correct instances of the functions will be created.
     
  6. fifidong

    fifidong Active Member

    Joined:
    May 27, 2003
    Messages:
    2,056
    Likes Received:
    0
    Location:
    Colorado
    awesome. you rock :) thx
     

Share This Page