Итераторы C++ и наследование
Имейте быстрый вопрос о том, что было бы лучшим способом реализовать итераторы в следующем:
Скажите, что у меня есть шаблонный базовый класс 'Список' и два подкласса "ListImpl1" и "ListImpl2". Основное требование базового класса должно быть повторяемым, т.е. Я могу сделать:
for(List<T>::iterator it = list->begin(); it != list->end(); it++){
...
}
Я также хочу позволить дополнение итератора, например:
for(List<T>::iterator it = list->begin()+5; it != list->end(); it++){
...
}
Таким образом, проблема состоит в том, что реализация итератора для ListImpl1 будет отличаться от этого для ListImpl2. Я обошел это при помощи обертки ListIterator, содержащий указатель на ListIteratorImpl с подклассами ListIteratorImpl2 и ListIteratorImpl2, но это все становится довольно грязным, особенно когда необходимо реализовать оператор + в ListIterator.
Какие-либо мысли о лучшем дизайне для обхождения этих проблем?
5 ответов
Если вы можете обойтись без того, чтобы сделать List невиртуальным, то делегирование виртуальности от add к List упрощает ситуацию:
template<typename T>
class List
{
virtual void add_assign(iterator& left, int right) = 0;
public:
class iterator
{
const List* list;
const T* item;
public:
iterator(const List* list, const T* item) : list(list), item(item) {}
iterator& operator +=(int right)
{
list->add_assign(*this, right);
return *this;
}
static iterator operator +(iterator const& left, int right)
{
iterator result = left;
result += right;
return result;
}
};
virtual iterator begin() const = 0;
virtual iterator end() const = 0;
};
В противном случае (если итераторы должны хранить существенно разные данные, например), вам придется сделать обычную, скучную реализацию указателя для получения виртуальности:
template<typename T>
class List
{
class ItImpl
{
virtual ItImpl* clone() = 0;
virtual void increment() = 0;
virtual void add(int right) = 0;
};
public:
class iterator
{
ItImpl* impl;
public:
// Boring memory management stuff.
iterator() : impl() {}
iterator(ItImpl* impl) : impl(impl) {}
iterator(iterator const& right) : impl(right.impl->clone()) {}
~iterator() { delete impl; }
iterator& operator=(iterator const& right)
{
delete impl;
impl = right.impl->clone();
return *this;
}
// forward operators to virtual calls through impl.
iterator& operator+=(int right)
{
impl->add(right);
return *this;
}
iterator& operator++()
{
impl->increment();
return *this;
}
};
};
template<typename T>
static List<T>::iterator operator+(List<T>::iterator const& left, int right)
{
List<T>::iterator result = left;
result += right;
return result;
}
template<typename T>
class MagicList : public List<T>
{
class MagicItImpl : public ItImpl
{
const MagicList* list;
const magic* the_magic;
// implement ...
};
public:
iterator begin() const { return iterator(new MagicItImpl(this, begin_magic)); }
iterator end() const { return iterator(new MagicItImpl(this, end_magic)); }
};
Итак, проблема в том, что реализация итератора для ListImpl1 будет отличаться от этого для ListImpl2. Я обошел это используя оболочку ListIterator содержащий указатель на ListIteratorImpl с подклассами ListIteratorImpl2 и ListIteratorImpl2, но это все становится довольно грязным, особенно когда вам нужно реализовать оператор + в ListIterator.
Этот дизайн хорош ИМХО, я не вижу в нем ничего путного. За исключением равенства и вычитания, операции итератора могут быть довольно легко реализованы виртуальной функцией, поэтому у вас будет что-то вроде
class ListIteratorInterface // abstract
{
protected:
virtual Data& operator*()=0;
// and other operations
};
class ListIteratorA;
class ListIteratorB; // implementation of the above
class ListIterator
{
ListIteratorInterface* impl_;
public:
// when you create this, allocate impl_ on the heap
// operations, forward anything to impl_
};
Среди итераторов есть нечто очень важное, называемое категорией итератора:
- InputIterator
- OutputIterator
- ForwardIterator
- BidirectionalIterator
- RandomAccessIterator
Каждая категория определяет точный набор операций, которые эффективно поддерживаются итератором.
Здесь, похоже, вы хотите отказаться от этого мощного механизма идентификации, чтобы создать некую ублюдочную категорию, в которой все операции присутствуют, но не гарантируется их эффективность.
Я думаю, что ваша конструкция попахивает.
Допустим, у меня есть шаблонный базовый класс List и два подкласса ListImpl1 и ListImpl2
Что именно вы получаете, используя здесь наследование?
Вы можете хранить operator+ как частный виртуальный метод в базовом классе, и пусть итератор вызывает его.
В качестве альтернативы можно рассмотреть статически полиморфные классы списков, а не полиморфизм во время выполнения.