Undefined Symbol error in C++ Hashing Program

Question

I have a set of files that compile with a makefile to make a separate chaining hashing program. The program functions until I added code for insert, remove, and contains functions. I pulled code straight out of the book, but I'm getting an ambiguous error I cannot figure out and am hoping someone here can help identify it. I didn't post the whole program because I'm taking an educated guess that the cause of the error won't be found outside this code (but I could be wrong)

The error in question is:

Undefined                       first referenced
 symbol                             in file
hash(std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)hashApp.o

Also, not sure if this is relevant, but if I try and compile the .cpp file with the functions by itself I get:

Undefined                       first referenced
 symbol                             in file
main                                /opt/csw/gcc3/lib/gcc/sparc-sun-solaris2.8/3.4.6/crt1.o
ld: fatal: Symbol referencing errors. No output written to a.out
collect2: ld returned 1 exit status

Here are the functions, strings are being hashed in a vector of lists:

template <class HashObj>
bool HashTable<HashObj>::contains(HashObj &item)
{
  const list<HashObj> & whichList = theLists[ myhash( item ) ];
  return find( whichList.begin( ), whichList.end( ), item ) != whichList.end( );    
}        

template <class HashObj>
bool HashTable<HashObj>::insert(const HashObj &item)
{
    list<HashObj> & whichList = theLists[ myhash( item ) ];
    if( find( whichList.begin( ), whichList.end( ), item ) != whichList.end( ) )
        return false;
    whichList.push_back( item );
    return true; 
} 

template <class HashObj>
bool HashTable<HashObj>::remove(const HashObj &item)
{
  list<HashObj> & whichList = theLists[ myhash( item ) ];
  typename list<HashObj>::iterator itr = find( whichList.begin( ), whichList.end(), item );

  if( itr == whichList.end( ) )
  return false;

  whichList.erase(itr);
  return true;
 }

This is the myhash function from the same file:

 template <class HashObj>
int HashTable<HashObj>::myhash(const HashObj &item) const
{
    int hashVal = hash(item);

    hashVal %= theLists.size();
    if (hashVal < 0)
        hashVal += theLists.size();

    return hashVal;
}

The above .cpp code has an include for hashTable.h, which in turn includes hashPrototypes.h

In hashPrototypes.h is

int hash(int key);
int hash(const string &key);

and my hash function gets compiled from a makefile that creates an executable based on what you enter. For example, I'm using hash1.cpp, so by typing make HASH=hash1, it should compile them all together.

Here is my hash1.cpp code:

#include "hashTable.h"
#include <cmath>
#include <cstdlib>
using namespace std;

template <class HashObj>
int hash(const HashObj &item)
    {
    int hashVal = 0;

    for( int i = 0; i < item.length( ); i++ )
        hashVal = 37 * hashVal + item[ i ];

    return hashVal;
}

If you think the error is in the makefile, here is the makefile code:

#   Make file for hashing
#   Executable for the program will be in: hashTest

#default function is looked for in hashS1
#to give it another function make=filename without the suffix
HASH = hashS1

$(HASH)Test:  $(HASH).o hashTable.o hashApp.o
    g++ -o $(HASH)Test $(HASH).o hashTable.o hashApp.o

hashApp.o:      hashTable.h hashPrototypes.h hashApp.cpp hashTable.cpp
    g++ -c hashApp.cpp

hashTable.o:    hashTable.h hashTable.cpp $(HASH).cpp
g++ -c hashTable.cpp

$(HASH).o:  hashPrototypes.h $(HASH).cpp
g++ -c $(HASH).cpp

clean:
rm -f *.o 
touch *

Can you post the code for your `myhash()` function? It looks like you may be using `std::hash` in which case you're probably just need to `#include ` but it's hard to be sure. — Jonathan Potter, Oct 08 '13 at 04:29
'when i try to compile the .cpp file with the functions by itself ...' no that's not relevant. — john, Oct 08 '13 at 04:34
You have an undefined symbol `hash` but nothing in the code you have posted uses a symbol called `hash`. So from the posted code it's a bit of a mystery. Post more code. — john, Oct 08 '13 at 04:35

score 3 · Answer 1 · edited May 23 '17 at 12:10

3

The problem is that you have put template code in a cpp file. All template code should go in header files. Otherwise you get link errors when using those templates.

edited May 23 '17 at 12:10

Community

1
1

answered Oct 08 '13 at 04:55

john

85,011
4
57
81

There was template code in the program before I added the insert, remove, and contains functions however (like the above mentioned myhash function), and it had compiled cleanly. Could that still be the problem? – Rekson Oct 08 '13 at 05:04
I don't know about the structure of the rest of your code (it's not completely clear from your question), but you have a link error, you have template code in a cpp file, putting template code in a cpp file is a well known cause of link errors (see link above). You should not put template code in a cpp file. Fix that, and if you still have problems ask again. – john Oct 08 '13 at 05:08
Sometimes to get around this problem what people do is put template code in a cpp file but then #include the cpp file in a header file. Of course that comes to the same thing, the template code is effectively in the header file. Maybe that's what's happening with your other code. – john Oct 08 '13 at 05:11

score 0 · Answer 2 · answered Oct 08 '13 at 14:14

Found the issue, it was simpler than I thought, but John's answer regarding where template code helped.

Turns out I needed to make my hash function (not myhash) a non-templated class and make it take a string variable. This is obvious to me now after looking at the prototype:

int hash(const string &key);

I just assumed during my initial creation of the definition that it would be a templated class like everything else!

Undefined Symbol error in C++ Hashing Program

2 Answers2