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.