Topic: 25.1.7: mismatch algorithm: bad design
Author: Alberto Ganesh Barbati <AlbertoBarbati@libero.it>
Date: Wed, 8 Feb 2006 22:36:11 CST Raw View
Krzysztof ha scritto:
> 2. use mismatch; but the code is likely to cause undefined behaviour if the
> second sequence is longer than the first one. (BTW this should be
> explicitly noted in the standard, it is not).
It's the other way round. The behaviour is undefined if the second
sequence is shorter, not longer. It's true that it's not explicit in the
standard (at least I could not find any explicit reference), but all
books on the STL that I have read warn about that. Adding a
"precondition" paragraph wouldn't hurt, anyway. Notice that other
algorithms, for instance std::equal, have the same problem. However, I
don't think this can be accounted for "bad design" as the subject of
your post suggests, but that's my personal opinion.
> Neither solution is feasible. Can you please give me a hint?
Just write your own algorithm. It's not that difficult.
HTH,
Ganesh
---
[ 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 ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: kuyper@wizard.net
Date: Thu, 9 Feb 2006 12:50:18 CST Raw View
"Krzysztof elechowski" wrote:
> I was trying to solve the problem of comparing sequences (input iterators)
> of characters ignoring case. There are two possible solutions:
> 1. use lexicographical_compare; but I have no way to know whether the
> arguments are equal. This can perhaps be solved using a state pointer but
> the solution is clumsy.
If all that you want to know is whether or not they are equal, you can
use std::equal(). However, if you need a three-way branch, depending
upon whether one string is less than, equal to, or greater than
another, the simplest approach is two calls to
lexicographical_compare():
if(lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),
ignore_case)
/* a < b */;
else if(lexicographical_compare(b.begin(), b.end(), a.begin(), a.end(),
ignore_case)
/* b < a */;
else /* a==b */;
> 2. use mismatch; but the code is likely to cause undefined behaviour if the
> second sequence is longer than the first one. (BTW this should be
> explicitly noted in the standard, it is not).
The standard specifies that mismatch() evaluates *(first2+(i-first1))
for various values of i in the range [first1, last1). It's left up to
the reader to notice that this expression has unintended (and in some
cases, undefined) behavior if distance(first1,last1) is too large. I
think there's no limit to the number of warnings like that which could
be added to virtually any library function which uses pointers,
references, or iterators. At some point you have to count on the reader
working out the consequences of things like that, or the standard would
be several hundred pages longer.
A slightly more complicated but more efficient alternative to two calls
to lexicographical_compare would be to determine the lengths of the two
sequences, and then find() the first case-insensitive mismatch in the
length of shorter string. If no mismatch is found, order the sequences
by their lengths. If a mismatch is found, order them according to the
case-insensitive ordering of the characters at the point of first
mismatch. This isn't a pre-packaged algorithm, but it's also not a
difficult one to write.
---
[ 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 ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: krixel@qed.pl ("Krzysztof elechowski")
Date: Wed, 8 Feb 2006 14:07:45 GMT Raw View
I was trying to solve the problem of comparing sequences (input iterators)
of characters ignoring case. There are two possible solutions:
1. use lexicographical_compare; but I have no way to know whether the
arguments are equal. This can perhaps be solved using a state pointer but
the solution is clumsy.
2. use mismatch; but the code is likely to cause undefined behaviour if the
second sequence is longer than the first one. (BTW this should be
explicitly noted in the standard, it is not).
Neither solution is feasible. Can you please give me a hint?
Chris
---
[ 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 ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]