I now believe that the CD2 specification for find_end is correct. I
mis-interpeted the meaning of a half-open iterator range. In addition,
I believe the range for iterator i is open instead of close to handle
the case where the search sequence may be empty.

 -- Wayne

On 02 Jul 97 08:40:06 GMT, ouchida@sirius.com (Wayne B. Ouchida)
wrote:

 >I have a question about the CD2 specification for find_end. It either
 >has an error or I do not understand the specification. For example,
 >the CD2 specification for find_end is the following:
 >
 >Line
 > 1 Effects:
 > 2  Finds a subsequence of equal values in a sequence.
 > 3 Returns:
 > 4  The last iterator i in the range [first1, last1 - (last2-first2))
 > 5  such that for any non-negative integer n < (last2-first2), the
 > 6  following corresponding conditions hold: *(i+n) == *(first2+n),
 > 7  pred(*(i+n),*(first2+n)) != false. Returns last1 if no such itera-
 > 8  tor is found.
 > 9 Complexity:
 >10  At most (last2 - first2) * (last1 - first1-(last2 - first2)+1)
 >11  applications of the corresponding predicate.
 >
 >Shouldn't line 4 be
 >
 >   The last iterator i in the range [first1, last1 - (last2-first2)+1)
 >         or equivalently,
 >   The last iterator i in the range [first1, last1 - (last2-first2)]
 >
 >
 >For example, consider the following integer sequences
 >        sequence1: { 1, 2, 3, 4, 5}
 >        sequence2: {4, 5}
 >
 >Using the above specification, the range i for sequence1 contains the
 >following elements 1, 2 and 3. The range ends with 4, but does not
 >include it. Therefore, if sequence2 is the search pattern, the find
 >will fail for this case even though sequence2 is contained within
 >sequence1.
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

I have a question about the CD2 specification for find_end. It either
has an error or I do not understand the specification. For example,
the CD2 specification for find_end is the following:

Line
 1 Effects:
 2  Finds a subsequence of equal values in a sequence.
 3 Returns:
 4  The last iterator i in the range [first1, last1 - (last2-first2))
 5  such that for any non-negative integer n < (last2-first2), the
 6  following corresponding conditions hold: *(i+n) == *(first2+n),
 7  pred(*(i+n),*(first2+n)) != false. Returns last1 if no such itera-
 8  tor is found.
 9 Complexity:
10  At most (last2 - first2) * (last1 - first1-(last2 - first2)+1)
11  applications of the corresponding predicate.

Shouldn't line 4 be

   The last iterator i in the range [first1, last1 - (last2-first2)+1)
         or equivalently,
   The last iterator i in the range [first1, last1 - (last2-first2)]


For example, consider the following integer sequences
        sequence1: { 1, 2, 3, 4, 5}
        sequence2: {4, 5}

Using the above specification, the range i for sequence1 contains the
following elements 1, 2 and 3. The range ends with 4, but does not
include it. Therefore, if sequence2 is the search pattern, the find
will fail for this case even though sequence2 is contained within
sequence1.
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]