|
|
The algebraic operators (union, intersection, difference, symmetric difference) can all be implemented using the similarly-named Array Algorithms that ``understand'' how to treat arrays as sets. For example, consider the union operator, operator|():
Array_set<T> operator|(const Array_set<T>& s)const{
check();
if(b==s.b) return *this;
Array_set<T> result;
result.b.reserve(n+s.n);
result.n = set_union(&b[0],&b[n],&(s.b[0]),
&(s.b[s.n]),&(result.b[0])) - &(result.b[0]);
return result;
}
After checking the invariant, we make sure that this is not an attempt to take the union of s with itself (by comparing Block identities, not Block contents). Since the union of two sets potentially contains all the elements of both sets (this happens when the sets are disjoint), we create an Array_set called result and reserve for the worst case.
set_union(), described in set_union(C++), transfers the algebraic union of the two input arrays into result.b. As with many other Array Algorithms, the pointer identifying the end of the output array is implicit; set_union() simply assumes that the output array has enough cells to hold the result (an assumption justified by our initial reservation). set_union() returns a pointer just beyond the end of the result array, allowing us to compute the number of elements in the union by subtracting a pointer to the first cell.
Defining a local Array_set and returning its value as we have done here is not very efficient because it requires two copies: (1) moving the elements of the union into the output array and (2) invoking Block(Block&) to copy the output Block back into the stack frame of the caller. There are techniques to avoid the second copy that are not specific to Blocks and are therefore not discussed in this tutorial.