implicit ranges

[Alexandru]

I recently faced the following problem: I have an increasing sequence
a1 <= a2 <= ... <= an <= ... The sequence is generated by a function f
such that ai = f(i). Now I want to search for a certain number inside
set a1 ... an. This could be easily done with a binary search. However
I could not find implicit ranges (like xrange in python) in stl such
that I can use lower_bound or upper_bound from <algorithm>. Is there
any such thing in STL or boost? Or do I always have to rewrite the
binary search to support my operation?

--Alexandru

 

[Guest]

I recently faced the following problem: I have an increasing sequence
a1 <= a2 <= ... <= an <= ... The sequence is generated by a function f
such that ai = f(i). Now I want to search for a certain number inside
set a1 ... an. This could be easily done with a binary search. However
I could not find implicit ranges (like xrange in python) in stl such
that I can use lower_bound or upper_bound from <algorithm>. Is there
any such thing in STL or boost? Or do I always have to rewrite the
binary search to support my operation?

I am not sure what these implicit ranges are, so all I can tell you is
that lower_bound will work on any sorted container supporting forward
iterators. If you have to write your own container for the implicit
ranges make it support iterators and you will get lower_bound for free
along with other algorithms.

 

[James Kanze]

On 2007-10-08 22:06, Alexandru wrote:

I am not sure what these implicit ranges are, so all I can tell you is
that lower_bound will work on any sorted container supporting forward
iterators. If you have to write your own container for the implicit
ranges make it support iterators and you will get lower_bound for free
along with other algorithms.

You don't need a container, only iterators. (And lower_bound
will work a lot better if your iterator is random access.)
Boost.iterators has support for iterators which don't require a
backing container; I think once supplies exactly what he's
looking for (but if not, it's really pretty trivial to do).

The problem, of course, is that formally, without a backing
container, the operator* can't return a unique reference, which
means that only input iterator can be supported. I think that
the boost iterators have a way of working around this, as well,
for const iterators (which is what his would be), but I'm not
familiar with the details.