YXD's Blog

这段时间用了WTL，感觉着实不错，很是轻巧。。。

YXD — 2005-02-04 20:34:00Z

无标题文档

最显而易见的一个效果就是程序的体积会减小不少，我基于wtl写了一个SDI的程序（Release，无document/view architecture支持，静态链接atl库），并添加功能性代码2000多行（也作的模板封装），体积为112K，但是用MFC（Release，无document/view architecture支持，静态链接MFC库），程序通过VC向导自动生成，未添加任何代码体积就已有304k。

模板“被用到才被编译”的特性不觉中起到了缩小程序体积的效果。

wtl的使用也很方便，类、方法名称和MFC几乎一致，与MFC里的类几乎都可以一一对应起来，同时对CE也有支持（当然MFC也有for CE，不过通常我不会用，因为往往手持设备的硬件条件并不像PC那样富余），而且同样因为模板封装的缘故，使得其在CE上的程序体积既表现与纯sdk程序相差不大，wtl出来这么久，才用它实在是惭愧，俺早先固执的认为GUI的编程并不适合用模板的风格，看来对不了解的东西抱着既定的思维去看待必定会产生很大的偏差。

模板封装的方式也无意更叫巧妙、代码也更具高复用性。

附图，我写的那个wtl的程序（其实是老早就想写的Java Script菜单编辑器，托了很长时间上周末才开始写的。。。。:>，争取过年这段时间能利用上。。。）

实现了一个通用的内存流模板类，支持与标准流(stl)的高效直接通信，具有线程策略选择机制，也可用于对COM接口IStream的封装中。

YXD — 2004-12-20 14:31:00Z

早先简单封装了一个CByteStream类（继承了IStream COM接口），但是很低效，且不够灵活。利用周末的两天实现了如下定义的通用内存流类。
template
<
class _Ty,
template < class > class _ThreadingModel = DefaultThreadingModel,
template < class > class _Allocator = ::std::allocator,
class _Size = long,
_Size _block_size = 4096
>
class MemoryStream: public _ThreadingModel< MemoryStream< _Ty, _ThreadingModel, _Allocator > >
{
public:
typedef _Ty      value_type;
typedef value_type*    pointer;
typedef const value_type*  const_pointer;
typedef value_type&    reference;
typedef const value_type&  const_reference;
typedef _ThreadingModel< MemoryStream< _Ty, _ThreadingModel, _Allocator > > ThreadingModel;
typedef _Allocator< _Ty >  block_allocator;
typedef _Size     size_t;
//
// ...
//
}

除了内存管理器(Allocator)外与内存相关访问的封装：
template < class _Ty, class _Size = unsigned int >
struct MemCopier
{
_Ty* operator()( _Ty* pDest, const _Ty* pSrc, _Size cbCopy )
{
::memcpy( pDest, pSrc, cbCopy * sizeof( _Ty ) );
return pDest;
}
};

提供如下公开的调用接口：
函数：
// Read a specified number of type_sizes from the stream object
// into memory, starting at the current seek pointer.
// Return the actual number of type_sizes read from the stream
// object.
size_t Read( pointer pBuf, size_t cbRead )

// Write a specified number of type_sizes into the stream object
// starting at the current seek pointer.
// Return the actual number of type_sizes written into the stream
// object.
size_t Write( const_pointer pBuf, size_t cbWrite )

// Copy a specified number of bytes from the current seek pointer
// in the stream to the current seek pointer in another stream.
size_t CopyTo( MemoryStream& stream, size_t cbCopy )

// Generic version of CopyTo function
template < class _OutStream >
size_t CopyTo( _OutStream& stream, size_t cbCopy )

// Getneric CopyFrom function
template < class _InStream >
size_t CopyFrom( const _InStream& stream, size_t cbCopy )

// Move the stream pointer to a specified location.
// Return the new position of the stream pointer.
size_t Seek( size_t offset, int nSeekMode = MemoryBase::seek_cur )

// Release the memory space occupied by the stream object.
void Clear()

// Return the number of type_sizes of the data existing in the
// stream object.
size_t GetSize() const

// Return the current position of the pointer of the stream object.
size_t Tell() const

// Judge whether the stream pointer is at the end of the stream
// object.
bool End() const

// Judge whether the stream object has data.
bool Empty() const
操作符：
MemoryStream& operator = ( const MemoryStream& stream )

// operator >>
MemoryStream& operator >> ( const_reference vInput )
MemoryStream& operator >> ( const_pointer pInput )
template < class _InStream >
MemoryStream& operator >> ( const _InStream& stream )
MemoryStream& operator >> ( MemoryStream& stream )

// operator <<
MemoryStream& operator << ( reference vOutput )
MemoryStream& operator << ( pointer pOutput )
template < class _OutStream >
MemoryStream& operator << ( _OutStream& stream )
MemoryStream& operator << ( MemoryStream& stream )

几个测试用例如下：
void Test1()
{
fstream infile;
infile.open( "E:\\yxd\\fuzhuang.mpg", ios_base::in | ios_base::binary );
MemoryStream< char > theStream;
theStream >> infile;
infile.close();
fstream outfile;
outfile.open( "E:\\fuzhuang.mpg", ios_base::out | ios_base::binary );
theStream.Seek( 0, MemoryBase::seek_set );
theStream << outfile;
outfile.close();
}

