set_sdiff(C++)

Synopsis

   template <class T>
   T* set_sdiff(
        const T* b1,
        const T* e1,
        const T* b2,
        const T* e2,
        T* b3
   );
   template <class T>
   T* set_sdiff_r(
        int (*rel)(const T*,const T*),
        const T* b1,
        const T* e1,
        const T* b2,
        const T* e2,
        T* b3
   );

Assumptions

(1) For the plain version, T::operator< defines a total ordering relation on T and both input arrays are sorted w.r.t. that relation.

(2) For the relational version, rel defines a total ordering relation on T and both input arrays are sorted w.r.t. that relation.

(3) Neither input array has any repetitions.

(4) The output array does not overlap either of the input arrays.

(5) The output array has enough cells to hold the result.

(6) T has operator=.

Description

These functions put elements from two sorted arrays with no repetitions into a new sorted array with no repetitions such that every element which is in only in one of the original arrays will be placed into the new array. The pointer after the last element of the new array s returned.

   template <class T
   T* set_sdiff(
       const T* b1,
       const T* e1,
       const T* b2,
       const T* e2,
       T* b3
   );

Uses T::operator< for comparing elements. That is, if p and q are pointers into the first and second array, then *p will not appear in the second array if !(*p<*q) and !(*q<*p).

   template <class T>
   T* set_sdiff_r(
       int (*rel)(const T*,const T*),
       const T* b1,
       const T* e1,
       const T* b2,
       const T* e2,
       T* b3
   );

Uses rel for comparing elements. That is, if p and q are pointers into the first and second array, then *p will not appear in the second array if rel(p,q)==0.

Complexity

If N and M are the sizes of the arrays, then complexity is O(N+M). At most N+M-1 equality tests and max(N, M) assignments 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 Block. In fact, these two components were actually designed to be used together.

References