Questions about "mismatch"

[jacob navia]

Hi

I would like to know more about the C++ "mismatch" template function.

(1) If both sequences are empty, what is the result?
(2) If one sequence is shorter than the other, what is the result?

Thanks for any info. I use "The C++ STL" from Plauger/Stepanov
/Lee/Musser but they do not describe any special cases.

The web docs do the same. Are the special cases specified?
Or they are implementation defined?

jacob

 

[Jorgen Grahn]

Hi

I would like to know more about the C++ "mismatch" template function.

(1) If both sequences are empty, what is the result?
(2) If one sequence is shorter than the other, what is the result?

Since std::mismatch(A1, A2, B1) only takes three iterators, the second
sequence cannot safely be shorter than the first one -- we don't know
how long it it.

Apart from that, it's well-defined. std::mismatch(A1, A2, B1).second==A2
in both case (1) and (2).

/Jorgen

 

[jacob navia]

Le 18/12/10 16:21, Jorgen Grahn a écrit :

Since std::mismatch(A1, A2, B1) only takes three iterators, the second
sequence cannot safely be shorter than the first one -- we don't know
how long it it.

Apart from that, it's well-defined. std::mismatch(A1, A2, B1).second==A2
in both case (1) and (2).

/Jorgen

Thanks but precisely what do you mean?
If the second sequence *is* shorter, what is the result?

Crash?

Implementation defined?

That is what I wanted to know.

jacob

 

[Jorgen Grahn]

Le 18/12/10 16:21, Jorgen Grahn a écrit :

Thanks but precisely what do you mean?
If the second sequence *is* shorter, what is the result?

Crash?

Implementation defined?

That is what I wanted to know.

You got to know the answer to the other 3/4 of your question, I hope.

For this last case someone else has to answer. For me personally
it's sufficient to know that it's a bug to end up in that situation.
A crash indeed seems like a possibility.

/Jorgen

 

[jacob navia]

Le 18/12/10 16:59, Jorgen Grahn a écrit :

You got to know the answer to the other 3/4 of your question, I hope.

No, I do not know C++ very well, that is why I am asking questions here.
I am implementing a container library in plain C. Now, one of the most
important features of my library will be precisely that there is no
"undefined behavior", all behavior will be defined either

(1) As an error, with a defined result: an error code
(2) As a special case where the result is (maybe arbitrarily)
defined as being "X".

In this case I decided that when
the containers are of different length the result is
1+length of shorter container, if there is no difference
before that of course.

For this last case someone else has to answer. For me personally
it's sufficient to know that it's a bug to end up in that situation.
A crash indeed seems like a possibility.

/Jorgen

This looks (in my humble opinion) like a badly specified software.

Accepting that errors occur and that software must be able to handle
those errors producing known and similar results at each similar
error is the basis of my specification.

As far as I could read in the book from Plauger and others, nowhere
is explicitely required that the containers should have the same length.

It *can* be deduced but that doesn't give any answer to the question:

And what happens then?

