implicit ranges

Discussion in 'C++' started by Alexandru, Oct 8, 2007.

  1. Alexandru

    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?

    --Alexandru
     
    Alexandru, Oct 8, 2007
    #1
    1. Advertising

  2. On 2007-10-08 22:06, Alexandru wrote:
    > 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.

    --
    Erik Wikström
     
    =?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=, Oct 8, 2007
    #2
    1. Advertising

  3. Alexandru

    James Kanze Guest

    On Oct 8, 11:58 pm, Erik Wikström <> wrote:
    > On 2007-10-08 22:06, Alexandru wrote:


    > > 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.


    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.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Oct 9, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. valentin tihomirov

    another array ranges mystery

    valentin tihomirov, Jun 18, 2005, in forum: VHDL
    Replies:
    2
    Views:
    491
    Mike Treseler
    Jun 18, 2005
  2. C
    Replies:
    1
    Views:
    460
    Sunil TG [MVP]
    Oct 29, 2003
  3. Philip Townsend

    Determining date ranges

    Philip Townsend, Nov 6, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    331
    Philip Townsend
    Nov 6, 2003
  4. Strider76

    Excel Defined ranges

    Strider76, Apr 13, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    327
    Strider76
    Apr 13, 2004
  5. Bob Hairgrove

    Working with ranges of scalar values

    Bob Hairgrove, Jun 26, 2004, in forum: C++
    Replies:
    1
    Views:
    323
    Ivan Vecerina
    Jun 29, 2004
Loading...

Share This Page