|
|
template <class T> T* set_union( const T* b1, const T* e1, const T* b2, const T* e2, T* b3 ); template <class T> T* set_union_r( int (*rel)(const T*,const T*), const T* b1, const T* e1, const T* b2, const T* e2, T* b3 );
These functions put elements from two sorted arrays with no repetitions into a new sorted array with no repetitions so that for every element in the original arrays there is an element in the result array that is equal to it. The pointer to the cell following the last element of the new array is returned.
template <class T> T* set_union( const T* b1, const T* e1, const T* b2, const T* e2, T* b3 );
Uses T::operator< to define the ordering relation.
template <class T> T* set_union_r( int (*rel)(const T*,const T*), const T* b1, const T* e1, const T* b2, const T* e2, T* b3 );
Uses rel to define the ordering relation.
If N and M are the sizes of the two arrays, then complexity is O(N+M). At most N + M-1 tests of the ordering relation and N+M assignments are done.
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.