Why is this C++ constructor called twice at the same memory location in this implementation of a linked list?

Question

I was reading Data Structures and Algorithm Analysis in C++ by Shaffer (available for free at https://people.cs.vt.edu/shaffer/Book/) because I saw that it uses templates and I'm trying to learn more about C++ and generic programming in C++.

When the author introduces Linked Lists, he gives a variant that uses a freelist. (This is around pg 111, pdf page 130). In his implementation, he creates a class for a Link and overrides operator new to pull from the freelist. Then there is a class for LinkedList.

However, it turns out that in this implementation, calling new LinkedList will cause a constructor to be called by the same object twice, and I'm having trouble figuring out why.

This code shows the relevant parts of the example.

#include <cstddef>
#include <iostream>

struct S {
  S()  { std::cout << "ctor at " << this << "\n"; }
  ~S() { std::cout << "dtor at " << this << "\n"; }
};

class Link {
private:
  static Link * freelist;
  S elem;
  Link * next;
public:
  void * operator new(size_t) {
    if (freelist == nullptr) { return ::new Link; }
    Link * tmp = freelist;
    freelist = freelist->next;
    return tmp;
  }
  // other logic
};
Link * Link::freelist = nullptr;

class LinkedList {
private:
  Link * head;
public:
  LinkedList() { head = new Link; }
  // other logic
};

int main() { LinkedList ll; }

Example output of this code was

ctor at 0x458bbd954eb0
ctor at 0x458bbd954eb0

and so we can see that the constructor for the struct S was called twice by the same object.

Here is what I would have expected.

1. In main, we construct a LinkedList.
2. In this LinkedList, we call new Link. I believe this invokes Link::operator new, which we've overridden.
3. In Link::operator new, we see that Link sees that its freelist is empty, and so then calls ::new Link.
4. ::new Link constructs a Link, including its private member variable S elem, constructing an S struct.

Clearly this is incorrect. I would bet that I'm missing an implicit new from the compiler --- but even then, I'm surprised that a single S instance's constructor is called twice. So my mental model is definitely incomplete.

Can you help explain why the constructor is called twice at the same location in memory?

Answer 1

operator new's task is to allocate memory; it must not call a constructor. The constructor is called automatically after operator new returns.

Therefore, your implementation should look like this:

void * operator new(size_t size) {
    if (freelist == nullptr) {
       // here is the difference:
       return ::operator new(size);
    }
    Link * tmp = freelist;
    freelist = freelist->next;
    return tmp;
}

In your implemenation, the constructor was called from ::new Link, and then after the pointer was returned, it was called again as usual on the same address.

Of course, you should implement complementary operator delete. This one must not call a destructor (that has already been called), but just put the memory into the freelist.