Как избежать дублирования кода, реализующего константные и неконстантные итераторы?

Question

Я реализую пользовательский контейнер с STL-подобным интерфейсом. Я должен предоставить обычный итератор и константный итератор. Большая часть кода для двух версий итераторов идентична. Как я могу избежать этого дублирования?

Например, мой контейнерный класс Foo, и я реализую FooIterator и FooConstIterator. Оба итератора должны предоставлять методы, подобные operator++(), которые идентичны.

Мой вопрос похож на Как убрать дублирование кода между похожими константными и неконстантными функциями-членами? , но ответ на этот вопрос специфичен для константных и неконстантных методов, особенно методов доступа. Я не понимаю, как это может обобщить проблему итератора.

Должен ли я FooIterator наследовать от FooConstIterator и расширять его дополнительными неконстантными методами? Это приводит либо к виртуальным методам, либо к скрытию методов, которые здесь неуместны.

Возможно, FooIterator должен содержать FooConstIterator. Несмотря на то, что такой подход сокращает дублирование реализации, он, похоже, повторно вводит множество стандартных определений методов.

Есть ли хитрый шаблонный метод для генерации двух итераторов из одного определения? Или, возможно, есть способ - вздрогнуть - использовать препроцессор для удаления этих почти идентичных классов.

Я попытался посмотреть на мою локальную реализацию STL, чтобы увидеть, как она справляется с этим. Есть так много вспомогательных классов, что у меня возникают проблемы с дизайном, но похоже, что функциональность просто дублируется.

В предыдущих проектах мой пользовательский контейнер создавался поверх стандартного контейнера STL, поэтому мне не нужно было предоставлять собственные итераторы. Это не вариант в этом случае.

Answer 1

[Лучший ответ, к сожалению, был удален модератором, потому что это был ответ только по ссылке. Я понимаю, почему ответы только на ссылки не рекомендуются; однако его удаление лишило будущих искателей очень полезной информации. Ссылка оставалась стабильной в течение более семи лет и продолжает работать на момент написания этой статьи.]

Я настоятельно рекомендую оригинальную статью доктора Добба в журнале Мэтта Остерна, озаглавленную «Стандартный библиотекарь: определение итераторов и константных итераторов» , январь 2001 г. Если эта ссылка испортится, теперь, когда у доктора Добба есть перестал работать, он также доступен здесь .

Чтобы не допустить удаления этого замещающего ответа, я кратко изложу решение.

Идея состоит в том, чтобы реализовать итератор один раз в качестве шаблона, который принимает дополнительный параметр шаблона, логическое значение, указывающее, является ли это константной версией. Везде, где реализация отличается от константной и неконстантной версий, вы используете шаблонный механизм для выбора правильного кода. Механизм Мэтта Остерна назывался 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 включала бы определения типа, подобные этому:

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

и неконстантная реализация будет иметь:

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 для базовых типов все методы итератора могут иметь одинаковую реализацию. См. полный пример Мэтта Остерна .

Answer 2

Начиная с C ++ 11/14, вы можете избежать таких маленьких помощников и вывести константу непосредственно из логического шаблона.

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;

}

Answer 3

STL использует наследование

template<class _Myvec>
    class _Vector_iterator
        : public _Vector_const_iterator<_Myvec>

Answer 4

В дополнение к предложению о том, что вы можете шаблонизировать константу и неконстантность, вы также можете уменьшить объем работы, взглянув на Boost.Iterator, учебник - в котором также упоминается то же решение.

Answer 5

Вы можете использовать CRTP и общую базу для «внедрения» методов (но вам все равно придется дублировать ctors в текущем C ++) или просто использовать препроцессор (не требуется дрожание; легко обрабатывает ctors):

struct Container {

#define G(This) \
This operator++(int) { This copy (*this); ++*this; return copy; }
// example of postfix++ delegating to ++prefix

  struct iterator : std::iterator<...> {
    iterator& operator++();
    G(iterator)
  };
  struct const_iterator : std::iterator<...> {
    const_iterator& operator++();
    G(const_iterator)
  };

#undef G
// G is "nicely" scoped and treated as an implementation detail
};

Используйте std :: iterator, typedefs, которые он вам дает, и любые другие typedefs, которые вы можете предоставить, чтобы сделать макрос простым.

Answer 6

Arthor O'Dwyer подробно отвечает на это в своем блоге: https://quuxplusone.github.io/blog/2018/12/01/const-iterator-antipatterns/

По сути,

template<bool IsConst>
class MyIterator {
    int *d_;
public:
    MyIterator(const MyIterator&) = default;  // REDUNDANT BUT GOOD STYLE

    template<bool IsConst_ = IsConst, class = std::enable_if_t<IsConst_>>
    MyIterator(const MyIterator<false>& rhs) : d_(rhs.d_) {}  // OK
};
using Iterator = MyIterator<false>;
using ConstIterator = MyIterator<true>;
};

Кроме того, добавьте static_assert(std::is_trivially_copy_constructible_v<ConstIterator>); в свой код, чтобы убедиться, что ваши итераторы остаются тривиально копируемыми:

Вывод: если вы реализуете свои собственные итераторы контейнеров - или любую другую пару типов с этим поведением «одностороннего неявного преобразования», например const_buffers_type и mutable_buffers_type TS, то вам следует использовать один из приведенных выше шаблонов реализовать конвертирующие конструкторы без случайного отключения тривиального копирования .