Const-correctness semantics in C++

Question

For fun and profit™, I'm writing a trie class in C++ (using the C++11 standard.)

My trie<T> has an iterator, trie<T>::iterator. (They're all actually functionally const_iterators, because you cannot modify a trie's value_type.) The iterator's class declaration looks partially like this:

template<typename T>
class trie<T>::iterator : public std::iterator<std::bidirectional_iterator_tag, T> {
    friend class trie<T>;
    struct state {
        state(const trie<T>* const node, const typename std::vector<std::pair<typename T::value_type, std::unique_ptr<trie<T>>>>::const_iterator& node_map_it ) :
            node{node}, node_map_it{node_map_it} {}
// This pointer is to const data:
        const trie<T>* node;
        typename std::vector<std::pair<typename T::value_type, std::unique_ptr<trie<T>>>>::const_iterator node_map_it;
    };
public:
    typedef const T value_type;
    iterator() =default;
    iterator(const trie<T>* node) {
        parents.emplace(node, node->children.cbegin());
            // ...
    }
    // ...
private:
    std::stack<state> parents;
    // ...
};

Notice that the node pointer is declared const. This is because (in my mind) the iterator should not be modifying the node that it points to; it is just an iterator.

Now, elsewhere in my main trie<T> class, I have an erase function that has a common STL signature--it takes an iterator to data to erase (and returns an iterator to the next object).

template<typename T>
typename trie<T>::iterator trie<T>::erase(const_iterator it)
{
    // ...

    // Cannot modify a const object!
    it.parents.top().node->is_leaf = false;

    // ...
}

The compiler complains because the node pointer is read-only! The erase function definitely should modify the trie that the iterator points to, even though the iterator shouldn't.

So, I have two questions:

1. Should iterator's constructors be public? trie<T> has the necessary begin() and end() members, and of course trie<T>::iterator and trie<T> are mutual friends, but I don't know what the convention is. Making them private would solve a lot of the angst I'm having about removing the const "promise" from the iterator's constructor.
2. What are the correct const semantics/conventions regarding the iterator and its node pointer here? Nobody has ever explained this to me, and I can't find any tutorials or articles on the Web. This is probably the more important question, but it does require a good deal of planning and proper implementation. I suppose it could be circumvented by just implementing 1, but it's the principle of the thing!

Answer 1

1) All iterators are required to be copy-constructible. Your iterator is Bi-directional, hence is also required to be default-constructible (http://en.cppreference.com/w/cpp/concept/ForwardIterator), although I don't know why. So the default constructor needs to be public but you can do what you like with the const trie<T>* one. I would think it should be private, since the purpose of this class is to provide the user with an iterator over the trie, and so its public interface should be only that of an iterator of the appropriate category. No need for any extra public constructors.

2) erase is a non-const function. The only iterators you can validly pass to it are iterators that refer to the same trie that the function is called on, which means (I think, although I'm not quite certain I've followed your design) the whole hierarchy of parents are non-const objects. So I suspect this is one of those cases where you can const_cast<trie<T>*>(it.parents.top().node). The iterator isn't allowed to use it to modify the trie, which is why you want it to hold a pointer-to-const. But when you hold a non-const pointer to the trie, namely this, you are allowed to modify any part of it you like, and the iterator is just giving you the position to start modifying from.

There might be some more general principle of const-safety you can draw here. One possible case in container::erase(const_iterator) functions is that the const container* you'd get from the iterator is equal to this. In that case the const_cast is certainly both safe and legitimate (as well as unnecessary, because you can just use this, but that's beside the point of whether it's const-correct or not). In your container it is not (in general) equal to this, it points to one of the several trie objects that together make up the hierarchical container that this is part of. The good news is, that whole container is logically const or logically non-const together, hence the const_cast is just as safe and legitimate as if it were all one object. But a bit harder to prove correct, because you have to make sure that in your design the whole hierarchical container genuinely does, as I've assumed, share non-constness.

Answer 2

Non-const methods of trie that wish to modify what a const_iterator points to (what it points to should be within this instance of trie) should just const_cast as needed. You know this is a safe and defined cast because if someone managed to call a non-const instance of this trie, then this instance of trie itself is not const.*

Alternatively you could do the opposite and hold non-const pointer(s) to the trie within the const_iterator, which will require a const_cast upon construction. This is safe for the same reason, above. The const_iterator methods will only provide const access, so the user can't mutate the part(s) of trie that the iterator points to. And if a const_iterator needs to be mutated in a non-const trie method it's okay because the trie must not have been const in the first place.*

The premise of the safety of const_casting here is that it is safe to hold and use a non-const pointer to a const object so long as you do not mutate that object. And it is safe to turn a cast away the constness of a pointer which points to something which wasn't originally declared as const.

*Yes, the caller of the non-const trie method might have const_casted in an undefined way; but in that case the burdon of causing undefined behavior is on their head, not tries.

Answer 3

1. Should iterator's constructors be public?

At least the copy constructor, yes. Have a look at this chart that describes the traits each type of iterator should have:

http://www.cplusplus.com/reference/iterator/

All iterator types should be copy-constructible, copy-assignable and destructible, so that means they need public copy constructors. Some iterators, for example the RandomAccessIterator should also be default constructible so the default constructor should be public as well.

1. What are the correct const semantics/conventions regarding the iterator and its node pointer here?

If you want to have an erase then you don't really have a const_iterator, you have a regular iterator. The difference between the two is that if you have a const trie object then you can only get a const_iterator out of it because you're not allowed to modify it in any way.

You can notice this in the STL containers. They tend to have both:

iterator begin();
const_iterator begin() const;

What usually happens is that you implement a const_iterator then:

class iterator : public const_iterator {...};

which implements the one or two non-const functions. This probably means just erase for you, since your operator* is going to stay const.