I am surprised at this situation. Looking up in the C++ standard doesn't
help either. This "algorithm" is mentioned in page 635 ("Algorithms
Library") but nowhere is the length of the arguments mentioned. It is
specified at great length that the input iterators should be input
iterators, but there isn't any specification of borderline cases at all.

For instance the type of result in empty containers is not specified
either. This lead me to the question:

is it at all possible to create an input iterator of an empty container?

jacob

 

[jacob navia]

Le 18/12/10 17:18, Leigh Johnston a écrit :

Undefined Behaviour.

/Leigh

This is quite surprising. Any error leads to a crash, like in assembler



It could be more sensible to return the index of the first element
of the longer container isn't it?

If container1 has 4 elements, and container2 8, and elements 0-3
are equal in both, the result could be 4 and could be specified as
such, i.e. breaking the comparisons when one of the containers is
exhausted.

I am writing a container library in plain C, and I am trying to know
wat other programming languages offer.

Thanks for your answer.

jacob

 

[jacob navia]

Le 18/12/10 18:24, Paavo Helde a écrit :

This is the "don't pay for what was not ordered" policy inherited from C.

Not really. My container library is in C and has always error checking
on. I do not see how an integer comparison would make any difference
really.

If one does not like it one should probably consider another language (in
Java I think most of things are defined).

I am using "another language": C.

The upside of "undefined behavior" is that the implementation can define it
to do something useful. For bad iterator dereference I believe MSVC++ with
checked iterator support switched on gives you a quite good error message
and aborts the program.

Sure, but why shouldn't that be a part of the specifications of the
language instead of an optional feature?

In any case it is surprising that the C++ standard doesn't even mention
those errors and their consequences.

This kind of thing is not possible in Java, one
always has the checking overhead and has to handle the resulting errors
inside the same app.

In my design, all errors have defined consequences, i.e. if you throw
a NULL pointer (say) you know you will get the error code BADARG...

Of course not EVERY possible error is handled. Some errors like
a bad pointer (not NULL but just pointing to nowhere) can't be
catched. But any algorithmic errors provoke always a defined
outcome.

I suppose this is more of a design philosophy anyway. What is
astounding is that with machines today that are thousands of
times faster than 10 years ago we still keep the same botched
philosophy of not furnishing error analysis and error checking.

The C++ standard feels that is necessary to specify the complexity of
the operations but not any error checking analysis at all.

jacob

 

[Jeff Flinn]

Le 18/12/10 16:59, Jorgen Grahn a écrit :


No, I do not know C++ very well, that is why I am asking questions here.
I am implementing a container library in plain C. Now, one of the most
important features of my library will be precisely that there is no
"undefined behavior", all behavior will be defined either

(1) As an error, with a defined result: an error code
(2) As a special case where the result is (maybe arbitrarily)
defined as being "X".

In this case I decided that when
the containers are of different length the result is
1+length of shorter container, if there is no difference
before that of course.


This looks (in my humble opinion) like a badly specified software.

I'm not sure what the standard states about mismatch pre-conditions, 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. 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.

This design minimizes the loop iterator comparisons. 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.

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.

Jeff

 

[jacob navia]

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

 

[Jeff Flinn]

Le 19/12/10 17:44, Jeff Flinn a écrit :

As far as I can see it says absolutely nothing. See 25.1.7 "Mismatch"
in the n1905 C++ standard document.


Maybe. You can *deduce* that if you want, but it is not SPECIFIED.


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.



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.

Great. This produces the same result as the specifications I outlined
above.

Why not incorporate those specs into the specification of "Mismatch"?

Because, if the ranges I'm checking are already known to be of the
proper sizes, I can directly call mismatch without paying the cost of
the size check and swap code.

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.

And when they are not met my unit tests will inform me, by (debug)
iterators asserting when incremented or derefed.

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 profiling tells me it's important to meet my users requirements.

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.

Because in my case that extra compare kept the compiler from unrolling
the loop, leading to a 20% overall reduction in performance.

In THAT context, an integer comparison and a conditional jump are
NOTHING AT ALL.

That is totally context dependent with today's compilers/linkers.

Jeff

 

[jacob navia]

Le 19/12/10 19:50, Jeff Flinn a écrit :

Because, if the ranges I'm checking are already known to be of the
proper sizes, I can directly call mismatch without paying the cost of
the size check and swap code.

They are already known to be OK.

You think.

But, as you know so well, bugs do not announce themselves: Hi Jeff,
you are going to have a big trouble ahead if you keep that off by one
bug!

And when they are not met my unit tests will inform me, by (debug)
iterators asserting when incremented or derefed.

There is a different philosophy in my library. You do not need debug
iterators. All the iterators of my library are checked, and they will
return an error code if you try to go beyond their limits.

Besides, as you know well too, the unit tests never catch all branches
and all code in complex functions. They give you only a FALSE sense
of security. Yes, they are useful (I will never deny that), but they do
not catch all errors.

This was a hard design decision but I think it is CORRECT.

(1) Specify fully the software, trying to catch most errors, test
for NULL arguments, verify lengths, write correct software
(2) Speed is mainly controlled by the algorithm. Do not save pennies
risking to loose millions.

Because profiling tells me it's important to meet my users requirements.

Interesting.

You must have a hell of a profiler there, that can make a difference
between several millions instructions and several millions instructions
+2

Because in my case that extra compare kept the compiler from unrolling
the loop, leading to a 20% overall reduction in performance.

This is wrong. The test can be done at the start of "Mismatch" ONCE
if the length of the second sequence is known. There is no need in
theory to do it at each iteration.

That is totally context dependent with today's compilers/linkers.

No. I know enough assembler to be certain that in several million
instructions, adding 2 instructions doesn't make ANY difference.

Since in the normal case the branch will not be taken a conditional
branch that is correctly predicted will take not even a single cycle
since the speculative process of the processor assumes correctly
it will not be taken. Only in case of an error you will stall the
pipeline what is not important at all since performance is no longer
critical, your program has an error.

In my implementation of "Mismatch" I do:

siz = a1->count;
if (siz > a2->count)
siz = a2->count;
where
a1,a2 two vectors
"count" is a field where I store the length of each vector

gcc translates this to:
cmpq %rax, 8(%rsi)
cmovbe 8(%rsi), %rax
movq %rax, -72(%rbp)

Just 3 instructions. A comparison with the limit is even less.

Since I do this at the start of the "Mismatch" function the cost
is just 3 instructions for the whole mismtach call. If you are
comparing 2 longuish sequences say with 100 elements each, you
can execute several million instructions there. Note that
several million instructions take only a few ms in a 2.7GHZ processor.

jacob

 

[Öö Tiib]

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.

That is the biggest difference between all code that people write
compared to standard library. Lets say user reports that the program
is buggy because it crashed when he pressed button B in situation S.
Developer can not tell to that user that it is by manual and so fully
users own fault because he did not read user manual 16.14.7/2 that
clearly claims that pressing the button B in situation S is "undefined
behavior".

[...]

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.

You are correct that there are unhealthy amount of undefined behaviors
in C++ and its library so it has to be used carefully. Few things that
experts consider as round, soft and newbie safe ... like string or
vector ... are also full of bear traps. Most error handling has to be
added to software by developers and that is simply the nature of the
language. There are plenty of safer languages but i am not sure if
these let to write better software. The developers who are not used to
carefully deal with every exceptional situation often lack the needed
mindset to achieve quality.

For example the user asks from household database at what date his
sons computer was bought. Database realizes that computer was bought
as parts and the parts of the computer were actually bought at
different dates. So it answers something like "various dates". Even if
date will be a type in standard library one day i suspect that it
won't have values like "various dates". So it is a business of
developer to discover and give meaning to exceptional situations, not
business of language. Since developer has to deal with it anyway it
feels like double work.

 

[jacob navia]

Le 19/12/10 21:42, Leigh Johnston a écrit :
[snip]

I stated that the test needs to be done ONCE for the whole call to
Mismatch, before it starts its loop.

I just do not undesrtand why you go on saying that the tests could
be at a "critical section", i.e. in a loop. The tests are done
at the start of mismtach, and they are added to the setup and
initialization costs of the loop that are executed only ONCE!

(1) You agree that the speed of "mismatch" is of the order of

(a) Setup costs
(b) N * comparison costs
(c) N * incrementing iterators for the loop

Roughly. OK?

If N is (say) 10 elements before a mismtach is found,
the setup costs will be MUCH smaller than the 10 times the
loop went around. The critical part of "mismatch" is
the loop, not the setup!

In fact, the worst case for my tests is when the first
comparison fails. In tat case the setup costs will be
big compared to the useful work. But they will be never as big
as a single element comparison

In any case just to establish a stack frame the machine
executes more than 3 instructions

 

[Ian Collins]

Le 18/12/10 16:59, Jorgen Grahn a écrit :


This looks (in my humble opinion) like a badly specified software.

Accepting that errors occur and that software must be able to handle
those errors producing known and similar results at each similar
error is the basis of my specification.

As far as I could read in the book from Plauger and others, nowhere
is explicitely required that the containers should have the same length.

It is explicitly mentioned in Josuttis' "The C++ Standard Library",
which I consider to be the definitive work on the library.

It is pretty obvious from the nature of the algorithm that the
comparison container should be at least as long as the first.

It *can* be deduced but that doesn't give any answer to the question:

And what happens then?

I am surprised at this situation. Looking up in the C++ standard doesn't
help either. This "algorithm" is mentioned in page 635 ("Algorithms
Library") but nowhere is the length of the arguments mentioned. It is
specified at great length that the input iterators should be input
iterators, but there isn't any specification of borderline cases at all.

I guess there are two choices, offer an overload with a cmpEnd parameter
or check inside the existing one. Checking is impractical, so the only
option is another overload (or two).

Clarity is a good thing, so maybe a defect report is required? Try
asking on comp.std.c++.

 

[Ian Collins]

Besides, as you know well too, the unit tests never catch all branches
and all code in complex functions. They give you only a FALSE sense
of security. Yes, they are useful (I will never deny that), but they do
not catch all errors.

If the tests are written first, the branch won't exist unless it is
there to pass a test!

This was a hard design decision but I think it is CORRECT.

(1) Specify fully the software, trying to catch most errors, test
for NULL arguments, verify lengths, write correct software
(2) Speed is mainly controlled by the algorithm. Do not save pennies
risking to loose millions.

Fair comments. Most modern languages adopt similar principles.

This is wrong. The test can be done at the start of "Mismatch" ONCE
if the length of the second sequence is known. There is no need in
theory to do it at each iteration.

As I mentioned elsethread, that will require a new pair of overloads.
For now, there's nothing stopping the concerned developer adding their own!

 

[jacob navia]

Le 19/12/10 23:17, Leigh Johnston a écrit :

You are failing to recognize that the "setup cost" when determining the
distance between two std::list iterators (for example) is linear; i.e.
the "setup cost" is only constant for certain types of iterators and for
others is not constant at all but involves N operations.

/Leigh

Yes, in this case (for lists) you could be right. I didn't even think
that the C++ STL would be that bad, since my library caches the index
of each iterator cursor making the calculation of the distance between
two elements just a simple subtraction...

Yes, if you need to go through the whole list to know the distance
between two iterators you are right but really, it can't be that
bad.

 

[Ian Collins]

Le 19/12/10 23:17, Leigh Johnston a écrit :

Yes, in this case (for lists) you could be right. I didn't even think
that the C++ STL would be that bad, since my library caches the index
of each iterator cursor making the calculation of the distance between
two elements just a simple subtraction...

Yes, if you need to go through the whole list to know the distance
between two iterators you are right but really, it can't be that
bad.

Consider the case where the 'iterators' are plain old pointers. Or the
case where the distance isn't know or is expensive to calculate until
the iteration is done. I have an iterator for a directory class that
reads entries until it returns null for example.

That's one of the beauties of the standard algorithms, anything that
behaves like an iterator can be used.

 

[James Kanze]

On 12/20/10 09:24 AM, jacob navia wrote:

If the tests are written first, the branch won't exist unless it is
there to pass a test!

Three comments:

-- Are you sure? Exceptions introduce a lot of additional
branches, that aren't in the normal program logic (but which
have to be tested). It's very easy to write a test (or
a series of tests) for a factory function that tests that it
always returns a valid object, with values corresponding to
what they should be (at least in some trivial cases). But
writing such tests first does nothing to ensure that the
case when new throws bad_alloc has been correctly handled.
(It can, of course, but it's not "automatic", just because
you write the test first.)

