Is it safe to do a const cast here?

Question

I've written my own generic tree implementation, and when writing iterators for it, I am having trouble with const correctness. The issue I am having currently is as follows:

This is the header file for a DFS iterator I wrote:

template<class Item>
class DFSIterator
{
public:
    DFSIterator(const Item& rRootNode);
    ~DFSIterator();
    DFSIterator* First();
    DFSIterator* operator++(int rhs);
    Item* operator*() const;
    Item* operator->() const;
    bool isDone() const;

    template <class Node> friend class Node;

private:
    void initListIterator(const Item* currentNode);

    bool m_bIsDone;
    const Item* m_pRootNode;
    const Item* m_pCurrentNode;
    ListIterator<Item>* m_pCurrentListIter;
    std::map<const Item*, ListIterator<Item>*>  m_listMap;
};

So the bit I am concerned about is the dereference operator:

template<class Item>
Item* DFSIterator<Item>::operator*() const
{
    if(isDone())
    {
        return NULL;
    }
    else
    {
        return const_cast<Item*>(m_pCurrentNode);
    }
}

Is it appropriate to do a const_cast there? I'm wondering if this would cause problems if a user put const objects into the container?

Answer 1

const_casting in itself is always safe, but any attempt to write to const_casted values who have been declared const is undefined behaviour.

In this case, if your returned pointer points to a value that is declared const and you attempt to modify it, you'll get undefined behavior.

---

Rule of thumb: If you need to use const_cast for anything but interoperation with const-incorrect code, your design is broken.

---

The standard says in 7.1.6.1 The cv-qualifiers:

Except that any class member declared mutable (7.1.1) can be modified, any attempt to modify a const object during its lifetime (3.8) results in undefined behavior.

Answer 2

As your constructor uses a const Item, your operator shoud return a const pointer.

If you want to return a non-const item, you should use a non const parameter for your constructor. A solution is having a base class using const objects, and a subclass working with non-const objects (A bit in a way it is done in Objc, eg NSString and NSMutableString).

Answer 3

Do not cast the const away, as it will break its meaning! There is a reason why the STL has a const_iterator and iterator class. If you want const correctness you will have to implement two seperate iterator classes. One of the goals of a iterator is to mimic a save pointer. So you do not want to return null if you're beyond the iteration range, you want to raise a debug assertion if this actually happens.

A const iterator class could look something like this:

template<class Item>
class DFSIteratorConst
{
public:
    DFSIteratorConst(const Item& node)
    {
        m_pCurrentNode = &node;
    };

    const Item& operator*() const
    {
        assert(!IsDone());
        return *m_pCurrentNode;
    }

    void operator++()
    {
        assert(!IsDone());
        m_pCurrentNode = m_pCurrentNode->next;
    }

    operator bool() const
    {
        return !IsDone();
    }

    bool IsDone() const
    {
        return m_pCurrentNode == nullptr;
    }

private:
    Item const * m_pCurrentNode;
};

A few things to note:

• consider returning a reference to the node (a const reference). This causes you to not be able to return null if the iterator is past the last element. Dereferencing a past the end iterator is usually bad behaviour and you want to find those issues during debug builds and testing
• the const iterator class has a pointer to a const element. Meaning that it can change the pointer (otherwise you would not be able to iterate) but can not modify the element itself
• the implicit conversion to bool is practical if you want to check the iterator in a while loop. This allows you to write: while(it) { it++; } instead of while(!it.IsDone()) { it++; } again, something that resembles a classic pointer.
• use nullptr if available

As I can see from your use of std::map your are already using the STL. Maybe it would be easier to use exsiting STL iterators?

Answer 4

Normally, you write two iterators versions, an iterator and a const_iterator.

There are template tricks to avoid the code duplication that is exposed in the Boost.Iterator library documentation. See how the Iterator Adaptor is defined as it is quite long.

The thing is that you will write a BaseIterator that is const conscious, and then provide aliases:

• typedef BaseIterator<Item> Iterator;
• typedef BaseIterator<Item const> ConstIterator;

The trickery is in how you define the conversion constructor so that Iterator to ConstIterator is possible but the reverse is not.

Answer 5

The real problem is that this code/interface is "lying".

The constructor says: I don't change you (the root). But the iterator gives changeable Item away.

To be "honest" either the constructor takes a changeable root, even when it will not changed within this class, or this class does not give changeable Item away.

However, Item itself defines whether it give changeable childs away. Depending on that code may not compile. Maybe this is the reason for your construction.

Long talking, short meaning: this design is poor and should be changed

Probably you need two templates depending on the "const"-ness of given childs away