对一个容器来说，最常用的操作无非3个：插入，查找，删除。

一直想要个三个操作都非常高效的容器，好多年前做了个BaseObjectSet，用STL的MAP和LIST实现的，MAP管理所有插入的对象，实现快速查找，LIST作为空闲表，管理所有被删除的对象。这个实现有以下2个问题：
1. MAP的插入很慢，特别是STL的MAP
2. 插入对象时，要从LIST删除一个节点，然后到MAP增加一个节点，其实MAP和LIST可以共享一个管理节点，MAP用3个指针，LIST用1个指针；同理，删除时也可以省略删除和增加管理节点的开销

因此，最近从Linux内核中移植过来一个红黑树的算法，改成和LIST共享的管理节点，果然效率提高非常多。10万个对象中，插入1000个新对象，每个操作的开销从原先的1430（周期）下降到456，查找从611下降到304，删除从1766下降到343；也就是说，插入和删除有4-5倍的效率提升，查找效率也提升了1倍。

但是，测试的对象除了ID，只有4个字节的一个int。当我把对象大小提高到了512字节时，效率下降的很快。同样，10万个对象，插入1000个新对象，开销从456上升到1231，查找从304上升到454，删除从343上升到467。对于STL的实现来说，则没有这么大的变化，开销几乎没变。

无责任猜想：这是因为对象的ID保存在对象上，当管理的对象很大时，比如10万个512字节的对象，占用50M内存。这时因为每个ID间隔的很大，导致Cache命中率的下降，各类操作的效率都下降的很快。STL的MAP节点也是管理节点和ID在一起的，为啥STL没啥大的变化，本人百思不得其解。

因此，我做了一个新的对象容器，将所有的管理节点分配在整个内存区域的最前面，而数据块在后面。管理节点一共12个字节，比STL的MAP还少了2个字节。ID被移到了管理节点上，因此管理节点一共16个字节。

但是，这样的做法，导致了获取对象ID时的操作慢了很多，从原先直接加便宜读取，变成现在需要根据对象指针判断在哪个内存块中，然后计算偏移，获取对应的管理节点，才能在管理节点上得到ID。只有一块内存块时，获取ID的开销小于10周期，还算可以接受的。

下面是测试数据：
MY1是用自己实现的红黑树加上单链表实现的，要求对象从有ID的基类派生
MY2是在MY1之上改进的，开了256的hash table，table里才是红黑树，然后管理节点分配在开头，后面才是对象。


对网游来说，对象个数一般在10万这个数量级上，对象大小也不会大于512字节，插入、查找、删除开销都在400周期以下，是个可以放心使用的容器了。