[boost] Re: Any Interest in an Adapter for Sequences of Pointers?

From: Alex Chovanec (achovane_at_[hidden])
Date: 2003-06-12 21:40:04

Hi Thorsten,

Thank you for your feedback.

> You can avoid your handcoded loop by something like
>
> transform( ..., &address_of );
>

I suppose that's true. If you have a unary address_of() function, you can do
it cleanly enough with a transform.

> What would have been nice was some kind of template that could generate
> oprator<, operator= etc
> if there was a non-pointerversion of the class.

I suppose for starters, you could create a generic binary function for
operator< and other operators, maybe something like this:

    template <typename T>
    struct ptr_less
    {
        bool operator()(const T * lhs, const T * rhs)
        {
            return (*lhs < *rhs);
        }
    };

Going one step further, you could create a generic adapter for any binary
predicate:

    template <typename T, class Predicate>
    struct ptr_predicate
    {
        bool operator()(const T * lhs, const T * rhs)
        {
            Predicate pred;
            return pred(*lhs, *rhs);
        }
    };

Then you could instantiate it like this:

    ptr_predicate<Widget, std::less<Widget> > my_predicate;

That gets a little clunky though. What I had in mind is a mechanism where
you don't have to define a predicate for comparing pointers. Instead, you
would be able to use existing predicates for comparing objects.

My idea for implementing this was to pass a proxy that encapsulates a
pointer to an object of type T and defines some basic pointer operations,
like operator* and operator->. The key is that it also has an implicit
conversion to a const T &. That way, you could pass two of these proxies
directly to std::less<T>.

When it comes to operator= though, they would just perform shallow copies.
This way, you can have value semantics for comparisons and reference
semantics for copy, assignment, swap, etc. There would also be an implicit
conversion constructor that takes a T & as a parameter. That way, you could
assign a T & to a proxy.

With these operators, you could avoid using a call to transform (not that
it's a terrible thing to use transform). You could just apply the algorithm
you want directly.

For instance, suppose you wanted to perform an std::set_insersection on two
ranges of objects, and then modify each object in the first range that also
appears in the second. You could do this:

    . . .
    // make sure my_permutation is big enough to hold the result
    my_permutation.resize(std::min(end1 - begin1, end2 - begin2));

    // calculate the intersection
    std::set_intersection(
        begin1, end1, begin2, end2,
        std::back_inserter(my_permutation));

Now you have a range of proxies to all of the objects in the first range
that also appear in the second range. You could apply a transformation to
the original copies of those objects in [begin1, end1) using the following
function call.

    std::for_each(
        my_permutation.begin(),
        my_permutation.end(),
        some_functor());

I think this ability to go back and modify elements from the source range
via proxies in the destination range could be very useful.

Unfortunately (sigh), there is a problem here that I have not found a
satisfactory solution to. The preceding example with std::set_intersection
should (most likely) work. However, some other STL algorithms (e.g.
std::unique_copy) make local copies of objects from the source range and
then assign those copies to elements in the destination range. Since these
proxies provide shallow copy semantics, this places dangling pointers to
destroyed objects in my_permutation.

Looking at some different STL implementations, this use of local copies does
not appear to be too widespread, but it does occur. So function calls like
the preceding one to std::set_intersection are somewhat risky. As I said, I
have not found a satisfactory solution to this problem.

Still, this is only an issue if you pass iterators to objects as a source
range and iterators to proxies as a destination range. You can safely use
algorithms to assign proxies to proxies or proxies to objects, so the
preceding call would be ok if both of the source ranges were ranges of
proxies.

I'm still working on a solution to the other problem. Any suggestions would
be appreciated.

Cheers,

Alex

"Thorsten Ottosen" <nesotto_at_[hidden]> wrote in message
news:bc99o8$56c$1_at_main.gmane.org...
> Hi Alex,
>
> > There are many more possibilities beyond those described here. Does this
> > sound interesting to anyone????
>
> I don't have time to comment very thoroughly, but I can say that it does
> sound
> interesting. In the project I'm working on now I needed to sort the
pointers
> from
> several containers which was not that hard.
>
> >     // widgets_ and widget_ptrs_ get populated with some values
> >     . . .
> >     for (unsigned int i = 0; i < widgets_.size(); ++i)
> >     {
> >         widget_ptrs_.push_back(&widgets_[i]);
> >     }
>
> You can avoid your handcoded loop by something like
>
> transform( ..., &address_of );
>
> of course you would have to resize the destination vector, but wouldn't
you
> do that
> anyway to save some allocations?
>
> What would have been nice was some kind of template that could generate
> oprator<, operator= etc
> if there was a non-pointerversion of the class.
>
> regards
>
> Thorsten
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>