Boost logo

Boost :

Subject: Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-28 01:38:19


on Sat Dec 27 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:

> AMDG
>
> David Abrahams wrote:
>>> - transform_iterator.hpp
>>> - ...
>>>
>>> for the various partition_point overloads?
>>
>> Something like that seems likely. I'm still having trouble
>> understanding how you can implement a specialization for
>> transform_iterator without knowing more than actually possible about the
>> semantics of the transformation function.
>>
>
> I think the idea is that if an optimized partition_point exists for
> the underlying iterator, the partition_point specialization for
> transform_iterator should use it. This has nothing to do with the
> specific transformation function.

Sorry, I still don't get it. Here's the declaration of partition_point
as given by www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2666.pdf:

  template <class ForwardIterator, class Predicate>
    ForwardIterator partition_point(
      ForwardIterator first, ForwardIterator last, Predicate pred);

Let's say ForwardIterator is a transform_iterator whose transformation
function is

    f(x) => x >= 5 ? 1 : 0

and the underlying sequence is

    0 1 2 3 4 5 6 7 8 9

so the transformed sequence is

    0 0 0 0 0 1 1 1 1 1

and pred is

    p(x) => x < 1

How will the specialization of partition_point for transform_iterator
come up with a predicate to pass on to the partition_point that applies
to the underlying iterator type? In general, it can't reverse engineer the
transformation function and figure out how to get from p(x) above to

    p'(y) => y < 5

can it?

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk