|
|
template <class T>
T* part(const T& val,T* b,T* e);
template <class T>
T* part_c(const T& val,T* b1,T* e1,T* b2);
template <class T>
T* part_p(int (*pred) (const T*),T* b,T* e);
template <class T>
T* part_pc(int (*pred) (const T*),T* b1,T* e1,T* b2);
template <class T>
T* part_ps(int (*pred) (const T*),T* b,T* e);
template <class T>
T* part_psc(int (*pred) (const T*),T* b1,T* e1,T* b2);
template <class T>
T* part_r(int (*pred) (const T*),const T& val,T* b,T* e);
template <class T>
T* part_rc(
int (*rel) (const T*,const T*),
const T& val,
T* b1,
T* e1,
T* b2
);
template <class T>
T* part_rs(int (*rel)(const T*,const T*),
const T& val,T* b,T* e);
template <class T>
T* part_rsc(
int (*rel) (const T*,const T*),
const T& val,
T* b1,
T* e1,
T* b2
);
template <class T>
T* part_s(const T& val,T* b,T* e);
template <class T>
T* part_sc(const T& val,T* b1,T* e1,T* b2);
(1) For non-predicate and non-relational versions, T::operator== defines an equivalence relation on T.
(2) For relational versions, rel defines an equivalence relation on T.
(3) For copy versions, the output array does not overlap the input array.
(4) For copy versions, the output array has at least as many cells as the input array.
(5) T has operator=.
These functions partition an array into two groups such that the elements in the left group satisfy a given criterion and those in the right group do not. They return a pointer to the cell just beyond the last element in the left group.
template <class T> T* part(const T& val,T* b,T* e);
Uses equality with val as the partitioning criterion, with T::operator== used for the equality test. That is, if p is a pointer into the array, then *p will be in the left group if *p==val and in the right group otherwise. The algorithm is not stable; that is, it does not preserve the relative order of elements in both groups. If stability is required then part_s should be used. If extra memory is available, it is even better to use part_sc and then copy the result array back into place.
template <class T> T* part_c(const T& val,T* b1,T* e1,T* b2);
Like part except that the input array is preserved and the result written to a new array beginning at location b2.
template <class T> T* part_p(int (*pred)(const T*),T* b,T* e);
Like part except that it uses satisfaction of pred as the criterion for partitioning. That is, if p is a pointer into the array, then *p will be in the left group if pred(p) is true and in the right group if pred(p) is false.
template <class T> T* part_pc(int (*pred)(const T*),T* b1,T* e1,T* b2);
Like part_p except that the input array is preserved and the result written to a new array beginning at location b2.
template <class T> T* part_ps(int (*pred)(const T*),T* b,T* e);
Like part_p except that it uses a stable algorithm. That is, the relative order of elements within both groups is preserved.
template <class T> T* part_psc(int (*pred)(const T*),T* b1,T* e1,T*
Like part_ps except that the input array is preserved and the result written to a new array beginning at location b2.
template <class T> T* part_r(int (*rel)(const T*,const T*),const T& val,T* b,T* e);
Like part except that it uses rel to test for equality. That is, if p is a pointer into the array, then *p will be in the left group if rel(p,&val)==0 and in the right group otherwise.
template <class T>
T* part_rc(
int (*rel)(const T*,const T*),
const T& val,
T* b1,
T* e1,
T* b2
);
Like part_r except that the input array is preserved and the result written to a new array beginning at location b2.
template <class T>
T* part_rs(int (*rel)(const T*,const T*),
const T& val,T* b,T* e);
Like part_r except that it uses a stable algorithm. That is, the relative order of elements within both groups is preserved.
template <class T>
T* part_rsc(
int (*rel)(const T*,const T*),
const T& val,
T* b1,
T* e1,
T* b2
);
Like part_rs except that the input array is preserved and the result written to a new array beginning at location b2.
template <class T> T* part_s(const T& val,T* b,T* e);
Like part except that it uses a stable algorithm. That is, the relative order of elements within both groups is preserved.
T* part_sc(const T& val,T* b1,T* e1,T* b2);
Like part_s except that the input array is preserved and the result written to a new array beginning at location b2.
part, part_p, part_r
If N is the size of the array, then the complexity is O(N). Exactly N tests of the criterion are made. If P is the number of elements in the array that satisfy the criterion, then at most 3*min(P, N-P) assignments are done.
part_c, part_pc, part_rc
If N is the size of the array, then the complexity is O(N). Exactly N tests of the criterion and N assignments are done.
part_ps, part_rs, part_s
If N is the size of the array, then complexity is O(NlgN). Exactly N tests of the criterion and at most 3NlgN assignments are done.
part_psc, part_rsc, part_sc
If N is the size of the array, then complexity O(N). Exactly N tests of the criterion are made. If P is the number of locations in the array that do not satisfy the criterion, then exactly N + 3floor(P/2) assignments are done.
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.