-_-!!! 我还是少说两句吧～～～继续写代码～～～～

[quote]-_-!!! 我还是少说两句吧～～～继续写代码～～～～[/quote]


怎么了小小C哥，呼呼~~

你说的挺好的啊...

～～～过奖了～～～留些空间给别人么～～～欢迎大家也讲讲自己的～～～

假如不频繁做动态调整的话，同样数据结构，那么数组存储总比链表存储理想一些，至少速度快。例如，如果你用数组存储数据比用链表存储数据，以同样顺序搜索长度的话，前者往往比后者快1~5倍。但是，如果有很多空闲空间，那么数组存储就有点不划算了，还有就是当动态调整(插入或删除)十分频繁时最好不要用数组。

我的编辑器里头，只有当创建地形时才会去分配数组，所以不存在频繁动态调整……我在模型编辑器里头，开始是用 map 的，红黑树，后来测试发现，其查找与插入并不像原来想的这么快啊，尤其在数据量小的时候，于是用数组，二分排序法进行查找和插入，反而比红黑树快！

[quote]我的编辑器里头，只有当创建地形时才会去分配数组，所以不存在频繁动态调整……我在模型编辑器里头，开始是用 map 的，红黑树，后来测试发现，其查找与插入并不像原来想的这么快啊，尤其在数据量小的时候，于是用数组，二分排序法进行查找和插入，反而比红黑树快！[/quote]

如果不做频繁插入删除操作，vector可能最合适，一般性操作vector比deque和list都快，即使在末尾不停的push_back，置于红黑树开销太大，假如您的数据域仅仅存放简单类型，一个节点就需要3个指针和一个标志的额外开销，在32位系统上，一个节点额外开销就是13个字节，由于编译器默认"对齐"，往往达到16个字节的额外开销，如果不是为了动态有序就没有必要用红黑树。

你的情况可能类似这样吧，vector<Type> v; v.reserve(初始值);这样只要不频繁的突破"初始值"个元素空间，存取速度会非常快。

如果对一个简单类型序列的排序，sort最快，如果只对少部分元素排序就用partial_sort，partial_sort通过建议二叉堆进行筛选，您也可以改进partial_sort，比如用您上面提到的四叉堆。如果您只想简单归两类，那么nth_element可能最合适。

其实我们没有必要太死扣数据结构和算法教材，树的存储结构本来就可以用数组或链表，前者没有指针，不适合频繁动态调整，后者有指针适合频繁动态调整。

三维地形数据很不规律，可能没有办法哈希，否则哈希最快。例如，Linux内核的很大一部分功能可能是针对网络，其中有一小项的小项为了提升速度需要缓存一些IP地址，缓存这些地址用了哈希。不过后来有人用trie做了改进，速度虽然基本上没有提升，但是适合动态调整的情况，而且存取速度跟协议无关，使用高负荷下在服务器上测试结果IPV4和IPV6处理速度几乎没有任何差别。

我也曾经用不常用的数据结构二叉trie和链表以及一些内存管理算法配合做了一个malloc/free的替代品，结果测试发现居然比栈上动态分配空间(C99支持栈上动态分配空间)还快，神了！其实trie是一种特殊的哈希，不知道您的能不能用trie。trie的搜索长度只跟二进制位数有关，搜索一个值，在64位系统上最多64步，在32位系统上最多32步，不需要平衡而且也不平衡。

[quote]其实我们没有必要太死扣数据结构和算法教材，树的存储结构本来就可以用数组或链表，前者没有指针，不适合频繁动态调整，后者有指针适合频繁动态调整。

三维地形数据很不规律，可能没有办法哈希，否则哈希最快。例如，Linux内核的很大一部分功能可能是针对网络，其中有一小项的小项为了提升速度需要缓存一些IP地址，缓存这些地址用了哈希。不过后来有人用trie做了改进，速度虽然基本上没有提升，但是适合动态调整的情况，而且存取速度跟协议无关，使用高负荷下在服务器上测试结果IPV4和IPV6处理速度几乎没有任何差别。

我也曾经用不常用的数据结构二叉trie和链表以及一些内存管理算法配合做了一个malloc/free的替代品，结果测试发现居然比栈上动态分配空间(C99支持栈上动态分配空间)还快，神了！其实trie是一种特殊的哈希，不知道您的能不能用trie。trie的搜索长度只跟二进制位数有关，搜索一个值，在64位系统上最多64步，在32位系统上最多32步，不需要平衡而且也不平衡。[/quote]


汗颜！～

数据结构的把握到了这种境界～

现在我想好好学一些高级数据结构，可是资料很不全面，Mark Allen Weiss的 Data Structures and Algorithms Analysis上面都没有提到Trie和Treap，不知道楼上能不能推荐一些书或者网站，我想仿您在博客中红黑树的C++ Templates实现，写一下所有的高级而又少用的数据结构，到时候也挂到论坛和自己的博客上去~~

谢谢～

哥你真的太牛了～～～我一点也看不懂了～～～～

有关trie的介绍到这里下载[url]http://www.cppblog.com/Files/Chipset/trie.rar[/url]