Интерфейсы и проблема ковариации - PullRequest
7 голосов
/ 08 августа 2011

У меня есть определенный класс, который хранит часть данных, которая реализует интерфейс:

template<typename T>
class MyContainer : public Container<T> {
    class Something : public IInterface {
    public:
        // implement *, ->, and ++ here but how?
    private:
        T x;
    };

    // implement begin and end here, but how?

private:
    Something* data; // data holds the array of Somethings so that references to them can be returned from begin() and end() to items in this array so the interface will work, but this makes the problem described below
};

И у меня есть массив Something с.

У меня есть потребность в Something для реализации класса интерфейса (IInterface в примере), который:

  1. Содержит чисто виртуальные функции-члены, которые возвращают что-то такое, что *retval возвращает ссылку на x член, retval-> возвращает адрес x, а ++retval заставляет retval обращаться к следующему Something в массиве.
  2. Вещи, которые возвращают чисто виртуальные члены, могут наследоваться и возвращаться реализацией членов
  3. container[i] (где container - массив, содержащий объекты Something) всегда возвращает что-то такое, что *retval всегда возвращает ссылку на один и тот же T для того же i.

Прямо сейчас интерфейс выглядит так:

template<typename T>
class Container {
    class IInterface {
    public:
        virtual T& operator*() = 0;
        virtual T* operator->() = 0;
        virtual IInterface& operator++(); // this is the problem 
    };

    // returning a reference right now to support covariance, so subclasses can
    // derive from Container and then have a member class derive from IInterface
    // and override these to return their derived class, but this has a problem
    virtual IInterface& begin() = 0;
    virtual IInterface& end() = 0;
};

Мое текущее решение (пусть виртуальные методы возвращают IInterface& и возвращают Something& в реализации) не имеет проблем с требованиями, за исключением для требования ++retval. Поскольку Something напрямую связан с объектом, который он содержит, и не может указывать на T с указателем, я не могу найти способ получить ++, чтобы заставить переменную ссылаться на следующую Something в массиве.

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

Цель этой настройки состоит в том, чтобы можно было написать функции, которые принимают Container& и выполняют итерацию контейнера, не зная, какой это тип контейнера:

void iterate(Container<int>& somecontainer) {
    Container<int>::IIterator i = somecontainer.begin(); // right now this would return a reference, but it doesn't/can't work that way
    while (i != somecontainer.end()) {
         doSomething(*i);
         ++i; // this is the problem
    }
}

Мне сложно описать, не стесняйтесь, дайте мне знать, если вам нужна дополнительная информация.

Ответы [ 5 ]

7 голосов
/ 08 августа 2011

То, что вы пытаетесь сделать, называется тип стирания .По сути, вы хотите предоставить тип значения (который одинаков во всей иерархии наследования), который охватывает конкретный тип итератора и предлагает единый динамический интерфейс.

Стирание типа обычно реализуется с помощью невиртуального класса (тип стерты ), в котором хранится указатель на виртуальный базовый класс, который реализует стирание , из которого вы получаете различные типы, которые переносятсякаждый конкретный итератор.Статический класс будет предлагать шаблонные операторы конструктора / присваивания, которые динамически будут создавать экземпляр объекта производного типа и хранить указатель внутри.Тогда вам нужно только реализовать набор операций как отправку внутреннему объекту.

Для самой простой формы стирания типов вы можете взглянуть на реализацию boost::any (документация здесь )

Эскиз:

namespace detail {
   template<typename T>
   struct any_iterator_base {
      virtual T* operator->() = 0;    // Correct implementation of operator-> is tough!
      virtual T& operator*() = 0;
      virtual any_iterator_base& operator++() = 0;
   };
   template <typename T, typename Iterator>
   class any_iterator_impl : any_iterator_base {
      Iterator it;
   public:
      any_iterator_impl( Iterator it ) : it(it) {}
      virtual T& operator*() {
         return *it;
      }
      any_iterator_impl& operator++() {
         ++it;
         return *this;
      }
   };
}
template <typename T>
class any_iterator {
   detail::any_iterator_base<T>* it;
public:
   template <typename Iterator>
   any_iterator( Iterator it ) : it( new detail::any_iterator_impl<T,Iterator>(it) ) {}
   ~any_iterator() {
      delete it;
   }
   // implement other constructors, including copy construction
   // implement assignment!!! (Rule of the Three)
   T& operator*() {
      return *it;   // virtual dispatch
   }
};

