首页 文章

如何删除const_iterator的constness?

提问于
浏览
39

作为这个问题的延伸Are const_iterators faster?,我在 const_iterators 上有另一个问题 . 如何删除 const_iterator 的常量?虽然迭代器是指针的通用形式,但仍然是两个不同的东西 . 因此,我相信,我也不能使用 const_cast<>const_iterator 转换为 iterator .

一种方法可能是您定义一个迭代器,该迭代器将移动到 const_iterator 指向的元素 . 但这看起来像是一个线性时间算法 .

对于实现这一目标的最佳方法有什么想法吗?

9 回答

  • 64

    在C 11中有一个具有恒定时间复杂度的解决方案:对于任何序列,关联或无序关联容器(包括所有标准库容器),可以使用空范围调用范围擦除成员函数:

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

    范围擦除成员函数有一对 const_iterator 参数,但它们返回 iterator . 由于提供了空范围,因此对erase的调用不会更改容器的内容 .

    Hat tip to Howard Hinnant and Jon Kalb for this trick.

  • 3

    不幸的是,线性时间是唯一的方法:

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

    其中iter和constIter是合适的typedef,d是你要迭代的容器 .

  • 0

    在上一篇文章的答案中,有一些人,包括我在内,建议使用const_iterators代替非性能相关的原因 . 可读性,从设计板到代码的可追溯性......使用const_iterators提供对非const元素的变异访问比从不使用const_iterator要糟糕得多 . 您正在将代码转换为只有您才能理解的内容,设计更糟糕且可维护性更差 . 使用const只是为了抛弃它比使用const完全更糟糕 .

    如果你确定你想要它,那么C的好/坏部分就是你可以随时获得足够的绳索来吊死自己 . 如果你的意图是使用const_iterator来解决性能问题,你应该重新考虑它,但是如果你仍然想要开始射击......那么C可以提供你选择的武器 .

    首先,最简单的:如果你的操作将参数作为const(即使内部应用const_cast),我相信它应该在大多数实现中直接工作(即使它可能是未定义的行为) .

    如果你不能改变仿函数,那么你可以从任何一方解决问题:在const迭代器周围提供一个非const迭代器包装器,或者在非const仿函数周围提供一个const仿函数包装器 .

    Iteratorfaçade,漫长的道路:

    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
    };
    
  • 4

    这可能不是你想要的答案,但有些相关 .

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

    像这样的东西

    const_cast<T&>(*it);

  • 3

    Scott Meyer's article关于优先于const_iterators的迭代器可以解答这个问题 . Visage的答案是唯一安全的前C 11替代方案,但实际上是实现良好的随机访问迭代器的恒定时间,而其他人则是线性时间 .

  • 14

    我相信在精心设计的程序中不需要这种转换 .

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

    作为解决方法,您可以做下一步:

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

    但我认为有时这种转换是不可能的,因为你的算法无法访问容器 .

  • 2

    您可以从const_iterator中减去begin()迭代器以获取const_iterator指向的位置,然后将begin()添加回到该位置以获取非const迭代器 . 我不认为这对于非线性容器非常有效,但对于像线性容器这样的线性容器,这将需要恒定的时间 .

    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 :这似乎只适用于线性(随机访问)容器 .

  • 1

    你可以将你的const迭代器值指针转换为非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;
    
  • 0

    我认为提出一个适用于不在标准库中的容器并且不包含erase()方法的解决方案会很有趣 .

    尝试使用此选项会导致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
    

相关问题