Ein C ++ Iterator-Adapter, die Packungen und verbirgt eine innere Iterator und wandelt den iterierten Typen

Question

Nachdem mit diesem toyed ich vermute, dass es nicht aus der Ferne möglich ist, aber ich dachte, dass ich die Experten fragen würde. Ich habe den folgenden C ++ Code:

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

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

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

Ich möchte diese Methoden Container hinzuzufügen:

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

Damit Anrufer schreiben:

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

So im Wesentlichen möchte ich eine Klasse schaffen, das Iterieren über eine gewisse Sammlung zu sein scheint (was der Anrufer von Begin () und End () nicht sehen darf) von IInterface Zeigern, aber das ist eigentlich iteriert über eine Sammlung von Zeiger auf andere Objekte (privat an die Container-Klasse), die in IInterface Zeiger umgewandelt werden können.

Ein paar wichtige Punkte:

• MagicIterator ist außerhalb Container definiert werden.
• Container::Item muss privat bleiben.

• MagicIterator hat iterieren IInterface Zeiger, trotz der Tatsache, dass Container eine std::list<Container::Item> hält. Container::Item enthält eine Object* und Object kann verwendet werden IInterface* zu holen.

• MagicIterator hat mit mehreren Klassen wiederverwendbar sein, die Container ähneln, aber vielleicht hat intern andere Liste Implementierungen halten verschiedene Objekte (std::vector<SomeOtherItem>, mylist<YetAnotherItem>) und mit IInterface* in einer anderen Weise jedes Mal erhalten.

• MagicIterator sollte nicht Container-spezifischen Code enthalten, obwohl es an Klassen delegieren können, die Sie, sofern eine solche Übertragung nicht schwer zu besonderen Behälter innerhalb MagicIterator codiert (also irgendwie automatisch durch den Compiler behoben wird, zum Beispiel).

• Die Lösung muss unter Visual C ++ kompilieren, ohne Verwendung anderer Bibliotheken (wie Boost), die eine Lizenzvereinbarung von ihren Autoren erfordern würde.

• Auch Iteration alle Heap-Speicher nicht zuordnen kann (also keine new() oder malloc() in jeder Phase), und keine memcpy().

Vielen Dank für Ihre Zeit, auch wenn Sie gerade lesen; Dieser ist wirklich mich worden nervt!

Update: Während ich einige sehr interessante Antworten habe, noch keiner alle oben genannten Voraussetzungen erfüllt sind. Bemerkenswert ist die heikelen Bereiche sind i MagicIterator von Containern Entkopplung) irgendwie (Standardvorlage Argumente schneiden Sie es nicht), und ii) die Vermeidung Zu; aber ich bin wirklich nach einer Lösung, die alle oben genannten Kugeln abdeckt.

Answer 1

Ich habe nun eine Lösung gefunden, die fitter für meinen ursprünglichen Zweck ist. Ich glaube nicht, es immer noch gerne aber:)

Die Lösung beinhaltet MagicIterator * auf IInterface Templat ist und mit einem void * beide an einen Iterator aufgebaut ist, wobei die Byte-Größe des Iterators, und eine Tabelle von Zeigern auf Funktionen, die auf Standard-Iteration Funktionen ausführen genannte void * wie Inkrement , Abnahme, dereferenzieren usw. MagicIterator geht davon aus, dass es sicher ist, die gegebene Iterator in einen internen Puffer mEMCPY und implementiert ihre eigenen Mitglieder durch einen eigenen Puffer als void * zu den mitgelieferten Funktionen vorbei, als ob es das Original Iterator war.

Container dann statische Iteration Funktionen zu implementieren haben, die zu einem std :: list :: iterator ein geliefertes void * zurückgeworfen. Container :: begin () und Container :: end () konstruieren einfach eine std :: list :: iterator, übergeben Sie einen Zeiger auf sie in eine MagicIterator zusammen mit einer Tabelle der Iterationsfunktionen, und gibt die MagicIterator.

