First garbage collector Today I tried to learn how to make a simple garbage collector for a future project, it didn't need to be fast nor complex nor optimal, it just needed to work. After lots of searching and reading, I was able to make something work.

So, how can I improve it from here? At some point I guess I'll have to ditch the std::array (the small size is just for testing purposes). Do I actually need to use new and delete, or can I just keep using STL containers?

For what I've read, I have a couple options: mark and compact, copying garbage collection, generational garbage collector. Which of them would be the more natural evolution from what I've done?

#include &lt;array&gt;
#include &lt;iostream&gt;
#include &lt;string&gt;

using std::cout;
using std::endl;

template &lt;typename T&gt;
struct Handle {
    bool marked {};
    T value {};
    Handle * next {};
};

template &lt;typename T&gt;
class Heap {
    std::array&lt;Handle&lt;T&gt;, 10&gt; heap;

    Handle&lt;T&gt; * root {};
    Handle&lt;T&gt; * free_list {};

    void push(Handle&lt;T&gt; * handle) {
        handle-&gt;next = free_list;
        free_list = handle;
    }

    void reset() {
        for (size_t i = 0; i &lt; heap.size(); ++i) {
            heap[i].marked = false;
        }
    }

    void mark(Handle&lt;T&gt; * handle) {
        if (handle &amp;&amp; !handle-&gt;marked) {
            handle-&gt;marked = true;
            mark(handle-&gt;next);
        }
    }

    void sweep() {
        free_list = nullptr;
        for (size_t i = 0; i &lt; heap.size(); ++i) {
            if (!heap[i].marked) {
                heap[i].value = {};
                push(&amp;heap[i]);
            }
        }
    }

public:
    Heap() {
        for (size_t i = 0; i &lt; heap.size(); ++i) {
            push(&amp;heap[i]);
        }
    }

    template &lt;typename U&gt;
    Handle&lt;T&gt; * allocate(U &amp;&amp; u) {
        if (!free_list) {
            reset();
            mark(root);
            sweep();
            if (!free_list) {
                throw std::bad_alloc();
            }
        }
        Handle&lt;T&gt; * handle = free_list;
        free_list = free_list-&gt;next;
        handle-&gt;value = std::forward&lt;T&gt;(u);
        handle-&gt;next = nullptr;
        return handle;
    }

    Handle&lt;T&gt; * keep_alive(Handle&lt;T&gt; * handle) {
        handle-&gt;next = root;
        root = handle;
        return handle;
    }

    void signal() {
        root = nullptr;
    }
};

int main() {

    Heap&lt;std::string&gt; heap;

    auto a = heap.allocate("A");
    auto b = heap.keep_alive(a);

    a = heap.allocate("B");
    auto c = heap.keep_alive(a);

    a = heap.allocate("C");
    a = heap.allocate("D");
    a = heap.allocate("E");

    cout &lt;&lt; a-&gt;value &lt;&lt; endl;
    cout &lt;&lt; b-&gt;value &lt;&lt; endl;
    cout &lt;&lt; c-&gt;value &lt;&lt; endl;

    return 0;
}
From a design and interface point of view, I find the use of:

auto a = heap.allocate("A");
cout &lt;&lt; a-&gt;value &lt;&lt; endl;


unnatural. I would expect a to act like a pointer to std::string since it's the value returned from a function named allocate using an object of type Heap&lt;std::string&gt;.

It would be more natural if:


*a evaluated to std::string&amp; (std::string const&amp; if a were const)
a-&gt; evaluated to std::string* (std::string const* if a were const)


Then, you could replace a-&gt;value by *a.

auto a = heap.allocate("A");
cout &lt;&lt; *a &lt;&lt; endl;


P.S. I haven't spent enough time delving into the implementation of Heap to suggest how it can be done.