常见问题解答

关于 SGI 标准模板库

STL 是否兼容 Y2K（千年虫）？
是的。STL 不会以任何方式存储或操作日期，因此不存在 2000 年问题。

我能否下载整个网站以供离线查看？
是的。从主页转到下载 STL页面。您将找到下载整个 STL 文档（单个文件）的链接zip, tar或tar.gz文件。

该文档是以下文件的集合：HTML文件。它不存在于单个文本或 PostScript^TM文档的形式。其他资源页面列出了关于 STL 的几本书。

支持哪些编译器？
STL 已在以下编译器上进行了测试：SGI 7.1 及更高版本，或 7.0 且带有 -n32 或 -64 标记；gcc 2.8 或 egcs 1.x；Microsoft 5.0 及更高版本。（但请参见下文。）Boris Fomitchev 为一些其他编译器分发了移植版本。

如果您成功地使用 SGI STL 与其他编译器，请告知我们，并告诉我们您做了哪些修改（如果有）。我们预计大多数更改将仅限于<stl_config.h>头文件。

旧版 SGI 编译器怎么样？
鉴于 C++ 实现的改进速度，SGI 强烈建议您升级编译器。如果无法做到这一点，您可以尝试针对旧版 Borland 和 Microsoft 编译器的 STL 版本（请参见下载 STL页面），或 Boris Fomitchev 的移植版本。这两个版本都不受支持。

如何安装 SGI STL？
您应该将 STL 包含文件解压到一个新目录中，然后使用-I（或/I）选项指示编译器首先查找该目录。我们不建议覆盖供应商的包含文件。

目前，SGI STL 完全由头文件组成。您无需构建或链接任何其他运行时库。

与 Visual C++ 存在任何兼容性问题吗？
Visual C++ 提供了自己的 STL 实现，并且其他一些 Microsoft C++ 库头文件可能依赖于该实现。特别是，SGI STL 尚未与 Microsoft 的新版本结合测试<iostream>头文件。它已成功与旧版本一起使用<iostream.h>头文件。

SGI STL 是否线程安全？
是的。但是，您应该意识到并非每个人都以相同的方式使用“线程安全”一词。请参阅我们的线程安全讨论，了解我们的设计目标。

哈希表是 C++ 标准的一部分吗？
不是。哈希表类（hash_set, hash_map hash_multiset hash_multimap hash）是扩展。它们可能会添加到 C++ 标准的未来修订版中。

Therope和slist类也是扩展。

为什么list<>::size()是线性时间？
Thesize()成员函数，对于list和slist，花费的时间与列表中元素的数量成正比。这是一个经过深思熟虑的权衡。获得常数时间size()对于链表的唯一方法是维护一个额外的成员变量，其中包含列表的大小。这将需要花费额外的时间来更新该变量（它会使splice()成为线性时间操作，例如），并且它还会使列表更大。许多列表算法不需要额外的字（需要它的算法可能比列表更适合使用向量），并且，当需要维护显式的大小计数时，用户可以自己完成。

此选择由 C++ 标准允许。标准指出size()“应该”是常数时间，“应该”与“必须”的意思不同。这是 ISO 官方推荐的措辞，用于表示实现应该执行某些操作，除非有充分理由不执行。

线性时间的一个含义size()：您永远不应该编写

  if (L.size() == 0)
    ...

  if (L.empty())
    ...

为什么map的 operator< 不使用map的比较函数？
Amap具有比较的概念，因为它其中一个模板参数是比较函数。但是，operator<对于映射，使用元素的operator<而不是该比较函数。这看起来很奇怪，但这是故意的，我们相信它是正确的。

在最简单的层面上，这不是我们实现中的错误，因为这是 C++ 标准规定的。（operator<的行为在第 23.1 节的表 65 中进行了描述。）

一个更有趣的问题：标准中的要求是否正确，或者标准中实际上是否存在错误？

我们认为标准中的要求是正确的。

首先，存在一个一致性参数operator<对于一个vector（或deque或list）使用元素的operator<。应该map的operator<执行其他操作，仅仅因为存在另一种合理的比较对象的方法吗？对于所有容器来说，说operator<总是意味着operator<，并且如果您需要其他类型的比较，您可以显式地使用lexicographical_compare.

其次，如果我们确实使用了map的比较函数，就会出现一个问题：我们使用哪一个？有两个map参数，虽然我们知道它们的比较函数具有相同的类型，但我们不知道它们的行为是否相同。毕竟，比较函数是一个函数对象，它可能具有影响比较的内部状态。（例如，您可能有一个函数对象来比较字符串，并使用一个布尔标志来确定比较是否区分大小写。）

