set_remove(C++)

Synopsis

   template <class T>
   T* set_remove(
        const T& val,
        T*b,
        T* e
   );
   template <class T>
   T* set_remove_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.

(F) T has operator=.

Description

If a sorted array with no repetitions contains an element equal to val, these functions remove it in such a way that the array remains sorted. They return a pointer to the cell just beyond the cell containing the last remaining element.

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

Uses T::operator< to find the element.

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

Uses rel to find the element.

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