Le 19/12/10 17:44, Jeff Flinn a écrit :
jacob navia wrote:
I'm not sure what the standard states about mismatch pre-conditions,
As far as I can see it says absolutely nothing. See 25.1.7 "Mismatch"
in the n1905 C++ standard document.
but
based on its arguments being an input iterator range and a comparable
iterator, it's apparent the sequence pointed to by the comparable
iterator must be at least as large as the input range.
Maybe. You can *deduce* that if you want, but it is not SPECIFIED.
In "The C++
Standard Library" by Josuttis (a much more complete reference than the
one you cited, IMO) states on pg358: "The caller must ensure that the
range starting with cmpBeg contains enough elements.
Yes, that is a sensible comment, but even that doesn't specify what
happens when the error arises.
ERROR ANALYSIS is completely missing, period.
That is one of the biggest differences between the library I am writing
and the C++ STL: I try to specify exactly what will happen for each
of the "borderline" conditions. For instance in this case I specified
that the matching search stops when the shorter container is exhausted
and the result is one more than the length of the shorter container.
This follows design principles like:
(1) be forgiving. Programming errors should never lead to a crash but
should be acnowledged by the software and an orderly return code
shoud notify the calling software of the condition.
(2) Error conditions can be converted in features: instead of crashing
when an error occurs, you return a meaningful result.
This design minimizes the loop iterator comparisons.
At the enormous cost of crashing at the slightest error. You are saving
1 integer comparison and a conditional jump at each iteration, what is
absolutely NOTHING. The cost of a crash is much more serious. This is
exactly the kind of philosophy that produces brittle software that is
always just crashing around.
When either range
could be the longest, check the range sizes and swap the input range
with the comparison range, and swap the resulting pair of iterators.
Great. This produces the same result as the specifications I outlined
above.
Why not incorporate those specs into the specification of "Mismatch"?
When the pre-condition is met, there is no undefined behavior, and the
results for all cases are easily rationalized: if there is no mismatch
result.first == range1 end, result.second == range2 begin + range1 size.
Since range2 size >= range1 size, the result is well defined for all
sizes of range1 and range2.
`
Sure, WHEN the preconditions are met. Error analysis investigates what
happens when those preconditions are NOT met, and prescribes a defined
behavior for exceptional circumstances. That is correctly specified
software.
As I said elsewhere the machines running today's software are thousands
of times faster than merely 10 years ago. It is completely ridiculous
to go on trying to take enormous risks for the sake of saving an integer
comparison and a conditional jump, what in today's CPUs counts as a
few cycles at 2GHZ or more.
Why?
Because the mindset of people designing software today is still in the
times when "efficiency" was counted on cycles.
Obviously "Mismatch" will spend millions of cycles in the searech
through a generalized container, comparing each element with another,
fetching both, calling the predicate, retrieving the result,
advancing both iterators, etc.
In THAT context, an integer comparison and a conditional jump are
NOTHING AT ALL.
In any case, in my container library those cases are specified. I am
rewriting the STL in C. Yes, pure C.
I have implemented iterators, containers, abstract containers (what
C++ calls "algorithms"), and many other things like automatic
saving and loading to/from disk, and other goodies that the STL never
even touches.
jacob
jacob