7.14　对STL的扩充

尽管STL容器可以提供用户曾经需要的全部功能，但它们不是十全十美的。比如标准的set和map的实现都使用树型数据结构，尽管其操作相当快速，但并没有快速到足以满足用户需要的程度。在C++标准委员会中，对将利用散列算法实现的set和map包括进C++标准中的想法已经达到共识。然而由于没有足够的时间加入这些组件，最终他们放弃了这样做。^[1]

幸运的是，还有可利用的免费替代品。有关STL的美好之处之一，就是它为创建类-STL（STL-like）的类建立了基本的模型。因此如果用户已经熟悉了STL，那么使用同样的模型创建的任何东西就都很容易理解了。

来自于Silicon Graphics^[2]的SGI STL是最健壮的STL的实现之一，如果有需要可以用这个SGI STL替代用户编译器所使用的STL。另外，SGI增加了很多扩充的容器，包括hash_set、hash_multiset、hash_map、hash_multimap、slist（单链表）和rope（它是一个string的变种，对非常大型的字符串、字符串的快速联结和取子串等操作进行了优化）。

现在考虑在基于树结构的map和SGI hash_map之间进行性能比较。为简单起见，这里将进行从int到int之间的映射：

通过运行这个演示性能测试的程序，在所有的操作中hash_map超越map其速度有大约4：1的改进（而且就像所预期的那样，对于两种类型的map进行查寻，find（）都比operator[]稍微快些）。如果profiler显示出用户map中的性能成为系统的瓶颈，可以考虑使用hash_map。

[1]它们可能包括在标准C++的下一个发行版本中。

[2]参见http：//www.sgi.com/tech/stl。