3

有人对我说，每个编译器都以不同的方式实现标准模板库，这是正确的吗？

如果（例如）集合容器是用链表而不是红黑树实现的，如何观察计算复杂性（时间和空间）？

我错过了什么？

4

5 回答 5

11

每个 C++ 编译器都带有 C++ 标准库的实现。一些实现是基于其他的，而一些是独立的。

但是，它们都必须执行该标准。并且该标准对各种功能都有一定的复杂性规范。Aset 不能纯粹作为链表实现并且仍然满足这些保证。因此，如果 C++ 标准库实现set为链表，则它违反了标准。if这与实现错误的 C++ 编译器没有什么不同。

于 2012-10-05T16:44:00.973 回答
10

首先，您可能指的是C++ 标准库，而不是STL。STL 是在 C++ 标准化之前编写的一个库，它严重影响了 C++ 标准库。

现在，C++ 标准提供了实现应该遵循的规则和定义。特别是，标准库被描述为各种部分类定义和函数声明以及它们应具有的属性。该实现可以自由地以它选择的任何方式实现该库，只要它完全符合标准所说的。以下是标准对符合标准的实现（第 1.4 节）的说明：

对于类和类模板，库子句指定部分定义。未指定私有成员（第 11 条），但每个实现都应提供它们以根据库条款中的描述完成定义。

对于函数、函数模板、对象和值，库子句指定声明。实现应提供与库条款中的描述一致的定义。

例如，为了确保std::list实现的复杂度与双链表的复杂度相等，对其成员函数给出了复杂度要求。例如，std::list::insert函数具有以下要求（第 23.3.5.4 节，强调添加）：

将单个元素插入列表需要恒定的时间，并且只需一次调用 T 的构造函数。

这并不一定意味着std::list 必须作为双链表来实现。然而，这是一个常见的选择。实现只能以满足要求的方式运行（或者看起来已经满足要求；as-if 规则）。

于 2012-10-05T16:51:47.937 回答
5

实际标准的示例可能有助于澄清，并且unordered_*我认为这是一个很好的示例，因为它是专门添加的，以便将哈希表纳入标准。这句话来自草稿，但我希望最终版本大体相似：

23.5.4.4 unordered_map 修饰符

template <class P>
pair<iterator, bool> insert(P&& obj);
  1. 要求： value_type 可以从std::forward<P>(obj).
  2. 效果：插入转换为 value_type 的 obj 当且仅当容器中没有与 的键等效的元素时value_type(obj)。
  3. 返回：bool返回的对对象的组件指示插入是否发生，并且迭代器组件指向与 key 的 key 等效的元素value_type(obj)。
  4. 复杂性：平均情况 O(1)，最坏情况 O(size())。
  5. 备注：除非 P 可隐式转换为 ，否则此签名不应参与重载决议value_type。

该标准的其他部分实际上也要求将其实现为哈希表，但我认为重要的部分是它们提出了复杂性要求。

于 2012-10-05T16:54:02.700 回答
3

简短的回答：它不能，作者可能误解了。红黑树被实现为基于节点的容器（即节点以某种方式相互链接），就像链表一样，但是节点链接在一起的方式不同，因为它们对复杂性的要求不同他们的各种操作。

长答案：实际上，有一个误解。

C++ 标准中有两个（在一定程度上交错）组件：

  • C++ 语言本身
  • C++ 标准库

只需要编译器来实现 C++ 语言。事实上，编译器和标准库的实现之间不一定存在一对一的匹配。

例子：

  • Dinkumware 是一家提供自己的 C++ 标准库实现的公司。它卖给了微软，后者将它与 Visual Studio C++ 编译器和 IDE 捆绑在一起。
  • Clang 是一个 C++ 编译器，在大多数 Linux 发行版上将使用 libstdc++ 实现，它通常与 gcc 编译器捆绑在一起。LLVM 项目（托管 Clang）有自己的实现（libc++ 库），但尚未移植到许多 linux 发行版。

标准库的任何实现都必须满足许多要求，包括接口（哪些类/方法、哪些参数、哪些类型……）以及复杂性方面。但是，实现方式确实有所不同。

例子：std::string

  • 在 libstdc++（与 gcc 一起提供）中，std::string该类仅包含一个指向共享类的指针，因为它实现了 Copy-On-Write 习惯用法。
  • 另一方面，在 Dirkumware 实现中，std::string该类要胖得多，因为它实现了 Small-String-Optimization，它new通过重用类中的一些空间来存储小字符串而无需动态分配内存（通过）。

两者都实现相同的接口，但大不相同。

例子：std::sort

The sort algorithm is only required to have a N*log(N) overall complexity, in average. However good implementations will implement either IntroSort algorithms or variations of TimSort, which have lower complexity in many common cases or less disastrous worst case complexity.

It is my understanding that libc++'s implementation is currently the best out of the three libraries I cited, for example.

于 2012-10-05T18:46:32.017 回答
1

如果（例如）集合容器是用链表而不是红黑树实现的，如何观察计算复杂性（时间和空间）？

圣安东尼奥海洋世界曾经归 Anheuser-Busch 所有。当 Anheuser-Busch 买下它时，得克萨斯州奇怪的酒类法律要求 Anheuser-Busch 在海洋世界只销售竞争对手的啤酒。卖芽是违法的。因此，这些酒法的布希例外。Busch 例外没有命名 Anheuser-Busch 或 SeaWorld。那未免太露骨了。但它确实允许 SeaWorld 出售 Bud，并且不适用于其他任何地方。立法者非常擅长制定针对特定组织的法律，而无需命名该组织。

这同样适用于标准编写者。该标准没有在任何地方说红黑树，但要求被严重操纵以支持它们。我怀疑即使是 AVL 树也能满足这些严格的插入要求。AVL 树在插入时放弃了一些性能，以便尽可能快地进行查找。在搜索方面，AVL 树甚至比红黑树更快。

于 2012-10-05T17:58:51.160 回答