# insert(3C++)

**insert --
insert an element into a sorted array
**

## Synopsis

template <class **T**>
**T*** insert(**T** val, **T*** b,**T*** e);
template <class **T**>
**T*** insert_r(int (*rel)(const **T***,const **T***),**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) **T** has **operator=**.

## Description

These functions assign the value **val** to the location in
the sorted array that contains the leftmost element greater than **val**
and returns a pointer to this location.
Before making the assignment, all elements
from that location to the end of the array are moved one location to the right.

template <class T>
T* insert(T val,T* b,T* e);

Uses **T::operator<** to define the ordering relation.

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

Uses **rel** to define the ordering relation.

## Complexity

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

## Notes

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++),
**Block**(3C++)
**set_insert**(3C++)

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

UnixWare 7 Release 7.1.4 - 25 April 2004