[boost] Re: std::sort(zip_iterator...) does not compile

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2004-07-26 05:54:44

David Abrahams <dave_at_[hidden]> writes:

> Anthony Williams <anthony_w.geo_at_[hidden]> writes:
>
>> David Abrahams <dave_at_[hidden]> writes:
>>
>>> Anthony Williams <anthony_w.geo_at_[hidden]> writes:
>>>
>>>>> Which is why we have to change counting_iterator to not be a forward
>>>>> iterator.
>>>>
>>>> Darn. I missed that requirement --- I was working off table 74, which
>>>> just requires *a==*b if a==b (amusingly adding a requirement that the
>>>> value type supports operator== in the process). This requirement makes it
>>>> actually impossible to make an aggregating iterator anything other than
>>>> an input or output iterator.
>>>>
>>>> :(
>>>>
>>>> On the plus side, my tuple iterator works with std::sort on every compiler
>>>> I've tested it on. Do you know of any implementations that depend on this
>>>> requirement being met for any of the standard algorithms?
>>>
>>> I don't know, but it seems to me that there's another problem.  If
>>> one of the component sequences contains types whose copy ctor may
>>> throw, how do you write the internal cache back to the sequence
>>> without potentially throwing during destruction?  Consider passing
>>> the tuple iterator and a new value to this:
>>>
>>>         template <class Iterator, class Value>
>>>         void f(Iterator a, Value const& x)
>>>         {
>>>            *a = x;
>>>         }
>>
>> The internal cache in the iterator does not hold any values, it is
>> essentially just an aggregator of references (derived from
>> boost::typle<Iter1::value_type&,Iter2::value_type&....>). Since the sources
>> are separate there is no real object to reference for the return value of
>> operator*, so I had to make one.
>
> Oh, then it doesn't conform in another way.  operator* on a
> ForwardIterator must return a real reference.

I am somehow failing to communicate the design to you; it may be best for you
to look at the code, or read my article on the original pair-based
implementation (http://web.onetel.com/~anthony_w/cplusplus/pair_iterators.pdf)

I worked hard on this to ensure it met all the requirements of the various
iterator categories. I am disturbed that I missed the requirement about ==
implying the same object, but please do not assume that other requirements are
not met unless you have direct evidence.

operator* returns a real reference to an object stored within the
iterator. This object is a tuple of references to the objects returned by
dereferencing the source iterators, with some custom behaviour to handle
copying.

This custom behaviour means that copies of this tuple actually hold copies of
the originally-referenced data, and the references on this new copy point back
within itself to the copies of the data.

Anthony
-- 
Anthony Williams
Senior Software Engineer, Beran Instruments Ltd.