Адаптер итератора C ++, который оборачивает и скрывает внутренний итератор и преобразует итерированный тип

Question

Поиграв с этим, я подозреваю, что это невозможно, но я решил спросить экспертов. У меня есть следующий код C ++:

class IInterface
{
    virtual void SomeMethod() = 0;
};

class Object
{
    IInterface* GetInterface() { ... }
};

class Container
{
private:
    struct Item
    {
        Object* pObject;
        [... other members ...]
    };
    std::list<Item> m_items;
};

Я хочу добавить эти методы в контейнер:

    MagicIterator<IInterface*> Begin();
    MagicIterator<IInterface*> End();

Для того, чтобы звонившие могли написать:

Container c = [...]
for (MagicIterator<IInterface*> i = c.Begin(); i != c.End(); i++)
{
    IInterface* pItf = *i;
    [...]
}

Так что, по сути, я хочу предоставить класс, который, кажется, выполняет итерацию по некоторой коллекции (которую не могут видеть вызывающие объекты Begin () и End ()) указателей IInterface, но который фактически выполняет итерацию по коллекции указатели на другие объекты (частные для класса Container), которые можно преобразовать в указатели IInterface.

Несколько ключевых моментов:

• MagicIterator должно быть определено за пределами Container.
• Container::Item должен оставаться приватным.

• MagicIterator должен перебирать указатели IInterface, несмотря на то, что Container содержит std::list<Container::Item>. Container::Item содержит Object*, а Object может использоваться для получения IInterface*.

• MagicIterator необходимо многократно использовать с несколькими классами, которые похожи на Container, но могут внутренне иметь разные реализации списка, содержащие разные объекты (std::vector<SomeOtherItem>, mylist<YetAnotherItem>) и с IInterface*, полученными каждый раз по-разному.

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

• Решение должно компилироваться под Visual C ++ без использования других библиотек (например, boost), для чего потребуется лицензионное соглашение от их авторов.

• Кроме того, итерация не может выделять какую-либо кучу памяти (поэтому на всех этапах нет new() или malloc()) и memcpy().

Спасибо за ваше время, даже если вы просто читаете; этот действительно давал мне покоя!

Обновление: Хотя у меня были очень интересные ответы, ни один из них еще не удовлетворял всем вышеуказанным требованиям. Примечательно, что хитрыми областями являются: i) каким-то образом отключение MagicIterator от Container (аргументы шаблона по умолчанию не обрезают его) и ii) избегание выделения кучи; но я действительно ищу решение, которое охватывает все вышеперечисленные пули.

Answer 1

Я думаю, что у вас есть две отдельные проблемы здесь:

Сначала создайте итератор, который будет возвращать IInterface* из вашего list<Container::Item>. Это легко сделать с помощью boost::iterator_adaptor:

class cont_iter
  : public boost::iterator_adaptor<
        cont_iter                       // Derived
      , std::list<Container::Item>::iterator // Base
      , IInterface*                     // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
      , IInterface*                     // Reference :)
    >
{
 public:
    cont_iter()
      : cont_iter::iterator_adaptor_() {}

    explicit cont_iter(const cont_iter::iterator_adaptor_::base_type& p)
      : cont_iter::iterator_adaptor_(p) {}

 private:
    friend class boost::iterator_core_access;
    IInterface* dereference() { return this->base()->pObject->GetInterface(); }
};

Вы бы создали этот тип как внутренний в Container и вернули бы его методы begin() и end().

Во-вторых, вам нужна полиморфная среда выполнения MagicIterator. Это именно то, что делает any_iterator. MagicIterator<IInterface*> это просто any_iterator<IInterface*, boost::forward_traversal_tag, IInterface*>, и ему можно просто присвоить cont_iter.

Answer 2

Звучит не слишком сложно. Вы можете определить итератор снаружи. Вы также можете использовать typedefs. Нечто подобное подойдет, я думаю. Обратите внимание, что было бы намного чище, если бы MagicIterator был не бесплатным шаблоном, а элементом Item, возможно, с определением типа в контейнере. Как сейчас, в нем есть циклическая ссылка, что делает необходимым написание какого-то уродливого обходного кода.

