id:Cryolite:20040422で紹介したスレッドの続きですが
http://www.talkaboutprogramming.com/group/comp.lang.c++.moderated/messages/160306.html
[snip] The bad news is that most compiler implementations store all instantiations of a particular template (MaxSize) in a single linked list, which means that instead of an O(1) hash_map lookup, you get linear time for each lookup. That said, the constant for doing a lookup in the linked list is usually negligible compared to the cost of actually instantiating a template. [snip]
この問題も前から言われてましたが，instantiationのコストに対して十分償却できるコストなのであんまり指摘されてきませんでした．が，こうもTMPが普及してきてここで議論されているようなinstantiationの数が多いものに対してはヤバい話です．compile時にcomplilerが持っている内部データ構造に依存するなんてとんでもない話ではあるんですが・・・．個人的にはそのうち規格書に「O(n) in compile time」な〜んてcomplexityの記述が載るんじゃないかと思ったりしてるんですがｗ．（半分冗談，半分本気ｗ）