顺便说一句，还有一个相关的问题：operator==对于集合应该如何表现？Aset的比较函数会产生一个等价关系，因此，就像您可以使用set的比较函数进行字典序排序一样，您也可以将其用于等价版本。但是，我们定义operator==(const set&, const set&)以便它只调用元素的operator==.

为什么一个vector在执行重新分配时将其存储空间扩展两倍？
扩展一个vector两倍是一个时间-空间权衡；这意味着当您构建一个vector一次一个元素时，每个元素（平均）将被复制两次，并且浪费空间与使用空间的比率最多为 1。（一般来说，如果扩展的指数为 r，则最坏情况下的浪费/使用比率为 r - 1，并且元素被复制的次数接近于 r/(r - 1)。例如，如果 r = 1.25，则元素被复制五次而不是两次。）

如果您需要更精细地控制vector的内存使用情况，您可以使用成员函数capacity()和reserve()而不是依赖于自动重新分配。

为什么pop成员函数返回void?
所有 STL 的pop成员函数（pop_backinvector, list，和deque; pop_frontinlist, slist，和deque; popinstack, queue，和priority_queue）返回void，而不是返回已删除的元素。这是为了提高效率。

如果pop成员函数要返回已删除的元素，那么它们必须通过值而不是通过引用返回该元素。（该元素正在被删除，因此没有可供引用指向的内容。）但是，通过值返回效率低下；它将至少涉及一次不必要的复制构造函数调用。pop成员函数不返回任何内容，因为它们无法以既正确又高效的方式返回值。

如果您需要检索值然后将其删除，则可以显式地执行这两个操作。例如

  std::stack<T> s;
  ...
  T old_value = s.top();  
  s.pop();

如何按降序而不是升序对一个范围进行排序？

sort(first, last, greater<T>());

为什么我从 Purify 中获得未初始化内存读取？^TM?
我们认为 STL 数据结构中的未初始化内存读取 (UMR) 消息是人为因素，可以忽略。

编译器可能会生成来自未初始化内存的读取的原因有很多（例如结构填充、从空基类继承，这些类仍然具有非零大小）。Purify 试图通过区分未初始化内存读取 (UMR) 和未初始化内存复制 (UMC) 来解决此问题。后者默认情况下不会显示。两者之间的区别并不完全清楚，但似乎有点启发式。启发式方法的有效性似乎取决于编译器优化等。因此，一些完全合法的代码会生成 UMR 消息。不幸的是，通常很难判断 UMR 消息是否代表真正的问题或仅仅是人为因素。

为什么 Bounds Checker^TM说我存在内存泄漏？
这不是 STL 错误。这是某些类型的泄漏检测器的产物。

在默认的 STL 分配器中，为小对象块分配的内存不会返回给malloc。它只能被后续allocate（大约）相同大小的请求重用。因此，使用默认分配器的程序在某些类型的简单泄漏检测器的监控下可能会显示内存泄漏。这是故意的。此类“泄漏”不会随着时间的推移而累积。此类“泄漏”不会被垃圾收集器之类的泄漏检测器报告。

默认 STL 分配器的主要设计标准是使其不比 HP STL 每个类的分配器慢，但可能线程安全，并且不易出现碎片。与 HP 分配器一样，它不维护必要的数据结构来释放所有包含的小对象都不在使用状态时整个小对象块。这是一个有意选择执行时间而不是空间使用率的选择。它可能不适用于所有程序。在许多系统上malloc_alloc可能更节省空间，并且可以在空间使用率至关重要时使用。

HP 分配器设计在整个分配器不再需要时返回整个内存池。为了允许这样做，它维护了一个使用特定分配器的容器计数。使用 SGI 设计，这只会发生在最后一个容器消失时，这通常就在程序退出之前。在大多数环境中，这将适得其反；free通常必须在操作系统回收它们之前触摸许多长时间未引用的页面。它通常会在程序退出时引入明显的延迟，并且可能会换出其他应用程序的大部分内容。此操作没有任何好处，因为操作系统会在程序退出时回收内存，并且它应该在不触摸该内存的情况下回收内存。

一般来说，我们建议使用malloc_alloc运行泄漏检测测试。这会产生更精确的结果（例如，Pure Atria 的 Purify^TM），并且即使对于仅计算分配和释放的检测器，它也提供了有用的结果。