Why do C++ templates let me circumvent incomplete types (forward declarations)?

Question

I tried three iterations of the following simple program. This is a highly simplified attempt to write a container-and-iterator pair of classes, but I was running into issues with incomplete types (forward declarations). I discovered that this was in fact possible once I templatized everything - but only if I actually used the template parameter! (I realized this by looking at the Google sparsetable code.)

Any hints explaining why the second works while the third doesn't? (I know why the first one doesn't work - the compiler needs to know the memory layout of the container.)

Thanks in advance.

// This doesn't work: invalid use of incomplete type.
#if 0
struct container;
struct iter {
  container &c;
  int *p;
  iter(container &c) : c(c), p(&c.value()) {}
};
struct container {
  int x;
  int &value() { return x; }
  iter begin() { return iter(*this); }
};
int main() {
  container c;
  c.begin();
  return 0;
}
#endif

// This *does* work.
template<typename T> struct container;
template<typename T> struct iter {
  container<T> &c;
  T *p;
  iter(container<T> &c) : c(c), p(&c.value()) {}
};
template<typename T> struct container {
  T x;
  T &value() { return x; }
  iter<T> begin() { return iter<T>(*this); }
};
int main() {
  container<int> c;
  c.begin();
  return 0;
};

// This doesn't work either.
#if 0
template<typename T> struct container;
template<typename T> struct iter {
  container<int> &c;
  int *p;
  iter(container<int> &c) : c(c), p(&c.value()) {}
};
template<typename T> struct container {
  int x;
  int &value() { return x; }
  iter<int> begin() { return iter<int>(*this); }
};
int main() {
  container<int> c;
  c.begin();
  return 0;
}
#endif

Answer 1

You could do this without templates by defining iter::iter() after definition of container:

struct container;

struct iter {
  container &c;
  int *p;
  iter(container &c);
};

struct container {
  int x;
  int &value() { return x; }
  iter begin() { return iter(*this); }
};

iter::iter(container &c)
    : c(c), p(&c.value()) {}

int main() {
  container c;
  c.begin();
  return 0;
}

Template version works because when you instantiate templates both classes are completely defined.

Answer 2

In the first case, you are trying to access a member function of the Container class before the class has been defined, so this won't work.

In the second case, the template is instantiated the first time it is used with a particular type. At that point the Container class has been defined, in main, and so it compiles.

In the third case there is a circular reference. container uses iter and iter uses container, so it can't work.

Answer 3

The first requires a definition of container since you are doing a copy operation. If you define the constructor of iter after container's definition you'd be okay. So:

struct container;
struct iter {
  container &c;
  int *p;
  iter(container &c);
};

struct container {
  int x;
  int &value() { return x; }
  iter begin() { return iter(*this); }
};

iter::iter(container &c) : c(c), p(&c.value()) {}

int main() {
  container c;
  c.begin();
  return 0;
}

The second example works because there is no class until you actually instantiate one in your main function. By that time all types are defined. Try moving any of the iter or container templates definition after main and you'll hit an error.

The third example is a specialization for int or so it appears. This should compile because the template parameter for iter is not used. You've got the specialization syntax a bit off. However, there is no proper constructor so you'll only get garbage for x. Moreover, iterators are modeled well by pointers. Passing this's value will not be of much help. Iterators are typically required for a sequence and not an individual object. Though, there is nothing that can stop you from building one.

And you don't need a ; after a function body.