set_insert(C++)

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.

(M) 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