前缀压缩词典
包含多个固定索引，一个可变索引，
固定索引使用一个内存池和一个数组保存项目在内存中的偏移，并且使用前缀压缩，使用空间最小（每个词条4个字节的索引空间）
可变索引不压缩，并且可以动态插入词条，占用空间较大（每个词条20个字节的索引空间）
存储 1000 万个词，占用内存 100M 左右，平均每个词10个字节（包括了字符串空间和索引空间）。
接口采用 stl 容器的风格
cpu 的 cache 是很宝贵的——从互相平行的数组看
以前一直想不通，为什么在有些系统中，要把同一个数据结构的不同字段放入 多个互相平行的数组中，而不是放入一个结构中。 继续阅读
未来的 PC 会怎样
是更简化，还是更复杂？我觉得应该是更简化。
网络速度变得越来越快，终究有一天，会光纤入户，最终，或许用不了多久，网络速度已经比我们的硬盘快了。
目前的PC（个人电脑）之所以是现在这个样子，是因为我们的硬盘，相对于网络有两个优势，一个是速度，一个是隐私。当速度已经不是问题，就只剩一个隐私了。而隐私问题实际上只是一个心理问题，人们总觉得把隐私敏感的东西也存储到网上 不安全，容易泄露，而实际上，保存在自己的硬盘上并不比存在网络上更安全，更不容易泄露。如果大家都认识到这个问题，那么，硬盘，对于PC，就已经不重要了。（——除非此时硬盘已被如Flash一类的新产品代替了，并且速度比网络至少快一个数量级，并且大家有那么高的吞吐量需求。）
应该不会太久，我们设想这时的网络速度是50MB/s，那么pc，只需要内存和cpu，操作系统都不需要了，就像现在的电视，一打开就可以用，并且所有的东西都是最新的（根本不需要什么软件更新一类的东西）。仅仅需要的就如同现在和很久以前的旧时代里从终端登录：用户名，密码。不同的是，那时是consol终端，现在是比Vista更强劲的终端。
pc 的cpu也更快，内存也更大了，而同时，网络分布式计算的增长更快。很多计算根本都不需要pc的参与，他只需要向网络发出命令，比如编辑文档，收发邮件，游戏（图象计算密集的除外，现在的网游服务器可以认为是未来全分布式游戏时代的雏形）。
浏览器也泛化了，进入计算机所有的操作都是在“浏览器”中进行，就像我们现在在在图形界面或consol终端进行操作一样。我们个性化的东西就是自己的配置，配置哪些东西是我一步（我的顶级目录）操作就可以得到，那些东西需要两步（二级目录），那些需要三步，……整个世界上所有的东西我们都可以得到，只是得到它的方便程度不同。
这个终极的理想在过去和现在已经有一些雏形，如一些网吧里的机器，一些学校的机房，有windows的，有linux的。现在ubuntu已经在朝这个方向努力了。如果linux最终能在这个方向上走到windows前面，或许微软的日子就到头了，除非他也顺应时代潮流。
用C++的高级模版特性实现一个不需要IDL的RPC
当然，首要的是为了有用，其次是挑战自己驾驭 C++ 的能力，目前已经全部完成，并且取得了非常好的效果。使用该 RPC 的简短示例代码： 继续阅读
VC++ 6.0 的函数模版解析 bug
struct TTT1 { int x; };
struct TTT2 { int x; };
template<class T1, class T2>
void foo(T1& t1, T2& t2)
{
printf("111111111111/n");
}
template<class T1>
void foo(T1& t1, TTT2& t2)
{
printf("222222222222/n");
}
void foo2()
{
TTT1 x;
TTT2 y;
foo(x, y);
}
上述代码在 vc6 中编译会出错：
error C2667: ‘foo’ : none of 2 overload have a best conversion
error C2668: ‘foo’ : ambiguous call to overloaded function
在 vc2005 中，gcc 中编译都通过。本来一个好好的库，因为这个原因在 VC6 下不能用了。
按序号索引二叉树的应用
主要是快速计数。
可以从Index得到相应结点，也就可以从相应结点得到 Index。
如果有两个结点，通过彼此间的 Index 相减，就可以得到他们之间的结点个数。
这种算法可以推广到使用 B+Tree 或其它更复杂的树。
使用" 参数化基类" 和" 成员函数指针" 模拟实现虚函数－－在实际中的应用
// 使用" 参数化基类" 和" 成员函数指针" 模拟实现虚函数－－在实际中的应用。
#include <stdio.h>
#include <string.h>
/*
病毒或许可以使用这种技术有效地实现，不过这是我在写 Windows PE 文件
加壳程序的时候总结出来的技术。当然可以被用在恶意程序上，任何事情总有两面性！
***注意***
在 VC 中测试时，必须去掉“启用增量连接”，即(/INCREMENTAL:NO)
如果在 ShellCode 或者 Virus 中使用该技术，字符串文字量（string literal）
也必须进行地址转化，即：convert_address("string literal").
使用 "参数化基类 "和 "成员函数指针 "模拟实现虚函数。
可能大家都以为只有疯子才会这么干，好好的虚函数干吗不用，而偏要拐弯抹角地
搞得这么复杂，但有时候这可能是最好地选择。举个例子吧，我写 Windows PE 文件
加壳程序的时候，遇到一个问题：
1. 我开发了一个框架，可以只用 C++ 来写 "壳程序 "，大家很难想到吧！
2. 但不能使用一些 C++ 功能：虚函数，异常处理，还有 switch-case 语句
3. C++ 异常处理可以不用，但是不能使用虚函数可能太过苛刻。
当我看了 "generative programming"以后，觉得 "参数化继承 "
或许可以满足这个需求，模拟实现虚函数。
以下是使用 "参数化继承 "实现虚函数的框架，以及要注意的事项。
BaseClass 显然，实际上是 "抽象基类 "，因为如果实例化
"InstantialClass<ConcreteClass>" 时，ConcreteClass 中
必须定义响应的 "虚函数 "，否则编译就报错。如果相应的
BaseClass 和 InstantialClass 定义正确无误（从代码可以
看到，这很简单，但比较麻烦，必须注意一些细节）。因此
ConcreteClass 编译期错误不会被推迟到运行时才发现，
而使用其它方式模拟，就很难有这个保证。
其实，如果了解 C++ 的底层对象模型，这些需要注意的细节
很容易理解！
//——-
另外有一种 C 语言模拟 C++ 虚函数的方法，可以在我以前
(2002年 )一篇文章中看到。
*/
struct Context
{
int (*printf)(const char *, …);
// other external fuctions…
};
// construct these codes…
int entry(const Context* context)
{
int imp_entry(const Context* context);
return imp_entry(context);
}
template< typename AddressType >
AddressType convert_address(AddressType address)
{
// if used in shell code, this must return another valid address.
#define SUPPORT_RECLOCATION
#ifdef SUPPORT_RECLOCATION
__asm {
call LL
LL: pop eax
sub eax, offset LL
add eax, address
mov address, eax
}
#endif
return address;
}
class BaseClass
{
#define DEFINE_VIRTUAL(ret , name, param_list, call_list ) /
protected : /
typedef ret (BaseClass ::*T## name) param_list ; /
T## name p ##name; /
public : /
ret name param_list /
{ return ( this->*this ->p## name)call_list ; }
//////////////////////////////////////////////////////////////////////////
// expansion of :
/* DEFINE_VIRTUAL(int, Func1,
(int x1, int x2),
( x1, x2)
);
*/
protected :
typedef int (BaseClass ::*TFunc1)( int x1 , int x2);
TFunc1 pFunc1;
public :
int Func1(int x1, int x2 )
{
return ( this->*this ->pFunc1)( x1, x2 );
// return (this->*pFunc1)(x1, x2); // can be simplified as this line.
}
// end expansion
//////////////////////////////////////////////////////////////////////////
DEFINE_VIRTUAL( int, Func2 ,
(int x1, int x2, int x3 ),
( x1 , x2 , x3 )
);
public :
template< typename BaseFuncType , typename ConcreteFuncType>
void assign(BaseFuncType & x, ConcreteFuncType y )
{
// if use C Style cast like "(BaseFunType)(y)", it is danger!!
// any member function can be assigned to x!!
// x = convert_address((BaseFuncType)(y)); // danger!!
x = convert_address(static_cast <BaseFuncType>(y));
}
BaseClass()
{
pFunc1 = 0;
pFunc2 = 0;
}
};
class ConcreteClass1
{
private :
const Context* context;
int x1, x2 , x3;
public :
ConcreteClass1(const Context* context)
{
this->context = context;
}
int Func1(int x1, int x2)
{
this-> x1 = x1 ;
this-> x2 = x2 ;
context->printf("ConcreteClass1::Func1/n");
context->printf("x1=%d, x2=%d/n/n", x1, x2);
return 0;
}
int Func2(int x1, int x2 , int x3)
{
this-> x1 = x1 ;
this-> x2 = x2 ;
this-> x3 = x3 ;
context->printf("ConcreteClass1::Func2/n");
context->printf("x1=%d, x2=%d, x3=%d/n/n", x1, x2, x3);
return 0;
}
};
class ConcreteClass2
{
private :
const Context* context;
int x1, x2 , x3;
public :
ConcreteClass2(const Context* context)
{
this->context = context;
}
int Func1(int x1, int x2 )
{
this-> x1 = x1 ;
this-> x2 = x2 ;
context->printf("ConcreteClass2::Func1/n");
context->printf("x1=%d, x2=%d/n/n", x1, x2);
return 0;
}
int Func2(int x1, int x2 , int x3)
{
this-> x1 = x1 ;
this-> x2 = x2 ;
this-> x3 = x3 ;
context->printf("ConcreteClass2::Func2/n");
context->printf("x1=%d, x2=%d, x3=%d/n/n", x1, x2, x3);
return 0;
}
};
template <class ConcreteClass>
class InstantialClass :
// "BaseClass" must be first base class, otherwise,
// function pointer convert in "BaseClass::assign()" may be not valid!
public BaseClass, // interface inherit, multi inherit is not allowed!!
protected ConcreteClass // implementation inherit, multi inherit is allowed
{
// it is a guide line that do not hold any data member in this class!!
//
// if ‘BaseClass’ is not the first base class for ‘this’ class,
// and data member is defined here,
// and these data member will be modified,
// it will error at runtime!
// you can reverse the inherit order of
// BaseClass and ConcreteClass, and try!!
//
int x1, x2 , x3;
public :
// must delegate these member functions…
int Func1(int x1, int x2 ) { return ConcreteClass::Func1 (x1, x2); }
int Func2(int x1, int x2 , int x3)
{
this-> x1 = x1 ;
this-> x2 = x2 ;
this-> x3 = x3 ;
return ConcreteClass::Func2 (x1, x2, x3 );
}
InstantialClass(const Context* context)
: ConcreteClass(context)
{
// must assign these member function pointers…
// BaseClass::pFunc1 = (TFunc1)(Func1);
// int v = _MSC_VER;
#if _MSC_VER >= 1310 // vc2003
assign(pFunc1, Func1);
assign(pFunc2, Func2);
#else // in vc6, vc6 template support is not perfect!!
pFunc1 = (TFunc1)Func1;
pFunc2 = (TFunc2)Func2;
#endif
// if use C Style cast in assign, follow line can be compiled,
// but will error at runtime, because pointer to ConcreteClass
// is different from to ‘this’!!
// pointer to ‘BaseClass’ is equal to ‘this’..
// so, do not write such code,
// must delegate ‘ConcreteClass::Func2’ to ‘this->Func2’.
// assign(pFunc2, ConcreteClass::Func2);
}
};
template InstantialClass<ConcreteClass1>;
template InstantialClass<ConcreteClass2>;
int imp_entry(const Context* context)
{
InstantialClass<ConcreteClass1> v1(context);
InstantialClass<ConcreteClass2> v2(context);
BaseClass* p1 = &v1;
BaseClass* p2 = &v2;
p1-> Func1(1111 , 2222);
p2-> Func1(1111 , 2222);
p1-> Func2(1111 , 2222, 3333);
p2-> Func2(1111 , 2222, 3333);
p1-> Func1(1111 , 2222);
p2-> Func1(1111 , 2222);
p1-> Func2(1111 , 2222, 3333);
p2-> Func2(1111 , 2222, 3333);
return 0;
}
// template instantiation generated functions were not
// lie in ‘entry()’ and ‘end_address()’.
// this is a problem, we must guess the actual codes size.
//
// it looks as if this is not a good solution for small shell codes.
//
// but in my shell code, I put all code in a PE file,
// and relocate the whole code section of the PE file.
// so, this is good idea for shell code.
// this technic is a good solution for virus,
// —- if you want write virus in C++ and use virtual function!
void end_address() {}
int main(int argc , char* argv[])
{
Context context;
context.printf = printf;
typedef int (*T_entry)(const Context* context);
unsigned char codeBuffer[16*1024];
size_t codeSize = (unsigned char*)end_address – (unsigned char*)entry;
size_t guessedCodeSize = sizeof(codeBuffer);
// memcpy(codeBuffer, (void*)entry, codeSize); // run error!!
memcpy(codeBuffer, (void*)entry, guessedCodeSize); // run ok!!
// entry(&context);
((T_entry)(void*)codeBuffer)(&context);
return 0;
}
使用" 参数化基类" 和" 成员函数指针" 模拟实现虚函数
// 使用" 参数化基类" 和" 成员函数指针" 模拟实现虚函数。
#include "stdafx.h"
/*
使用 "参数化基类 "和 "成员函数指针 "模拟实现虚函数。
可能大家都以为只有疯子才会这么干，好好的虚函数干吗不用
搞得这么复杂，但有时候这可能是最好地选择。举个例子吧，我写 Windows PE 文件
加壳程序的时候，遇到一个问题：
1. 我开发了一个框架，可以只用 C++ 来写 "壳程序 "，大家很难想到吧！
2. 但不能使用一些 C++ 功能：虚函数，异常处理，还有 switch-case 语句
3. C++ 异常处理可以不用，但是不能使用虚函数可能太过苛刻。
当我看了 "generative programming"以后，觉得 "参数化继承 "
或许可以满足这个需求，模拟实现虚函数。
以下是使用 "参数化继承 "实现虚函数的框架，以及要注意的事项。
BaseClass 显然，实际上是 "抽象基类 "，因为如果实例化
"InstantialClass<ConcreteClass
必须定义响应的 "虚函数 "，否则编译就报错。如果相应的
BaseClass 和 InstantialClass 定义正确无误（从代码可以
看到，这很简单，但比较麻烦，必须注意一些细节）。因此
ConcreteClass 编译期错误不会被推迟到运行时才发现，
而使用其它方式模拟，就很难有这个保证。
其实，如果了解 C++ 的底层对象模型，这些需要注意的细节
很容易理解！
//——-
另外有一种 C 语言模拟 C++ 虚函数的方法，可以在我以前
(2002年 )一篇文章中看到。
*/
class BaseClass
{
#define DEFINE_VIRTUAL(ret , name, param_list, call_list ) /
protected : /
typedef ret (BaseClass ::*T## name) param_list ; /
T## name p ##name; /
public : /
ret name param_list /
{ return ( this->*this ->p## name)call_list ; }
//////////////////////////////
// expansion of :
/* DEFINE_VIRTUAL(int, Func1,
(int x1, int x2),
( x1, x2)
);
*/
protected :
typedef int (BaseClass ::*TFunc1)( int x1 , int x2);
TFunc1 pFunc1;
public :
int Func1(int x1, int x2 )
{
return ( this->*this ->pFunc1)( x1, x2 );
// return (this->*pFunc1)(x1, x2); // can be simplified as this line.
}
// end expansion
//////////////////////////////
DEFINE_VIRTUAL( int, Func2 ,
(int x1, int x2, int x3 ),
( x1 , x2 , x3 )
);
protected :
template< typename AddressType >
AddressType convert_address(AddressType address)
{
// if used in shell code, this must return another valid address.
return address;
}
public :
template< typename BaseFuncType , typename ConcreteFuncType>
void assign(BaseFuncType & x, ConcreteFuncType y )
{
// if use C Style cast like "(BaseFunType)(y)", it is danger!!
// any member function can be assigned to x!!
// x = convert_address((BaseFuncType)
x = convert_address(static_cast <BaseFuncType>( y));
}
BaseClass()
{
pFunc1 = 0;
pFunc2 = 0;
}
};
class ConcreteClass1
{
private :
int x1, x2 , x3;
public :
int Func1(int x1, int x2 )
{
this-> x1 = x1 ;
this-> x2 = x2 ;
std:: cout << "ConcreteClass1::Func1" << "/n" ;
std:: cout << "x1=" << x1 << ", x2=" << x2 << "/n/n";
return 0;
}
int Func2(int x1, int x2 , int x3)
{
this-> x1 = x1 ;
this-> x2 = x2 ;
this-> x3 = x3 ;
std:: cout << "ConcreteClass1::Func2" << "/n" ;
std:: cout << "x1=" << x1 << ", x2=" << x2 << ", x3=" << x3 << "/n/n";
return 0;
}
};
class ConcreteClass2
{
private :
int x1, x2 , x3;
public :
int Func1(int x1, int x2 )
{
this-> x1 = x1 ;
this-> x2 = x2 ;
std:: cout << "ConcreteClass2::Func1" << "/n" ;
std:: cout << "x1=" << x1 << ", x2=" << x2 << "/n/n";
return 0;
}
int Func2(int x1, int x2 , int x3)
{
this-> x1 = x1 ;
this-> x2 = x2 ;
this-> x3 = x3 ;
std:: cout << "ConcreteClass2::Func2" << "/n" ;
std:: cout << "x1=" << x1 << ", x2=" << x2 << ", x3=" << x3 << "/n/n";
return 0;
}
};
template <class ConcreteClass>
class InstantialClass :
// "BaseClass" must be first base class, otherwise,
// function pointer convert in "BaseClass::assign()" may be not valid!
public BaseClass, // interface inherit, multi inherit is not allowed!!
protected ConcreteClass // implementation inherit, multi inherit is allowed
{
// it is a guide line that do not hold any data member in this class!!
//
// if ‘BaseClass’ is not the first base class for ‘this’ class,
// and data member is defined here,
// and these data member will be modified,
// it will error at runtime!
// you can reverse the inherit order of
// BaseClass and ConcreteClass, and try!!
//
int x1, x2 , x3;
public :
// must delegate these member functions…
int Func1(int x1, int x2 ) { return ConcreteClass::Func1 (x1, x2); }
int Func2(int x1, int x2 , int x3)
{
this-> x1 = x1 ;
this-> x2 = x2 ;
this-> x3 = x3 ;
return ConcreteClass::Func2 (x1, x2, x3 );
}
InstantialClass()
{
// must assign these member function pointers…
// BaseClass::pFunc1 = (TFunc1)(Func1);
assign( pFunc1, Func1 );
assign( pFunc2, Func2 );
// if use C Style cast in assign, follow line can be compiled,
// but will error at runtime, because pointer to ConcreteClass
// is different from to ‘this’!!
// pointer to ‘BaseClass’ is equal to ‘this’..
// so, do not write such code,
// must delegate ‘ConcreteClass::Func2’ to ‘this->Func2’.
// assign(pFunc2, ConcreteClass::Func2);
}
};
int _tmain( int argc , _TCHAR* argv[])
{
BaseClass* p1 = new InstantialClass< ConcreteClass1>();
BaseClass* p2 = new InstantialClass< ConcreteClass2>();
p1-> Func1(1111 , 2222);
p2-> Func1(1111 , 2222);
p1-> Func2(1111 , 2222, 3333);
p2-> Func2(1111 , 2222, 3333);
p1-> Func1(1111 , 2222);
p2-> Func1(1111 , 2222);
p1-> Func2(1111 , 2222, 3333);
p2-> Func2(1111 , 2222, 3333);
delete p2;
delete p1;
return 0;
}
stl::set 的一个缺陷
stl::set 什么都好，就一点不好：不能仅仅通过 key去查找元素。
例如 ：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <set> struct my_struct { int key; int value1; int value2; //…………… explicit my_struct(int key_) // explicit 禁止将 int 悄悄转化为 my_struct : key( key_) { } struct compare { bool operator()(const my_struct& l, const my_struct& r) const { return l.key < r. key; } bool operator()(const int key, const my_struct& r) const { return key < r .key; } bool operator()(const my_struct& l, const int key) const { return l.key < key; } }; struct ptr_compare { bool operator()(const my_struct* l, const my_struct* r) const { return l->key < r-> key; } bool operator()(const int key, const my_struct* r) const { return key < r ->key; } bool operator()(const my_struct* l, const int key) const { return l->key < key; } }; }; //…… typedef std:: set<my_struct , my_struct::compare> my_set_type ; typedef std:: set<my_struct*, my_struct::ptr_compare> my_ptr_set_type ; //…… void foo() { my_set_type my_set; my_struct x( 1); //.... my_set. insert(x ); my_struct y( 100); my_set. insert(y ); //..... // 错误，不能这样，如果把 explicit my_struct(int key_) // 中的 explicit 去掉，这样就可以，但仍然（悄悄地） // 增加了创建一个 my_struct 的开销 my_set_type:: iterator iter2 = my_set. find(100 ); // 只能这样 my_struct asKey(100 ); my_set_type:: iterator iter1 = my_set. find(asKey ); // 或者这样，都增加了创建一个 my_struct 的开销 my_set_type:: iterator iter3 = my_set. find(my_struct (100)); } void foo2() { my_ptr_set_type my_ptr_set; my_struct x( 1); //.... my_ptr_set. insert(&x ); my_struct y( 100); my_ptr_set. insert(&y ); //..... // 错误，不能这样 my_ptr_set_type:: iterator iter2 = my_ptr_set. find(100 ); // 只能这样 my_struct asKey(100 ); my_ptr_set_type:: iterator iter1 = my_ptr_set. find(&asKey ); // 或者这样 my_ptr_set_type:: iterator iter3 = my_ptr_set. find(&my_struct (100)); } // 如果 std::set::find 是个 template member function: // template<typename Key> iterator find(Key key) { ... } // 那么 my_ptr_set.find(100) 就是合法的，并且不会增加创建一个对象的开销 |
搞 Java 也有一段时间了
搞 Java 也有一段时间了。
Java 现在也支持 GP 了。
但是感觉 Java 好像总是那么那么的。
可能是 C++ 用惯了。
但是 C++ 的表达能力是在是比 Java 强得多。
MS 也推出了 C++/CLI，简单得看了一下，那简直就是我梦想中的 C++ 应该有的样子，虽然看上去有点复杂。
Java 的 GP 语法，虽未如 C++ 般达到了图灵完备，但是它的 F－约束，比起 C++ ，要好一些，它很直观，而实际上在 C++ 中没有相同的语法结构。
C++ 有没有必要也增加这种语法呢？