Sorting Input in Vector of Doubly Linked List Template (C++)

Question

I am writing a program that takes input in from a .txt file that contains a persons first name, last name, 9-digit Universal Identification number (UIN), and their phone number. I am supposed to read the input from this file into a vector of Doubly Linked Lists where element 0 of the vector corresponds to a doubly linked list of last names with the first letter 'A', element 1 corresponds to a doubly linked list of last names with the first letter 'B' and so on.

My code can read the data in from the file and place it in the correct lists but these lists aren't sorted. I am supposed to write an insert function in my TemplateDoublyLinkedList that places the new element in the correct position in the list, assuming the list is sorted, and will remain correctly sorted after I insert the new element.

My errors are coming from this function somehow but I am getting very vague linker errors (which means I probably made some silly mistake) and I can't figure out how to fix it. Here is my code:

TemplateDoublyLinkedList.h

#include "Record.h"
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstdio>
#include <sstream>
#pragma once
using namespace std;
template <typename T>
class DoublyLinkedList; // class declaration

// list node
template <typename T>
class DListNode {
private: T obj;
  DListNode<T> *prev, *next;
  friend class DoublyLinkedList<T>;
public:
  DListNode<T>(T object = T(), DListNode<T> *p = NULL, DListNode<T> *n = NULL)
    : obj(object), prev(p), next(n) {}
  T getElem() const { return obj; }
  DListNode<T> * getNext() const { return next; }
  DListNode<T> * getPrev() const { return prev; }
};

// doubly linked list
template <typename T>
class DoublyLinkedList {
protected: DListNode<T> header, trailer;
public:
  DoublyLinkedList<T>() : header(T()), trailer(T()) // constructor
  { header.next = &trailer; trailer.prev = &header; }
  DoublyLinkedList<T>(const DoublyLinkedList<T>& dll); // copy constructor
  ~DoublyLinkedList<T>(); // destructor
  DoublyLinkedList<T>& operator=(const DoublyLinkedList<T>& dll); // assignment operator
  // return the pointer to the first node
  DListNode<T> *getFirst() const { return header.next; } 
  // return the pointer to the trailer
  const DListNode<T> *getAfterLast() const { return &trailer; }
  // return if the list is empty
  bool isEmpty() const { return header.next == &trailer; }
  T first() const; // return the first object
  T last() const; // return the last object
  void insertFirst(T newobj); // insert to the first of the list
  T removeFirst(); // remove the first node
  void insertLast(T newobj); // insert to the last of the list
  T removeLast(); // remove the last node
  DListNode<T> *insert(T& newobj);
};
// output operator
template <typename T>
ostream& operator<<(ostream& out, const DoublyLinkedList<T>& dll);

// extend range_error from <stdexcept>
struct EmptyDLinkedListException : std::range_error {
  explicit EmptyDLinkedListException(char const* msg=NULL): range_error(msg) {}
};

