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

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2004-07-22 11:06:24

David Abrahams <dave_at_[hidden]> writes:

> Anthony Williams <anthony_w.geo_at_[hidden]> writes:
>
>> Gunter Winkler <guwi17_at_[hidden]> writes:
>>
>>> I tried to use boost::zip_iterator to sort 2 parallel arrays. Unfortunatly
>>> gcc does not compile the appended example because it can not convert
>>>
>>>    boost::detail::iterator_category_with_traversal<std::input_iterator_tag, 
>>>    boost::random_access_traversal_tag>
>>>
>>> to either 
>>>   std::bidirectional_iterator_tag
>>> or
>>>   std::random_access_iterator_tag.
>>> Thus it cannot dispatch the correct stl::__copy_backward() procedure.
>>>
>>> Is sort() not yet supported? 
>>
>> As Dave already posted, zip_iterator doesn't support return forward or
>> bidirectional iterators, so std::sort() cannot be used.
>>
>> What you need is something like my tuple iterator (tupleit.zip from the files
>> area on the boost yahoo group), which *does* support use with std::sort ---
>> the iterator category of the tuple iterator is the minimum category of the
>> supplied iterators.
>
> How can sorting work?
> What type is returned from its operator* ?

For Forward, Bidi and Random-access Iterators, it returns a reference to a
value held in the iterator.

This value is a tuple of references to the value types of the supplied
iterators. Actually it is a new class derived from the appropriate
instantiation of boost::tuple, which ensures that copies are true copies ---
the references in the boost::tuple base point *inside* the object, whereas
access through the original object will reference the source.

The downside of this is that the iterator has to hold the refernce tuple,
which has to have space for a copy of the value tuple. This can be big if the
value types are big. I could make this heap-allocated, which would reduce that
size back again, at the expense of increased copy times, and an extra source
of exceptions.... I've done that and it works OK.

Looking at the code, operator[] returns a ref to a temporary, so that needs
changing to just return the value_type (current discussions in the LWG
notwithstanding), but that's not a big issue. (I've also done that in my copy)

Here are some samples of usage; the testtupleit.cpp file from the archive has
an example using std::sort.

typedef std::vector<int> VecInt;
VecInt v1,v2;
// initialize v1 and v2
v1.resize(3);
v2.resize(3);
v1[0]=42;
v2[0]=23;

typedef TupleIt<boost::tuple<VecInt::iterator,VecInt::iterator> >
TupleIteratorType;

TupleIteratorType tupleIterator=makeTupleIterator(v1.begin(),v2.begin());

*tupleIterator=boost::tuple<int,int>(1,3); // write to vectors
assert(v1[0]==1);
assert(v2[0]==3);

TupleIteratorType::value_type valueCopy=*tupleIterator; // read values
valueCopy=boost::tuple<int,int>(9,27); // write to copy only

// verify original vector unchanged
assert(v1[0]==1);
assert(v2[0]==3);

// Ok, operator* returns a reference
TupleIteratorType::value_type& opStarResult=*tupleIterator; 
int& intRef=opStarResult.get<0>(); // ref to element in v1
intRef=46;
assert(v1[0]==46);

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