Re: [Boost-users] boost solution for transforming stl algorithms on proxy iterators?

Subject: Re: [Boost-users] boost solution for transforming stl algorithms on proxy iterators?
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2012-10-16 08:40:55

On Tue, Oct 16, 2012 at 3:25 AM, Oswin Krause <
Oswin.Krause_at_[hidden]> wrote:

> Hi,
>
> I often have problems which look a bit like this:
>
>     //example code, only for problem statement
>     //std::vector<bool> chosen only because it is no container :). If this
> is too silly for you,
>     //think about a matrix interpreted as range of row-vectors.
>     std::vector<bool> myContainer;//does only have proxy iterators.
>     std::vector<double> myDistances; //stores for every element in
> myContainer a distance
>
>     //now i want to to sort the elements of both ranges in place
>     //as if they were in a hypothetic range std::vector<std::pair<bool,
> double> >
>     //and sort them by the second part:
>     boost::sort(make_key_value_**range(myContainer,myDistances)**);//bam,
> not allowed
>
> I omited the definition of make_key_value_range but it should be clear
> that this returns a proxy range with writable iterators and reference type
> similar to std::pair<std::vector<bool>::**reference,double&> for which
> swap is overloaded to do the right thing.
>

You should be able to equally well use zip_iterator's, or, if supported by
Boost.Range, something like a make_zip_range.

> This is not allowed by the standard as boost::sort calls std::sort which
> in turn requires random_access_iterators - and they disallow proxy
> references.

Ugh, yes :(

This issue is AFAIK resolved with C++11 but some of us still need to
> support C++03 - and I am really annoyed by this problem.
>

Hmmm...how is this resolved in C++11? AFAIK, C++11 still uses the old
archaic iterator categories and requires a real C++ reference as the
reference type of forward iterators.

The thing is: this will compile on most compilers. One could just lie about
> the iterator category, saying it is a random_access_iterator and even VC
> would be happy with it. However it could just break randomly on a new
> compiler without warning or has severe performance issus (for example gcc
> works, but completely ignores my nicely defined swap and instead does a
> triangle copy :-( ).
>
> So how can one resolve this issue? I have the problem, that i need to do
> this in-place, since copying would result in std::bad_alloc almost surely.
> Also the above single line of code just looks that nice, that i just want
> to have it this way.
>
> So, how do you resolve this issue? is there maybe some boost library
> capable of getting this done? e.g. boost.betterSTL? :-).
>

I agree, this is a deficiency in the standard. Unfortunately, maybe the
only thing you can do to guarantee this works in a portable way is to code
up your own introsort [1] implementation :/

- Jeff

[1] http://en.wikipedia.org/wiki/Introsort