C++ : error LNK2019: unresolved external symbol

Question

Possible Duplicate:
What is an undefined reference/unresolved external symbol error and how do I fix it?

So I have compared my issue to the vast library of problems that have spawned from this category on this site. I still have no clue as to why my compiler is complaining.

So let me give a short briefing on what it is I want to do with my program. I am researching elevator algorithms. I want to implement priority queues using a binary heap.

I have got the source code from mark allen wiess website. For the heaps.

I am constructing my own reqnode class that represents the nodes of the binary tree.

reqnode = request node.

The scenario is: A user makes a request. I service the request. I am working with multiple requests. Thus I have to use a priority, on which user to satisfy first.

This is my header file for my binary heap.

#include <vector>
using namespace std;

BinaryHeap class.

CONSTRUCTION: with no parameters or vector containing items.

template <class Comparable>
class BinaryHeap
{
public:
BinaryHeap( );
BinaryHeap( const vector<int> & v );

bool isEmpty( ) const;
const Comparable & findMin( ) const;

void insert( const Comparable & x);
void deleteMin( );
void deleteMin( Comparable & minItem );
void makeEmpty( );

private:
int theSize;  // Number of elements in heap
vector<Comparable> Array;    // The heap Array

void buildHeap( );
void percolateDown( int hole );
};

These are the functions defined for my binary heap.

#include "binaryHeap.h"
using namespace std;

// Construct the binary heap.
template <class Comparable>
BinaryHeap<Comparable>::BinaryHeap( )
: Array( 11 ), theSize( 0 )
{
}

// Insert item x into the priority queue, maintaining heap order.
// Duplicates are allowed.


template <class Comparable>
void BinaryHeap<Comparable>::insert( const Comparable & x) 
{
Array[ 0 ] = x;   // initialize sentinel
if( theSize + 1 == Array.size( ) )
    Array.resize( Array.size( ) * 2 + 1 );

  // Percolate up
int hole = ++theSize;
for( ; x < Array[ hole / 2 ]; hole /= 2 )
    Array[ hole ] = Array[ hole / 2 ];
Array[ hole ] = x;
}

// Find the smallest item in the priority queue.
// Return the smallest item, or throw UnderflowException if empty.
template <class Comparable>
const Comparable & BinaryHeap<Comparable>::findMin( ) const
{
if( isEmpty( ) ){
    cout << "heap empty" << endl; //throw UnderflowException( );
    break;
}
return Array[ 1 ];
}

// Remove the smallest item from the priority queue.
// Throw UnderflowException if empty.
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( )
{
if( isEmpty( ) ){
    cout << "heap empty" << endl; //throw UnderflowException( );
    break;
}

Array[ 1 ] = Array[ theSize-- ];
percolateDown( 1 );
}

// Remove the smallest item from the priority queue
// and place it in minItem. Throw UnderflowException if empty.
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( Comparable & minItem )
{
minItem = findMin( );
Array[ 1 ] = Array[ theSize-- ];
percolateDown( 1 );
}

// Establish heap-order property from an arbitrary
// arrangement of items. Runs in linear time.
template <class Comparable>
void BinaryHeap<Comparable>::buildHeap( )
{
for( int i = theSize / 2; i > 0; i-- )
    percolateDown( i );
}

// Test if the priority queue is logically empty.
// Return true if empty, false otherwise.
template <class Comparable>
bool BinaryHeap<Comparable>::isEmpty( ) const
{
return theSize == 0;
}

// Make the priority queue logically empty.
template <class Comparable>
void BinaryHeap<Comparable>::makeEmpty( )
{
theSize = 0;
}

// Internal method to percolate down in the heap.
// hole is the index at which the percolate begins.
template <class Comparable>
void BinaryHeap<Comparable>::percolateDown( int hole )
{
int child;
Comparable tmp = Array[ hole ];

for( ; hole * 2 <= theSize; hole = child )
{
    child = hole * 2;
    if( child != theSize && Array[ child + 1 ] < Array[ child ] )
        child++;
    if( Array[ child ] < tmp )
        Array[ hole ] = Array[ child ];
    else
        break;
}
Array[ hole ] = tmp;
}

This is my header file for reQnode

class reqNode//create a node that takes in several properties.
{
public:
reqNode(){  //default constructor
static priority = start = destination = timestamp = start_time = finish_time = -1;
}

reqNode(const reqNode &copy){       //copy constructor
priority = copy.priority;
start = copy.start;
destination = copy.destination;
timestamp = copy.timestamp;
start_time = copy.start_time;
finish_time = copy.finish_time;
}

reqNode & operator=(const reqNode & copy){
priority = copy.priority;
start = copy.start;
destination = copy.destination;
timestamp = copy.timestamp;
start_time = copy.start_time;
finish_time = copy.finish_time;

return *this;
}

int priority, start, destination, timestamp, start_time, finish_time;
bool direction;

bool operator<(reqNode &rhs){
if(this->priority < rhs.priority)
return true;
else
return false;
}

void setPriority(int x){
priority=x;
}
};

