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.