YXD's Blog

Home Contact Syndicate this Site (RSS 2.0) Syndicate this Site (Atom) 登录
  随笔 18 :: 收藏 1 :: 评论 0 :: 寻迹: 1

随笔

随笔归档

收藏

图库

Friends' Blogs

from cndev

Technical Blogs

2005-02-04 #

无标题文档

最显而易见的一个效果就是程序的体积会减小不少,我基于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菜单编辑器,托了很长时间上周末才开始写的。。。。:>,争取过年这段时间能利用上。。。)

发表于 @ 20:34 | 评论与反馈 (1)

2004-12-20 #

早先简单封装了一个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之间的直接通信支持,不过比较容易实现。

发表于 @ 14:31 | 评论与反馈 (6)

2004-12-14 #

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

发表于 @ 12:16 | 评论与反馈 (6)

2004-11-25 #

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。。。

 

自醒。。。

发表于 @ 19:03 | 评论与反馈 (0)

2004-10-21 #

Untitled Document

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

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

发表于 @ 01:35 | 评论与反馈 (2)