boost solution for transforming stl algorithms on proxy iterators?
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. 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. 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. 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? :-). Greetings, Oswin
On Tue, Oct 16, 2012 at 3:25 AM, Oswin Krause < Oswin.Krause@ruhr-uni-bochum.de> 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
Hi,
You should be able to equally well use zip_iterator's, or, if supported by Boost.Range, something like a make_zip_range. zip_iterators are AFAIK not even writeable. At least i remember a discussion about this issue. Also, zip iterators use tuples which are compared lexicographically, which is not what i want. The third thing was, that i would like more meaningful member names than get<0> and get<1> or first/second. so my strcture uses instead key/value
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. Okay, than it is not resolved :-(.
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 :/ and unfortunately, sort is not the only algorithm required...partition, stable_partition, random_shuffle...*sigh* maybe i can implement partition/stable partition and use this for a sort? at least in my use case this should be a good solution...
Greetings, Oswin
I have thought a bit about this issue. would there be a general interest in a boost.iterator conforming implementation of stl algorithms? On 2012-10-16 14:40, Jeffrey Lee Hellrung, Jr. wrote:
On Tue, Oct 16, 2012 at 3:25 AM, Oswin Krause <Oswin.Krause@ruhr-uni-bochum.de [1]> 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 :(
Links: ------ [1] mailto:Oswin.Krause@ruhr-uni-bochum.de [2] http://en.wikipedia.org/wiki/Introsort
On Tue, Oct 16, 2012 at 11:08 PM, Oswin Krause < Oswin.Krause@ruhr-uni-bochum.de> wrote: [...]
would there be a general interest in a boost.iterator conforming implementation of stl algorithms?
I think any STL-like algorithms should be added to Boost.Range's existing collection of algorithms. I've personally found range interfaces to such algorithms (when appropriate) are significantly more convenient and easier to read. It's possible, for example, that a given algorithm can use the one in the STL when the iterators are conforming standard iterators or when Boost detects the underlying STL implementation relaxes the standard requirements on iterators (e.g., does not actually require the reference type to be a real reference); and otherwise dispatch to a Boost-provided implementation. Perhaps the present Boost.Range maintainer (Neil Groves, I believe?) can comment. - Jeff
Hi, yes, this was indeed my idea. it should be quite easy to check whether the class is an "old-style iterator" or "new style iterator" and call the standard implementation if this is applicable. I would branch using is_same< remove_const<remove_reference<iterator_reference<X>::type>::type>::type, iterator_value<X>::type
(i.e. underlying type of X::reference is X::value_type) In my opinion, this would give real value to boost.range aside from the smarter interface :) On 2012-10-17 13:33, Jeffrey Lee Hellrung, Jr. wrote:
On Tue, Oct 16, 2012 at 11:08 PM, Oswin Krause <Oswin.Krause@ruhr-uni-bochum.de [1]> wrote: [...]
would there be a general interest in a boost.iterator conforming implementation of stl algorithms?
I think any STL-like algorithms should be added to Boost.Range's existing collection of algorithms. I've personally found range interfaces to such algorithms (when appropriate) are significantly more convenient and easier to read.
It's possible, for example, that a given algorithm can use the one in the STL when the iterators are conforming standard iterators or when Boost detects the underlying STL implementation relaxes the standard requirements on iterators (e.g., does not actually require the reference type to be a real reference); and otherwise dispatch to a Boost-provided implementation.
Perhaps the present Boost.Range maintainer (Neil Groves, I believe?) can comment.
- Jeff
Links: ------ [1] mailto:Oswin.Krause@ruhr-uni-bochum.de
Dear all, I have a simple Jamroot file for which I don't know why it does not work. Bjam is always complaining: error: Unable to find file or target named error: '/boost/filesystem//fs' error: referred from project at error: '.' However, since I use "use-project boost : c:/boost_1_50_0 ; ", I would assume that it would find it easily. Here is the Jamroot: using msvc ; use-project boost : c:/boost_1_50_0 ; project spectraImport : requirements <library>/boost/filesystem//fs : build-dir ../boost-build ; exe spectraImport : [ glob *.cpp ] ; install ../boost-build : spectraImport ; I appriciate any help. Thank you, Ronny
AMDG On 10/17/2012 05:13 AM, Ronny Herzog wrote:
Dear all,
I have a simple Jamroot file for which I don't know why it does not work. Bjam is always complaining:
error: Unable to find file or target named error: '/boost/filesystem//fs' error: referred from project at error: '.'
However, since I use "use-project boost : c:/boost_1_50_0 ; ", I would assume that it would find it easily.
It would find it if you used the correct name: /boost/filesystem//boost_filesystem or, /boost//filesystem In Christ, Steven Watanabe P.S. Please don't reply to an existing thread with a new subject. Start a new thread instead.
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.
C++ requires it to be `iterator_traits<Iterator>::reference`, I thought, or does it require it to be real reference like `iterator_traits<Iterator>::value_type&`?
Hi,
C++ requires it to be `iterator_traits<Iterator>::reference`, I thought, or does it require it to be real reference like `iterator_traits<Iterator>::value_type&`?
The first is a requirement for every iterator. However, there are a few more lines written in pure standardese which are described in the boost.iterator docu: http://www.boost.org/doc/libs/1_51_0/libs/iterator/doc/new-iter-concepts.htm... "Value Access Requirements in Existing Iterator Categories: [..] Forward Iterator *i is T&" where T is the value_type of the iterator. Greetings, Oswin
On Wed, Oct 17, 2012 at 4:10 AM, Oswin Krause < Oswin.Krause@ruhr-uni-bochum.de> wrote:
Hi,
C++ requires it to be `iterator_traits<Iterator>::**reference`, I
thought, or does it require it to be real reference like `iterator_traits<Iterator>::**value_type&`?
The first is a requirement for every iterator. However, there are a few more lines written in pure standardese which are described in the boost.iterator docu:
http://www.boost.org/doc/libs/**1_51_0/libs/iterator/doc/new-** iter-concepts.html#motivation<http://www.boost.org/doc/libs/1_51_0/libs/iterator/doc/new-iter-concepts.html#motivation>
"Value Access Requirements in Existing Iterator Categories: [..] Forward Iterator *i is T&"
where T is the value_type of the iterator.
Just to be technically accurate, T const & is also acceptable, of course; but otherwise, yes, a real reference is still technically required by the standard for forward iterators. - Jeff
participants (5)
-
Jeffrey Lee Hellrung, Jr. -
Oswin Krause -
paul Fultz -
Ronny Herzog -
Steven Watanabe