error LNK2019: link error

Question

About this program:

The program is for achieving HashTable.

The problem is as follows:

1>正在链接... 1>HashTable.obj : error LNK2019: 无法解析的外部符号 "public: int __thiscall HashTable::remove(class Employee const &)" (?remove@?$HashTable@VEmployee@@@@QAEHABVEmployee@@@Z)，该符号在函数 _wmain 中被引用

1>HashTable.obj : error LNK2019: 无法解析的外部符号 "public: int __thiscall HashTable::contains(class Employee const &)" (?contains@?$HashTable@VEmployee@@@@QAEHABVEmployee@@@Z)，该符号在函数 _wmain 中被引用

1>HashTable.obj : error LNK2019: 无法解析的外部符号 "public: void __thiscall HashTable::display(void)const " (?display@?$HashTable@VEmployee@@@@QBEXXZ)，该符号在函数 _wmain 中被引用 1>HashTable.obj : error LNK2019: 无法解析的外部符号 "public: int __thiscall HashTable::insert(class Employee const &)" (?insert@?$HashTable@VEmployee@@@@QAEHABVEmployee@@@Z)，该符号在函数 _wmain 中被引用

1>HashTable.obj : error LNK2019: 无法解析的外部符号 "public: __thiscall HashTable::HashTable(int)" (??0?$HashTable@VEmployee@@@@QAE@H@Z)，该符号在函数 _wmain 中被引用

QUESTION:

I do not know why this happens since I have given declaration in Hash.h and definition in Hash.cpp.Before this question is posted,I have searched answer through the Internet but no answers are what i want.Is the reason that there are some special ways in using template while I misuse it?

Hash.h:

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

template <class T>
class HashTable
{
    public:
        HashTable(int size = 101);
        int insert(const T& x);
        int remove(const T& x);
        int contains(const T& x);
        void make_empty();
        void display()const;
    private:
        vector<list<T> > lists;
        int currentSize;
        int hash(const string& key);
        int myhash(const T& x);
        void rehash();
};

class Employee
{
    public:
        Employee(){}
        Employee(const string n,int s=0):name(n),salary(s){ }
        const string & getName()const { return name; } 
        
        bool operator == (const Employee &rhs) const
        {
            return getName() == rhs.getName();
        }
        
        bool operator != (const Employee &rhs) const
        {
            return !(*this == rhs);
        }
        
        friend ostream& operator <<(ostream& out,const Employee& e)
        {
            out<<"("<<e.name<<","<<e.salary<<") ";
            return out;
        }
    
    private:
        string name;
        int salary;
};

Hash.cpp

#include "stdafx.h"
#include "Hash.h"

int nextPrime(const int n);

template <class T> HashTable<T>::HashTable(int size)
{
    lists = vector<list<T> >(size);
    currentSize = 0;
}

template <class T> int HashTable<T>::hash(const string& key)
{ 
    int hashVal = 0;
    int tableSize = lists.size();
    for(int i=0;i<key.length();i++)
        hashVal = 37*hashVal+key[i];
    hashVal %= tableSize;
    if(hashVal < 0)
        hashVal += tableSize;
    return hashVal;
}

template <class T> int HashTable<T>:: myhash(const T& x)
{
    string key = x.getName();
    return hash(key);
}

template <class T> int HashTable<T>::insert(const T& x)
{
    list<T> &whichlist = lists[myhash(x)];
    if(find(whichlist.begin(),whichlist.end(),x) != whichlist.end())
        return 0;
    whichlist.push_back(x);
    currentSize = currentSize + 1;
    if(currentSize > lists.size())
        rehash();
    return 1;
}

template <class T> int HashTable<T>::remove(const T& x)
{
    typename std::list<T>::iterator iter; list<T> &whichlist = lists[myhash(x)];
    iter = find(whichlist.begin(),whichlist.end(),x);
    if( iter != whichlist.end())
    {
        whichlist.erase(iter); 
        currentSize--;
        return 1;
    }
    return 0;
}