This is my driver implementation

#include <iostream>
#include <fstream>
#include <string>
#include "binaryHeap.h"
#include "reqnode.h"

#include <algorithm>
using namespace std;

void setNode(reqNode nizzode, int priority)
{
nizzode.priority = priority;
}


int main()
{
int numItems = 10000;
BinaryHeap<reqNode> h;
int i = 37;
reqNode x;
reqNode * temp;

for( i = 37; i != 0; i = ( i + 37 ) % numItems ){
temp = new reqNode;
temp->setPriority(i);
h.insert( *temp );
}

for( i = 1; i < numItems; i++ )
{
h.deleteMin( x );
if( x.priority != i )
cout << "Oops! " << i << endl;
}

for( i = 37; i != 0; i = ( i + 37 ) % numItems ){
temp = new reqNode;
temp->setPriority(i);
h.insert( *temp );
}

temp = new reqNode;
temp->setPriority(i);
h.insert( *temp );


return 0;
}

Finally, These are the errors that haunt me!

1>Driver2.obj : error LNK2019: unresolved external symbol "public: void __thiscall BinaryHeap<class reqNode>::deleteMin(class reqNode &)" (?deleteMin@?$BinaryHeap@VreqNode@@@@QAEXAAVreqNode@@@Z) referenced in function _main
1>Driver2.obj : error LNK2019: unresolved external symbol "public: void __thiscall BinaryHeap<class reqNode>::insert(class reqNode const &)" (?insert@?$BinaryHeap@VreqNode@@@@QAEXABVreqNode@@@Z) referenced in function _main
1>Driver2.obj : error LNK2019: unresolved external symbol "public: __thiscall BinaryHeap<class reqNode>::BinaryHeap<class reqNode>(void)" (??0?$BinaryHeap@VreqNode@@@@QAE@XZ) referenced in function _main
1>C:\Users\Aaron Artis\Documents\Visual Studio 2010\Projects\Elevator_Algo_Remix1\Debug\Elevator_Algo_Remix1.exe : fatal error LNK1120: 3 unresolved externals

I'm unsure of where to pinpoint this problem. I had a previous linker error. I resolved it. This one just seems like a doozy.

Are your template methods defined in a .h or a .cpp? usually template members are defined in the same file as the template class declaration. — alestanis, Oct 21 '12 at 20:36

score 2 · Answer 1 · answered Oct 21 '12 at 20:36

2

Don't put template definitions in the .CPP file - they need to be in the .H file, else the compiler can't expand them.

Probably, you shouldn't even need BinaryHeap.c

answered Oct 21 '12 at 20:36

Roddy

66,617
42
165
277

I think this fact is a shock to many people the first time they write template code. – john Oct 21 '12 at 20:37
@john Judging by the number of duplicates to this question (and answer) that run rampant on SO, you're assessment is most-certainly valid. – WhozCraig Oct 21 '12 at 20:40

alestanis · Answer 2 · 2012-10-21T21:09:19.453

1

Your compiler is complaining because it found declarations for functions constructor, deleteMin and insert, but not definitions.

This is due to the fact that your definitions must be in a .cpp file.

Putting them directly inside the binaryHeap.h file, after the class declaration, solves the issue.

Think of doing this for template functions.

edited Oct 21 '12 at 21:09

answered Oct 21 '12 at 20:38

alestanis

21,519
4
48
67

Not necessarily always. Are you aware of specialized templates? – Luchian Grigore Oct 21 '12 at 20:50
Yes I am. I was just highlighting the fact that this is not just to fix his actual error, but that it's something he should think of when working with templates. – alestanis Oct 21 '12 at 21:01
Of course, but "think of" and "always do this" are totally different. When you set out a rule, make sure to cover the corner cases, or at least not make it sound so restrictive. – Luchian Grigore Oct 21 '12 at 21:03

score 0 · Answer 3 · answered Oct 21 '12 at 20:37

0

It looks like the definition of the constructor and the two methods is in a CPP file; they need to be in a header file.

answered Oct 21 '12 at 20:37

Dabbler

9,733
5
41
64

score 0 · Answer 4 · edited May 23 '17 at 11:50

0

Short Answer: You should have your BinaryHead<>'s declaration and definition in the same file, as this is a template class.

Long Answer: Read this Stackoverflow answer which explain things in good detail.

edited May 23 '17 at 11:50

Community

1
1

answered Oct 21 '12 at 20:39

vvnraman

1,322
13
21

C++ : error LNK2019: unresolved external symbol

4 Answers4