Реальная реализация становится действительно грязной.Вам необходимо предоставить разные версии итератора для разных типов итераторов в стандарте, и детали реализации операторов также могут быть не тривиальными.В частности, operator-> применяется итеративно, пока не будет получен необработанный указатель, и вы хотите убедиться, что ваше стертое поведение типа не нарушает этот инвариант или не документирует, как вы его нарушаете (т.е. ограничения на тип T, которые может использовать ваш адаптерwrap)

Для расширенного чтения: - О напряженности между объектно-ориентированным и общим программированием в C ++ - any_iterator: Реализация Erasure для итераторов C ++ - adobeany_iterator ,

2 голосов
/ 08 августа 2011

Я бы посоветовал взглянуть на шаблон Visitor.

Помимо этого, вам нужен тип значения, который будет наполнен полиморфным поведением.Существует гораздо более простое решение, чем использование Джеймсом вашего IInterface.

class IInterface
{
  virtual ~IInterface() {}
  virtual void next() = 0;
  virtual void previous() = 0;
  virtual T* pointer() const = 0;

  virtual std::unique_ptr<IInterface> clone() const = 0;
};

std::unique_ptr<IInterface> clone(std::unique_ptr<IInterface> const& rhs) {
  if (!rhs) { return std::unique_ptr<IInterface>(); }
  return rhs->clone();
}

class Iterator
{
  friend class Container;
public:
  Iterator(): _impl() {}

  // Implement deep copy
  Iterator(Iterator const& rhs): _impl(clone(rhs._impl)) {}
  Iterator& operator=(Iterator rhs) { swap(*this, rhs); return *this; }

  friend void swap(Iterator& lhs, Iterator& rhs) {
    swap(lhs._impl, rhs._impl);
  }

  Iterator& operator++() { assert(_impl); _impl->next(); return *this; }
  Iterator& operator--() { assert(_impl); _impl->previous(); return *this; }
  Iterator operator++(int); // usual
  Iterator operator--(int); // usual

  T* operator->() const { assert(_impl); return _impl->pointer(); }
  T& operator*() const { assert(_impl); return *_impl->pointer(); }

private:
  Iterator(std::unique_ptr<IInterface> impl): _impl(impl) {}
  std::unique_ptr<IInterface> _impl;
};

И, наконец, класс Container предложит:

protected:
  virtual std::unique_ptr<IInterface> make_begin() = 0;
  virtual std::unique_ptr<IInterface> make_end() = 0;

И реализует:

public:
  Iterator begin() { return Iterator(make_begin()); }
  Iteraotr end() { return Iterator(make_end()); }

Примечание:

Вы можете покончить с std::unique_ptr, если сможете избежать проблемы с владением.Если вы можете ограничить интерфейс II только поведенческим (путем извлечения состояния в Iterator), то вы можете использовать шаблон Strategy и использовать указатель для статически размещенного объекта.Таким образом, вы избегаете динамического выделения памяти.

Конечно, это означает, что ваши итераторы не будут настолько богатыми, так как для реализации без состояния требуется IInterface реализация и реализация «фильтрующих» итераторов, например, станет невозможным.

1 голос
/ 08 августа 2011

Задумывались ли вы об использовании CRTP . Я считаю это хорошим кандидатом здесь. Вот краткое демо . Это просто объясняет вашу ++retval проблему (если я правильно понял). Вы должны изменить определение IInterface с pure virtual на интерфейс типа CRTP.

template<class Derived>
struct IInterface
{
  Derived& operator ++ ()
  {
    return ++ *(static_cast<Derived*>(this));
  }
};

struct Something : public IInterface<Something>
{
  int x;
  Something& operator ++ ()
  {
    ++x;
    return *this;
  }
};

Есть некоторые ограничения CRTP, что template всегда будет следовать за вашим IInterface. Это означает, что если вы передаете объект Something функции, подобной этой:

foo(new Something);

Тогда foo() следует определить как:

template<typename T>
void foo(IInterface<T> *p)
{
  //...
  ++(*p);
}

Однако для вашей проблемы это может подойти.

1 голос
/ 08 августа 2011

Как вы сказали, проблема в том, что экземпляры Something привязаны к объекту, который он содержит. Итак, давайте попробуем развязать их.

