Cast of const_iterator to iterator& in definition of std::set

Question

C++ STL uses a red-black tree to store data inside std::set and std::map. I noticed that set::iterator is actually a typedef of the const iterator of the red black tree:

//All code snippets taken from SGI STL. https://www.sgi.com/tech/stl/

typedef _Rb_tree<key_type, value_type, _Identity<value_type>, key_compare, _Alloc> _Rep_type;
typedef typename _Rep_type::const_iterator iterator;

This is reasonable because users are supposed not to modify the content of the set through an iterator. But set has to implement operations like insert and erase, which calls for a non-const iterator of the red-black tree. SGI STL uses a c-style cast to do this:

void erase(iterator __position) { 
  typedef typename _Rep_type::iterator _Rep_iterator;
  _M_t.erase((_Rep_iterator&)__position); 
}

I'm wondering:

1. Why is this cast safe? It is casting _Rep_type::const_iterator to _Rep_type::iterator&.
2. How to write the cast in C++ style? I've tried to do it: Neither static_cast nor const_cast will do the job. reinterpret_cast can compile, but I'm not sure if it does the same thing as the C-style cast.

Answer 1

iterator and _Rep_type::iterator are instances of the same class template, the former using const qualified types and the latter using the same, but non-const types. Something like this:

template <class T, class U>
struct B {};

using S = B<int&, int*>;
using Sconst = B<const int&, const int*>;

So for your questions:

1. It is safe because the two types have the exact same memory layout.
2. You cannot use static_cast because the compiler considers the types to be unrelated. You have to bring in the heavy artillery, reinterpret_cast:

int test() {
    S s;
    Sconst& sconst = reinterpret_cast<Sconst&>(s);
}

Answer 2

A C-Cast has no direct mapping to one specific C++ cast.

But a C-Cast can be mapped to one or more C++ casts.

When doing a C-Cast you can think of the compiler trying this set of C++ casts in order. The first one that is valid is what the C++ compiler will do: (see also C++ Standard, In N4917 7.6.3 Explicit type conversion (cast notation) [expr.cast])

1. const_cast
2. static_cast
3. static_cast followed by const_cast
4. reinterpret_cast
5. reinterpret_castfollowed by const_cast

So looking at your example, it looks like option 3 or 5 (but would need to try it with a compiler to be sure).

 (_Rep_iterator&)__position

 // Maps to:

 const_cast<_Rep_iterator&>(static_cast<_Rep_iterator const&>(__position))

 // or

 const_cast<_Rep_iterator&>(reinterpret_cast<_Rep_iterator const&>(__position))