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.

Answer 3

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 4

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

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

I believe this conversion is not needed in a well-designed program.

If you need do this - try redesigning the code.

As workaround you can use the following:

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 think that sometimes this conversion is impossible, because your algorithms don't have access to the container.

Answer 7

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 8

I thought it would be fun to come up with a solution to this that works for containers that aren't in the standard library and don't include the erase() method.

Attempting to use this causes Visual Studio 2013 to hang on compile. I'm not including the test case because leaving it to readers who can quickly figure out the interface seems like a good idea; I don't know why this hangs on compile. This occurs even when the const_iterator is equal to begin().

// deconst.h

#ifndef _miscTools_deconst
#define _miscTools_deconst

#ifdef _WIN32 
    #include <Windows.h>
#endif

namespace miscTools
{
    template < typename T >
    struct deconst
    {

        static inline typename T::iterator iterator ( typename T::const_iterator*&& target, T*&& subject )
        {
            typename T::iterator && resultant = subject->begin ( );

            bool goodItty = process < 0, T >::step ( std::move ( target ), std::move ( &resultant ), std::move ( subject ) );

        #ifdef _WIN32
             // This is just my habit with test code, and would normally be replaced by an assert
             if ( goodItty == false ) 
             {
                  OutputDebugString ( "     ERROR: deconst::iterator call. Target iterator is not within the bounds of the subject container.\n" ) 
             }
        #endif
            return std::move ( resultant );
        }

    private:

        template < std::size_t i, typename T >
        struct process
        {
            static inline bool step ( typename T::const_iterator*&& target, typename T::iterator*&& variant, T*&& subject )
            {
                if ( ( static_cast <typename T::const_iterator> ( subject->begin () + i ) ) == *target )
                {
                    ( *variant ) += i;
                    return true;
                }
                else
                {
                    if ( ( *variant + i ) < subject->end () )
                    {
                        process < ( i + 1 ), T >::step ( std::move ( target ), std::move ( variant ), std::move ( subject ) );
                    }
                    else { return false; }
                }
            }
        };
    };
}

#endif

Answer 9

Assuming your container's const_iterator has the same layout as its iterator (a valid assumption for all STL containers), you can simply bit-cast the former to the latter:

#include <bit>
#include <vector>

void demo() {
    using vec_t = std::vector<int>;
    vec_t v { 1, 2, 3 };
    vec_t::const_iterator c_it = v.cbegin();
    vec_t::iterator it = std::bit_cast<vec_t::iterator>(c_it);
    *it = 4; // OK, now v holds { 4, 2, 3 }
}

Answer 10

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;