Why is it that some algorithms that don't change their input (eg
lower_bound(), upper_bound(), binary_search(), min_element(),
max_element() ) which do not change their input take forward iterators
(as opposed to input iterators)?

Prateek Karandikar

--                                                     --
To iterate is human, to recurse divine. -L. Peter Deutsch
--                                                     --

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Prateek" <kprateek88@gmail.com> wrote in message
news:1113311986.131684.132890@f14g2000cwb.googlegroups.com...

> Why is it that some algorithms that don't change their input (eg
> lower_bound(), upper_bound(), binary_search(), min_element(),
> max_element() ) which do not change their input take forward iterators
> (as opposed to input iterators)?

One reason might be that when you increment an input iterator, it is allowed
to invalidate any copies of the previous iterator value.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

In article <1113311986.131684.132890@f14g2000cwb.googlegroups.com>,
Prateek <kprateek88@gmail.com> wrote:

> Why is it that some algorithms that don't change their input (eg
> lower_bound(), upper_bound(), binary_search(), min_element(),
> max_element() ) which do not change their input take forward iterators
> (as opposed to input iterators)?
>
  Input iterators [those that are not foreward iterators] are incapable
of holding history. All the mentioned algorithms either require history
to perform or return an iterator in the [begin,end) sequence. The
latter requires history after the application of the algorithm.
Example:

template <class For>
For min_element(For begin,For end)
{
   if(begin==end) return end;
   For ans(begin);   // history #1
   for(++begin;begin!=end;++begin)
   {
      if(*begin < *ans) ans = begin; // history #2
   }
   return ans; // history #3
}
All the lines marked history above are not valid for strictly input
iterators.  The binary searching algorithms use history to restrict the
range used in the next iteration in addition to returning an iterator
in
the input range. Binary_search returns bool but still uses history to
restrict the range to check as it iterates to the result.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Prateek wrote:
> Why is it that some algorithms that don't change their input (eg
> lower_bound(), upper_bound(), binary_search(), min_element(),
> max_element() ) which do not change their input take forward iterators
> (as opposed to input iterators)?

Input iterators requirements are simply not good enough for those
algorithms.

The key point is stated explicitly in table 72 (=A724.1.1) as the
post-condition of the expression ++r: "any copies of the previous value
of r are no longer required either to be dereferenceable or to be in the
domain of =3D=3D." Because of this very relaxed "requirement", it has ver=
y
little sense to return an input iterator from an algorithm. Consider,
for example, max_element: you have to scan the entire range to find the
largest element, however as soon as you increment the "running"
iterator, the "candidate" iterator you had pointing to the
largest-so-far element becomes practically useless.

For binary_search the reason is a bit different, because it does not
return an iterator, so the previous argument does not apply. In this
case, the requirement above forces the algorithm to degenerate in a
linear search. Despite the obvious contradiction, the algorithm couldn't
in any case satisfy the complexity requirement "At most log(last -
first) + 2 comparisons".

HTH,

Alberto

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]