.\" ident	@(#)Array_alg:man/set_inter.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_inter\fP \f3Array_alg(3C++)\fP " "
.SH NAME
set_inter \- treating arrays as sets, take the intersection
.SH SYNOPSIS OF Array_alg.h
.Bf

    template <class \*(gt>
    \*(gt* set_inter(
	const \*(gt*b1, 
	const \*(gt* e1, 
	const \*(gt* b2, 
	const \*(gt* e2, 
	\*(gt* b3
    );
    template <class \*(gt>
    \*(gt* set_inter_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, \*(gt\f4::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 input array has any 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 both arrays 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_inter(\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 to define the ordering relation. 
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* set_inter_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 to define the ordering relation.
.SH COMPLEXITY
If \f2N\f1 and \f2M\f1 are the sizes of the two arrays,
then complexity is \f2O(N+M)\f1.
At most \f2N+M\-1\f1 tests of the ordering relation
and \f2max(N,M)\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).
.PP
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_diff(.)\f1
\f3set_insert(.)\f1
\f3set_union(.)\f1
\f3set_union(.)\f1
\f3set_sdiff(.)\f1

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