Why does this c++ code not compile in g++ 4.8.2

Question

I'm trying to compile C++ pulse chess engine [0] using g++ 4.8.2 (Ubuntu 14.04 environment).

I get the following errors at linking stage:

Linking CXX executable pulse-
CMakeFiles/pulse.dir/main.cpp.o: In function `pulse::MoveGenerator::MoveGenerator()':
/home/user/cpp/movegenerator.h:15: undefined reference to `pulse::MoveList<pulse::MoveEntry>::MoveList()'
libcore.so: undefined reference to `pulse::MoveList<pulse::MoveEntry>::rateFromMVVLVA()'
libcore.so: undefined reference to `pulse::MoveList<pulse::RootEntry>::sort()'
libcore.so: undefined reference to `pulse::MoveList<pulse::RootEntry>::MoveList()'
libcore.so: undefined reference to `pulse::MoveList<pulse::MoveEntry>::sort()'
collect2: error: ld returned 1 exit status

When I run the command:

g++ -std=c++11 -c movelist.cpp && nm movelist.o | grep sort

I get the output

0000000000000000 W _ZN5pulse8MoveListINS_9MoveEntryEE4sortEv
0000000000000000 W _ZN5pulse8MoveListINS_9RootEntryEE4sortEv

when using 4.9.1, but no output when using 4.8.2.

Why is that g++ 4.9.1 generates the sort function while 4.8.2 does not, is it a bug in the compiler or in the pulse source code?

EDIT:

As stated in the pointed out duplicate question "Why can templates only be implemented in the header file?", I don't get it then, how does it work in g++ 4.9.1? The movelist header:

#include "value.h"
#include "move.h"

#include <array>
#include <memory>

namespace pulse {

/**
 * This class stores our moves for a specific position. For the root node we
 * will populate pv for every root move.
 */
template<class T> 
class MoveList {
private:
  static const int MAX_MOVES = 256;

public:
  std::array<std::shared_ptr<T>, MAX_MOVES> entries;
  int size = 0; 

  MoveList();

  void sort();
  void rateFromMVVLVA();
};

class MoveVariation {
public:
  std::array<int, Depth::MAX_PLY> moves;
  int size = 0; 
};

class MoveEntry {
public:
  int move = Move::NOMOVE;
  int value = Value::NOVALUE;
};

class RootEntry : public MoveEntry {
public:
  MoveVariation pv;
};

}

The movelist source:

#include "movelist.h"

#include <cassert>

namespace pulse {

template class MoveList<MoveEntry>;
template class MoveList<RootEntry>;

template<class T>
MoveList<T>::MoveList() {
  for (unsigned int i = 0; i < entries.size(); ++i) {
    entries[i] = std::shared_ptr<T>(new T());
  }  
}

/**
 * Sorts the move list using a stable insertion sort.
 */
template<class T> 
void MoveList<T>::sort() {
  for (int i = 1; i < size; ++i) {
    std::shared_ptr<T> entry(entries[i]);

    int j = i; 
    while ((j > 0) && (entries[j - 1]->value < entry->value)) {
      entries[j] = entries[j - 1];
      --j;
    }  

    entries[j] = entry;
  }  
}

/**
 * Rates the moves in the list according to "Most Valuable Victim - Least Valuable Aggressor".
 */
template<class T> 
void MoveList<T>::rateFromMVVLVA() {
  for (int i = 0; i < size; ++i) {
    int move = entries[i]->move;
    int value = 0; 

    int piecetypeValue = PieceType::getValue(Piece::getType(Move::getOriginPiece(move)));
    value += PieceType::KING_VALUE / piecetypeValue;

    int target = Move::getTargetPiece(move);
    if (Piece::isValid(target)) {
      value += 10 * PieceType::getValue(Piece::getType(target));
    }

    assert(value >= (PieceType::KING_VALUE / PieceType::KING_VALUE)
      && value <= (PieceType::KING_VALUE / PieceType::PAWN_VALUE) + 10 * PieceType::QUEEN_VALUE);

    entries[i]->value = value;
  }
}

[0] https://github.com/fluxroot/pulse/tree/master/src/main/cpp

Answer 1

The solution

Move the two lines that start with template class to the end of the source file.

The explanation

This source uses explicit template instantiation (14.7.2). It is perfectly OK to define the template in the source file (not in the header) as long as only the explicit instantiations of the template are used in the entire program. In this case, these would be MoveList<MoveEntry> and MoveList<RootEntry>.

However, there is a problem: the explicit specialization must appear after the template definition (14.7.2/4)

A declaration of a function template, a variable template, a member function or static data member of a class template, or a member function template of a class or class template shall precede an explicit instantiation of that entity. A definition of a class template, a member class of a class template, or a member class template of a class or class template shall precede an explicit instantiation of that entity unless the explicit instantiation is preceded by an explicit specialization of the entity with the same template arguments.

Why g++ 4.9 does not enforce this is anyone's guess.