|
|
template <class T>
T* rem_dup(T* b,T* e);
template <class T>
T* rem_dup_c(T* b1,T* e1,T* b2);
template <class T>
T* rem_dup_r(int (*rel)(const T*,const T*),
T* b,T* e);
template <class T>
T* rem_dup_rc(int (*rel)(const T*, const T),
T* b1,T* e1,T* b2);
(1) For the non-relational versions, T::operator== defines an equivalence relation on T.
(2) For the relational versions, rel defines an equivalence relation on T.
(3) For the copy versions, the output array does not overlap the input array.
(4) For the copy versions, the output array has enough cells to hold the result.
(5) T has operator=.
These functions move the unique elements (those elements that are not equal to one another) to the left and return a pointer to the cell just beyond the cell containing the last unique element.
If b and p are, respectively, the pointer to the beginning of the output array and the function result, then b and p delimit a conceptually "new" array in which duplicates have been removed. The algorithms used by all functions in this group are stable; that is, the relative order of unique elements is preserved.
template <class T> T* rem_dup(T* b,T* e);
Uses T::operator== for the uniqueness test.
template <class T> T* rem_dup_c(T* b1,T* e1,T* b2);
Like rem_dup except that the input array is preserved and the result is written to a new array beginning at location b2.
template <class T> T* rem_dup_r(int (*rel)(const T*,const T*),T* b,T* e);
Like rem_dup except that it uses rel to test for uniqueness. That is, if p and q are pointers into the array, then *p and *q will be treated as duplicates if rel(p,q)==0.
template <class T>
T* rem_dup_rc(int (*rel)(const T*,const T*),
T* b1,T* e1,T* b2);
Like rem_dup_r except that the input array is preserved and the result is written to a new array beginning at location b2.
If N is the size of the array, then complexity is O(N*N) for all versions. More precisely,
non-copy versions
At most N*N/2 uniqueness tests and at most N-2 assignments are done.
copy versions
At most N*N/2 uniqueness tests and N assignments are done.
rem_dup is quadratic and should not be used with large (more than 16 or so elements) array. Large arrays should be first sorted with sort or sort_s and then passed through unique.
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.