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?

Solution 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.

Solution 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.

Solution 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
};

Solution 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.

Solution 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);

View more solutions

Comments

[PaulJWilliams]

That will only work if you have a suitable operator defined for subtracting iterators from const iterators. AFAIK there is no such thing.

[aJ.]

It might work for vector(Random Access iterator). It may not work for list and other container.

[X-Istence]

@Visage: You don't need an suitable operator, in this case you are subtracting a const_iterator from a const_iterator, getting an integer offset, and adding it to an iterator. Perfectly valid, and works as it would be expected to work.

[CB Bailey]

Implementations are allowed to (and do) specialize std::advance and std::distance for random access iterators so that this can be constant time for some containers.

[tstenner]

Some functions like erase etc. require a const_iterator, so this wouldn't work.

[leiz]

You mean that erase takes a non const iterator, right? If that is the case, why do you use const_iterator at first place? most of time this kinda const cast I needed was for debugging propers.

[David Rodríguez - dribeas]

+1 on refactoring. Moreover when using const_iterators is intended as a performance hack.

[Pontus Gagge]

Actually, this should be constant time for (well-implemented) random access iterators. See aristeia.com/Papers/CUJ_June_2001.pdf.

[David Rodríguez - dribeas]

The article is pre-2003 standard (back from 2001). I'd like to see an updated revision after the 2003 changes to the standard

[michelson]

More specifically, this will only work with a Random Access Iterator since it is the concept that defines the necessary operations. Take a look at the SGI docs (sgi.com/tech/stl/RandomAccessIterator.html) for what I consider the best description.

[Steve Jessop]

For non-random-access iterators, I think iter i(d.begin()); while (ConstIter(i) != ci) ++i; would be more efficient. Still disappointing, but at least it only walks forwards from i once. You can use iterator-type-tag dispatch to write function templates that in effect overload on iterator type, at least they do assuming the iterators are tagged correctly.

[James McNellis]

This "works" for std::vector and other containers with contiguous storage, but not for other containers (like std::list).

[Xeo]

You need access to the container, however.

[James McNellis]

@xeo: Well, of course. It would be a gaping hole in const safety if you could do this without a non-const reference to the container.

[James McNellis]

@DavidRodríguez-dribeas: See my answer for a well-defined, constant time complexity solution for C++11 (three years late, but better than never! :-D).

[Steve Jessop]

+1. Ultra-pedantry: this works for all standard containers, since all standard containers are either sequences or associative containers or unordered associative containers. But erase isn't actually part of the container requirements, so it needn't necessarily work for all user-defined types that satisfy the container requirements. You've sort of already said this in the answer, but add "unordered associative" to the list in parens. Maybe this pedantry should be applied to your comment on Visage's answer, where you said "all containers", more than on your full answer.

[James McNellis]

@SteveJessop: Good point. I added unordered associative containers; I forgot that they aren't really "associative containers."

[James McNellis]

There is a constant time solution that has well-defined behavior and works for all Standard Library containers (and most other containers); see the answer that I have just posted.

[Steve Jessop]

Btw, std::array is close to a counter-example, but not quite there. It almost satisfies the container requirements, and it's not too difficult to imagine a third-party container type a bit like an array, that truly is a container without erase.

[Jonathan Jansson]

For std::string, make sure cast the string to a const string before calling begin. GCC's standard library implements copy on write and begin may cause the string to reallocate its memory which invalidates the iterators!

[Quuxplusone]

@JonathanJansson C++03 allowed the behavior you're talking about, but C++11 (21.4.1#6) implicitly prohibits it. The wording that in C++03 explicitly allowed begin() to invalidate iterators under certain circumstances has been removed, so that in C++11 begin() no longer invalidates iterators.

[newbie]

It should be noted that the erase invocation implies potential iterators and references invalidation for some containers. Of course it shouldn't happen for empty ranges, but certain b̶r̶a̶i̶n̶-̶d̶e̶a̶d̶ implementations like VS2017's one can trigger an assertion error.

[Paweł Stankowski]

You forgot about forward_list. It is the special container that contains the same methods, but with "_after" suffix. Correct implementation for it would be: c++ auto after_i = i; return c.erase_after(i, ++after_i);