Dealing with lazy computation in C++ classes

Question

Let's say I have a class:

class NumberCollection
{
public:
    typedef std::set<int> SetType;
    typedef SetType::iterator iterator;
    void insert(int n);

    iterator begin();
    iterator end();
    size_t size() const;

    iterator difficultBegin();
    iterator difficultEnd();
    size_t difficultSize() const;    

private:
    SetType easySet_, difficultSet_;
}

Where insert() adds an element to easySet_. difficultSet_'s members change depending on the members of easySet_.

The problem I am having is that, multiple insertions means that difficultSet_ is constantly recalculated. So I want difficultSet_ to be calculated lazily (i.e., only when difficultBegin(), difficultEnd(), or difficultSize() are called). The problem is, then I actually have to make difficultSet_ into a mutable because otherwise difficultSize() cannot operate on it.

So now my class declaration looks like

class NumberCollection
{
public:
    typedef std::set<int> SetType;
    typedef SetType::iterator iterator;
    void insert(int n);

    iterator begin();
    iterator end();
    size_t size() const;

    iterator difficultBegin();
    iterator difficultEnd();
    size_t difficultSize() const;    

private:
    SetType easySet_; 
    mutable SetType difficultSet_;
    mutable bool upToDate_;
}

I feel like this is bad design though. Is there a better way?

Answer 1

That's totally the way to do it. Const can mean binary const, or it can mean conceptually const. Using mutable means you're doing the later, which is fine.

Answer 2

This is essentially the reason C++ has the mutable construct. Alan De Smet's rant about the misuse of mutable shows the kinds of situations in which mutable should not be used.

In this case, difficultSize() does not change what the NumberCollection represents - which is suitable for marking as const. It does how ever need to change the internals at times, which is why you need to mark difficultSet_ and upToDate_ as mutable.

Answer 3

To help understand why to use mutable, we can explore other options.

You can solve the same problem using const_cast:

size_t NumberCollection::difficultSize() const
{
     if(!upToDate_)
     {
          NumberCollection& nonConst = const_cast<NumberCollection&>(*this);
          nonConst.difficultSet_ = PerformExpensiveCalculationFunction();
          nonConst.upToDate_ = true;
     }
     // etc....
}

Having offered this solution, I'll say that it's inferior to using mutable. If a member is marked as mutable, then simply by looking at the header I can gather how you are treating it. I don't get this information if you use const_cast.

But then somebody might take the other side of the debate, and say that it's better not to expose implementation details in the header.