namespace detail {
    template<typename T, typename U>
    struct constify;

    template<typename T, typename U>
    struct constify<T*, U*> {
        typedef T * type;
    };

    template<typename T, typename U>
    struct constify<T*, U const*> {
        typedef T const * type;
    };
}

template<typename DstType, 
         typename Container,
         typename InputIterator>
struct MagicIterator;

class Container
{
private:
    struct Item
    {
        Object* pObject;
    };

    std::list<Item> m_items;

public:

    // required by every Container for the iterator
    typedef std::list<Item> iterator;
    typedef std::list<Item> const_iterator;

    // convenience declarations
    typedef MagicIterator< IInterface*, Container, iterator > 
        item_iterator;
    typedef MagicIterator< IInterface*, Container, const_iterator > 
        const_item_iterator;

    item_iterator Begin();
    item_iterator End();
};

template<typename DstType, 
         typename Container = Container,
         typename InputIterator = typename Container::iterator>
struct MagicIterator : 
    // pick either const T or T, depending on whether it's a const_iterator.
    std::iterator<std::input_iterator_tag, 
                  typename detail::constify<
                           DstType, 
                           typename InputIterator::value_type*>::type> {
    typedef std::iterator<std::input_iterator_tag, 
                 typename detail::constify<
                          DstType, 
                          typename InputIterator::value_type*>::type> base;
    MagicIterator():wrapped() { }
    explicit MagicIterator(InputIterator const& it):wrapped(it) { }
    MagicIterator(MagicIterator const& that):wrapped(that.wrapped) { }

    typename base::value_type operator*() {
        return (*wrapped).pObject->GetInterface();
    }

    MagicIterator& operator++() {
        ++wrapped;
        return *this;
    }

    MagicIterator operator++(int) {
        MagicIterator it(*this);
        wrapped++;
        return it;
    }

    bool operator==(MagicIterator const& it) const {
        return it.wrapped == wrapped;
    }

    bool operator!=(MagicIterator const& it) const {
        return !(*this == it);
    }

    InputIterator wrapped;
};

// now that the iterator adepter is defined, we can define Begin and End
inline Container::item_iterator Container::Begin() {
    return item_iterator(m_items.begin());
}

inline Container::item_iterator Container::End() {
    return item_iterator(m_items.end());
}

Теперь начните использовать его:

for(MagicIterator<IInterface*> it = c.Begin(); it != c.End(); ++it) {
    // ...
}

Вы также можете использовать миксин итератора, предоставляемый boost, который работает как входная версия boost :: function_output_iterator. Он вызывает ваш итератор operator(), который затем возвращает соответствующее значение, делая то, что мы делаем выше в нашем operator* в принципе. Вы найдете это в random/detail/iterator_mixin.hpp. Это, вероятно, приведет к уменьшению кода. Но это также требует, чтобы нам пришлось позаботиться о дружбе, потому что Item является приватным, а итератор не определен внутри Item. В любом случае, удачи:)

Answer 3

Создать реферат IteratorImplementation класс:

template<typename T>
class IteratorImplementation
{
    public:
        virtual ~IteratorImplementation() = 0;

        virtual T &operator*() = 0;
        virtual const T &operator*() const = 0;

        virtual Iterator<T> &operator++() = 0;
        virtual Iterator<T> &operator--() = 0;
};

И класс Iterator, чтобы обернуть его вокруг:

template<typename T>
class Iterator
{
    public:
        Iterator(IteratorImplementation<T> * = 0);
        ~Iterator();

        T &operator*();
        const T &operator*() const;

        Iterator<T> &operator++();
        Iterator<T> &operator--();

    private:
        IteratorImplementation<T> *i;
}

Iterator::Iterator(IteratorImplementation<T> *impl) :
    i(impl)
{
}

Iterator::~Iterator()
{
    delete i;
}

T &Iterator::operator*()
{
    if(!impl)
    {
        // Throw exception if you please.
        return;
    }

    return (*impl)();
}

// etc.

(Вы можете сделать IteratorImplementation классом "изнутри" Iterator, чтобы держать вещи в порядке.)

