memory management for an immutable data model

Question

I've written a little toy data model, which uses a std::set to unique instances. This may be called either the flyweight pattern, or hash-consing (though, technically, I'm not yet using a hash table).

#include <set>
#include <cassert>

enum Color { Red, Green, Blue };

struct Shape {

  // Set the color, return a new shape.
  virtual const Shape* color(Color) const = 0;

};

template<class T>
const T* make_shape(T value) {

  struct cmp {
    bool operator()(const T* a, const T* b) const {
      return *a < *b;
    }
  };

  static std::set<const T*, cmp > values;

  auto iter = values.find(&value);

  if(iter != values.end()) {
    return *iter;
  }

  auto p = new T(value);
  values.insert(p);
  return p;

}

struct Circle : public Shape {
  Color c = Red;
  virtual const Shape* color(Color c) const {
    Circle r;
    r.c = c;
    return make_shape(r);
  }
  bool operator<(const Circle& rhs) const { return c < rhs.c; }
};

Here's my test code. Notice how the first two lines return the same pointer, so these semantics are different from normal allocation via new or make_shared.

void test_shape() {

  auto s0 = make_shape(Circle{});
  auto s1 = make_shape(Circle{});

  // Structurally equivalent values yield the same pointer.
  assert(s0 == s1);

  // Color is red by default, so we should get the same pointer.
  auto s2 = s0->color(Red);

  assert(s2 == s0);

  // Changing to Green gives us a different pointer.
  auto s3 = s0->color(Green);

  assert(s3 != s0);

  printf("done\n");

}

int main() {
    test_shape();
}

Right now, the shapes are simply leaked. That is to say that once a client of this data model no longer has a pointer to a Shape, that shape is not deallocated (consider the set to be weak references that should be broken).

So I'd like to use shared_ptr to manage my objects, because it seems simple (also open to other ideas, but I don't want to add dependencies, like boost).

But I'm having a little trouble with shared_ptr. I've tried updating the std::set to store std::weak_ptr<const T> with a comparison using owner_before.

I need a shared_ptr to look up the object in the set. But that would require newing an object, and part of the point here is to be able to quickly get an existing structurally equal object.

Update

I also tried keeping the set as raw pointers, and using the shared_ptr deleter to remove elements. Alas, that requires me to use shared_from_this which seems to balk, though I'm not exactly sure why:

shape.cpp:30:16: error: member reference base type 'Circle *const' is not a
      structure or union
    return iter->shared_from_this();
           ~~~~^ ~~~~~~~~~~~~~~~~

Answer 1

Here's the complete code. Turns out I'm just not very good at programming and didn't realize I had to deref something.

Basic approach is that the shared_ptr deleter removes the raw pointer from the set.

#include <set>
#include <cassert>
#include <memory>

enum Color { Red, Green, Blue };

struct Shape;
struct Circle;

struct Shape : public std::enable_shared_from_this<Shape> {

    virtual ~Shape() = default;

    // Set the color, return a new shape.
    virtual std::shared_ptr<Shape> color(Color) const = 0;

};

template<class T>
std::shared_ptr<Shape> make_shape(T value) {

    struct cmp {
        bool operator()(const T* a, const T* b) const {
            return *a < *b;
        }
    };

    static std::set<T*, cmp> values;

    auto iter = values.find(&value);

    if(iter != values.end()) {
        return (*iter)->shared_from_this();
    }

    auto ptr = std::shared_ptr<T>(new T(value), [](T* p) {
        printf("deleting %p\n", (void*)p);
        values.erase(p); delete p;
    });
    values.insert(ptr.get());
    return ptr;

}

struct CircleCount {
    static int count;

    CircleCount() { ++count; }
    CircleCount(const CircleCount&) { ++count; }
    ~CircleCount() { --count; }
};

int CircleCount::count;

struct Circle : public Shape {
    CircleCount count;
    Color c = Red;
    virtual std::shared_ptr<Shape> color(Color c) const {
        Circle r;
        r.c = c;
        return make_shape(r);
    }
    bool operator<(const Circle& rhs) const { return c < rhs.c; }
};

void test_shape() {

    {
        auto s0 = make_shape(Circle{});
        auto s1 = make_shape(Circle{});

        assert(s0 == s1);

        auto s2 = s0->color(Red);

        assert(s2 == s0);

        auto s3 = s0->color(Green);

        assert(s3 != s0);
    }

    // All circles should be cleaned up.
    printf("circles: %d\n", CircleCount::count);
    assert(CircleCount::count == 0);

    printf("done\n");

}

int main() {
    test_shape();
}

Update

I made this into something generic, which is up for code review here

Answer 2

One alternative solution is for your clients to use a factory that owns the objects it hands out. This way your clients can use plain pointers to refer to objects.

Once the client is done, it can dispose of the factory along with all the objects.

In addition, may be, have the factory reference counted, or keep a shared_ptr to it.