How to remove constness of const_iterator?

Question

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?

Answer 1

There is a solution with constant time complexity in C++11: for any sequence, associative, or unordered associative container (including all of the Standard Library containers), you can call the range-erase member function with an empty range:

template <typename Container, typename ConstIterator> typename Container::iterator remove_constness(Container& c, ConstIterator it) {     return c.erase(it, it); } 

The range-erase member functions have a pair of const_iterator parameters, but they return an iterator. Because an empty range is provided, the call to erase does not change the contents of the container.

Hat tip to Howard Hinnant and Jon Kalb for this trick.

Answer 2

Unfortunately linear time is the only way to do it:

iter i(d.begin()); advance (i,distance<ConstIter>(i,ci)); 

where iter and constIter are suitable typedefs and d is the container over which you are iterating.