Is "just-in-time calculation" an appropriate use for mutable?

Question

A graph can be represented as either an adjacency matrix or an adjacency list. My Graph object represents the graph as an adjacency matrix. For performance reasons, I don't calculate the adjacency list unless it is requested; however, once requested, I would like to retain the list (to avoid re-building it).

Is it appropriate to make the adjacency list mutable, so that users can generate the adjacency list for otherwise const Graph objects? I ask because I'm not convinced that building the adjacency matrix would be considered a "physical" as opposed to "logical" change to the state of the Graph. I also have an adjacencyListBuilt method, so the building of the adjacency list isn't "invisible" (see https://isocpp.org/wiki/faq/const-correctness#mutable-data-members).

If I understand correctly, declaring the adjacencyList instance variable mutable will allow any method to update it. Is there a way whereby only the buildAdjacencyList method is able to modify the adjacencyList instance variable on a const object?

Answer 1

Caching the results calculated from internal members using mutable is appropriate. Be aware that it can break the thread safety.

But I would also consider a separate class or function that performs a computation on a const object.

Answer 2

"Just-in-time calculation" is exactly what mutable was invented for, therefore yes, it is an appropriate use. Note that the interface would not specifically request building it; you'd just request access to it, and the class would notice that it wasn't yet built, and build it "behind the scenes". Therefore the logical state would not be affected.

If you are thinking of a function to request the building, and then a function or set of access functions that would be invalid to call when building was not yet requested, you are doing it wrong. Note that the problem then would be on the interface and not on the implementation; therefore it would be wrong no matter whether you implement it using mutable or not.

On your question of how to further protect it from other methods: If I understand you correctly, there are only two things that should ever be done to the adjacency list: Either it should be calculated from the current adjacency matrix, or it should be invalidated. Therefore I'd suggest to encapsulate it into a separate class (private to the Graph class) that encapsulates the mutable member (and is itself used as non-mutable member variable) and only offers two operations: (1) access the incidence matrix (const function, calculating the list if not yet calculated) and (2) invalidate the list (non-const, as only changes to the graph can make the list invalid). That way, no const member function of the Graph class can modify the list.

Answer 3

Is there a way whereby only the buildAdjacencyList method is able to modify the adjacencyList instance variable on a const object?

Sure, using a nested private member and friend:

class myGraph;
void buildAdjacencyListImpl(const myGraph&);

class myGraph
{
    class myAdjacencyListCache
    {
         mutable realAdjacencyList cached_list;

         friend void buildAdjacencyListImpl(const myGraph&);
    } adj_list;
    friend void buildAdjacencyListImpl(const myGraph&);

    void buildAdjacencyList() const { buildAdjacencyListImpl(*this); }
};

void buildAdjacencyListImpl( const myGraph& g )
{
    realAdjacencyList& listToBuild = g.adj_list.list_cache;
    // it isn't const, and can be modified
}

Answer 4

As it turned out, in my particular case, there were so many different cached values that making things mutable got gross pretty fast. (The description above was simplified.) Instead, I decided to make two different versions of Graph: ImmutableGraph and MutableGraph. ImmutableGraph has no methods to add or remove edges and vertices; thus, there are few cases where ImmutableGraph should be declared const.