如题，想进行带模板参数的 typedef，如：

template <typename T>

typedef RBTree<T> Set<T>;

template <typename T>

typedef Set<List<T>> MultiSet<T>;

template <typename K, typename V>

typedef Set<Pair<K, V>> Map<K, V>;

template <typename K, typename V>

typedef Map<K, List<V>> MultiMap<K, V>;

却无这种语法。

 

目前能想到的就是

template <typename T>

class Set : public RBTree<T>

{

};

template <typename T>

class MultiSet : public Set<List<T>>

{

};

template <typename K, typename V>

class Map : public Set<Pair<K, V>>

{

};

template <typename K, typename V>

class MultiMap : public Map<K, List<V>>

{

};

 

不知有没有更好的方法？

我被那些 红黑树规则+双向指针 搞得头昏脑胀了
现在总算有点头绪了，自己看看似乎没问题
求请各位大大有空帮忙小测试一下，可能有些情况我还是没考虑到

测试程序下载
（如果有问题，烦请告知操作序列(可以按 P 查看)）

测试程序是一个 InstallShield 做的 Windows Installer 安装程序，发布方式为单一 EXE，Menifest 中指定 requireAdministrator，在 Win7 标准用户下双击执行，在弹出的 UAC 对话框中选择一个管理员用户。这种情况下，对于这个程序来说，HKEY_CURRENT_USER 为管理员用户的数据，SH… 系列 API 的执行环境也是管理员用户，如 SHGetFolderPath 取 AppData 目录取到的是管理员用户的 AppData 目录。

但如果从控制面板=>添加删除程序（程序和功能）里执行（相当于执行 msiexec /…），在过一会儿弹出的 UAC 对话框中选管理员用户，此时 HKEY_CURRENT_USER 为管理员用户的数据，但是 SH… 系列 API 的执行环境却是标准用户。查看两个 MsiExec.exe 进程，其中一个是 System 用户的，也就是 Windows Installer 服务对应的进程；另一个是管理员用户的，但是用 Process Explorer 查看，它的所有环境路径全是标准用户的。

觉得有点奇怪，是以记之。^_^

我作了双向扩充实现。昨天的方案是：

先判断插入的元素靠前还是靠后，靠哪边就准备往哪边挪旧元素，然后检查那头有没有空，没空换另一头，要是都没空但两头加起来却有空，那就重新调整位置，最后才重新分配空间。

我原以为考虑得好周到，可是实现起来却傻了眼。往末尾插入10万数据，有9万多次发生移动元素，不慢才怪。

 

调整了下，变成：

先判断考前还是靠后，靠哪边就往哪边挪旧元素，如果那头没空，直接重新分配空间，空间按每次*3增长直至足够。

 

这样，push_back 的性能与 std::vector 以及 std::deque 的粗略比较如下（图中的单位写错了，全是秒）：

 

insert(begin(), i) 比较：

（vector 参与这项比较果然是不公平的，呵呵）

 

insert 到 begin + size() / 2 处：

 

resize 至固定大小，然后用 iterator 遍历赋值：

（今天回家了。以上测试都在家里的机器上做的，配置： AMD SP2500+ 1.4GHz，512MB RAM。）

 

这样的结果还算满意的。不知道 vector 为什么能保持 push_back 如此高效~

还有个挺奇怪的现象，使用 deque 的时候，如果数据量到百万，临退出前有好长一段时间要等待，难道是 deque 在做某些析构动作？

再呢。。貌似 deque 的 push_front 并没有 vector 的 push_back 神么、、

 

嗯……我的本意不是为了着重性能，而是尝试些有着那么一套接口的东西出来，同时也给自己用。现在来比性能只是为了论证一下实用程度如何，如此而已。

具体实现代码就不贴了，基本接口和上上篇里没多少变化。等以后这方面的东西做完了再一起拿出来。

push_back 100000 次，比 std::vector 慢100倍，比 std::deque 慢八九倍

push_back 1000000 次，std::vector 0.0x 秒，std::deque 0.1x秒，我的……等了一分钟没等到，放弃了

 

虽然我不注重性能，但也不能差这么多呀，慢一两倍也差不多了……继续改进

 

居然已经是国庆了