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;
};