ISO/ IEC JTC1/SC22/WG21 N0793

                        Doc.      X3J16/95-0193
                        No.:      WG21/N0793
                        Date:     September 26, 1995
                        Project:  C++ Standard Library
                        Reply to: Pete Becker
                                  pete@borland.com
 
 
            Clause 25 (Algorithms Library) Issues
 
Revision History:
     Version 1: September 26, 1995
 
Introduction:
     This document summarizes the open issues for clause 25,
including recommended actions, and indicates resolutions as
they occur.
 
Issue Number: 001
Title:        find_end() unimplementable
Section:      25.1.3
Requester:    Nathan Myers, myersn@roguewave.com
Owner:
Status:       Open
 
Description:
 
     In the description of the algorithm
 
     template <typename FwdIter1, typename FwdIter2>
          FwdIter find_end(FwdIter1 first1, FwdIter1 last1,
                         FwdIter2 first2, FwdIter2 last2)
 
     find_end is supposed to return an iterator i such that
     for 0 < n < (last2-first2), the following holds:
 
     *(i-n) == *(last2-n)
 
     This is impossible, because for n==0, *(last2-0) is
     undefined. Also, the complexity "at most (last1-first1)
     applications of the predicate" is unimplementable.
 
Discussion:
 
     Here is what find_end() is doing:
 
Given a sequence:
 
     L__________xxxxxxxxx_______________xxxxxxxxx_____________|
     ^                                  ^       ^^             ^
     first1                             H       FG           last1
 
     and another sequence
 
     xxxxxxxxx
     ^        ^
     first1   last2
 
     it is trying to say that find_end() should return F, or
     last1 if the  subsequence is not found. This is quite
     peculiar, for two reasons. First, an iterator usually
     refers to the first or the next-after-last  element in
     a sequence; here, it refers to the last element.
     Second, because forward iterators can't be stepped
     back, the last element is the least useful position to
     return.
 
     The minimal change to implement the above semantics
     correctly would be to say it returns i so that
 
     *(i-n) == *(last2-n-1)
 
     but this would leave the function behaving quite
     peculiarly.
 
     It would be more consistent to return G, or both more
     useful *and* more consistent to return H. (If the
     former, then "not found" would be indicated by
     returning first1, not last1.) I recommend the latter.
 
     The complexity of such a search is clearly quadratic.
     The search can be specialized for better efficiency if
     the iterators are bi-directional, though the worst-case
     complexity is the same.
 
Proposed Resolution:
 
     1. Change the description of find_end() to require that
     the following expressions hold:
 
     *(i+n) == *(first2+n)
     pred(*(i+n), *(first2+n)) == true
 
     2. Change the complexity requirement "no more than
     (last2-first2)*(last1-first1-(last2-first2)+1)
     applications" of the predicate.
 
Issue Number: 002
Title:        find_first_of() unimplementable
Section:      25.1.4
Requester:    Nathan Myers, myersn@roguewave.com
Owner:
Status:       Open
 
Description:
 
     In the description of the algorithm
 
     template <typename FwdIter1, typename FwdIter2>
          FwdIter find_first_of(FwdIter1 first1, FwdIter1
     last1,
                             FwdIter2 first2, FwdIter2
                         last2)
 
     it is supposed to return an iterator i such that for 0
     < n < (last2-first2), the following holds:
 
     *i == *(first2+n)
     pred(i,first2+n) == true
 
     Both are wrong: the elements in [first1,last1) need not
     all be equal to anything, and pred() applies to element
     values, not iterator values. Finally, the complexity
     spec is meaningless, because it refers to the result of
     the function as if it were numeric, and takes only 3
     arguments.
 
Discussion:
 
     This function is intended to be similar to
     basic_string<>::find_first_of, or the C library
     function strchr(). It is supposed to test each element
     in the first range against a set of elements in the
     second, until it finds a match.
 
