DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK

# 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++)