|
|
发表于 2005-7-6 12:03:00
|
显示全部楼层
Re: 大家写engine的，用stl还是自己写？
拿去年一件事情来说，当时我还在用std::string 实现一个脚本解析引擎。但是后来发现同一个字符串有可能在内存中存在N个，比如 "int" "function" "temp"等等。于是就想到把所有的script 载入，接着tokenlize 然后根据每个token的hash(key, 字符串地址)来保存，脚本所牵涉的字符串分配的时候首先计算字符串的哈西值，然后检索hash_table ,如果已经存在，直接返回这个字符串地址，如果不存在，则再创建。 字符串hash的算法复杂度很小很小，且脚本约定全部使用小写，连tolower,toupper也都免了。最后的结果也证明，这样做效率很高。而且引发一个思路，这样分配的同内容字符串地址在运行期是唯一的，那么对资源的管理，确保资源读取的唯一性上也很方便，一般是判断资源文件名是否已经存在，后来可以就直接根据字符串地址的hash(资源路径字符串地址 ---> 资源对象)来判断资源是否已经读取。地址的hash是再快不过的了。
问题来了。我需要修改整个项目中所有的std::string , 所有的new char 所有的delete p(字符串指针) 操作！ 所有的str+str2 这样的东东。。。。。
我不是很明白你的意思，但是我估计可能是这么回事，你一开始用了std::string来解析脚本文件，然后觉得这种方法不好，后来改用hash表来检索脚本。然后你觉得是std::string不够灵活，这有点牵强。呵呵，我是这么觉得的，可能我的理解不对。
我还是谈一谈我对std::string的看法和理解，STL都是有源代码的，只不过大师们的编码风格太怪异了，看他们的代码比较费劲。
STL不会使用任何C或者C++的库函数，也更不会使用操作系统应用接口函数，当然，唯一与系统打交道的是构造器，不同的编译器STL内中的构造器汇编出来可能会不一样。
std::string里面究竟封装了什么？封装了2个东西，一块静态的内存空间和一个指针。也就是说std::string在使用时是静态的连续的。只有当长度变大时，就是原来的空间无法满足现有的字符串内容时才会分配新的地址。同时要注意的是这里仅仅是变大，如果字符串变小了，不会重新分配一个小的地址空间。也就是说std::string只会越来越大不会越来越小，直到最后释放。
也就是说std::string是一个轻量级的MFC中的CString，std::string主要的用途就是用来处理字符串的查找比较替换等等常见操作，比如你想把字符串中的空格都去掉，那么用std::string要比char *，wchar *要方便一些。而且std::string也重载了一些操作符，你可以把它当字符数组使用[]来检索，也是很方便的，这个效率不会太差，因为本身也就是指针操作，还避免了越界。如果你对这个越界的检查损失的效率感觉有点舍不得，那你就把那段代码注释掉吧。如果你仅仅就是用个地址存放一下字符串，不对字符串作很多的操作，那么用char *，wchar * 就可以了，也没有必要用std::string。
再说hash表，STL据我了解是没有hash表的，有些版本的STL中增加了hash表，比如VC++.NET(VC7.1)中就有hash_set和hash_map，但是不在std命名空间中，而是在stdex命名空间里。我要说的就是VC++.NET中的hash表算法。
VC++.NET中的hash值有4个函数，分别是std::base_string(也就是std::string)，const char * ，const wchar *和其他类型，对于其他类型，hash值算法非常简单就是将其转换成整型然后和_HASH_SEED异或一下。
#define _HASH_SEED (size_t)0xdeadbeef
也就是说hash函数有专门针对std::string的算法，当然也是比较简单的，如果对这些hash值的算法不满意，可以完全替换掉，写一套新的或者增加新的。
对于其中要注意的是const char * 和char *的区别，平时我们可能在其中转换来转换去的并不在意，但是，在使用VC++.NET的hash表时有可能会把char *当成其他类型来处理，会出现明明两个相同的字符串怎么hash值不一样的情况。
再说一下STL中的比较大小，STL经常会判断2个变量是否相等，但是我们印象中很难想象比如我们自定义的类型怎么比较大小。STL使用一个叫comparator的玩意（比较器？）来比较大小，其实就是一些隐含的运算符，都定义在#include<functional>中。
同时hash表中使用的是向量std::vector来存储hash表的，这个跟std::string机制一样，也是变长度的。
上面说的是我对STL的一些理解，不知道对不对，欢迎大家指教，至于说好不好用，愿不愿意用，那是个人喜好，不强求。
|
|