-- I'm not sure what he means by "all the branches". To give
a simple and somewhat artificial case:

void f(bool c1, bool c2)
{
if (c1)
doA();
else
doB();
if (c2)
doC();
else
doD();
}

"Obviously", you need four tests to test all of the branches
(unless some of the functions can throw---then you likely
need more). Regardless of whether you write the tests
before or after, it's easy to only write two or three cases;
some coverage tools I've seen report full coverage with just
f(false, false) and f(true, true).

Similar issues arrive with executing loops 0 times (which is
probably a more realistic example).

-- Finally, some problems (including most involving floating
point) aren't linear; for a lot of numerical work, for
example, just testing the end points and a couple of values
between them offers no guarantee that the implementation is
stable for all possible input. Thread safety has similar
issues: to be complete, you'd have to ensure that there was
a test for a thread switch between every machine
instruction. (This doesn't mean that you don't need the
tests. Just that they aren't sufficient.)

Thorough testing is important, and I strongly disagree with the
posting you are responding to: just because it can't be 100%
perfect is no reason to skimp on it (and you should be able to
reasonably address my first two points above---if the
development process decides to address the issues). But writing
tests first isn't a silver bullet; I'd argue, in fact, that it's
not important when they're written, as long as they *are*
written. (If requiring tests to be written first is the only
way to ensure that they are written, of course, then that's the
route you have to go. I've not found that to be the case,
however.)

 

[Anand Hariharan]

Le 19/12/10 23:17, Leigh Johnston a crit :





Yes, in this case (for lists) you could be right. I didn't even think
that the C++ STL would be that bad, since my library caches the index
of each iterator cursor making the calculation of the distance between
two elements just a simple subtraction...

It's a design decision to cache the index, and your design is not
necessarily right or better. E.g., when do you update the cache? Or
what is the big-Oh complexity of insertion or removal of elements from
the list?

Yes, if you need to go through the whole list to know the distance
between two iterators you are right but really, it can't be that
bad.

The complexity to know the distance is O(n).


I am curious to know why you pick on mismatch in particular -- several
other algorithms have a similar interface (e.g., std::copy).

Also (and you may already be aware of this) if you go by typical
usage, mismatch "returns that there isn't mismatch" if the first
sequence is a 'sub-sequence' of the second. If the first sequence
contains n elements, and the second sequence contains the exact n
elements plus some other elements, then mismatch returns a pair of
iterators, the first of which is the (one past) last element of the n
elements in the first sequence. Most examples you'd find will simply
use the first portion of the pair to conclude that there is no
mismatch.

- Anand

 

[jacob navia]

Le 20/12/10 18:30, Anand Hariharan a écrit :

It's a design decision to cache the index, and your design is not
necessarily right or better. E.g., when do you update the cache?

When updating the cursor of course. Since in list you can move only
one element at the time, it is fairly easy to do

Or
what is the big-Oh complexity of insertion or removal of elements from
the list?

This has nothing to do with the discussion.

The complexity to know the distance is O(n).

No, if the cursor has an index...

I am curious to know why you pick on mismatch in particular -- several
other algorithms have a similar interface (e.g., std::copy).

Because I am writing"mismtach" for my library. Now it has the signature:

For vectors for instance:

int Mismatch(SequentialContainer *a1,
SequentialContainer *a2,size_t *presult);

Result is bigger than zero if there was a mismatch, zero if there
is no mismtach or smaller than zero if there was an error.

If there was a mismatch and result is bigger than zero, the index of
the first element that compared unequal is in the passed pointer
"presult".

Errors can be:
Any of the arguments a1 or a2 is NULL. If presult is NULL it means
you are not interested in the exact position

If the containers are of different length, the shorter container
makes iteration stop when exhausted. In that case the result is
1 and "mismatch" contains 1+length of the shorter container.

Also (and you may already be aware of this) if you go by typical
usage, mismatch "returns that there isn't mismatch" if the first
sequence is a 'sub-sequence' of the second. If the first sequence
contains n elements, and the second sequence contains the exact n
elements plus some other elements, then mismatch returns a pair of
iterators, the first of which is the (one past) last element of the n
elements in the first sequence. Most examples you'd find will simply
use the first portion of the pair to conclude that there is no
mismatch.

You can test this if you test that the result is one and the index is
1+length of the shorter container.