Array_set relations

The Array_set relations equality and proper subset illustrate a couple of interesting points about Array Algorithms. Abstractly, two Array_sets are equal if they contain exactly the same elements. We can immediately rule out equality if the two Array_sets have different numbers of elements. If both Array_sets have N elements, however, we must compare elements 0,1,2,...N of their respective Blocks; we can quit as soon as two corresponding elements are unequal, thanks to sortedness (if it were not for sortedness, the algorithm would be quadratic). The Array Algorithm mismatch(), described in mismatch(C++), can be used to do this. It returns a pointer to the first location at which two arrays differ, or zero if no mismatch occurs:

       int operator==(const Array_set(T)& s)const{
           check();
           return (n==s.n &&
               mismatch(&b[0],&b[n],&(s.b[0]),&(s.b[s.n]))==0);
       }