C ++ итераторы и наследование - PullRequest
Новая
       11

C ++ итераторы и наследование

5 голосов
/ 07 июня 2010

У меня есть быстрый вопрос о том, как лучше всего реализовать итераторы в следующем:

Скажем, у меня есть шаблонный базовый класс "List" и два подкласса "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, но все становится довольно грязно, особенно когда вам нужно реализовать operator + в ListIterator.

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

Ответы [ 5 ]

5 голосов
/ 07 июня 2010

Если вам удастся сделать List<T>::iterator не виртуальным, то делегирование виртуальности из 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)); }
};
1 голос
/ 07 июня 2010

Среди итераторов есть нечто очень важное, называемое Iterator Category:

  • InputIterator
  • OutputIterator
  • ForwardIterator
  • BidirectionalIterator
  • RandomAccessIterator

Каждая категория определяет точный набор операций, которые эффективно поддерживаются итератором.

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

Я думаю, твой дизайн пахнет.

0 голосов
/ 07 июня 2010

Скажем, у меня есть шаблонный базовый класс "List" и два подкласса "ListImpl1" и "ListImpl2"

Что именно вы получаете, используя здесь наследование?

0 голосов
/ 07 июня 2010

Вы можете хранить operator + как частный виртуальный метод в базовом классе и вызывать его итератор.

В качестве альтернативы, вы можете рассмотреть статически полиморфные классы списков, а не полиморфизм во время выполнения.

0 голосов
/ 07 июня 2010

Так что проблема в том, что реализация итератора для 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_
};
...