|
|
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 );
(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) T has operator=.
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.
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.
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.