Minimal example mark and sweep garbage collector.

gc.cpp

#include <cassert>
#include <list>
#include <set>
#include <functional>

struct object_t {
    object_t() : child_(nullptr) {}
    virtual ~object_t() {};
    object_t * child_;
protected:
    friend class gc_t;
    virtual void enumerate__(std::function<void(object_t *)> & func) {
        func(child_);
    }
};

struct gc_t {
    template <class T, class... Types>
    object_t * alloc(Types && ... args) {
        // check allocation derives from object_t
        static_assert(std::is_base_of<object_t, T>::value, "type must derive from object_t");
        // perform the allocation and call constructor
        object_t * obj = new T(std::forward<Types>(args) ...);
        // add to 'allocated' list
        allocs_.push_back(obj);
        return obj;
    }
    gc_t();
    void collect();
    void check_in(object_t *);

protected:
    std::list<object_t*> allocs_;
    std::set<object_t*> valid_;
    std::set<object_t*> mark_;
    std::function<void (object_t*)> bounce_;
    void follow(object_t * obj, std::set<object_t*> & out);
};

gc_t::gc_t() {
    bounce_ = [&](object_t * obj) {
        if (obj) {
            follow(obj, mark_);
        }
    };
}

void gc_t::follow(object_t * obj, std::set<object_t*> & out) {
    if (obj && out.find(obj) == out.end()) {
        out.insert(obj);
        obj->enumerate__(bounce_);
    }
}

void gc_t::collect() {
    for (auto & obj : valid_) {
        if (obj) {
            follow(obj, mark_);
        }
    }
    for (auto itt = allocs_.begin(); itt != allocs_.end();) {
        if (mark_.find(*itt) == mark_.end()) {
            assert(*itt);
            delete *itt;
            itt = allocs_.erase(itt);
        }
        else {
            ++itt;
        }
    }
    valid_.clear();
}

void gc_t::check_in(object_t * obj) {
    valid_.insert(obj);
}

int main(int argc, char ** args) {
    gc_t gc;
    // simple alloc chain
    object_t * obj1 = gc.alloc<object_t>();
    obj1->child_ = gc.alloc<object_t>();
    // lost allocation chain
    object_t * obj2 = gc.alloc<object_t>();
    obj2->child_ = gc.alloc<object_t>();
    obj2->child_->child_ = gc.alloc<object_t>();
    obj2 = nullptr;
    // cyclic reference
    object_t * obj3 = gc.alloc<object_t>();
    obj3->child_ = gc.alloc<object_t>();
    obj3->child_->child_ = obj3;
    // check in discoverable root
    gc.check_in(obj1);
    // collect any unreachable allocations
    gc.collect();
    return 0;
}

note: If the check-ins' are kept up to date, a collection could be triggered every x number of allocs. Question is, how do you keep the check-ins' up to date?

note: The member 'valid_' is a list of currently known valid allocations, typically the root of any data graph. Allocations can be added via the check_in() method. Known valid allocations must be checked in before any collection; any allocations not reachable from those checked in will be collected when collect() is called.