Does a template type waste space in C++?

Question

I was going through EASTL's list class to look at how the author has implemented the nodes. My expectation was a simplistic class/structure. Instead, I see a base and a node that is inheriting from this base (still simplistic, but why two classes?). His comments explain why:

We define a ListNodeBase separately from ListNode (below), because it allows us to have non-templated operations such as insert, remove (below), and it makes it so that the list anchor node doesn't carry a T with it, which would waste space and possibly lead to surprising the user due to extra Ts existing that the user didn't explicitly create. The downside to all of this is that it makes debug viewing of a list harder, given that the node pointers are of type ListNodeBase and not ListNode. However, see ListNodeBaseProxy below.

I don't understand a couple of things here. I do understand the part about why it will make debug viewing a bit harder, but what does he mean by list anchor node doesn't carry a T with it and would waste space and possibly lead to surprising the user due to extra Ts existing that the user didn't explicitly create?

Answer 1

Without the helper class, the list root node would contain an instance of T that is never used. The second sentence is saying that you might not expect an empty list to create a T. For example, creating a T might have side effects.

Answer 2

It seems to me that the idea is to separate the abstraction of the list, from the data it carries. You only need the ListNode when you actually want to access the data, all the rest can be done on the abstract ListNodeBase. That's how I understand the list anchor node doesn't carry a T with it.

There's something there about space. Template classes are created per type, so if you have several different types used for T, without the ListNodeBase you would be creating templated copies of all the operations per type, with it - you don't, and the LinkNode inherits them, and only requires the memory for the actual data. Seems that the space saved refers to the actual size of the code in this case.

Answer 3

You really want to support empty lists. If the head node itself always contains one T, and every list contains a head node, then it follows that every list contains at least one T, and therefore never can be empty.