Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > implicit ranges

Reply
Thread Tools

implicit ranges

 
 
Alexandru
Guest
Posts: n/a
 
      10-08-2007
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

 
Reply With Quote
 
 
 
 
=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=
Guest
Posts: n/a
 
      10-08-2007
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
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      10-09-2007
On Oct 8, 11:58 pm, Erik Wikström <(E-Mail Removed)> 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:(E-Mail Removed)
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
ranges vs subnets Peter Lecki Cisco 7 01-17-2006 10:32 AM
another array ranges mystery valentin tihomirov VHDL 2 06-18-2005 05:53 PM
Multiple ISPs and Multiple IP Ranges from Each ISP Chennak Cisco 10 06-08-2005 09:29 PM
PIX-501 with multiple outside IP ranges Mike Ruskai Cisco 3 02-14-2005 11:43 PM
Cisco Playstation 2 Setup Comments, Ports forwarding Ranges Jim Saunders Cisco 0 03-05-2004 10:16 AM



Advertisments