How to remove const_iterator constant?

Question

As a complement to this question, are const_iterators faster? I have one more question about const_iterators . How to remove const_iterator constant? Although iterators are a generic form of pointers, const_iterator and iterator are two different things. Therefore, I believe, I also can not use const_cast<> for hidden from const_iterator to iterator s.

One approach might be that you define an iterator that moves to the level that const_iterator points to. But it looks like a linear time algorithm.

Any idea that this is the best way to achieve this?

Answer 1

C ++ 11 has a solution with constant time complexity: for any sequence, associative or disordered associative container (including all containers of the standard library), you can call the 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); } 

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

Hat advice to Howard Hinnant and John Kalb for this trick.

Answer 2

Unfortunately, linear time is the only way to do this:

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

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

Answer 3

There were several people in the answers to your previous post, including me, who recommended using constant constants instead of reasons not related to performance. Readability, traceability from the design board to the code ... Using const_iterators to provide mutating access to a non-constant element is much worse than never using const_iterators. You turn your code into something that only you will understand, with worse design and real maintainability. Using const just to remove it is much worse than not using const at all.

If you are sure you want this, 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 take your foot off ... well, C ++ can provide you with your weapon.

First, the simplest: if your operations accept arguments as const (even if they are used inside const_cast), I believe that it should work directly in most implementations (even if this is probably undefined behavior).

If you cannot change functors, you can solve the problem on either side: provide a non-const-iterator wrapper around constant iterators or provide a wrapper of a const functor around non-const functors.

Iterator facade, a long way:

 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

Perhaps this is not the answer you need, but somewhat related.

I assume that you want to change what the iterator points to. The easiest way I do is const_cast instead of the returned link.

Something like that

const_cast<T&>(*it);

Answer 5

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

Answer 6

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

If you need it, try redesigning the code.

As a workaround, you can do 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 not possible because your algorithms cannot access the container.

Answer 7

You can subtract the begin () iterator from const_iterator to get the position that const_iterator points to, and then add begin () back to this to get a non-constant iterator. I don’t think it will be very effective for non-linear containers, but for linear ones like a vector, it will take a 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 only works for linear (random access) containers.

Answer 8

you can convert the pointer value of a constant iterator to a pointer not const value 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 9

I thought it would be great to come up with a solution for this that works for containers that are not part of the standard library and do not include the erase () method.

Attempting to use this causes Visual Studio 2013 to freeze during compilation. I do not include a test case, because leaving it to readers who can quickly understand the interface seems like a good idea; I do not know why this freezes when compiling. This happens even when 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 10

I don't have a (good) answer, but the suggested answer is the typename Container :: iterator remove_constness template (Container & c, ConstIterator it)

doesn't work for std :: forward_list (because it doesn't have an erase method).

The std :: advance () approach obviously works, but at an awful cost.