A C++ iterator adapter which wraps and hides an inner iterator and converts the iterated type

Question

Having toyed with this I suspect it isn't remotely possible, but I thought I'd ask the experts. I have the following 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;
};

I want to add these methods to Container:

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

In order that callers can write:

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

So essentially I want to provide a class which appears to be iterating over some collection (which the caller of Begin() and End() is not allowed to see) of IInterface pointers, but which is actually iterating over a collection of pointers to other objects (private to the Container class) which can be converted into IInterface pointers.

A few key points:

• MagicIterator is to be defined outside Container.
• Container::Item must remain private.

• MagicIterator has to iterate over IInterface pointers, despite the fact that Container holds a std::list<Container::Item>. Container::Item contains an Object*, and Object can be used to fetch IInterface*.

• MagicIterator has to be reusable with several classes which resemble Container, but might internally have different list implementations holding different objects (std::vector<SomeOtherItem>, mylist<YetAnotherItem>) and with IInterface* obtained in a different manner each time.

• MagicIterator should not contain container-specific code, though it may delegate to classes which do, provided such delegation is not hard coded to to particular containers inside MagicIterator (so is somehow resolved automatically by the compiler, for example).

• The solution must compile under Visual C++ without use of other libraries (such as boost) which would require a license agreement from their authors.

• Also, iteration may not allocate any heap memory (so no new() or malloc() at any stage), and no memcpy().

Thanks for your time, even if you're just reading; this one's really been bugging me!

Update: Whilst I've had some very interesting answers, none have met all the above requirements yet. Notably the tricky areas are i) decoupling MagicIterator from Container somehow (default template arguments don't cut it), and ii) avoiding heap allocation; but I'm really after a solution which covers all of the above bullets.

Marylinmarylinda

"...which can be converted into IInterface pointers." does that mean that other class is a base-class? or do you man the actual pointer is a member of the class? – Pulsifer

The pointer is to be obtained by calling Object::GetInterface(), and so can't be relied upon to be a member of the class. – Marylinmarylinda

MagicIterator can't access the internals of Container or shouldn't? – Sillsby

Ideally can't, I was hoping for some form of (/handwave) adapter-based solution where by MagicIterator doesn't have to be specific to Container. So it's not a hacky class, but one that could be reused in other situations to abstract away exactly what's iterated. – Marylinmarylinda

Answer 1

I've now found a solution which is fitter for my original purpose. I still don't like it though :)

The solution involves MagicIterator being templated on IInterface* and being constructed with both a void* to an iterator, the byte size of said iterator, and a table of pointers to functions which perform standard iteration functions on said void* such as increment, decrement, dereference, etc. MagicIterator assumes that it is safe to memcpy the given iterator into an internal buffer, and implements its own members by passing its own buffer as a void* to the supplied functions as if it were the original iterator.

Container then has to implement static iteration functions which cast back a supplied void* to a std::list::iterator. Container::begin() and Container::end() simply construct a std::list::iterator, pass a pointer to it into a MagicIterator along with a table of its iteration functions, and return the MagicIterator.

It's somewhat disgusting, and breaks my original rule regarding "no memcpy()", and makes assumptions about the internals of the iterators in question. But it avoids heap allocation, keeps Collection's internals (including Item) private, renders MagicIterator entirely independent of the collection in question and of IInterface*, and in theory allows MagicIterators to work with any collection (provided its iterators can be safely memcopy()'d).

Marylinmarylinda

Answer 2

I think you have two separate issues here:

First, create an iterator that will return the IInterface* from your list<Container::Item>. This is easily done with 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(); }
};

You would create this type as inner in Container and return in from its begin() and end() methods.

Second, you want the runtime-polymorphic MagicIterator. This is exactly what any_iterator does. the MagicIterator<IInterface*> is just any_iterator<IInterface*, boost::forward_traversal_tag, IInterface*>, and cont_iter can be just assigned to it.