Proposed Resolution:
 
     Change the description to the following:
 
     Effects: Finds an element that matches one of a set of
          values.
     Returns: The first iterator i in the range [first1,
          last1) such that for some j in the range [first2,
          last2), the following conditions hold: *i == *j,
          pred(*i,*j) == true. Returns last1 if no such
          element is found.
     Complexity: At most (i-first1)*(last2-first2)+(j-
          first2)+1 applications of the corresponding
          predicate.
 
Issue Number: 003
Title:        adjacent_find, min_element, and max_element
              unimplementable
Section:      25.1.5, 25.3.7.3, 25.3.7.4
Requester:    Meng Lee, lee@hpl.hp.com
Owner:        Nathan Myers, myersn@roguewave.com
Status:       Open
 
Description:
 
     The algorithms adjacent_find, min_element, and
     max_element are specified to take Input Iterators, and
     return an iterator value that might be any distance
     back from the last element examined.  This is
     impossible, because Input Iterators are only useful for
     one "pass"; snapshots of the iterator are useless. (In
     fact, the sample HP implementation depends on
     operations not provided in the input iterators, so
     trying to use these algorithms on an input iterator
     would have failed anyway.)
 
Discussion:
 
     These algorithms demand more of their iterator
     arguments than an Input Iterator provides. The
     semantics they use are those of Forward Iterator. They
     should be declared as such.
 
Proposed Resolution:
 
     In [lib.alg.adjacent.find], and also in the Clause 25
     synopsis, declare the function templates adjacent_find
     as follows:
 
     template <class ForwardIterator>
     ForwardIterator adjacent_find(ForwardIterator first,
          ForwardIterator last);
 
     template <class ForwardIterator, class BinaryPredicate>
     ForwardIterator adjacent_find(ForwardIterator first,
          ForwardIterator last, BinaryPredicate pred);
 
     In [lib.alg.min.max], and also in the Clause 25
     synopsis, declare the function templates min_element
     and max_element as follows:
 
     template <class ForwardIterator>
     ForwardIterator min_element(ForwardIterator first,
          ForwardIterator last);
 
     template <class ForwardIterator>
     ForwardIterator max_element(ForwardIterator first,
          ForwardIterator last);
 
Issue Number: 004
Title:        Relaxing iterator requirements to forward
              iterator for certain algorithms
Section:      25.2.9.1, 25.2.9.2, 25.2.10.1, 25.2.10.2,
              25.2.11, 25.2.12.1, 25.2.12.2, 25.3.1.1,
              25.3.1.2, 25.3.4.2
Requester:
Owner:
Status:       Open
 
Description:
 
     Box 97 in the March 27, 1995 draft says:
 
     For the following algorithms: reverse, rotate,
     partition, random_shuffle, stable_partition, sort,
     stable_sort and inplace_merge the iterator requirement
     can be relaxed to ForwardIterator. These algorithms
     could then be dispatched upon the iterator category
     tags to use the most efficient implementation for each
     iterator category. We have not included the relaxation
     at this stage since it is not yet fully implemented.
 
Discussion:
 
     This is an editorial comment about the state of the HP
     implementation. It should not limit what the standard
     requires. If this is implementable as described it
     should be part of the standard.
 