// copy constructor
template <typename T>
DoublyLinkedList<T>::DoublyLinkedList(const DoublyLinkedList<T>& dll)
{
  header=T();
  trailer=T();
  header.next = &trailer; trailer.prev = &header;
  if (dll.isEmpty()) 
      return;

  DListNode<T>* current = dll.getFirst();
  while (current != dll.getAfterLast()) {
      T newObj = current->obj;
      insertLast(newObj);
      current = current->getNext();
  }

}
// assignment operator
template <typename T>
DoublyLinkedList<T>& DoublyLinkedList<T>::operator=(const DoublyLinkedList<T>& dll)
{
  delete this;

  header.next = &trailer; trailer.prev = &header;

  DListNode<T>* current = dll.getFirst();
  while (current != dll.getAfterLast()) {
      T newObj = current->obj;
      insertLast(newObj);
      current = current->getNext();
  }

  return *this;
}
// insert the object to the first of the linked list
template <typename T>
void DoublyLinkedList<T>::insertFirst(T newobj)
{ 
  DListNode<T> *newNode = new DListNode<T>(newobj, &header, header.next);
  header.next->prev = newNode;
  header.next = newNode;
}
// insert the object to the last of the linked list
template <typename T>
void DoublyLinkedList<T>::insertLast(T newobj)
{
  DListNode<T> *newNode = new DListNode<T>(newobj, trailer.prev,&trailer);
  trailer.prev->next = newNode;
  trailer.prev = newNode;
}
// remove the first object of the list
template <typename T>
T DoublyLinkedList<T>::removeFirst()
{ 
  if (isEmpty())
    throw EmptyDLinkedListException("Empty Doubly Linked List");
  DListNode<T> *node = header.next;
  node->next->prev = &header;
  header.next = node->next;
  T obj = node->obj;
  delete node;
  return obj;
}
// remove the last object of the list
template <typename T>
T DoublyLinkedList<T>::removeLast()
{
  if (isEmpty())
    throw EmptyDLinkedListException("Empty Doubly Linked List");
  DListNode<T> *node = trailer.prev;
  node->prev->next = &trailer;
  trailer.prev = node->prev;
  T obj = node->obj;
  delete node;
  return obj;
}
// destructor
template <typename T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
  DListNode<T> *prev_node, *node = header.next;
  while (node != &trailer) {
    prev_node = node;
    node = node->next;
    delete prev_node;
  }
  header.next = &trailer;
  trailer.prev = &header;
}
// return the first object
template <typename T>
T DoublyLinkedList<T>::first() const
{ 
  if (isEmpty())
    throw EmptyDLinkedListException("Empty Doubly Linked List");
  return header.next->obj;
}
// return the last object
template <typename T>
T DoublyLinkedList<T>::last() const
{
  if (isEmpty())
    throw EmptyDLinkedListException("Empty Doubly Linked List");
  return trailer.prev->obj;
}
// return the list length
template <typename T>
int DoublyLinkedListLength(DoublyLinkedList<T>& dll) {
  DListNode<T> *current = dll.getFirst();
  int count = 0;
  while(current != dll.getAfterLast()) {
    count++;
    current = current->getNext(); //iterate
  }
  return count;
}
// output operator
template <typename T>
ostream& operator<<(ostream& out, const DoublyLinkedList<T>& dll) {
  DListNode<T> *current = dll.getFirst();
  while (current != dll.getAfterLast()) {
      out << current->getElem() << '\n';
      current = current->getNext();
  }
  return out;
}

template <typename T>
DListNode<T> *insert(T& obj) {
    DListNode<T> *current = this->getFirst();
    while (obj < current->obj) {
        current = current->getNext();
    }

    DListNode<T> *newNode = new DListNode<T>(obj, current->prev, current);
    curren->prev = newNode;
    added->prev->next = added;
    return newNode;
}

Record.h (the class that is for my ADT, contains each "persons" and their name, UIN, and phone number)

#include <iostream>
#include <cstdlib>
#include <string>
#pragma once
using namespace std;

class Record {
private:
    string lastName, firstName, universalIdentificationNumber, phoneNumber;
public:
    Record(string last = "EMPTY", string first = "EMPTY", string UIN = "EMPTY", string phone = "EMPTY") : 
        lastName(last), firstName(first), universalIdentificationNumber(UIN), phoneNumber(phone) {}
    bool operator < (const Record& r);

    string getLast() const { return lastName; }
    string getFirst() const { return firstName; }
    string getUIN() const { return universalIdentificationNumber; }
    string getPhone() const { return phoneNumber; }

    void setLast(string s) { lastName = s; }
    void setFirst(string s) { firstName = s; }
    void setUIN(string s) { universalIdentificationNumber = s; }
    void setPhone(string s) { phoneNumber = s; }
};

ostream& operator<<(ostream& out, const Record& r);

Record.cpp

#include "Record.h"
#include "TemplateDoublyLinkedList.h"
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

bool Record::operator < (const Record& r) {
    if (getLast().compare(r.getLast()) < 0) 
        return true;
    if (getLast().compare(r.getLast()) >0)
        return false;
    if (getLast().compare(r.getLast()) == 0) {
        if (getFirst().compare(r.getFirst()) < 0)
            return true;
        if (getFirst().compare(r.getFirst()) > 0)
            return false;
        if (getFirst().compare(r.getFirst()) == 0) {
            if (getUIN().compare(r.getUIN()) < 0) 
                return true;
            if (getUIN().compare(r.getUIN()) > 0)
                return false;
            if (getUIN().compare(r.getUIN()) == 0) {
                if (getPhone().compare(r.getPhone()) < 0)
                    return true;
                if (getPhone().compare(r.getPhone()) > 0)
                    return false;
                if (getPhone().compare(r.getPhone()) == 0)
                    return true;
            }
        }
    }
    return false;
}