template <class T> int HashTable<T>::contains(const T& x)
{
    list<T> whichlist;
    typename std::list<T>::iterator iter;
    whichlist = lists[myhash(x)];
    iter = find(whichlist.begin(),whichlist.end(),x);
    if ( iter != whichlist.end())
        return 1;
    return 0;
}

template <class T> void HashTable<T>::make_empty()
{
    for(int i=0;i<lists.size();i++)
        lists[i].clear();
    currentSize = 0;
    return 0;
}

template < class T > void HashTable < T >::rehash()
{
    vector < list < T > >oldLists = lists;
    lists.resize(nextPrime(2 * lists.size()));
    for (int i = 0; i < lists.size(); i++)
    lists[i].clear();
    currentSize = 0;
    for (int i = 0; i < oldLists.size(); i++) {
    typename std::list < T >::iterator iter = oldLists[i].begin();
    while (iter != oldLists[i].end())
        insert(*iter++);
    }
}

template < class T > void HashTable < T >::display() const const
{
    for (int i = 0; i < lists.size(); i++) {
    cout << i << ": ";
    typename std::list < T >::const_iterator iter = lists[i].begin();
    while (iter != lists[i].end()) {
        cout << *iter << " ";
        ++iter;
    }
    cout << endl;
    }
}

int nextPrime(const int n)
{
    int ret, i;
    ret = n;
    while (1) {
    int flag = 1;
    for (i = 2; i < sqrt((float) ret); i++)
        if (ret % i == 0) {
        flag = 0;
        break;
        }
    if (flag == 1)
        break;
    else {
        ret = ret + 1;
        continue;
    }
    }
    return ret;
}

Hashtable.cpp:

// HashTable.cpp :
// #include "stdafx.h"

#include "Hash.h"
int _tmain(int argc, _TCHAR * argv[])
{
    Employee e1("Tom", 6000);
    Employee e2("Anker", 7000);
    Employee e3("Jermey", 8000);
    Employee e4("Lucy", 7500);
    HashTable < Employee > emp_table(13);
    emp_table.insert(e1);
    emp_table.insert(e2);
    emp_table.insert(e3);
    emp_table.insert(e4);
    cout << "Hash table is: " << endl;
    emp_table.display();
    if (emp_table.contains(e4) == 1)
    cout << "Tom is exist in hash table" << endl;
    if (emp_table.remove(e1) == 1)
    cout << "Removing Tom form the hash table successfully" << endl;
    if (emp_table.contains(e1) == 1)
    cout << "Tom is exist in hash table" << endl;
    else
    cout << "Tom is not exist in hash table" << endl;
    return 0;
}

You have to define the template functions in the header file, as the compiler won't know which types to instantiate in the cpp file. — Crowman, Sep 13 '13 at 01:36

score 2 · Answer 1 · answered Sep 13 '13 at 01:36

Is the reason that there are some special ways in using template while I misuse it?

Precisely. The definition of a template class/function must be accessible on every translation unit where it's used, in other words, you can't separate its declaration from its definition like you did. To workaround this limitation, just define the templates inline, that is, on the header file.

Quoting draft n3485

[temp] paragraph 1

A function template, member function of a class template, or static data member of a class template shall be defined in every translation unit in which it is implicitly instantiated [...] unless the corresponding specialization is explicitly instantiated [...] in some translation unit; no diagnostic is required.

prehistoricpenguin · Answer 2 · 2013-09-13T01:50:30.230

A template is not a class or a function. A template is a "pattern" that the compiler uses to generate a family of classes or functions.

In order for the compiler to generate the code, it must see both the template definition (not just declaration) and the specific types/whatever used to "fill in" the template. For example, if you're trying to use a Foo, the compiler must see both the Foo template and the fact that you're trying to make a specific Foo.

Your compiler probably doesn't remember the details of one .cpp file while it is compiling another .cpp file. It could, but most do not and if you are reading this FAQ, it almost definitely does not. BTW this is called the "separate compilation model."

You may read this FAQ, and here is the Chinese version
Don't write using namespace std; in your head files, when you want to use string from std, write std::string instead.
For constructors just have one parameter, you may use the explicit keyword to avoid implicit conversion.

error LNK2019: link error

2 Answers2