void Test2()
{
MemoryStream< char > theStream;
for ( char n = 'a'; n < 'z' + 1; ++ n )
theStream >> n;
theStream >> 'A';
theStream.Seek( 0, MemoryBase::seek_set );
theStream << cout;
cout << endl;
char szText[] = "this is a test.";
theStream.Write( szText, MemoryStream< char >::size_t( strlen( szText ) ) );
theStream.Seek( 0, MemoryBase::seek_set );
theStream << cout;
cout << endl;
theStream.Seek( 10, MemoryBase::seek_end );
theStream << cout;
cout << endl;
theStream.Seek( -20, MemoryBase::seek_cur );
theStream << cout;
cout << endl;
MemoryStream< char > theStream1( theStream );
theStream1 << cout;
cout << endl;
MemoryStream< char > theStream2 = theStream1;
theStream2 << cout;
cout << endl;
MemoryStream< char > theStream3;
theStream2.Seek( 13, MemoryBase::seek_set );
theStream3 >> theStream2;
theStream3.Seek( 0, MemoryBase::seek_set );
theStream3 << cout;
cout << endl;
char szRead[256] = { 0 };
theStream.Seek( 0, MemoryBase::seek_set );
cout << "Total read size is " << theStream.Read( szRead, 256 ) << " bytes:" << endl;
cout << szRead << endl;
}

void Test3()
{
MemoryStream< char > theStream1;
theStream1.CopyFrom( cin, 10 );
theStream1.Seek( -10 );
theStream1 << cout;
cout << endl;
theStream1.Seek( 0, MemoryBase::seek_set );
MemoryStream< char > theStream2;
theStream1.CopyTo( theStream2, theStream2.GetSize() );
theStream2.Seek( 0, MemoryBase::seek_set );
theStream2 << cout;
cout << endl;
MemoryStream< char > theStream3;
theStream1.Seek( 5, MemoryBase::seek_set );
cout << "Copied " << theStream1.CopyTo( theStream3, theStream1.GetSize() ) << " bytes from theStream1 to theStream3:" << endl;
theStream3.Seek( 0, MemoryBase::seek_set );
theStream3 << cout;
cout << endl;
}

void Test4()
{
MemoryStream< char, ::Loki::ObjectLevelLockable >* theLockableStream = new MemoryStream< char, ::Loki::ObjectLevelLockable >;
for ( unsigned char c = 0; c < 255; ++ c )
*theLockableStream >> char( c );
theLockableStream->Seek( 0, MemoryBase::seek_set );
*theLockableStream << cout;
cout << endl;
//RunStreamPrint( theLockableStream );// Thread #1
//RunStreamPrint( theLockableStream );// Thread #2
//RunStreamPrint( theLockableStream );// Thread #3
//RunStreamPrint( theLockableStream );// Thread #4
//RunStreamPrint( theLockableStream );// Thread #5
//RunStreamPrint( theLockableStream );// Thread #6
}

MemoryStream内部的内存组织方式采用的是基于::std::map这样的索引方式，采用散列的方式在大多数情况下性能应该会有更好的表现，但是这样代码的复杂性会增加，所以我就借用了::std::map，这层针对MemoryStream内部内存结构的组织策略原本也向上一层延迟，交给用户自己决定，但是还是复杂性太高，俺也没想出太好的方法，并且不像线程模型、allocator这样的有很多现成的东西可供选择。另外暂时还缺少对模板参数_Ty一样的MemoryStream之间的直接通信支持，不过比较容易实现。

网上收罗的几道程序笔试题，并附上我的C++解答，有兴趣的可以看看，如果有好的题望不吝赐教。。。俺急需这样的题啊

YXD — 2004-12-14 12:16:00Z

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;
}
};

刚写的程序中犯的一个低级错误。。。。

YXD — 2004-11-25 19:03:00Z

typedef ::std::vector< int > IntArray;

...

IntArray theInts;

...

IntArray::iterator it1, it2;

....

::std::swap( it1, it2 );// error!, should be ::std::swap( *it1, *it2 );

很早以前曾犯的另一个错误：

IntArray theInts;

...

int* g_pTheInt;

...

g_pTheInt = &( *it ) or it;//无效，::std::vector会reallocate。。。

自醒。。。

最近有一个把类似BT的东西与P2P整合在一起做一个服务的想法，虽然概念比较模糊，但是感觉应该会比较有意思

YXD — 2004-10-21 01:35:00Z

Untitled Document

最近有一个把类似BT的东西与P2P整合在一起做一个服务的想法，虽然概念比较模糊，但是感觉应该会比较有意思（不知道是缺点还是有点，当每有新想法时，俺总想立即写出代码印证一下），随即便先实现了一个我特定应用的http server(对于BT还是P2P应用来说，应该都会很有必要)，呵呵，尽管很简陋，但的确是可行的。。。如下图。

But，虽然想做的事很多，人的精力毕竟有限啊，烦心的事也多，fuck！只有一件一件地先做好吧。恨不得做梦也梦见有人给我投资让我无忧无虑地专心写程序。。。