[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

lower_bound() misbehaving

Steve555

12/7/2008 4:02:00 PM

In the case where lower_bound() doesn't find the value, my book
(O'Reilly STL) states "...the iterator points to the position of the
first item greater than the value.

In my code I check that the value doesn't exist, but the iterator
points to it anyway!:

MovieRatingVector::iterator iter;
for(iter = mMovieRatings.begin(); iter != mMovieRatings.end(); ++iter)
{
thisMovieID = (*iter).movieID;
thisRating = (*iter).rating;
cout << thisMovieID<< " "<< thisRating<<endl;

}
Produces:
457 3
3151 1
11607 3
12155 3
12911 4

This is correct.

Then, suspecting a problem, immediately I test for movieID = 16469
(which I know ISN'T there)

MovieRating pair;
pair.movieID = 16469;
pair.rating = 0;
iter = std::lower_bound(mMovieRatings.begin(), mMovieRatings.end(),
pair);
cout<< (*iter).movieID << " "<<(*iter).rating;
Produces:
16469 3

What's happened? Has it just happened to find the value 16469 in an
adjacent block of memory?
And even if it has, why return it? How do I guard against this?
I don't know if it's just lucky coincidence, but the following worked
on the first first few thousand such checks without error: (I expected
that, per O'Reilly, it would be pointing to a value greater than my
value, NOT equal)

if((*iter).movieID == inMovieID)
return outRating;
else
return 0;

-----------------------
BTW, this is the functor:
bool operator<(MovieRating lhs, MovieRating rhs) {
return lhs.movieID < rhs.movieID;
}
2 Answers

Pete Becker

12/7/2008 4:11:00 PM

0

On 2008-12-07 11:02:24 -0500, Steve555 <foursheds@btinternet.com> said:

> In the case where lower_bound() doesn't find the value, my book
> (O'Reilly STL) states "...the iterator points to the position of the
> first item greater than the value.
>
> In my code I check that the value doesn't exist, but the iterator
> points to it anyway!:
>
> MovieRatingVector::iterator iter;
> for(iter = mMovieRatings.begin(); iter != mMovieRatings.end(); ++iter)
> {
> thisMovieID = (*iter).movieID;
> thisRating = (*iter).rating;
> cout << thisMovieID<< " "<< thisRating<<endl;
>
> }
> Produces:
> 457 3
> 3151 1
> 11607 3
> 12155 3
> 12911 4
>
> This is correct.
>
> Then, suspecting a problem, immediately I test for movieID = 16469
> (which I know ISN'T there)

So, in the list above, what is the first value that's greater than 16469?

It's a little misleading to say that the iterator points to the
position of the first item greater than the value, because that item
might not exist.

>
> What's happened? Has it just happened to find the value 16469 in an
> adjacent block of memory?

Your code dereferenced the end() iterator.

> And even if it has, why return it? How do I guard against this?

If you're going to look at the element, first check whether the
iterator is equal to end(). If you're going to insert a new element at
that position, just do it; no check needed.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Steve555

12/7/2008 4:36:00 PM

0

On 7 Dec, 16:11, Pete Becker <p...@versatilecoding.com> wrote:
> On 2008-12-07 11:02:24 -0500, Steve555 <foursh...@btinternet.com> said:
>
>
>
> > In the case where lower_bound() doesn't find the value, my book
> > (O'Reilly STL)  states "...the iterator points to the position of the
> > first item greater than the value.
>
> > In my code I check that the value doesn't exist, but the iterator
> > points to it anyway!:
>
> > MovieRatingVector::iterator iter;
> > for(iter = mMovieRatings.begin(); iter != mMovieRatings.end(); ++iter)
> > {
> >            thisMovieID = (*iter).movieID;
> >            thisRating = (*iter).rating;
> >            cout << thisMovieID<< "  "<< thisRating<<endl;
>
> > }
> > Produces:
> > 457  3
> > 3151  1
> > 11607  3
> > 12155  3
> > 12911  4
>
> > This is correct.
>
> > Then, suspecting a problem,  immediately I test for movieID = 16469
> > (which I know ISN'T there)
>
> So, in the list above, what is the first value that's greater than 16469?
>
> It's a little misleading to say that the iterator points to the
> position of the first item greater than the value, because that item
> might not exist.
>
>
>
> > What's happened? Has it just happened to find the value 16469 in an
> > adjacent block of memory?
>
> Your code dereferenced the end() iterator.
>
> > And even if it has, why return it? How do I guard against this?
>
> If you're going to look at the element, first check whether the
> iterator is equal to end(). If you're going to insert a new element at
> that position, just do it; no check needed.
>
> --
>   Pete
> Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
> Standard C++ Library Extensions: a Tutorial and Reference
> (www.petebecker.com/tr1book)

Thanks for the clear explanation Pete, I understand why it's pointing
to end() now.

Steve