Ключевым моментом, который следует помнить, является то, что в ООП общедоступные неконстантные члены данных обычно не одобряются. В вашей текущей реализации каждый экземпляр Something связан с наличием элемента данных T x, который является общедоступным. Вместо этого лучше сделать абстракцию, т.е. вместо этого предоставить методы доступа:

class Something : IInterface
{
private:
    T x;

public:
    T GetX()
    {
        return x;
    }
};

Теперь пользователь знает, что это за вещь x, тем более, что существует x.

Это хороший первый шаг, однако, поскольку вы хотите, чтобы x ссылался на разные объекты в разное время, нам в значительной степени потребуется сделать x указателем. И в качестве уступки обычному коду, мы также заставим GetX() возвращать константную ссылку, а не обычное значение:

class Something: IInterface
{
private:
    T *x;

public:
    T const& GetX()
    {
        return *x;
    }
};

Теперь реализовать методы в IInterface тривиально:

class Something: IInterface
{
private:
   T *x;

public:
    T const& GetX()
    {
        return *x;
    }

    T& operator*()
    {
        return *x;
    }

    T* operator->()
    {
        return x;
    }

    Something& operator++()
    {
        ++x;
        return *this;
    }
};

Оператор ++ теперь тривиален - он действительно просто применяет ++ к x.

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

Редактировать

Что касается реализации begin и end методов Container, это также не должно быть слишком сложным, но потребует некоторых изменений Container.

Прежде всего, давайте добавим приватный конструктор к Something, который принимает указатель на начальный объект. Мы также сделаем MyContainer другом Something:

класс Something: IInterface {

    friend class MyContainer; // Can't test the code right now - may need to be MyContainer<T> or ::MyContainer<T> or something.

private:
   T *x;

    Something( T * first )
    : x(first)
    {
    }

public:

    T const& GetX()
    {
        return *x;
    }

    T& operator*()
    {
        return *x;
    }

    T* operator->()
    {
        return x;
    }

    Something& operator++()
    {
        ++x;
        return *this;
    }
};

Делая конструктор приватным и устанавливая зависимость от друга, мы гарантируем, что только MyContainer может создавать новые Something итераторов (это защищает нас от перебора по случайной памяти, если пользователь дал что-то ошибочное) .

Далее мы немного изменим MyContainer, чтобы вместо массива Something у нас был просто массив T:

class MyContainer
{
    ...
private:

    T *data;

};

Прежде чем мы перейдем к реализации begin и end, давайте внесем это изменение в Container, о котором я говорил:

template<typename T, typename IteratorType>
class Container {
public:
    ...
    // These prototype are the key. Notice the return type is IteratorType (value, not reference)
    virtual IteratorType begin() = 0;
    virtual IteratorType end() = 0;
};

Таким образом, вместо того, чтобы полагаться на ковариацию (которая в данном случае будет действительно трудной), мы используем небольшую магию шаблонов, чтобы делать то, что мы хотим.

Конечно, поскольку Container теперь принимает другой параметр типа, нам нужно соответствующее изменение на MyContainer; а именно нам нужно предоставить Something в качестве параметра типа для Container:

template<class T>
class MyContainer : Container<T, Something>
...

И методы begin / end теперь просты:

template<class T>
MyContainer<T>::begin()
{
    return Something(data);
}

template<class T>
MyContainer<T>::end()
{
    // this part depends on your implementation of MyContainer.
    // I'll just assume your have a length field in MyContainer.
    return Something(data + length);
}

Итак, это то, что у меня есть для размышлений в полночь. Как я уже упоминал выше, в настоящее время я не могу протестировать этот код, поэтому вам, возможно, придется немного его настроить. Надеюсь, это делает то, что вы хотите.

0 голосов
/ 08 августа 2011

Если предполагается, что использование похоже на stdlib, итератор должен быть объектом значения, потому что он обычно копируется по значению. (Кроме того, в противном случае, на что бы методы begin и end возвращали ссылку?)

template <class T>
class Iterator
{
    shared_ptr<IIterator> it;
public:
    Iterator(shared_ptr<IIterator>);
    T& operator*() { it->deref(); }
    T* operator->() { return &it->deref(); }
    Iterator& operator++() { it->inc(); return *this; }
    etc.
};
...