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

You can subtract the begin() iterator from the const_iterator to obtain the position the const_iterator is pointing to and then add begin() back to that to obtain a non-const iterator. I don't think this will be very efficient for non-linear containers, but for linear ones such as vector this will take constant time.

vector<int> v;                                                                                                         
v.push_back(0);
v.push_back(1);
v.push_back(2);
v.push_back(3);
vector<int>::const_iterator ci = v.begin() + 2;
cout << *ci << endl;
vector<int>::iterator it = v.begin() + (ci - v.begin());
cout << *it << endl;
*it = 20;
cout << *ci << endl;

EDIT: This appears to only work for linear (random access) containers.

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.

Answer 3

Can I suggest getting hold of a copy of Scott Meyers' excellent book Effective STL, where issues like this and the others you have raised are discussed in detail. Scott spends three pages describing the solution to your current question.

Answer 4

You could also use find to search for the element (if there are no duplicate elements):

iterator it=find(container.begin(), container.end(), *constit);

Answer 5

This may not be the answer you wanted, but somewhat related.

I assume you want to change the thing where the iterator points to. The simplest way I do is that const_cast the returned reference instead.

Something like this

const_cast<T&>(*it);

Answer 6

you can convert your const iterator value pointer to a non const value pointer and use it directly something like this

    vector<int> v;                                                                                                         
v.push_back(0);
v.push_back(1);
v.push_back(2);
v.push_back(2);
vector<int>::const_iterator ci = v.begin() + 2;
cout << *ci << endl;
*const_cast<int*>(&(*ci)) = 7;
cout << *ci << endl;

Answer 7

I believe this conversion is not needed in good designed program.

If you need do this - try redesign code.

As workaround you can do next:

typedef std::vector< size_t > container_type;
container_type v;
// filling container code 
container_type::const_iterator ci = v.begin() + 3; // set some value 
container_type::iterator i = v.begin();
std::advance( i, std::distance< container_type::const_iterator >( v.begin(), ci ) );

But I'm think that sometimes this conversion is impossible, because your algorithms can haven't access to container.

Answer 8

In the answers to your previous post, there were a couple of people, me included, that recommended using const_iterators instead for non-performance related reasons. Readability, traceability from the design board to the code... Using const_iterators to provide mutating access to a non-const element is much worse than never using const_iterators at all. You are converting your code into something that only you will understand, with a worse design and a real maintainability pain. Using const just to cast it away is much worse than not using const at all.

If you are sure you want it, the good/bad part of C++ is that you can always get enough rope to hang yourself. If your intention is using const_iterator for performance issues, you should really rethink it, but if you still want to shoot your foot off... well C++ can provide your weapon of choice.

First, the simplest: if your operations take the arguments as const (even if internally apply const_cast) I believe it should work directly in most implementations (even if it is probably undefined behavior).

If you cannot change the functors, then you could tackle the problem from either side: provide a non-const iterator wrapper around the const iterators, or else provide a const functor wrapper around the non-const functors.

Iterator façade, the long road:

template <typename T>
struct remove_const
{
    typedef T type;
};
template <typename T>
struct remove_const<const T>
{
    typedef T type;
};

template <typename T>
class unconst_iterator_type
{
    public:
        typedef std::forward_iterator_tag iterator_category;
        typedef typename remove_const<
                typename std::iterator_traits<T>::value_type
            >::type value_type;
        typedef value_type* pointer;
        typedef value_type& reference;

        unconst_iterator_type( T it )
            : it_( it ) {} // allow implicit conversions
        unconst_iterator_type& operator++() {
            ++it_;
            return *this;
        }
        value_type& operator*() {
            return const_cast<value_type&>( *it_ );
        }
        pointer operator->() {
            return const_cast<pointer>( &(*it_) );
        }
        friend bool operator==( unconst_iterator_type<T> const & lhs,
                unconst_iterator_type<T> const & rhs )
        {
            return lhs.it_ == rhs.it_;
        }
        friend bool operator!=( unconst_iterator_type<T> const & lhs,
                unconst_iterator_type<T> const & rhs )
        {
            return !( lhs == rhs );
        }
    private:
        T it_;  // internal (const) iterator
};

Answer 9

Scott Meyer's article on preferring iterators over const_iterators answers this. Visage's answer is the only safe alternative, but is actually constant time for well-implemented random access iterators, and linear time for others.

Answer 10

Is it possible to specify some part of the data the iterator is pointing to as mutable?