C++ Undefined Reference Error from using List class and Pair class

Question

I am currently suffering with problems with adding Pairs to my List program and then spitting it out to have it work in my scramble program which is mean to find words sorta like boggle, but with no set size and I have to generate the words/letters.

This code is in my scramble.cc program.

List history;

bool placeAlreadyUsed(int x, int y, List history)
{
 for(size_t i=0; i < history.getSize(); i++)
  {
   Pair p1 = history.get(i)
   if(p1.r == x && p1.c == y)
    return true;
  }
 return false
}

bool findUsersWord(string findThis, string alreadyFound, List &history, int maxR, int maxC)
{  
  // need to find the findThis  base case
  if (findThis == alreadyFound)
    cout << "SOLVED" << endl;
    return true;

  // need to find the first letter within the board and then progress around that.
  if (alreadyFound.empty())
  {
    for (int rows = 0; rows < maxR; rows++)
      for (int cols = 0; cols < maxC; cols++)
        // find the each character within the 
        if (theBoard[rows][cols] == findThis[0])
        {
          alreadyFound = findThis[0];
          Pair newR;
          newR.r = rows;
          newR.c = cols;
          history.add(newR);
          if (findUsersWord(findThis, alreadyFound, history, maxR, maxC))
            return true;
          else
           {
            // clear out the found Board 
            size_t temp = history.getSize()
            for(size_t i=0; i<temp; i++
            {
             history.removeAt(i);
            }
          }
        }
  }
  else
  {
    // try and find the next letters within the area around the base letter
    // spin around the letter 3 * 3 grid
    for (int x= (p1.r > 0 ? p1.r-1: p1.r); y <=(p1.r == (maxR-1) ? p1.r : p1.r+1);x++)
      for (int y= (p1.c> 0 ? p1.c-1: p1.c); x<=(p1.c == (maxC-1) ? p1.c : p1.c+1);y++)
        if ((board[x][y] == findThis[alreadyFound.length()]) && (!(x==p1.r && y==p1.c)))
          // already used letter
          if (!placeAlreadyUsed(y,x,history))
          {
            alreadyFound += findThis[alreadyFound.length()];
            Pair newR;
            newR.r = x;
            newR.c = y;
            history.add(newR, alreadyFound.length());
            if (findUsersWord(findThis, alreadyFound, history, maxR, maxC))
              return true;
            else
            {
              if (alreadyFound.length() > 1)
                alreadyFound = alreadyFound.substr(0, alreadyFound.length()-1);
              history.removeAt(history.getSize()-1);
            }
          }
    return false;
  }
  return false;
}

My list.cc is the thing that is having a problem with this code:

#include <iostream>
#include <cassert>
#include <cstdlib>
#include "list.h"

using namespace std;

List::Node::Node()
{
 prev = next = NULL;
}

List:: List()
{
 front = new Node()
 rear = new Node()
 front->next = rear;
 rear->prev = front;

 currentIndex=0;
 current = front->next;
 size=0;
}

List::~List()
{
 _setCurrentIndex(0);
 while(current)
  {
   Node *temp = current;
   current = current -> next;
   delete temp;
  }
//not showing deep copy function b/c it isn't important for this program
void List::add(const ElementType & item, size_t index)
{
 assert(0<=index && index <= size);
 _setCurrentIndex(index);
 size++;

 Node *born = new Node;
 born->data = item;
 born->prev = current->prev;
 born->prev->next = current;
 born->prev = born;
 current = born;
}

void List::removeAt(size_t index)
{
 assert(0<=index<=getSize());
 _setCurrentIndex(index);

 Node *old = current;
 current->prev->next = current->next;
 current->next->prev = current->prev;
 delete old;
 size--;
}

void List::remove(const ElementType & item)
{
 for(size_t i=0; i<size; i++)
  {
  _setCurrentIndex(i);
   if(find(item)<getSize())
    {
     Node *tempOld = current;
     current->next->prev = current->prev;
     current->prev->next = current->next;
     current = current->next;

     delete tempOld;
     size--;
    }
  }
}

size_t List::find(const ElementType & item) const
{
 for(size_t i=0; i<size; i++)
  {
   _setCurrentIndex(i)
   if(get(i) == item)
    return i;
  }
 return getSize();
}

List::ElementType List::get(size_t index) const
{
 assert(0 <= index < size);
 _setCurrentIndex(index);
 assert(current->next != NULL);
 return current->data;
}

size_t List::getSize() const
{
 return size;
}

void List::output(std::ostream & ostr) const
{
 for(size_t i=0; i<size; i++) 
  {
  _setCurrentIndex(i);
  ostr << current->data << " ";
  }
 ostr << endl;
}

void List:: _setCurrentIndex(size_t index) const
{
 int x;
 if(currentIndex > index)
  x = currentIndex - index;
 else
  x = index-currentIndex;

 if(index < (sizez_t)x)
  {
  current = front->next;
  curentIndex=0;
  while(currentIndex != index)
   {
   current = current->next;
   currentIndex++;
   }
  }
 else if((size-index) < (size_t)x)
  {
   current = rear;
   currentIndex = size;
   while(currentIndex != index)
    {
     current = current->prev;
     currentIndex--;
    }
  }
 else
  {
   if(currentIndex > index)
    {
    while(currentIndex!=index)
     {
      current = current->prev;
      currentIndex--;
     }
    }
   else
    {
     while(currentIndex!=index)
      {
       current = current->next;
       currentIndex++;
      }
    }
  }
}

The errors I am getting is scramble.cc(.text+0x480): undefined reference to List::List(List const&)' collect2: ld returned 1 exit status make: * [scramble Error 1

Any ideas what is exactly is going on and how to approach to fix this?

EDIT: I am not missing any include statements, just didn't put them in

Answer 1

It looks like your list.h probably declares a copy constructor, List::List(List const&), and your scramble.cc attempts to use it. However, you don't actually implement the copy constructor in your list.cc file, so when it comes to linking, the copy constructor isn't found. You'll need to implement this function somewhere in list.cc:

List::List(List const& other)
{
  // Implement this
}

Top tip: when you get an error that looks like this (file.cc(.text+0x12AB) and mentions ld), it means you have a linker error. This is almost always because you're attempting to use something that you've declared in one translation unit but never defined/implemented anywhere else. The compiler stage works fine because often it only needs to find a declaration to constitute a well-formed program, but when it comes to linking your program together, the linker throws up because it can't find the actual implementation.

Answer 2

While the error reported is that you have declared but not implemented a copy constructor, the real problem is that you're accidentally trying to make a copy of your list in the first place.

Here's where it happens

bool placeAlreadyUsed(int x, int y, List history)

Change this to a const reference and the error should go away.

bool placeAlreadyUsed(int x, int y, const List &history)

Declaring (but not implementing) a copy constructor is actually a way of 'preventing' your class being accidentally copied. boost::noncopyable uses a similar technique, making the copy constructor private.

Answer 3

You must include list.h into your scramble.cc