Colquitt

That is beautifully brief, but I sadly don't have boost available. Terrible I know, and this is a neat answer which I may have to try in principle even though I can't use it in this case. – Marylinmarylinda

Answer 3

Create an abstract IteratorImplementation class:

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

And an Iterator class to wrap around it:

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.

(You can make IteratorImplementation a class "inside" of Iterator to keep things tidy.)

In your Container class, return an instance of Iterator with a custom subclass of IteratorImplementation in the 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);
}

Flaming

I did try that, but sadly the abstract Iterator class can't be instantiated, so the caller can't store it anywhere (even in a for loop header) without knowing the concrete type. – Marylinmarylinda

It can be instantiated. Your begin() and end() classes instantiate it. I don't see the problem. – Flaming

for (Iterator<Object*> i = c.begin(); i != c.end(); i++) ...will not compile, as Iterator<> is abstract. – Marylinmarylinda

Ah, you are right. Dang, and I thought I had something working. =] You could have a wrapper around the abstract class, and pass the wrapped class to the constructor of the Iterator object. I think that'd work. – Flaming

Actually, having looked more closely, this won't do; the reason I didn't do it is I can't have heap allocation caused by iteration in my case, so "new" is out. alloca() (possibly via an evilly overloaded new operator) won't help either, as it'll go out of scope when ObjectContainer::begin() returns. – Marylinmarylinda

Answer 4

Doesn't sound too complicated. You can define the iterator outside. You can also use typedefs. Something like this would fit i think. Note that it would be way cleaner if that MagicIterator would be not a free template, but a member of Item, typedefed in Container maybe. As it's now, there is a cyclic reference in it, which make it necassary to write some ugly workaround code.

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

Now, start using it:

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

You can also use a iterator mixin provided by boost, which works like the input version of boost::function_output_iterator. It calls your iterator's operator() which then returns the appropriate value, doing what we do above in our operator* in principle. You find it in random/detail/iterator_mixin.hpp. That would probably result in fewer code. But it also requires to wrack up our neck to ensure the friend-stuff because Item is private and the iterator isn't defined inside Item. Anyway, good luck :)

Pulsifer

That compiles and runs beautifully except that Item is private to Container. I could move MagicIterator into Container, but I really want MagicIterator to be applicable to several Container-like classes, which perhaps implement MagicIterator-specific "glue" functionality. – Marylinmarylinda

@El Zorko, That's what friends are for. – Flaming

El, Zorko. the iterator is a friend of Container. so it should be able to see Item, even if it is private – Pulsifer

El, Zorko. if you want to decouple the iterator from Container, make Container a template parameter too, and assert "each Container must have a typedef that declares the InputIterator wrapped as "wrapped_iterator" , for example. Then you can do Container::Item to get the item type too – Pulsifer

(and default the InputIterator parameter to Container::wrapped_iterator or remove it completely) – Pulsifer

Ei, Zorko. Oh that's interesting. comeau also rejects it. default arguments do not seem to be blessed by friendship. i will have to change the stuff :) – Pulsifer

Upon closer inspection, this sadly doesn't quite fit the bill either. MagicIterator has to accept a template argument indicating its container and the real iterator, which couples it directly to the COntainer class. I need a decoupled MagicIterator to work with multiple Container-esque classes. – Marylinmarylinda

EI Zorko, that's impossible without using new. your iterator needs to be polymorphic then. but you said you don't want that. – Pulsifer

you can use stack allocation for the most common iterator sizes, but sooner or later, you will have to do with an iterator size that doesn't fit a small buffer optimization anymore, and then heap allocation will be needed. boost::any doesn't even buffer with that. it always uses the heap – Pulsifer

i can show you a version that exactly fits your bill, but uses new behind the hood (using boost::any and boost::function). anyway, why the heck do you want to avoid new? can you show us an example where that hurts? – Pulsifer

