const input vs non-const output

Question

I have a function which traverses a tree of objects and does not modify any of the objects in the tree.

The function looks something like this:

static Node* findMatchingNode(const Node& root, const SomeFilterData& d);

struct Node {
   Node* left;
   Node* right;
};

The function can return the root or any object in the tree or nothing. It's obvious than with given declaration I have to perform const_cast somewhere, which is forbidden in most cases.

Is it acceptable for a function to guarantee constness and at the same time allow anyone to modify its output?

EDIT. I haven't stated this clearly, my function really does not modify any of the nodes in the tree, doesn't create new Node, it's pure function. I'd like to always have const qualifier there to tell everyone clearly that the function doesn't modify anything

EDIT. The unspoken problem behind is that there is no legal way to express constness of the input during the function execution (and only inside the function) without enforcing the output constness.

Answer 1

As always, you cannot modify const data because it is constant. In particular:

Even though const_cast may remove constness or volatility from any pointer or reference, using the resulting pointer or reference to write to an object that was declared const or to access an object that was declared volatile invokes undefined behavior.

(from here)

So if a pointer to the const input argument root is a sensible outcome, the return type should be const as well. You should be really careful with returning pointers anyway: As of now, your function can return a pointer to a temporary!

So better return a boost::optional<Node> or an std::optional<Node> (if the latter makes it into C++17 and you use that standard).

If your function only makes sense for a modifiable input root (e.g. if the outcome must be modifiable and the outcome can be the address of root), drop the const in your declaration. That would also prevent the input root from being a temporary.

---

Most likely the cleanest fix for your potential XY-problem:

If it fits your use-case (I find it highly unlikely that it does not), the most likely even better option would be defining your algorithm on a iteratable data structure like a tree or a list (whatever your Node is a node of) and then return an iterator to the matching node, or a past-the-end iterator (with respect to the high-level structure) if no such node exists.

As for the const-vs.-non-const discussion: With the iterator option you can differentiate between the constness of the high level structure and the reference node you compare stuff with by taking non-const iterators over the high level structure and a const & argument for the reference input node (where a temporary now would not be a problem).

From what I can see from your question, your function might even be replaceable with std::find_if. Then you would not have this problem in the first place.

Answer 2

Your code is not const-correct, it drops a const. This is why you have the problem of a "required" const cast. Don't do that:

static const Node* findMatchingNode(const Node& root, const SomeFilterData& d);

You may point out that you may want to call this function from another function that does modify the nodes, and thus wants a non-const result. As such, that should be a new function with a totally different signature:

static Node* findMatchingNode(Node& root, const SomeFilterData& d);

You may point out that these have identical bodies, and there's the DRY principle (DRY = Don't Repeat Yourself = Don't have copy-pasted code). Yes, so just take a shortcut here: const_cast. I think it's ok in this case, because it's only purpose is shared code, and it's clear that it's not violating any const-correctness principles.

//This function does not modify anything
static Node* findMatchingNode(Node& root, const SomeFilterData& d) {
    return const_cast<Node*>(findMatchingNode(const_cast<const Node&>(root),d));
}

Loki Asari suggests adding a third private function findMatchingNodeCommon() that both versions of findMatchingNode() call. Then you can get away with one less const_cast. If you want to go extreme then you can make findMatchingNodeCommon() templated and then all const_casts go away. I think it's not worth the bother, but they're very valid opinions, so worth a mention.