Proposed Resolution:
 
     In [lib.reverse] and in the Clause 25 synopsis, declare
     the function template reverse as follows:
 
     template <class ForwardIterator>
     void reverse(ForwardIterator first, ForwardIterator
     last);
 
     In [lib.reverse.copy] and in the Clause 25 synopsis,
     declare the function template reverse_copy as follows:
 
     template <class ForwardIterator, class OutputIterator>
     OutputIterator
     reverse_copy(ForwardIterator first, ForwardIterator
     last,
                  OutputIterator result);
 
     In [lib.rotate] and in the Clause 25 synopsis, declare
     the function template rotate as follows:
 
     template <class ForwardIterator>
     void rotate( ForwardIterator first, ForwardIterator
     middle,
                  ForwardIterator last);
 
     In [lib.rotate.copy] and in the Clause 25 synopsis,
     declare the function template rotate_copy as follows:
 
     template <class ForwardIterator, class OutputIterator>
     OutputIterator
     rotate_copy(ForwardIterator first, ForwardIterator
     middle,
                 ForwardIterator last, OutputIterator
     result);
 
     In [lib.alg.random.shuffle] and in the Clause 25
     synopsis, declare the function templates random_shuffle
     as follows:
 
     template <class ForwardIterator>
     void random_shuffle(ForwardIterator first,
                         ForwardIterator last);
 
     template <class ForwardIterator, class
     RandomNumberGenerator>
     void random_shuffle(ForwardIterator first,
                         ForwardIterator last,
                      RandomNumberGenerator& rand);
 
     In [lib.partition] and in the Clause 25 synopsis,
     declare the function template partition as follows:
 
     template <class ForwardIterator, class Predicate>
     ForwardIterator
     partition(ForwardIterator first,
               ForwardIterator last, Predicate pred);
 
     In [lib.stable.partition] and in the Clause 25
     synopsis, declare the function template
     stable_partition as follows:
 
     template <class ForwardIterator, class Predicate>
     ForwardIterator
     stable_partition(ForwardIterator first,
                      ForwardIterator last, Predicate pred);
 
     In [lib.sort] and in the Clause 25 synopsis, declare
     the function templates sort as follows:
 
     template <class ForwardIterator>
     void sort(ForwardIterator first, ForwardIterator last);
 
     template <class ForwardIterator, class Compare>
     void sort(ForwardIterator first, ForwardIterator last,
               Compare comp);
 
     In [lib.stable.sort] and in the Clause 25 synopsis,
     declare the function templates stable_sort as follows:
 
     template <class ForwardIterator>
     void stable_sort(ForwardIterator first, ForwardIterator
     last);
 
     template <class ForwardIterator, class Compare>
     void stable_sort(ForwardIterator first, ForwardIterator
     last,
                      Compare comp);
 
     In [lib.inplace.merge] and in the Clause 25 synopsis,
     declare the function templates inplace_merge as
     follows:
 
     template <class ForwardIterator>
     void inplace_merge(ForwardIterator first,
                        ForwardIterator middle,
                        ForwardIterator last);
 
     template <class ForwardIterator, class Compare>
     void inplace_merge(ForwardIterator first,
                        ForwardIterator middle,
                        ForwardIterator last,
                        Compare comp);
 
Issue Number: 005
Title:        Extraneous footnote
Section:      25.1.9
Requester:    Pete Becker
Owner:        Pete Becker
Status:       Open
 
Description:
 
     The ?Returns:? section of [lib.alg.search] contains a
     footnote that discusses HP?s choice of algorithms in
     their implementation. Although this is non-normative,
     it contains language like ?The Knuth-Morris-Pratt
     algorithm is not used here.? This footnote should be
     removed, or reworded so that it does not purport to be
     normative.
 
Discussion:
 
     This footnote appears to have been part of HP?s
     discussion of their implementation. It is probably not
     appropriate as part of the standard.
 
Proposed Resolution:
 
     Remove the footnote from [lib.alg.search].
 
Issue Number: 006
Title:        Missing description of direction of copy
Section:      25.2.1
Requester:    Pete Becker
Owner:        Pete Becker
Status:       Open
 
Description:
 
     In [lib.copy.backward] the direction of the copy is
     specified as "starting from last-1 and proceeding to
     first." [lib.copy] has no such specification,
     suggesting that the direction of copying is immaterial.
 
Discussion:
 
     It should not be left to the reader to infer that
     [lib.copy] requires forward copying. It should be
     explicit.
 
Proposed Resolution:
 
     Change the "Effects:" section of [lib.copy] to read:
 
     Effects: Copies elements in the range [first, last)
     into the range [result, result + (last - first) )
     starting from first and proceeding to last. For each
     non-negative integer N < (last - first), performs
     *(result + n) = *(first + n).
 
