YXD's Blog

1、从字符串A中找到匹配字符串B的第一个子串的位置，以下的代码经测试比Plauger的stl（VC7）中的
::std::string::find要快30%左右
// 仿函数版本
template < class Character = char, class Size = int >
struct StringFinder
{
 typedef Size size_t;
 typedef Character char_t;
 size_t operator()( const char_t* lpszSource, const char_t* lpszSearch )
 {
  // maybe the processing of the following line can delay to the caller
  if ( ( NULL == lpszSource ) || ( NULL == lpszSearch ) ) return -1;
  const char_t& cSource = *lpszSource;
  const char_t& cSearch = *lpszSearch;
  for ( ; ; )
  {
   if ( 0 == *lpszSearch )
   {
    return ( lpszSource - ( lpszSearch - &cSearch ) - &cSource );
   }
   if ( 0 == *lpszSource ) return -1;
   if ( *lpszSource != *lpszSearch )
   {
    lpszSource -= lpszSearch - &cSearch - 1;
    lpszSearch = &cSearch;
    continue;
   }
   ++ lpszSource;
   ++ lpszSearch;
  }
  return -1;
 }
};
// 函数版本
template < class char_t, class size_t >
size_t StringFind( const char_t* lpszSource, const char_t* lpszSearch )
{
 // maybe the processing of the following line can delay to the caller
 if ( ( NULL == lpszSource ) || ( NULL == lpszSearch ) ) return -1;
 const char_t& cSource = *lpszSource;
 const char_t& cSearch = *lpszSearch;
 for ( ; ; )
 {
  if ( 0 == *lpszSearch )
  {
   return ( lpszSource - ( lpszSearch - &cSearch ) - &cSource );
  }
  if ( 0 == *lpszSource ) return -1;
  if ( *lpszSource != *lpszSearch )
  {
   lpszSource -= lpszSearch - &cSearch - 1;
   lpszSearch = &cSearch;
   continue;
  }
  ++ lpszSource;
  ++ lpszSearch;
 }
 return -1;
}

2、字符串比较，同strcmp的功能，以下为仿函数版本。
struct StringCmp
{
 int operator()( const char* lpszStr1, const char* lpszStr2 )
 {
  if ( NULL == lpszStr1 )
  {
   if ( NULL == lpszStr2 ) return 0;
   return -1;
  }
  if ( NULL == lpszStr2 ) return 1;

  for ( ; ( 0 != ( ( *lpszStr1 ) & ( *lpszStr2 ) ) ); ++ lpszStr1, ++ lpszStr2 )
  {
   if ( *lpszStr1 < *lpszStr2 ) return -1;
   if ( *lpszStr1 > *lpszStr2 ) return 1;
  }
  if ( 0 != *lpszStr2 ) return -1;
  if ( 0 != *lpszStr1 ) return 1;
  return 0;
 }
};

3、快速排序算法（做了优化处理的），当元素总数不超过给定的阈值（threshold）时，采用插入排序，如果这个
做笔试题的话，个人认为难度偏大，因为其中程序部分可能技巧性比较强，需要很细心。俺也是花了很长时间上机
调试，我认为可能冒泡、插入排序更适合笔试。做完此题后，我还参读了Plauger's stl(VC7)中::std::sort
的源码，不同的是，其阈值默认为32，并且在超过阈值时也作了优化，小于或等于则都用了插入排序，呵呵。。。

struct NullType;

template < class T, class Iterator = T*, class Pr = NullType, class Diff = __int64, Diff threshold = 9 >
struct Sorter;

template < class T, class Iterator, class Diff, Diff threshold >
struct Sorter< T, Iterator, NullType, Diff, threshold >// sort by operator <
{
 typedef T type;
 typedef T& reference;
 typedef const T& const_reference;
 typedef T* pointer;
 typedef Iterator iterator;

 void operator()( iterator begin, iterator end )// sort in field [begin, end)
 {
  QuickSort( begin, end );
 }

 void InsertionSort( iterator begin, iterator end )// sort in field [begin, end)
 {
  type swap_temp;
  for ( iterator i = begin + 1; i < end; ++ i )
  {
   for ( iterator j = i; ( j > begin ) && ( *j < *( j - 1 )  ); -- j )
   {
    swap_temp = *j;
    j[0] = j[-1];
    j[-1] = swap_temp;
   }
  }
 }

 void QuickSort( iterator begin, iterator end )// sort in field [begin, end)
 {
  Diff diff = end - begin;
  // optimize speed with InsertionSort if the number of elements is not more than threshold
  if ( threshold >= diff )
  {
   InsertionSort( begin, end );
   return;
  }

  // find pivot
  iterator pivot = begin + ( diff >> 1 );

  // swap pivot with the element before end
  type swap_temp;
  swap_temp = end[-1];
  end[-1] = *pivot;
  pivot[0] = swap_temp;

  // partition
  iterator right_first = Partition( begin, end - 2, end[-1] );

  // restore pivot to primary position
  if ( right_first < ( end - 1 ) )
  {
   swap_temp = right_first[0];
   right_first[0] = end[-1];
   end[-1] = swap_temp;
  }

  if ( ( right_first - begin ) > 2 )
   QuickSort( begin, right_first );// sort in field [begin, right_first)
  if ( ( end - right_first ) > 3 )
   QuickSort( right_first + 1, end );// sort in field [right_first + 1, end )
 }
private:
 iterator Partition( iterator first, iterator last, const_reference pivot )
 {
  iterator last_temp = last;
  type swap_temp;
  for ( ; first < last; )
  {
   if ( *last < pivot )
   {
    if ( *first < pivot )
    {
     ++ first;
     continue;
    }
    swap_temp = *first;
    first[0] = *last;
    last[0] = swap_temp;
    ++ first;
    -- last;
   }
   else
   {
    if ( *first < pivot )
    {
     ++ first;
     -- last;
     continue;
    }
    -- last;
    continue;
   }
  }
  // calculate the first position of right part
  for ( ; ( !( pivot < *last ) )&& ( last <= last_temp ); ++ last ) {}
  return last;
 }
};

template < class T, class Iterator, class Pr, class Diff, Diff threshold >
struct Sorter< T, Iterator, Pr, Diff, threshold >// sort by Pr
{
 // Just change it1 < it 2 to Pr( it1, it2 )
};

4、判断字符串是否为回环串，类似于"abcdcba"（？），这个可能挺简单，但是好像很多大公司出的
笔试题似乎都很简单，不知其考察点在于什么。。。
template < class Character = char >
struct IsCircleString
{
 typedef Character char_t;
 bool operator()( const char_t* pStr )
 {
  const char_t* pLast = pStr;
  for ( ; 0 != *pLast; ++ pLast ) {}
  if ( ( ( pLast - pStr ) & 0x1 ) == 0 ) return false;//偶数即返回false
  -- pLast;
  for ( ; pStr < pLast; ++ pStr, -- pLast )
  {
   if ( *pStr != *pLast ) return false;
  }
  return true;
 }
};