Linking error

[afedorov]

I am trying to write simple LinkedList implementation with List interface and unit test. When I am trying to run my code in CLion I got following errors:

Undefined symbols for architecture x86_64:
"common::LinkedList<int>::add(int const&)", referenced from:
vtable for common::LinkedList<int> in LinkedListTest.cpp.o
"common::LinkedList<int>::get(int)", referenced from:
vtable for common::LinkedList<int> in LinkedListTest.cpp.o
"common::LinkedList<int>::size()", referenced from:
LinkedListTest_addTest_Test::TestBody() in LinkedListTest.cpp.o
vtable for common::LinkedList<int> in LinkedListTest.cpp.o
"common::LinkedList<int>::remove(int)", referenced from:
vtable for common::LinkedList<int> in LinkedListTest.cpp.o
ld: symbol(s) not found for architecture x86_64

My code:
List.h
#ifndef MARKOS_LIST_H
#define MARKOS_LIST_H

namespace common {
template<class T>
class List {
public:
virtual void add(const T &t)= 0;

virtual T get(int index)=0;

virtual T remove(int index)=0;

virtual int size()=0;
};
}
#endif //MARKOS_LIST_H


LinkedList implementation
LinkedList.h
#ifndef MARKOS_LINKEDLIST_H
#define MARKOS_LINKEDLIST_H
#include "List.h"

namespace common {
template<class T>
class LinkedList : public List<T> {
public:
void add(const T &t) override;

T get(int index) override;

T remove(int index) override;

int size() override;
};
}

#endif //MARKOS_LINKEDLIST_H

LinkedList.cpp
#include "LinkedList.h"

namespace common {
template<class T>
void LinkedList<T>::add(const T &t) {

}

template<class T>
T LinkedList<T>::get(int index) {
return nullptr;
}

template<class T>
T LinkedList<T>::remove(int index) {
return nullptr;
}

template<class T>
int LinkedList<T>::size() {
return 0;
}
}

Test files:
LinkedListTest.h
#ifndef MARKOS_LINKEDLISTTEST_H
#define MARKOS_LINKEDLISTTEST_H

#include "gtest/gtest.h"
#include "LinkedList.h"

class LinkedListTest : public ::testing::Test {

};
#endif //MARKOS_LINKEDLISTTEST_H


LinkedListTest.cpp
#include "LinkedListTest.h"


TEST_F(LinkedListTest, addTest) {
common::LinkedList<int> list;
list.add(5);
EXPECT_EQ(list.size(), 1);
}


I don't understand why error happens, is it something with my CMake config or I missed something in code?

[kbw]

You have template declarations in .cpp file(s). That's the root of the problem you're reporting.

But you should also know that a template abstract base class isn't quite what you think it is.

[afedorov]

Are you referring to LinkedList.cpp?

I still don't quite understand what is the issue.

I would like to have generic List interface and its implementations. How would I do this?

[kbw]

C++ templates are code generators. Like like macros, the code is generated at compile time, not link time.

Take this example:
helper.hpp

#pragma once

template <typename R>
R sigmoid(R r);

helper.cpp

#include "helper.hpp"
#include <iostream>

int main()
{
    std::cout << sigmoid(0.3) << std::endl;
}

It should be obvious that there's no definition of sigmoid().

Now, consider if there was a template definition in helper.cpp. That wouldn't make any difference because the compiler would not have reason to generate the code for double sigmoid(double). And the linker would still fail while looking for that function. This is what you have.

There are two solutions.
1. You can move the code to header.hpp, changing it from a declaration to a definition.
2. You can somehow generate the code in helper.cpp, allowing the linker to find this missing piece.

[afedorov]

hm, I am still confused.

I am a Java developer, and List<T>->LinkedList<T> hierarchy makes perfect sense to me. And it is very convenient to have such combination as I can use LinkedList in many places and change T to whatever I want to store.

Is it possible to do similar think in C++?

[kbw]

The problem is, List<int> a different class than List<double>. So LinkedList<int> and LinkedList<double> won't share a common base class, and polymorphic use is inapplicable.

Templates were "hacked" into Java because they couldn't change the JVM to copy the C++ implementation at the time. That's why that inheritance relationship exists between two different things. Plus, in C++, not everything is an object, some things are abstract data types.

In Java, you don't create objects on the stack, they're created on the heap. Object declarations really declare pointers to objects. That's why you need to use new or a creator on them before you use them.

So the equivalent of Java:

List<Integer> list;

In C++, you'd be more explicit that you've created a pointer:

List<Integer>* list;

Back in the old days, Rogue Wave Tools.h++ provided RWPtr... and RWVal... variants for its containers.
http://docs.roguewave.com/legacy-hpp/tlsref/index.html#Class%20Hierarchy

It's possible to implement a polymorphic linked list, but we tend not to do that kind of thing in that way. You'd simply declare a linked list of objects, and stick whatever you like in it.

class Object;
class LinkedList
{
    struct Node {
        Object* data;
        Node* prev, next;
        Node(Object* obj) : data(obj), prev(nullptr), next(nullptr) {}
    };

    Node *m_head, *m_tail;

public:
    void append(Object* obj);
    void prepend(Object* obj);
    //...
};

[afedorov]

But now every object I want to store in the list will have to extend Object class?
How will it work with primitives?

