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(3C++),
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);
}
Next topic:
Selecting an arbitrary Array_set element
Previous topic:
Array_set removal
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 27 April 2004