如何避免代码重复实现const和非const迭代器？

Question

我正在实现一个具有STL类接口的自定义容器.我必须提供一个常规迭代器和一个const迭代器.两个版本的迭代器的大多数代码都是相同的.我怎样才能避免这种重复？

例如,我的容器类是Foo,我正在实现FooIterator和FooConstIterator.两个迭代器都必须提供operator++()相同的方法.

我的问题类似于如何删除类似的const和非const成员函数之间的代码重复？但是那个问题的答案特定于const和非const方法,尤其是访问器.我没有看到这可能会如何推广到迭代器问题.

我应该FooIterator从FooConstIterator其他非const方法派生并扩展它吗？这要么导致虚拟方法或方法隐藏,这在这里似乎不合适.

也许FooIterator应该包含一个FooConstIterator.虽然这种方法确实减少了实现重复,但它似乎重新引入了许多样板方法定义.

是否有聪明的模板技术从单个定义生成两个迭代器？或许有一种方法 - 颤抖 - 使用预处理器来消除这些几乎相同的类.

我已经尝试查看我的本地STL实现,看看它是如何处理它的.有很多辅助类,我在设计中遇到了麻烦,但看起来功能很简单.

在以前的项目中,我的自定义容器是在标准STL容器之上构建的,所以我不必提供自己的迭代器.在这种情况下,这不是一个选项.

Answer 1

[不幸的是,最好的答案是由主持人删除,因为它只是一个链接答案.我理解为什么不鼓励仅限链接的答案; 但是,删除它会抢走未来寻求者非常有用的信息.该链接已保持稳定超过七年,并在撰写本文时继续有效.]

我强烈推荐Matt Austern 在2007年1月发表的题为"标准图书管理员:定义迭代器和常量迭代器"的原始Dr. Dobb's Journal文章.如果这个链接变坏,既然Dobb博士已经停止运行,它也可以在这里找到.

为了防止删除此替换答案,我将总结解决方案.

我们的想法是将迭代器作为一个模板实现一次,该模板需要一个额外的模板参数,一个布尔值表示这是否是const版本.在const和非const版本不同的实现中,您使用模板机制来选择正确的代码.Matt Austern的机制被称为choose.它看起来像这样:

template <bool flag, class IsTrue, class IsFalse>
struct choose;

template <class IsTrue, class IsFalse>
struct choose<true, IsTrue, IsFalse> {
   typedef IsTrue type;
};

template <class IsTrue, class IsFalse>
struct choose<false, IsTrue, IsFalse> {
   typedef IsFalse type;
};

如果你有const和非const迭代器的单独实现,那么const实现将包括这样的typedef:

typedef const T &reference;
typedef const T *pointer;

而非const实现将具有:

typedef T &reference;
typedef T *pointer;

但是choose,您可以使用基于额外模板参数选择的单个实现:

typedef typename choose<is_const, const T &, T &>::type reference;
typedef typename choose<is_const, const T *, T *>::type pointer;

通过对基础类型使用typedef,所有迭代器方法都可以具有相同的实现.请参阅Matt Austern的完整示例.

Answer 2

从C++ 11/14开始,您可以避免这样的小助手直接从布尔模板中推导出constness.

constness.h:

#ifndef ITERATOR_H
#define ITERATOR_H
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <iterator>

struct dummy_struct {
  int hello = 1;
  int world = 2;
  dummy_struct() : hello{ 0 }, world{ 1 }{ }
};

template< class T >
class iterable {
  public:
    template< bool Const = false >
    class my_iterator {
      public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        /* deduce const qualifier from bool Const parameter */
        using reference = typename std::conditional_t< Const, T const &, T & >;
        using pointer = typename std::conditional_t< Const, T const *, T * >;

      protected:
        pointer i;

      public:
        my_iterator( T* _i ) : i{ reinterpret_cast< pointer >( _i ) } { }

        /* SFINAE enables the const dereference operator or the non 
           const variant
           depending on bool Const parameter */          
        template< bool _Const = Const >
        std::enable_if_t< _Const, reference >
        operator*() const {
          std::cout << "Const operator*: ";
          return *i;
        }

        template< bool _Const = Const >
        std::enable_if_t< !_Const, reference >
        operator*() {
          std::cout << "Non-Const operator*: ";
          return *i; 
        }

        my_iterator & operator++() {
          ++i;
          return *this;
        }
        bool operator!=( my_iterator const & _other ) const {
          return i != _other.i;
        }

        bool operator==( my_iterator const & _other ) const {
          return !( *this != _other );
        }   
    };  



  private:
    T* __begin;
    T* __end; 
  public:
    explicit iterable( T* _begin, std::size_t _count ): __begin{ _begin }, __end{ _begin + _count } { std::cout << "End: " << __end << "\n"; }

    auto begin()  const { return my_iterator< false >{ __begin }; }
    auto end()    const { return my_iterator< false >{ __end }; }

    auto cbegin() const { return my_iterator< true >{ __begin }; }
    auto cend()   const { return my_iterator< true >{ __end }; }
};
#endif

这可以用于这样的事情:

#include <iostream>
#include <array>
#include "constness.h"

int main() {

  dummy_struct * data = new dummy_struct[ 5 ];
  for( int i = 0; i < 5; ++i ) {
    data[i].hello = i;
    data[i].world = i+1;
  } 
  iterable< dummy_struct > i( data, 5 );

  using iter = typename iterable< dummy_struct >::my_iterator< false >;
  using citer = typename iterable< dummy_struct >::my_iterator< true >;

  for( iter it = i.begin(); it != i.end(); ++it  ) {
    std::cout << "Hello: " << (*it).hello << "\n"
              << "World: " << (*it).world << "\n";
  }

  for( citer it = i.cbegin(); it != i.cend(); ++it  ) {
    std::cout << "Hello: " << (*it).hello << "\n"
              << "World: " << (*it).world << "\n";
  }
  delete[] data;

}