class Object;
class LinkedList
{
    struct Node {
        Object* data;
        Node* prev, next;
        Node(Object* obj) : data(obj), prev(nullptr), next(nullptr) {}
    };

    Node *m_head, *m_tail;

public:
    void append(Object* obj);
    void prepend(Object* obj);
    //...
};

int main() {
    LinkedList list;
    list.append(&"asdf");
    list.append(1);
    return 0;
}

[kbw]

But now every object I want to store in the list will have to extend Object class?

No. You don't extend anything, you just put pointers to objects in the linked list.

How will it work with primitives?

You can't. It's a Java-like linked list of (pointers to) objects.

[mbozzi]

Why can templates only be implemented in the header file?
https://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file

[afedorov]

Still don't get it. Here is the sample code that gives me compilation errors.

class Test{
    
};

class Object;
class LinkedList
{
    struct Node {
        Object* data;
        Node* prev, next;
        Node(Object* obj) : data(obj), prev(nullptr), next(nullptr) {}
    };

    Node *m_head, *m_tail;

public:
    void append(Object* obj);
    void prepend(Object* obj);
    //...
};

int main() {
    LinkedList list;
    Test *obj = new Test;
    list.append(obj);
    return 0;
}

Research/main.cpp:11:21: error: field has incomplete type 'LinkedList::Node'
Node* prev, next;
^
Research/main.cpp:9:12: note: definition of 'LinkedList::Node' is not complete until the closing '}'
struct Node {
^
Research/main.cpp:26:17: error: cannot initialize a parameter of type 'Object *' with an lvalue of type 'Test *'
list.append(obj);
^~~
Research/main.cpp:18:25: note: passing argument to parameter 'obj' here
void append(Object* obj);

[mbozzi]

Just a typo:

Inside the definition of struct Node, Node* prev, next; declares a pointer to Node named prev, and a Node named next.

There are no (trivially) recursive types in the language, so it doesn't compile. This is easy to understand if you recall that the size of every object must be known statically: what's the size of a class that contains itself?

struct Object {
  virtual ~Object() = default; 
};

// Java-style class is-an Object
struct Test : Object {};

class LinkedList {
  struct Node {
    Object *data;
    Node *prev, *next;
    Node(Object *obj) : data(obj), prev(nullptr), next(nullptr) {}
  };

  Node *m_head = nullptr, *m_tail = nullptr;

public:
  void append(Object *obj) { /* implementation here */ };
  void prepend(Object *obj);
  // NOTE:  This naive class owns resources directly.  Follow the rule of three:
  // http://en.cppreference.com/w/cpp/language/rule_of_three
};

int main() {
  LinkedList list;
  Test *const obj = new Test;
  list.append(new Test);
}

[afedorov]

Ok, I think I got it now.

Basically there is no way in C++ to design something that looks like Collection framework in Java. I cannot have template interfaces that are implemented in children and still uses templates.

This is kind of strange. So what if I have definition of List, and today I just want to use simple LinkedList implementation. If tomorrow I decide to change implementation I will have to go to all places where I specify LinkedList and change it to new class name. It doesn't look like polymorphism.

[mbozzi]

Basically there is no way in C++ to design something that looks like Collection framework in Java. I cannot have template interfaces that are implemented in children and still uses templates

No, you can certainly do this.

However, it would be a questionable design choice. C++ is strongly biased towards use of it's powerful static type system. For example, instead of defining a template class List and writing corresponding template classes which inherit from the appropriate instantiation of list - consider:

template <typename T>
struct list { 
  virtual ~list() = default; 
  virtual void push_back(T const &elt) = 0;
};
template <typename T> struct linked_list: list<T> {
  void push_back(T const &elt) override { /* ... */ }
}; 
template <typename T> struct array_list: list<T> {
  void push_back(T const &elt) override { /* ... */ }
};
// ... 

A more natural design would be to entirely dispense with the inheritance, along with the lack of value-semantics that burden such designs, and write containers to a common static interface. This idea is central to generic programming, which you should probably read about:

A very quick explanation:
http://www.boost.org/community/generic_programming.html

FWIW, C++'s type system is far more powerful than Java's.

[afedorov]

so here is your code transformed to class

template<typename T>
class list {
public:
    virtual ~list() = default;

    virtual void push_back(T const &elt) = 0;
};

template<typename T>
class linked_list : public list<T> {
public:
    void push_back(T const &elt) override { /* ... */ }
};

template<typename T>
class array_list : public list<T> {
public:
    void push_back(T const &elt) override { /* ... */ }
};

list<int> *createList();

int main() {
    list<int> *list = createList();
    list->push_back(7);
    return 0;
}

list<int> *createList() {
    return new linked_list<int>();
}

It compiles and builds in my IDE. I don't understand how is it different from my original code, besides the fact that I have .h and .cpp files for List and LinkedList. Is it definitions in .h files prevent it from linking?

[mbozzi]

Yes.

If you place the definitions of the template outside of the TU, only the declarations can be implicitly instantiated. For this reason, templates are usually implemented in the header file, so the definitions can be instantiated too when required.

Maybe do a search for "C++ phases of translation" and ''templates in source files'' if this is still confusing.

[afedorov]

so it looks like I achieved what I wanted by putting implementations in header files.

Is it bad? do people do stuff like that in C++?

[kbw]

Is it bad?

No.

do people do stuff like that in C++?

Yes

There's also another way, but putting everything in the header is one way.