# set_insert(3C++)

**set_insert --
treating arrays as sets, insert an element
**

## Synopsis

template <class **T**>
**T*** set_insert(
const **T**& val,
**T*** b,
**T*** e
);
template <class **T**>
**T*** set_insert_r(
int (*rel)(const **T***,const **T***),
const **T**& val,
**T*** b,
**T*** e
);

## Assumptions

(1) For the plain version, **T::operator<** defines a total
ordering relation on **T** and the array is sorted w.r.t. that relation.

(2) For the relational version, **rel** defines a total ordering
relation on **T** and the array is sorted w.r.t. that relation.

(3) The input array does not contain any repetitions.

(4) **e** points to a free cell; that is, if the insertion
is successful, **e** can be safely incremented in the client code.

(5) **T** has **operator=**.

## Description

If a sorted array does not already contain an element equal to **val**,
these functions insert **val** into the array in such a way that
the array remains sorted.
If the insertion is done, then the location of the new
value is returned as the function result.
Otherwise, 0 is returned.

template <class T>
T* set_insert(
const T& val,
T* b,
T* e
);

Uses **T::operator<** to find the insertion point.

template <class T>
T* set_insert_r(
int (*rel)(const T*,const T*),
const T& val,
T* b,
T* e
);

Uses **rel** to find the insertion point.

## Complexity

If *N* is the size of the array, then complexity
is *O(N)*.
At most *N* assignments
and at most *lgN* tests of the ordering relation are done.

## Notes

All functions whose names begin with **set_** 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 **Set(3C++)**
or **Bits(3C++)** (if **T** is **int**).

Because a Block (see **Block(3C++)**) 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.

## References

**Array_alg**(3C++),
**Bits**(3C++),
**Block**(3C++),
**Set**(3C++),
**insert**(3C++),
**set_diff**(3C++),
**set_inter**(3C++),
**set_remove**(3C++),
**set_union**(3C++),
**set_sdiff**(3C++)

*
© 2004 The SCO Group, Inc. All rights reserved.
*

UnixWare 7 Release 7.1.4 - 25 April 2004