Re: [boost] Should we make an algorithm header?

From: John E. Potter (jpotter_at_[hidden])
Date: 2000-12-31 21:31:43

On Sun, 31 Dec 2000, Daryle Walker wrote:

> Should we make an algorithm header, with algorithms not covered by the
> standard C++ headers <algorithm> or <numerics>.  I got the idea from both me
> (in "more_io.zip") and Jeremy Siek (in "TokenIterator/tokenizer.zip") having
> altered versions of the 'mismatch' algorithm as an implementation detail.
> Both versions make the same type of change*, so maybe it can start a new
> header.

An algorithm library would be nice.  Not sure that it should contain
non-standard versions of the standard algorithms.  One common desire
is erase_if.  It would require someone to take responsibility for it.

> * The problem with the standard 'mismatch' algorithm is that is assumes that
> the second sequence is at least as long as the first sequence.  If it is the
> other way, you can switch the arguments, of course.  However, sometimes you
> have no way of knowing which sequence ends first (like the input stream
> iterators).  Comparing with an end element is still safe, so we made a
> version of the algorithm that checks both sequences for their end before
> proceeding.

The standard mismatch algorithm does not assume that the second sequence
is at least as long as the first.  It likely assumes that the two
sequences are the same length.  Consider:

    vector<int> v1, v2(1, 5);
    cout << equal(v1.begin(), v1.end(), v2.begin()) << endl;
 
The output is, of course, 1 (true).  Since the standard does not say
that the two must be the same length, any conforming implementation
must also work when the second is longer.

    cout << equal(v2.begin(), v2.end(), v1.begin()) << endl;

gives 0 (false) on at least one implementation.  Interesting that
a == b but b != a.

Maybe fixing the standard would be better than creating non-standard
versions.

Back to algorithms.  How about next/prev combination like those for
permutations?  Others?  Maintainers?

John