Issue Number: 007
Title:        Missing constraint prohibiting overlapping
              ranges for copying algorithms
Section:      25.2.4.2, 25.2.7.2, 25.2.8.2
Requester:    Pete Becker
Owner:        Pete Becker
Status:       Open
 
Description:
 
     The copying versions of the algorithms do not specify
     that their input and output ranges cannot overlap.
 
Proposed Resolution:
 
     In [lib.replace.copy], [lib.remove.copy], and
     [lib.unique.copy] add the following constraint:
 
     Requires: The ranges [first, last) and [result, result
     + (last - first) ) shall not overlap.
 
Issue Number: 008
Title:        Incorrect return type for stable_partition
Section:      25.2.12.2
Requester:    Pete Becker
Owner:        Pete Becker
Status:       Open
 
Description:
 
     The declaration of stable_partition uses a return type
     of ForwardIterator, which is not defined. Since the
     function takes two parameters of type
     BidirectionalIterator, the return type should also be
     BidirectionalIterator.
 
Proposed Resolution:
 
     In [lib.stable.partition] and in the Clause 25
     synopsis, declare the template stable_partition as
     follows:
 
     template <class BidirectionalIterator, class Predicate>
     BidirectionalIterator
     stable_partition(BidirectionalIterator first,
                      BidirectionalIterator last, Predicate
     pred);
 
Issue Number: 009
Title:        Undefined order in partial_sort
Section:      25.3.1.3
Requester:    Pete Becker
Owner:        Pete Becker
Status:       Open
 
Description:
 
     The description of the effects of partial_sort says
     that it places the rest of the elements in an undefined
     order. Given the massive confusion caused by the word
     "undefined", this should probably say "unspecified".
 
Discussion:
 
     This is not strictly necessary, since it does not use
     the term "undefined behavior", but it is probably just
     a bit clearer to say that the order is unspecified.
 
Proposed Resolution:
 
     Change the last sentence of the "Effects:" section of
     [lib.partial.sort] to read as follows:
 
     The rest of the elements in the range [middle, last)
     are placed in an unspecified order.
 
Issue Number: 010
Title:        set difference not defined
Section:      25.3.5.4
Requester:    Pete Becker
Owner:        Pete Becker
Status:       Open
 
Description:
 
     The description of set_difference says that it
     "constructs a sorted difference of the elements from
     the two ranges." It should be more specific.
 
Discussion:
 
     Set difference is a legitimate term of art in
     mathematics, but is sufficiently obscure that users
     might not be able to readily determine what it means.
     The standard should describe this algorithm in terms of
     its effects.
 
Proposed Resolution:
 
     Change the "Effects:" section of [lib.set.difference]
     to read as follows:
 
     Effects: Copies the elements of the range [first1,
     last1) which are not present in the range [first2,
     last2) to the range beginning at result. The elements
     in the constructed range are sorted.
 
Issue Number: 011
Title:        set symmetric difference not defined
Section:      25.3.5.5
Requester:    Pete Becker
Owner:        Pete Becker
Status:       Open
 
Description:
 
     The description of set_symmetric_difference says that
     it "constructs a sorted symmetric difference of the
     elements from the two ranges." It should be more
     specific.
 
Discussion:
 
     Set symmetric difference is a legitimate term of art in
     mathematics, but is sufficiently obscure that users
     might not be able to readily determine what it means.
     The standard should describe this algorithm in terms of
     its effects.
 
Proposed Resolution:
 
     Change the "Effects:" section of
     [lib.set.symmetric.difference] to read as follows:
 
     Effects: Copies the elements of the range [first1,
     last1) which are not present in the range [first2,
     last2), and the elements of the range [first2, last2)
     which are not present in the range [first1, last1), to
     the range beginning at result. The elements in the
     constructed range are sorted.