Topic: reverse lower_bound
Author: "kostas" <skolarik@gmail.com>
Date: Tue, 3 Apr 2007 16:59:52 CST Raw View
On Apr 3, 8:18 pm, kuy...@wizard.net wrote:
> The reason is relatively simple. The lower_bound() and upper_bound()
> functions are supposed to return iterators that bound the range where
> matching elements of the container can be found. If there are no such
> elements, they're supposed to indicate an empty range, which means
> they must be equal to each other. They could either both return
> iterators pointing to the first bounding element, or they could both
> return iterators point to the second bounding element. Only the latter
> choice is compatible with the value that upper_bound() is supposed to
> return when there are matching elements.
>
I'm wondering only why the same functionality is not provided in
opposite direction
with reverse iterators. Is it redundant or the use of reverse
iterators is not generally
encouraged?
I'm wondering also why the relation &*(reverse_iterator(i)) == &*(i -
1) (24.4.1/1)
is qualified as fundamental.
Why this restriction related to arrays (24.4.1/2) must be also applied
to sets and maps?
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: "kostas" <skolarik@gmail.com>
Date: Mon, 9 Apr 2007 15:55:31 CST Raw View
On Apr 2, 6:53 am, a...@acm.org ("Andrew Koenig") wrote:
> What could you do with such a facility that you could not do with
> upper_bound?
Sorry, I missed that point. Probably because I hadn't seriously
considered
from the begining the use of reverse iterators. I hadn't realized that
upper_bound and
lower_bound when adapted to reverse iterators give the reverse
lower_bound and
upper_bound accordingly.
On Apr 3, 8:18 pm, kuy...@wizard.net wrote:
> Compared with the logarithmic time for a lower_bound() calculation,
> the amortized constant time associated with decrementing a bidirection
> iterator shouldn't be a big deal.
I think that, strictly speaking, amortization here is irrelevant. The
time is amortized
constant as far as tree traversal is considered. Here the best you can
say is that it is
constant on average, worst case being logarithmic. But you are right,
usually it's not
a big deal, although finding upper_bound from lower_bound is not a big
deal either.
Nevertheless i understand that the missing of an iterator before the
beginning is crucial.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: "kostas" <skolarik@gmail.com>
Date: Thu, 29 Mar 2007 17:47:01 CST Raw View
Wouldn't be useful a reverse lower_bound method for sets and maps of
STL? I mean a function that would return an iterator to the the
element less or equal to the searching value(assuming ascending
ordering).
Decrementing the lower_bound is not so easy-going as it may seems. It
may be as time consuming as lower_bound itself and thus not
acceptable when efficiency matters.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: "Andrew Koenig" <ark@acm.org>
Date: Sat, 31 Mar 2007 16:37:34 CST Raw View
"kostas" <skolarik@gmail.com> wrote in message
news:1175207237.407969.224930@d57g2000hsg.googlegroups.com...
> Wouldn't be useful a reverse lower_bound method for sets and maps of
> STL? I mean a function that would return an iterator to the the
> element less or equal to the searching value(assuming ascending
> ordering).
I don't see that such a function would be useful.
Consider the definition of lower_bound: If there is an element with the
given value, the result is the first element with that value. If there is
no element with the given value, the result is the first element >= that
value or end().
What would your reverse lower_bound do? There are two cases:
1) An element with the given value exists. In that case, presumably you
still want to return the first element with that value; because if you
wanted the last element with that value, you could have used upper_bound.
2) No element with the given value exists. In that case, presumably you
want to return an iterator referring to the last element before the given
value.
But in case 2, what do you do if the value sought is less than the first
element? There is no off-the-beginning iterator, so what should would you
like the function to return?
> Decrementing the lower_bound is not so easy-going as it may seems. It
> may be as time consuming as lower_bound itself and thus not
> acceptable when efficiency matters.
Why do you think so?
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: "kostas" <skolarik@gmail.com>
Date: Sun, 1 Apr 2007 14:43:32 CST Raw View
On Apr 1, 1:37 am, "Andrew Koenig" <a...@acm.org> wrote:
> But in case 2, what do you do if the value sought is less than the first
> element? There is no off-the-beginning iterator, so what should would you
> like the function to return?
I think the solution here should be the reverse lower_bound to return
a reverse iterator.
Of course current implementations of reverse iterators decrement
normal iterators in dereferencing.
>
> > Decrementing the lower_bound is not so easy-going as it may seems. It
> > may be as time consuming as lower_bound itself and thus not
> > acceptable when efficiency matters.
>
> Why do you think so?
Because adjacent values in tree structures are not always in nearby
tree nodes.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: ark@acm.org ("Andrew Koenig")
Date: Mon, 2 Apr 2007 03:53:16 GMT Raw View
"kostas" <skolarik@gmail.com> wrote in message
news:1175383936.092244.143130@q75g2000hsh.googlegroups.com...
> On Apr 1, 1:37 am, "Andrew Koenig" <a...@acm.org> wrote:
>> But in case 2, what do you do if the value sought is less than the first
>> element? There is no off-the-beginning iterator, so what should would
>> you
>> like the function to return?
>
> I think the solution here should be the reverse lower_bound to return
> a reverse iterator.
> Of course current implementations of reverse iterators decrement
> normal iterators in dereferencing.
What could you do with such a facility that you could not do with
upper_bound?
>> > Decrementing the lower_bound is not so easy-going as it may seems. It
>> > may be as time consuming as lower_bound itself and thus not
>> > acceptable when efficiency matters.
>>
>> Why do you think so?
> Because adjacent values in tree structures are not always in nearby
> tree nodes.
But if that's true, why do you think that your proposed reverse lower_bound
function would be any faster?
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: "kostas" <skolarik@gmail.com>
Date: Mon, 2 Apr 2007 14:11:53 CST Raw View
On Apr 2, 6:53 am, a...@acm.org ("Andrew Koenig") wrote:
> But if that's true, why do you think that your proposed reverse lower_bound
> function would be any faster?
I will try to clarify further my point.
In case the given value does not exist, lower_bound has already found
both the last before and the first after that value. By convention
returns the second (I cant see a reason why the one is preferable to
the other, trees are symmetric structures)
Now if we eventually agree that obtaining the one from the other using
decrement (or increment) operators is not so trivial (fast actually)
as it is with vector iterators for example, why don't we provide a
function to take it right away.
Furthermore, if we agree again that the reverse iterator is the only
option, I cant see any technical difficulty in providing an off-the-
beginning position for trees so as the reverse iterators for sets and
maps can be implemented more efficiently.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: kuyper@wizard.net
Date: Tue, 3 Apr 2007 11:18:02 CST Raw View
kostas wrote:
.
> I will try to clarify further my point.
> In case the given value does not exist, lower_bound has already found
> both the last before and the first after that value. By convention
> returns the second (I cant see a reason why the one is preferable to
> the other, trees are symmetric structures)
The reason is relatively simple. The lower_bound() and upper_bound()
functions are supposed to return iterators that bound the range where
matching elements of the container can be found. If there are no such
elements, they're supposed to indicate an empty range, which means
they must be equal to each other. They could either both return
iterators pointing to the first bounding element, or they could both
return iterators point to the second bounding element. Only the latter
choice is compatible with the value that upper_bound() is supposed to
return when there are matching elements.
> Now if we eventually agree that obtaining the one from the other using
> decrement (or increment) operators is not so trivial (fast actually)
> as it is with vector iterators for example, why don't we provide a
> function to take it right away.
Compared with the logarithmic time for a lower_bound() calculation,
the amortized constant time associated with decrementing a bidirection
iterator shouldn't be a big deal.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]