0

I'm trying to write code to solve the josephus problem, for an exercise in the book I'm currently reading.

main.cc :

#include <iostream>
#include <cstdlib>
#include "node_ll.h"

int main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), M = atoi(argv[2]);
    Node<int> *t, *x;
    Node<int>::construct(N);
    for (i = 2, x = Node<int>::newNode(1); i <= N; i++)
      {
        t = Node<int>::newNode(i);
        x->insert(t);
        x = t;
      }
    while (x != x->next())
      {
        for (i = 1; i < M; i++) x = x->next();
          x->remove()->deleteNode();
      }
    std::cout << x->item() << std::endl;
    return 0;
  }

node_ll.h : 

#ifndef NODE
#define NODE

template <class T>
class Node
{
private:
  static Node* freelist;
  Node* link;
  T data;

public:
  static Node* newNode(T);
  static void construct(int);
  void deleteNode();
  void insert(Node*);
  Node* remove();
  Node* next();
  T item();
};

template <class T>
void Node<T>::insert(Node* t)
{
  t->link = link;
  link = t;
}

template <class T>
Node<T>* Node<T>::remove()
{
  Node* t{link};
  link = t->link;
  return t;
}

template <class T>
Node<T>* Node<T>::next()
{
  return link;
}

template <class T>
T Node<T>::item()
{
  return data;
}

template <class T>
Node<T>* Node<T>::newNode(T x)
{
  Node* t{freelist->remove()};
  t->data = x;
  t->link = t;
  return t;
}

template <class T>
void Node<T>::construct(int N)
{
  freelist = new Node[N+1];
  for(int i{0}; i < N; i++)
    freelist[i].link = &freelist[i+1];
  freelist[N].link = 0;
}

template <class T>
void Node<T>::deleteNode()
{
  freelist->insert(this);
}
#endif

When compiling g++ throws the following error:

/usr/bin/ld: /tmp/ccNqFpW8.o: in function Node<int>::construct(int)': main.cc:(.text._ZN4NodeIiE9constructEi[_ZN4NodeIiE9constructEi]+0x31): undefined reference toNode::freelist' /usr/bin/ld: main.cc:(.text._ZN4NodeIiE9constructEi[_ZN4NodeIiE9constructEi]+0x4e): undefined reference to Node<int>::freelist' /usr/bin/ld: main.cc:(.text._ZN4NodeIiE9constructEi[_ZN4NodeIiE9constructEi]+0x65): undefined reference toNode::freelist' /usr/bin/ld: main.cc:(.text._ZN4NodeIiE9constructEi[_ZN4NodeIiE9constructEi]+0x85): undefined reference to Node<int>::freelist' /usr/bin/ld: /tmp/ccNqFpW8.o: in functionNode::newNode(int)': main.cc:(.text._ZN4NodeIiE7newNodeEi[_ZN4NodeIiE7newNodeEi]+0xe): undefined reference to Node<int>::freelist' /usr/bin/ld: /tmp/ccNqFpW8.o:main.cc:(.text._ZN4NodeIiE10deleteNodeEv[_ZN4NodeIiE10deleteNodeEv]+0xf): more undefined references toNode::freelist' follow collect2: error: ld returned 1 exit status

And I have no clue what's going on

Felix B.
  • 37
  • 7
  • Does this answer your question? [How to initialize private static members in C++?](https://stackoverflow.com/questions/185844/how-to-initialize-private-static-members-in-c) – rand'Chris Apr 25 '20 at 22:51

2 Answers2

0

You're declaring a member of a class to be static. This means that for every instance of the class you create, they will all reference the same static value. Because there is only one value, it needs to be initialized once somewhere in your program. So you're missing a statement like:

Node<int>::Node* freelist = foo;    // The one-and-only 'foo' for all Node<int>s

Let me point out that it doesn't make sense to me that all classes share a single instance of this variable. Further, your code also contains this constructor:

template <class T>
void Node<T>::construct(int N)
{
  freelist = new Node[N+1];

You're not treating this variable as though it were static if you are also trying to do per-instance initialization.

rand'Chris
  • 788
  • 4
  • 17
  • The construct function isn't meant to do per instance initialization, it's meant to be called once at beginning of main, to initialize freelist. What would be the correct way to design this ? – Felix B. Apr 25 '20 at 21:27
  • Okay, I wasn't thinking about the problem, just looking at the syntax. I believe the problem is the same though: you need to give the program some place to store the static variable. I don't know how to link to another SO answer, but see here: https://stackoverflow.com/questions/185844/how-to-initialize-private-static-members-in-c – rand'Chris Apr 25 '20 at 22:23
0

I fixed it by declaring freelist as:

inline static Node* freelist;

instead of:

static Node* freelist;

and compiling it for c++17

found here: How to initialize private static members in C++?

Felix B.
  • 37
  • 7