search(3C++)

Synopsis

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

Assumptions

(1) For the plain version, T::operator== defines an equivalence relation on T.

(2) For the relational version, rel defines an equivalence relation on T.

Description

These functions return a location in the first array at which begins a subarray of the same size as the second array such that every element in this subarray is equal to the corresponding element of the second array. If such a location does not exist, they return 0.

   template <class T>
   const T* search(
       const T* b1,
       const T* e1,
       const T* b2,
       const T* e2
       );

Uses T::operator== to define equality.

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

Uses rel to define equality. That is, if p and q are pointers into the first and second array, respectively, then p and q begin matching subarray of length 1 if rel(p,q)==0.

Complexity

If N and M are the sizes of first and second arrays, respectively, then complexity is O(N*M). At most N*M equality tests are done. However, it is quite fast on the average in most practical cases.

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