DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK

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