How to remove constness of const_iterator?

As an extension to this question Are const_iterators faster?, I have another question on const_iterators. How to remove constness of a const_iterator? Though iterators are generalised form of pointers but still const_iterator and iterators are two different things. Hence, I believe, I also cannot use const_cast<> to covert from const_iterator to iterators.

One approach could be that you define an iterator which moves 'til the element to which const_iterator points. But this looks to be a linear time algorithm.

Any idea on what is the best way to achieve this?