如題，想進行帶模板參數的 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秒，我的……等了一分鐘沒等到，放棄了

 

雖然我不注重性能，但也不能差這么多呀，慢一兩倍也差不多了……繼續改進

 

居然已經是國慶了