.\" ident	@(#)Array_alg:man/set_diff.3	3.2
.\"
.\" C++ Standard Components, Release 3.0.
.\"
.\" Copyright (c) 1991, 1992 AT&T and UNIX System Laboratories, Inc.
.\" Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
.\"
.\" THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and UNIX System
.\" Laboratories, Inc.  The copyright notice above does not evidence
.\" any actual or intended publication of such source code.
.\" 
.TH \f3set_diff\fP \f3Array_alg(3C++)\fP " "
.SH NAME
set_diff \- treating arrays as sets, take the set difference
.SH SYNOPSIS OF Array_alg.h
.Bf

    template <class \*(gt>
    \*(gt* set_diff(
	const \*(gt* b1,
	const \*(gt* e1,
	const \*(gt* b2,
	const \*(gt* e2, 
	\*(gt* b3
    );
    template <class \*(gt>
    \*(gt* set_diff_r(
        int (*rel)(const \*(gt*,const \*(gt*),
	const \*(gt* b1, 
	const \*(gt* e1, 
	const \*(gt* b2, 
	const \*(gt* e2, 
	\*(gt* b3
    );
.Be
.SH ASSUMPTIONS
.PP
(1) For the plain version, \f4\*(gt::operator<\f1
defines a total ordering relation on \*(gt and both 
input arrays are sorted w.r.t. that relation.
.br
(2) For the relational version, \f4rel\f1 defines 
a total ordering relation on \*(gt and both input arrays 
are sorted w.r.t. that relation.
.br
(3) Neither of the input arrays has repetitions
.br
(4) The output array does not overlap either of the 
two input arrays.
.br
(5) The output array has enough cells to hold the result
.br
(6) \*(gt has \f4operator=\f1
.SH DESCRIPTION
.PP
These functions put elements from two sorted arrays
with no repetitions into a new sorted array
with no repetitions such that 
every element which is in the first array but not in 
the second will be placed in the new array. 
They return a pointer to the cell just beyond the 
last element of the new array.
.sp 0.5v
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* set_diff(\f1"
.IC "\f4    const \*(gt* b1,\f1"
.IC "\f4    const \*(gt* e1,\f1"
.IC "\f4    const \*(gt* b2,\f1"
.IC "\f4    const \*(gt* e2,\f1"
.IC "\f4    \*(gt* b3\f1"
.IC "\f4);\f1"
Uses \f4\*(gt::operator<\f1 for comparing elements.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* set_diff_r(\f1"
.IC "\f4    int (*rel)(const \*(gt*,const \*(gt*),\f1"
.IC "\f4    const \*(gt* b1,\f1"
.IC "\f4    const \*(gt* e1,\f1"
.IC "\f4    const \*(gt* b2,\f1"
.IC "\f4    const \*(gt* e2,\f1"
.IC "\f4    \*(gt* b3\f1"
.IC "\f4);\f1"
Uses \f4rel\f1 for comparing elements.  
.SH COMPLEXITY
.PP
If \f2N\f1 and \f2M\f1 are the sizes of the arrays, then
complexity is \f2O(N+M)\f1.
At most \f2N+M\-1\f1 comparisons and 
\f2N\f1 assignments are done.
.SH NOTES
All functions whose names begin with \f3set_\f1
treat arrays as sets (they share assumptions 1\-3).
These all have linear time complexity, which may 
unacceptable for large sets.
As an alternative, consider using \f3Set(3C++)\f1 
or \f3Bits(3C++)\f1
(if \*(gt is \f4int\f1).
.SH NOTES
Because a Block (see \f3Block(3C++)\f1)
can always be used wherever an array is called for,
Array Algorithms can also be used with Blocks.
In fact, these two components were actually designed 
to be used together.
.SH SEE ALSO
.Bf
\f3intro(.)\f1
\f3set_inter(.)\f1
\f3set_insert(.)\f1
\f3set_remove(.)\f1
\f3set_union(.)\f1
\f3set_sdiff(.)\f1

\f3Bits(3C++)\f1
\f3Set(3C++)\f1
\f3Block(3C++)\f1
.Be