Why can I update member variables in a const member function?

Question

I'm trying to implement a linked list similar to how it might be implemented in the STL. While implementing the iterator, I made some const member functions (so the user can make use of a const iterator) and noticed that I was able to update member variables without getting a compiler error. The code uses templates, but I tested it calling a function that uses begin() and with a const list, so I know that the template functions that modify the member variables were generated by the compiler. Does anyone know why this works? The function in question is the const version of operator++.

Here's a version of my program, with irrelevant details taken out.

template<typename E>
struct Link {
    E val {};
    Link* next = nullptr;
    Link* prev = nullptr;
};

template<typename E>
struct List {   
    struct Iterator {
        Iterator(Link<E>* c) : curr{c} { }

        Iterator& operator++();
        const Iterator& operator++() const;

        const E& operator*() const {return curr->val;}
        E& operator*() {return curr->val;}

        // ...
    private:
        Link<E>* curr;
    };

    // Constructors, etc ...
    // Operations ...

    E& front() {return head->val;}
    const E& front() const {return head->val;}

    Iterator begin() {return Iterator{head};}
    const Iterator begin() const {return Iterator{head};}
    // Other iterator stuff ...

private:
    Link<E>* head;
    Link<E>* tail;
    int sz;
};

/*---------------------------------------------*/

template<typename E>
typename List<E>::Iterator& List<E>::Iterator::operator++() {
    curr = curr->next;
    return *this;
}

template<typename E>
const typename List<E>::Iterator& 
        List<E>::Iterator::operator++() const
{
    curr = curr->next;
    return *this;
}

I think conceptually, it makes sense to make a const version of operator++ even though it modifies member variables. A const iterator actually refers to the contents of the Link pointer being const, which is exactly why it returns a const E& in the dereference operator. Thus, with a const iterator, you can never update the contents of the iterator.

Let me know if there's anything I should include in the code snippet, thank you!

Answer 1

Template functions aren't actually checked for errors until they're instantiated. If you don't call them they just sit there unnoticed, bombs waiting to go off. You'll get a compiler error once you add a call to Iterator::operator++() const.

For example, I added:

int main() {
    List<int> list;
    const List<int>::Iterator iter = list.begin();
    ++iter;
}

And now clang complains:

main.cpp:52:10: error: cannot assign to non-static data member within const
      member function 'operator++'
    curr = curr->next;
    ~~~~ ^
main.cpp:61:3: note: in instantiation of member function
      'List<int>::Iterator::operator++' requested here
  ++iter;
  ^
main.cpp:14:25: note: member function 'List<int>::Iterator::operator++' is
      declared const here
        const Iterator& operator++() const;
                        ^

(Repl)

---

I think conceptually, it makes sense to make a const version of operator++ even though it modifies member variables. A const iterator actually refers to the contents of the Link pointer being const, which is exactly why it returns a const E& in the dereference operator. Thus, with a const iterator, you can never update the contents of the iterator.

A const iterator should not be mutable, nor have a ++ operator. The STL actually has separate iterator and const_iterator types. A const_iterator embodies the concept you're describing: the iterator is itself mutable, but what it points to is const.

I recommend you follow suit and create a separate ConstIterator class.