Problems with std::forward_iterator::equal (was: std::equal bombs if the)

[Ed Smith-Rowland <3dw4rd at verizon dot net>]

Sebastian Redl wrote:
> Smith-Rowland, Edward M wrote:
> > Hi,
> >
> > I'm working on an implementation of std::forward_list and bumped into 
> > something while testing equality of containers:
> >
> > bool eq = std::equal(firsst1, lasst1, firsst2);
> >
> > this will bomb if the number of elements in [firsst1, lasst1)
> > is greater than in [firsst2, firsst2 + distance(firsst1, lasst1)).
> >
> > The standard seemed to me to be quiet on this but mightn't it be a 
> > good idea to watch out that lasst2 doesn't hit the end() of the 
> > second list?
> >   
> How?
> > Maybe the powers that be didn't want the time overhead of the check?
> >
> > Is this the way it's supposed to be or is it a bug?
> >
> > The whole issue turned up for me because forward_list doesn't have 
> > size() so I wound up having to walk through and watch out for end() 
> > in both lists.  The other containers check size() of the two containers.
> >   
> It's a very weird specification by the standard, and I consider the 
> lack of an equal (and a mismatch) with two iterator pairs as input a 
> serious deficiency (especially since both sequences might be 
> single-traversal and of unknown length), but it's not a bug of the GCC 
> implementation.
>
> You can abuse search to the purpose of having an equal that takes the 
> lengths of both sequences, but it also may return incorrect results in 
> respect to the equal specification.
> You can also use lexicographical_compare to that purpose, at twice the 
> computational expense, of course.
>
> Sebastian
Howdy,

I guess it would be hard to detect in the 1.5 iterator pair version how 
to find the end of the list. ;-)

I implemented an equal that loops through both lists (we have lists not 
iterators in the method).  If a pair of items are not equal then return 
false.  If the end of one loop is reached without a pair of items not 
equal check if the other list is at the end.  If not, then the lists 
have different size and the equal will return false.  I think this is 
about as efficient as we can get.  We don't have to call distance 
twice.  We loop through all the pairs but we'd have to do that anyway.

Also, I noticed on http://www.open-std.org/JTC1/SC22/WG21/ that the new 
mailing is out.  (Whoohoo!)
In the active library issues is this DR:

 861. Incomplete specification of EqualityComparable for std::forward_list

This outlines this very issue and the prime suggestion is to do 
essentially what I'm talking about.

I think the intent of the standard was to do that too.  The standard 
just mistakenly referred to a non-existent size().  I think the 
statement that equals is equivalent to:
   return a.size() == b.size() && equal(a.begin(), a.end(), b.begin());
or better yet:
   return distance(x.begin(), x.end()) == distance(y.begin(), y.end()) 
&& equal(x.begin(), x.end(), y.begin());
is just for exposition and is not supposed to legislate an 
implementation.  This just describes the semantics.

Although I agree a std::equal(Start1,End1,Start2,End2) might be really 
nice and in some cases required.  In fact, the 1.5 iterator range 
version is pretty dangerous - really useless - with forward_list.

Ed