unique(C++)

Synopsis

   template <class T>
   T* unique(T* b,T* e);
   template <class T>
   T* unique_c(T* b1,T* e1,T* b2);
   template <class T>
   T* unique_r(int (*rel)(const T*,const T*),
        T* b,T* e);
   template <class T>
   T* unique_rc(int (*rel)(const T*,const T*),
        T* b1,T* e1,T* b2);

Assumptions

(C)

For the non-relational versions, T::operator== defines an equivalence relation on T.

(S)

For the relational versions, rel defines an equivalence relation on T.

(S)

For the copy versions, the output array does not overlap the input array.

(F)

For the copy versions, the output array has enough cells to hold the result.

(M)

T has operator=.

Description

These functions remove all but the first element from every consecutive group of equal elements in an array. They return a pointer to the location after the last unique element.

   template <class T>
   T* unique(T* b,T* e);

Uses T::operator== to define equality.

   template <class T>
   T* unique_c(T* b1,T* e1,T* b2);

Like unique except that the input array is preserved and the result written to a new array beginning at location b2.

   template <class T>
   T* unique_r(int (*rel)(const T*,const T*),T* b,T* e);

Uses rel to define equality.

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

Like unique_r except that the input array is preserved and the result written to a new array beginning at location b2.

Complexity

If N is the size of the array, then complexity is O(N) for all versions. Exactly N-1 equality tests and at most N-2 assignments are done.

Notes

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