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

Question

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

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

Мой вопрос аналогичен How do I remove code duplication between similar const and non-const member functions?, но ответ на этот вопрос специфичен для методов const и non-const, особенно для аксессуаров. Я не вижу, как это может быть обобщено на проблему итератора.

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

Возможно, FooIterator должно содержать FooConstIterator. Хотя этот подход уменьшает дублирование реализации, он, похоже, повторно вводит множество определений методов шаблонов.

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

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

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

Answer 1

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

Я настоятельно рекомендую оригинальную статью доктора Добба в журнале Мэтта Аустерна, озаглавленную "The Standard Librarian: Defining Iterators and Const Iterators", январь 2001 года. Если эта ссылка идет Плохо, теперь, когда доктор Добб прекратил работу, он также доступен here.

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

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

Если вы имели отдельные реализации для константных и неконстантных итераторов, то сопзЬ реализация будет включать определения типов, как это:

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; 

С помощью typedefs для базовых типов все методы итератора могут иметь идентичную реализацию. См. Мэтт Аустерн complete example.

Answer 2

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

Answer 3

Вы можете использовать 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 4

STL использует уделом

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