如何消除const_iterator的常量性？

Question

作为这个问题的扩展const_iterators更快吗？，我还有另一个问题在const_iterators上。 如何消除 const_iterator 的常量性？ 尽管迭代器是指针的广义形式，但 const_iterator 和迭代器仍然是两个不同的东西。 因此，我相信，我也不能使用 const_cast<> 从 const_iterator 转换为迭代器。

一种方法是定义一个迭代器，它移动到 const_iterator 指向的元素。 但这看起来是一个线性时间算法。

您知道实现此目标的最佳方法是什么吗？

Answer 1

C++11 中有一个时间复杂度恒定的解决方案：对于任何序列、关联或无序关联容器（包括所有标准库容器），您可以使用空范围调用 range-erase 成员函数

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

： -erase 成员函数有一对 const_iterator 参数，但它们返回一个迭代器。 由于提供了空范围，因此对擦除的调用不会更改容器的内容。

向 Howard Hinnant 和 Jon Kalb 的这一技巧致敬。

Answer 2

不幸的是，线性时间是执行此操作的唯一方法：

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

其中 iter 和 constIter 是合适的 typedef，而 d 是要迭代的容器。

Answer 3

在您上一篇文章的答案中，有几个人（包括我）出于与性能无关的原因建议使用 const_iterators 。 从设计板到代码的可读性、可追溯性……使用 const_iterators 提供对非常量元素的变异访问比根本不使用 const_iterators 糟糕得多。 您正在将代码转换为只有您才能理解的东西，并且设计更糟糕，并且真正的可维护性痛苦。 仅仅使用 const 来抛弃它比根本不使用 const 更糟糕。

如果你确定你想要它，C++ 的好处/坏处是你总能找到足够的绳子来吊死自己。 如果您的目的是使用 const_iterator 来解决性能问题，那么您确实应该重新考虑它，但如果您仍然想大快朵颐……那么 C++ 可以提​​供您选择的武器。

首先，最简单的：如果您的操作将参数作为 const （即使内部应用 const_cast），我相信它应该直接在大多数实现中工作（即使它可能是未定义的行为）。

如果您无法更改函子，那么您可以从任一方面解决问题：在 const 迭代器周围提供一个非常量迭代器包装器，或者在非常量函子周围提供一个 const 函子包装器。

迭代器外观，漫长的道路：

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 的文章关于优先使用迭代器而不是 const_iterators 回答了这个问题。 Visage 的答案是 C++11 之前唯一安全的替代方案，但实际上对于实现良好的随机访问迭代器来说是恒定时间，对于其他迭代器来说是线性时间。

Answer 5

这可能不是您想要的答案，但有些相关。

我假设您想更改迭代器指向的内容。 我做的最简单的方法是 const_cast 返回的引用。

像这样的

const_cast(*it);

Answer 6

我相信设计良好的程序不需要这种转换。

如果您需要这样做 - 尝试重新设计代码。

作为解决方法，您可以使用以下方法：

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

但我认为有时这种转换是不可能的，因为您的算法无权访问容器。

Answer 7

您可以从 const_iterator 中减去 begin() 迭代器以获得 const_iterator 指向的位置，然后将 begin() 添加回该位置以获得非常量迭代器。 我认为这对于非线性容器来说不是非常有效，但对于诸如矢量之类的线性容器来说，这将花费恒定的时间。

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;

编辑：这似乎仅适用于线性（随机访问）容器。

Answer 8

您可以将 const 迭代器值指针转换为非常量值指针并直接使用它，如下所示

    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

我认为提出一个适用于不在标准库中并且不包含擦除（）方法的容器的解决方案会很有趣。

尝试使用此选项会导致 Visual Studio 2013 在编译时挂起。 我没有包含测试用例，因为将其留给能够快速弄清楚界面的读者似乎是个好主意； 我不知道为什么这会在编译时挂起。 即使 const_iterator 等于 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

假设容器的 const_iterator 与其迭代器具有相同的布局（对于所有 STL 容器都是有效的假设），您可以简单地将前者位转换为后者：

#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 }
}