ostream& operator<<(ostream& out, const Record& r) {
    out << "Last Name: " << r.getLast() << '\n'
        << "First Name: " << r.getFirst() << '\n'
        << "UIN: " << r.getUIN() << '\n'
        << "Phone Number: " << r.getPhone() << '\n';

    return out;
}

Main.cpp

#include "Record.h"
#include "TemplateDoublyLinkedList.h"
#include <cstdlib>
#include <string>
#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
#include <fstream>
using namespace std;

void display(vector<DoublyLinkedList<Record>>& v) {
    for (int i=0; i<v.size(); ++i) {
        cout << v[i];
    }
}

int firstLetterSort (string s) {
    char firstLetter = s.at(0);
    int location;

    switch (firstLetter) {
    case 'a':
    case 'A':
        location = 0;
        break;
    case 'b':
    case 'B':
        location = 1;
        break;
    case 'c':
    case 'C':
        location = 2;
        break;
    case 'd':
    case 'D':
        location = 3;
        break;
    case 'e':
    case 'E':
        location = 4;
        break;
    case 'f':
    case 'F':
        location = 5;
        break;
    case 'g':
    case 'G':
        location = 6;
        break;
    case 'h':
    case 'H':
        location = 7;
        break;
    case 'i':
    case 'I':
        location = 8;
        break;
    case 'j':
    case 'J':
        location = 9;
        break;
    case 'k':
    case 'K':
        location = 10;
        break;
    case 'l':
    case 'L':
        location = 11;
        break;
    case 'm':
    case 'M':
        location = 12;
        break;
    case 'n':
    case 'N':
        location = 13;
        break;
    case 'o':
    case 'O':
        location = 14;
        break;
    case 'p':
    case 'P':
        location = 15;
        break;
    case 'q':
    case 'Q':
        location = 16;
        break;
    case 'r':
    case 'R':
        location = 17;
        break;
    case 's':
    case 'S':
        location = 18;
        break;
    case 't':
    case 'T':
        location = 19;
        break;
    case 'u':
    case 'U':
        location = 20;
        break;
    case 'v':
    case 'V':
        location = 21;
        break;
    case 'w':
    case 'W':
        location = 22;
        break;
    case 'x':
    case 'X':
        location = 23;
        break;
    case 'y':
    case 'Y':
        location = 24;
        break;
    case 'z':
    case 'Z':
        location = 25;
    }
    return location;
}

int main() {
    vector<DoublyLinkedList<Record>> phoneBook(26);
    const string phoneBookFile = "PhoneBook";
    string searchedLast, searchedFirst, searchedUIN;
    int firstLetter;

    ifstream ist(phoneBookFile.c_str());
    ist.open("PhoneBook.txt");
    if (ist.is_open()) {
        while (!ist.eof()) {
            Record nextRecord;
            string first, last, UIN, phone, empty;

            getline(ist, last);
            getline(ist, first);
            getline(ist, UIN);
            getline(ist, phone);
            getline(ist, empty);

            nextRecord.setLast(last);
            nextRecord.setFirst(first);
            nextRecord.setUIN(UIN);
            nextRecord.setPhone(phone);

            int location = firstLetterSort(last);
            phoneBook[location].insert(nextRecord);
        }
    }

    display(phoneBook);
}

And My errors as they are output by my compiler:

1>Main.obj : error LNK2019: unresolved external symbol "public: class DListNode<class Record> * __thiscall DoublyLinkedList<class Record>::insert(class Record &)" (?insert@?$DoublyLinkedList@VRecord@@@@QAEPAV?$DListNode@VRecord@@@@AAVRecord@@@Z) referenced in function _main
1>C:\Users\Snyperanihilatr\Documents\Visual Studio 2012\Projects\Phonebook\Debug\Phonebook.exe : fatal error LNK1120: 1 unresolved externals

Answer 1

Simple, the copy constructor has no body defined in your DoubleLinkedList. This is often done to prevent it being used. As you can see below the copy constructor has no body, that's why the linker can not find it.

DoublyLinkedList<T>(const DoublyLinkedList<T>& dll); // copy constructor

The reason you need to copy constructor is that the vector template uses it. You could prevent this by storing pointer to the DoubleLinkedList instead of the objects.

vector<DoublyLinkedList<Record>*> phoneBook(26);
for(char c='a' ; c<='z'; c++) 
{
    phoneBook[c] = new DoubleLinkedList();
}