[boost] passing ranges or output iterators to virtual functions

From: Simon Richter (Simon.Richter_at_[hidden])
Date: 2008-07-18 20:34:47

Hi,

I've written two small class templates that basically "work for me" in
the current state, but are not as generic as I'd like.

The task at hand: pass a list of objects through a function call with
fixed signature (such as a virtual function) without exposing the actual
container type used.

I'd like to get a bit of feedback on whether these might be a worthwhile
addition to Boost (after some cleanup and implementation of features
missing so far).

I'll start with the simpler class:

template<typename T>
class output_iterator
{
        class wrapper_base
        {
        public:
                virtual ~wrapper_base(void) throw() { }
                virtual void operator=(T const &) = 0;
                wrapper_base &operator*(void) { return *this; }
                wrapper_base &operator++(void) { return *this; }
                wrapper_base &operator++(int) { return *this; }
        };

        template<typename O>
        class wrapper :
                public wrapper_base
        {
        public:
                wrapper(O o) : o(o) { }
                virtual void operator=(T const &v) { *o++ = v; }
        private:
                O o;
        };

public:
        template<typename O>
        output_iterator(O o) : o(new wrapper<O>(o)) { }

        output_iterator(output_iterator<T> const &o) : o(new wrapper<wrapper_base &>(*o.o)) { }

        output_iterator<T> &operator*(void) { return *this; }
        output_iterator<T> &operator++(void) { return *this; }
        output_iterator<T> &operator++(int) { return *this; }
        output_iterator<T> &operator=(T const &v) { *o = v; return *this; }

private:
        std::auto_ptr<wrapper_base> o;
};

Basically, that allows code like the following to work:

class base
{
public:
        virtual ~base(void) throw() { }
        virtual output_iterator<int> get_some_ints(output_iterator<int>) = 0;
};

class derived :
        public base
{
public:
        virtual ~derived(void) throw() { }
        virtual output_iterator<int> get_some_ints(output_iterator<int>);
};

void derived::get_some_ints(output_iterator<int> o)
{
        *o++ = 5;
        *o++ = 7;
        return o;
}

int main(int, char **)
{
        std::list<int> l;
        derived d;
        base &b = d;
        b.get_some_ints(std::back_inserter(l));
        // l now contains {5, 7}
}

The most obvious problem is that it fails for output iterators that do
not advance on assignment, but that can be solved easily with a few more
virtual functions in the wrapper.

Something that is harder to do is that the return value from
get_some_ints should be assignable to a type that is equal to 

int main(int, char **)
{
        int some_ints[4];
        int *next = some_ints;

        derived d;
        next = d.get_some_ints(next);
}

It does work if the returned output iterator is stored in an
output_iterator<int>, and passing that to another function works as
well. Extracting the int * would probably require RTTI.

The third problem is that every time the output iterator is copied,
memory is allocated, which is freed only when the last copy goes out of
scope (there are some failure cases where memory is freed too early, but
I think these are invalid uses of the output iterator).

The second class attempts to do the same for range:

template<typename T>
void intrusive_ptr_add_ref(T *e, typename T::enumerator_tag = typename T::enumerator_tag())
{
        ++e->refcount;
}

template<typename T>
void intrusive_ptr_release(T *e, typename T::enumerator_tag = typename T::enumerator_tag())
{
        if(!--e->refcount)
                delete e;
}

template<typename T>
class range
{
        class wrapper_base
        {
        public:
                virtual ~wrapper_base(void) throw() { }

                class enumerator
                {
                public:
                        enumerator(void) throw() : refcount(0) { }
                        virtual ~enumerator(void) throw() { }

                        virtual T &operator*(void) const throw() = 0;
                        virtual enumerator &operator++(void) throw() = 0;
                        virtual bool operator!(void) const throw() = 0;

                private:
                        unsigned int refcount;

                        template<typename E>
                        friend void intrusive_ptr_add_ref(E *, typename E::enumerator_tag);
                        template<typename E>
                        friend void intrusive_ptr_release(E *, typename E::enumerator_tag);

                        struct enumerator_tag { };
                };

                virtual std::auto_ptr<enumerator> get(void) = 0;
        };

        template<typename I>
        class wrapper :
                public wrapper_base
        {
        public:
                wrapper(I first, I last) : first(first), last(last) { }

                class enumerator :
                        public wrapper_base::enumerator
                {
                public:
                        enumerator(I current, I end) : current(current), end(end) { }
                        virtual ~enumerator(void) throw() { }

                        virtual T &operator*(void) const throw()
                        {
                                return *current;
                        }
                        virtual enumerator &operator++(void) throw()
                        {
                                ++current;
                                return *this;
                        }
                        virtual bool operator!(void) const throw()
                        {
                                return current == end;
                        }
                private:
                        I current, end;
                };

                virtual std::auto_ptr<typename wrapper_base::enumerator> get(void)
                {
                        return std::auto_ptr<typename wrapper_base::enumerator>(new enumerator(first, last));
                }

        private:
                I first, last;
        };

public:
        template<typename C>
        range(C const &container) : r(new wrapper<typename C::const_iterator>(container.begin(), container.end())) { }

        template<typename C>
        range(C &container) : r(new wrapper<typename C::iterator>(container.begin(), container.end())) { }

        template<typename F>
        F for_each(F f)
        {
                std::auto_ptr<typename wrapper_base::enumerator> e(r->get());
                while(!!*e)
                {
                        f(**e);
                        ++*e;
                }
                return f;
        }

        class iterator :
                public std::iterator<std::input_iterator_tag, T>
        {
        public:
                iterator(void) : e() { }
                iterator(std::auto_ptr<typename wrapper_base::enumerator> e) : e(e.release()) { }

                T &operator*(void) const { return **e; }
                T *operator->(void) const { return &**e; }
                iterator &operator++(void) { ++*e; return *this; }

                bool operator==(iterator const &rhs) const
                {
                        if(e.get() && !!*e)
                                return rhs.e.get() && !!*rhs.e;
                        return !rhs.e.get() || !*rhs.e;
                }

                bool operator!=(iterator const &rhs) const
                {
                        return !operator==(rhs);
                }

        private:
                boost::intrusive_ptr<typename wrapper_base::enumerator> e;
        };

        iterator begin(void) { return iterator(r->get()); }
        iterator end(void) { return iterator(); }

private:
        wrapper_base *r;

};

Again, this class is pretty much incomplete, but "works for me". The
iterator can only implement the input iterator category as it is not
possible to compare two non-singular iterators. More constructors could
be added that accept other inputs than containers (I can also see the
memory leak, although valgrind can't -- the pointer inside the range<T>
class should probably be a shared_ptr or intrusive_ptr).

Any comments on these so far? Is the general idea useful?

   Simon