В вашем классе Container верните экземпляр Iterator с пользовательским подклассом IteratorImplementation в ctor:

class ObjectContainer
{
    public:
        void insert(Object *o);
        // ...

        Iterator<Object *> begin();
        Iterator<Object *> end();

    private:
        class CustomIteratorImplementation :
            public IteratorImplementation<Object *>
        {
            public:
                // Re-implement stuff here.
        }
};

Iterator<Object *> ObjectContainer::begin()
{
    CustomIteratorImplementation *impl = new CustomIteratorImplementation();  // Wish we had C++0x's "var" here.  ;P

    return Iterator<Object *>(impl);
}

Answer 4

Это действительно зависит от Container, потому что возвращаемые значения c.Begin() и c.End() определяются реализацией.

Если MagicIterator известен список Container с, можно использовать класс-обертку.

template<typename T>
class MagicIterator
{
    public:
        MagicIterator(std::vector<T>::const_iterator i)
        {
            vector_const_iterator = i;
        }

        // Reimplement similarly for more types.
        MagicIterator(std::vector<T>::iterator i);
        MagicIterator(std::list<T>::const_iterator i);
        MagicIterator(std::list<T>::iterator i);

        // Reimplement operators here...

    private:
        std::vector<T>::const_iterator vector_const_iterator;
        std::vector<T>::iterator       vector_iterator;
        std::list<T>::const_iterator   list_const_iterator;
        std::list<T>::iterator         list_iterator;
};

Способ easy заключается в использовании шаблона, который принимает тип Container:

// C++0x
template<typename T>
class Iterator :
    public T::iterator
{
    using T::iterator::iterator;
};

for(Iterator<Container> i = c.begin(); i != c.end(); ++i)
{
    // ...
}

Больше информации здесь.

Answer 5

Я не вижу причин, почему вы не можете реализовать это именно так, как выложили ... Я что-то упустил?

Чтобы уточнить, вам нужно добавить некоторые методы доступа в ваш класс Container. Они могут быть приватными, и вы можете объявить MagicIterator своим другом, если считаете, что это лучший способ его инкапсулировать, но я бы раскрыл их напрямую. Эти методы доступа используют обычный итератор STL внутри контейнера и выполняют преобразование в IInterface. Таким образом, итерация будет фактически выполняться с помощью методов доступа Контейнера, а MagicIterator будет просто своего рода прокси-объектом, чтобы упростить его. Чтобы сделать его реентерабельным, вы могли бы передать MagicIterator какой-то идентификатор для поиска итератора STL внутри контейнера, или вы могли бы фактически передать его в итераторе STL как void *.

Answer 6

Посетитель может быть более простым (и, следовательно, более простым в обслуживании) решением.

Answer 7

Я нашел решение, которое подходит для моей первоначальной цели. Я все еще не люблю это хотя:)

Решение заключается в том, что MagicIterator шаблонируется на IInterface * и создается с использованием итератора void *, размера байта указанного итератора и таблицы указателей на функции, которые выполняют стандартные функции итерации для указанного void *, такие как приращение , декремент, разыменование и т. д. MagicIterator предполагает, что безопасно записать данный итератор во внутренний буфер, и реализует свои собственные члены, передавая свой собственный буфер как пустоту * в предоставленные функции, как если бы это был исходный итератор.

Затем контейнер должен реализовать статические итерационные функции, которые возвращают предоставленный void * в std :: list :: iterator. Container :: begin () и Container :: end () просто создают std :: list :: iterator, передают указатель на него в MagicIterator вместе с таблицей его итерационных функций и возвращают MagicIterator.

Это несколько отвратительно и нарушает мое первоначальное правило относительно "no memcpy ()", и делает предположения о внутренностях рассматриваемых итераторов. Но он избегает выделения кучи, сохраняет внутреннее содержимое коллекции (включая Item) закрытым, делает MagicIterator полностью независимым от рассматриваемой коллекции и IInterface * и теоретически позволяет MagicIterator работать с любой коллекцией (при условии, что его итераторы могут быть безопасно memcopy () г).