Implementation of std::list::insert: casting away constness?

Lately I was implementing my own linked list class and emulating the behavior of std::list for practicing purpose. I came across a problem about constness when implementing the insert method. I've written an MWE to demonstrate my problem (so no templates or private members).

I start with the node:

struct MyNode {
    MyNode* prev;
    MyNode* next;
    int value;
};

and the iterators which hold the pointer to the node:

struct MyListIterator {
    MyNode* ptr;
};

struct MyListConstIterator {
    const MyNode* ptr;
};

And finally the list class. I have the problem when implementing the insert method. Following the C++ standard, the signature should be iterator insert( const_iterator pos, const T& value );, in particular, the first argument is a const_iterator. So I wrote:

struct MyList {
    using iterator = MyListIterator;
    using const_iterator = MyListConstIterator;

    iterator insert(const_iterator pos, const int& value) {
        auto node = new MyNode{pos.ptr->prev, pos.ptr, value}; // Error 1
        pos.ptr->prev = node; // Error 2

        // Other code...
    }
};

But here come the errors.

For error 1, pos.ptr is const MyNode*, so cannot be assigned to MyNode*.
For error 2, pos.ptr->prev cannot be modified since pos.ptr is a const pointer.

The only way I can think of is to cast away the constness of the underlying pointer of the const_iterator pos parameter, i.e.,

    iterator insert(const_iterator pos, const int& value) {
        auto unsafe_ptr = const_cast<MyNode*>(pos.ptr);

        auto node = new MyNode{pos.ptr->prev, unsafe_ptr, value}; // Error 1 solved
        unsafe_ptr->prev = nullptr; // Error 2 solved

        // Other code...
    }

I've always heard that casting away constness is bad. Is this the only way to do this?

By the way, how does "standard implementation" of C++ library do this? I tried to looking into libc++ and found some functions like __unsafe_link_pointer_cast, and it seems that the underlying pointer in MyListConstIterator isn't even a const pointer. I was not sure about my findings so I would like to seek for an answer.

Solution

The Standard requirements impose that, for a container, the iterator and const_iterator must provide a certain interface to value_type and const value_type, respectively. The interface may be one of the six types of iterator requirements.

For the std::list container, it is of type BidirectionalIterator.

This means that, when a const-iterator object is dereferenced, it should return a reference to const value_type. However, there's no a requirement on how the pointer is actually stored.

A common design is to store a pointer-to-T for both the iterator and const-iterator, so that there is no need to perform a const-cast operation on the stored pointer. This approach is also used by the libc++ implementation.

template <class _Tp, class _VoidPtr>
class __list_iterator {
  typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
  typedef typename _NodeTraits::__base_pointer __base_pointer;

  __base_pointer __ptr_;

  // ...

};

Conversely, it is also possible to store a pointer-to-T for the iterator and pointer-to-const-T for the const-iterator. This approach is used by the libstdc++ implementation.

template<typename _Tp>
  struct _List_iterator
  {
    
    // ...
    
    __detail::_List_node_base* _M_node;
  };

template<typename _Tp>
  struct _List_const_iterator
  {
    
    // ...
    
    const __detail::_List_node_base* _M_node;
  };