Apologies, but I did lead the post with a statement that I suspected it wasn't possible. This code is intended to ease iteration in a highly constrained environment where minimising use of heap allocation is very significant. – Marylinmarylinda

hmm, i see. if you have a limited set of containers, you can use boost::variant and avoid heap allocation here. maybe that would be an option? – Pulsifer

otherwise, i would just use the new/delete stuff and profile first, to see whether it really causes any significant slowdown – Pulsifer

I agree with @litb; new/delete may not be your bottleneck. You can reimplement it to use the stack, too. If you really wanted speed, why bother with MagicIterator in the first place? Also, "premature optimization is the root of all evil." – Flaming

Sadly you can't re-implement it to use the stack, without doing something evil like my solution below. I need speed, plus the ability to iterate over X* when really the underlying collection is of Y, with suitable abstraction. This is for performant code where excess heap allocs are unacceptable. – Marylinmarylinda

Answer 5

It really depends on the Container, because the return values of c.Begin() and c.End() are implementation-defined.

If a list of possible Containers is known to MagicIterator, a wrapper class could be used.

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

The easy way would be to use a template which accepts Container's type:

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

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

More information here.

Flaming

He isn't trying to support multiple container types with the same iterator (ala any_iterator)... – Hurry

Aye, the main task is to hide the fact that we're really using a std::vector::iterator<Item>, and make it look like we're iterating over IInterface* pointers (obtained from Object, within each Item). In particular Item must remain private to Container, unlike Object and IInterface. – Marylinmarylinda

Answer 6

I see no reason why you can't implement this exactly as you've laid it out... am I missing something?

To clarify, you'll need to put some kind of accessor methods on your Container class. They can be private and you can declare MagicIterator as a friend, if you feel that's the best way to encapsulate it, but I'd expose them directly. These accessor methods would use a normal STL iterator inside Container and perform the conversion to IInterface. Thus the iterating would actually be done with the Container's accessor methods and MagicIterator would just be a kind of proxy object to make it easier. To make it reentrant, you could have the MagicIterator pass in some kind of ID to look up the STL iterator inside Container, or you could actually have it pass in the STL iterator as a void *.

Bute

I don't want to have to make Container::Item public. I want the iterator to be externally unrelated to std::list::iterator; to appear to be iterating over a set of IInterface* pointers, and for Item to remain entirely private to Container. IInterface* comes from Item.pObject->GetInterface(). – Marylinmarylinda

my solution does not require you to make Item public. The iterator is externally unrelated. The accessors are wrapping the std::list::iterator, so only the insides of Container know that is the implementation. That's also why I suggested using a void* to pass it for making it reentrant. – Bute

Apologies, that was a mispost. [This is, as you can probably tell, my first time here. Very sorry!] I really want to keep MagicIterator decoupled from Container; I'd like to be able to re-use it on other arbitrary classes without changing it, even if said others had to have glue to make it work. – Marylinmarylinda

well, you could make Container implement some interface that provides appropriate accessor methods and thus be able to reuse MagicIterator with anything else that implements that inferface, but other than that, I'm out of ideas... sorry. – Bute

Some form of IMagicIteratable<IInterface*>...that is a thought. But how would one write the accessor methods on Container in a manner that uses a stack-allocated std::list<Item> iterator without exposing it (and the private class Item) to the caller of said methods? – Marylinmarylinda

My proposal didn't have a stack-allocated std::list::iterator. the iterator was inside Container (or in an untyped pointer inside the MagicIterator class). in either case, Container would act as a factory for MagicIterator, thus it could create the iterator inside itself or the MagicIterator. – Bute

At the risk of being dumb, if MagicIterator accesses the real iterator via an untyped pointer, where is said iterator? I want it on the stack somewhere really. It can't be in eg. a list in Container surely, as I don't want heap allocation during iteration...and I equally don't want to new() it. – Marylinmarylinda

Answer 7

A visitor may be a simpler (and therefore easier to maintain) solution.

Nimitz