Es ist etwas ekelhaft, und bricht meine ursprüngliche Regel in Bezug auf „no memcpy ()“ und macht Annahmen über die Interna der Iteratoren in Frage. Aber es vermeidet Heapzuordnung, hält Collection Einbauten (einschließlich Item) privat, macht MagicIterator völlig unabhängig von der Sammlung in Frage und dem IInterface *, und in der Theorie erlaubt MagicIterators mit jeder Kollektion zu arbeiten (vorausgesetzt, seine Iteratoren können sicher sein memcopy ()‘ d).

Answer 2

Ich glaube, Sie haben zwei getrennte Fragen hier:

Erstellen Sie zunächst einen Iterator, der die IInterface* von Ihrem list<Container::Item> zurückkehren wird. Dies ist leicht mit boost::iterator_adaptor getan:

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(); }
};

Sie würden diese Art als Innen in Container erstellen und zurück in aus seinen begin() und end() Methoden.

Zweitens wollen Sie die Runtime-polymorphen MagicIterator. Das ist genau das, was any_iterator tut. die MagicIterator<IInterface*> ist nur any_iterator<IInterface*, boost::forward_traversal_tag, IInterface*> und cont_iter kann nur zugewiesen werden.

Answer 3

Klingt nicht zu kompliziert. Sie können den Iterator außerhalb definieren. Sie können auch typedefs verwenden. So etwas wie diese passen würde, denke ich. Beachten Sie, dass es wäre viel sauberer, wenn das MagicIterator sei nicht eine kostenlose Vorlage, sondern ein Mitglied von Item, typedefed in Containern vielleicht. So wie es jetzt ist, gibt es eine zyklische Referenz darin, die es necassary einige hässliche Abhilfe Code zu schreiben.

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());
}

Nun starten Sie es:

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

Sie können auch einen Iterator mixin durch Schub zur Verfügung gestellt verwenden, die wie die Eingabeversion von boost :: function_output_iterator funktioniert. Er fordert Ihre Iterator operator() ist, die dann den entsprechenden Wert zurückgibt, zu tun, was wir oben in unseren operator* grundsätzlich tun. Sie finden es in random/detail/iterator_mixin.hpp. Das wäre wahrscheinlich in weniger Code führen. Aber es erfordert auch unseren Hals zu zerbrechen, um das Freund-Material sicherzustellen, weil Artikel ist privat und der Iterator nicht innerhalb Artikels definiert. Wie auch immer, viel Glück:)

Answer 4

Eine abstrakte IteratorImplementation Klasse:

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;
};

Und eine Iterator Klasse umwickeln es:

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.

(Sie können IteratorImplementation eine Klasse "innerhalb" von Iterator machen, um die Dinge sauber zu halten.)

In Ihrer Container Klasse, gibt eine Instanz von Iterator mit einer benutzerdefinierten Unterklasse von IteratorImplementation im 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 5

Es hängt wirklich von der Container, da die Rückgabewerte von c.Begin() und c.End() sind die Implementierung definiert.

Wenn Sie eine Liste möglicher Containers bekannt ist zu MagicIterator, eine Wrapper-Klasse verwendet werden könnte.

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;
};

Die einfach Weg wäre, eine Vorlage zu verwenden, die Container des Typs akzeptiert:

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

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

Mehr Informationen hier.

Answer 6

Ich sehe keinen Grund, warum Sie kann das nicht genau implementieren, wie Sie es aus gelegt habe ... bin ich etwas fehlt?

Um zu klären, müssen Sie irgendeine Art von Zugriffsmethoden auf dem Container-Klasse setzen. Sie können privat sein und Sie können MagicIterator als Freund erklären, wenn Sie das Gefühl, das ist der beste Weg, um es zu kapseln, aber ich würde sie direkt aus. Diese Zugriffsmethoden würden eine normale STL Iterator innerhalb Container verwenden und die Umwandlung zu IInterface zuführen. So würden die Iterieren tatsächlich mit den Zugriffsmethoden der Container erfolgen und MagicIterator wäre nur eine Art von Proxy-Objekt, um es einfacher zu machen. Um es einspringenden zu machen, könnten Sie den MagicIterator Pass in irgendeiner Art von ID haben den STL-Iterator innerhalb Container zu suchen, oder man könnte es tatsächlich in dem STL-Iterator als void * geben hat.

Answer 7

Ein Besucher kann ein einfache (und daher leichter pflegen) Lösung.