0

For example, consider the following Disjoint Set data structure with path compression (https://en.wikipedia.org/wiki/Disjoint-set_data_structure):

struct DisjointSet {
        /* Other stuff*/
        int find(int x) {
                if(parent[x] != x) {
                    parent[x] = find(parent[x]);
                }
                return parent[x];
        }
        private:
        std::vector<int> parent;
};

The method find() does not modify the implicit data represented by the data structure. Should I instead use the following implementation which lets find() be const?

struct DisjointSet {
        /* Other stuff*/
        int find(int x) const {
                if(parent[x] != x) {
                    parent[x] = find(parent[x]);
                }
                return parent[x];
        }
        private:
        mutable std::vector<int> parent;
};
user3559888
  • 1,157
  • 1
  • 9
  • 12
  • 1
    Yes, that's exactly what `mutable` was invented for. – n. m. could be an AI Aug 30 '15 at 15:28
  • The reason I picked this example is because it is quite extreme, all data members have to be mutable. But you would still use it in this case? That's what I am currently doing, and maybe it is because of the nature of my project but I end up with most data members as mutable which doesn't feel right. – user3559888 Aug 30 '15 at 15:35
  • You are interested in logical (application-level) equality. If a function preserves it, it should be `const`. If it doesn't, it shouldn't. Whatever becomes mutable as the result should stay mutable. If all data members become mutable then so be it. – n. m. could be an AI Aug 30 '15 at 15:39
  • Lots of mutables it is, thanks for your help! – user3559888 Aug 30 '15 at 15:42
  • There has been an interesting discussion started by Herb Sutter on how C++11 may have changed the meaning of `const` of `mutable`. See http://stackoverflow.com/questions/14131572/always-declare-stdmutex-as-mutable-in-c11 for a reference to the talk which initiated the discussion and some answers by people who disagree. – Christian Hackl Aug 30 '15 at 16:46

0 Answers0