"STL from the Ground Up"
- From: "Stephen Howe" <sjhoweATdialDOTpipexDOTcom>
- Date: Wed, 6 Feb 2008 22:03:02 -0000
Hi
Since "STL from the Ground Up" is avaliable on the shelf of a programmer at
work by Shildt, you-know-who's, never-done-anything-wrong,
motives-always-good author, I thought I would check it out.
Copyright is dated 1999.
1. I was shocked to find on page 227 the wrong return value described in the
event of lower_bound(), upper_bound() and equal_range():
"template <class ForIter, class T> pair <ForIter,
ForIter>equal_range(ForIter start, ForIter end, const T &val);
template <class ForIter, class T> ForIter lower_bound(ForIter start, ForIter
end, const T &val);
template <class ForIter, class T> ForIter upper_bound(ForIter start, ForIter
end, const T &val);
The lower_bound algorithm returns an iterator to the first element that
matchs val, upper_bound returns an iterator one beyond the last matching
element, and equal_range returns a pair of iterators that point to the lower
and upper bounds. If the sought-after element is not in the sequence, these
functions return iterators to end()."
Well that is wrong. Amazingly so.
Given the sequence of integers 1,3,3,3,5,7 in a vector v, no other
elements, searching for 4 using
vector<int>::iterator it1 = lower_bound(v.begin(), v.end(), 4);
vector<int>::iterator it2 = upper_bound(v.begin(), v.end(), 4);
then both it1, it2 will be pointing at 5, the place at which 4 can be
inserted while still maintaing the sorted sequence. it1 and it2 will not be
v.end().
it1 and it2 would be v.end() if the element being searched for was greater
than the maximum element.
2. On page 236, it says
"IN DEPTH
Although the STL supplies a left-rotate algorithm, it does not provide one
that right-rotates.
At first this might seems a serious flaw in the STL's design, or at least a
troublesome omission.
But neither is the case. To perform a right-rotate you simply use the
rotate() algorithm, but call it using reverse iterators.
Since reverse iterators run backwards, the net effect of such a call is that
right-rotate is performed on the sequence!"
He is right here, you can do this. But it completely unnecessary to use
reverse iterators.
He does not seem to be aware that a right-rotate by 2 elements is equivalent
to a left-rotate by all elements - 2.
His
rotate(v.rbegin(), v.rbegin()+2, v.rend());
is equivalent to
rotate(v.begin(), v.begin()+v.size() - 2 , v.end());
Seems like an authors mental block.
I am wondering what other horrors are in the book.
Stephen Howe
.
- Follow-Ups:
- Re: "STL from the Ground Up"
- From: Jon Harrop
- Re: "STL from the Ground Up"
- From: Anders Karlsson
- Re: "STL from the Ground Up"
- From: user923005
- Re: "STL from the Ground Up"
- Prev by Date: Re: "Sorting" assignment
- Next by Date: Re: "Sorting" assignment
- Previous by thread: best language
- Next by thread: Re: "STL from the Ground Up"
- Index(es):
Relevant Pages
|
