STL-每个编译器实现方式是否有所不同？ [英] STL - does every compiler implement it differently?

问题描述

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

It was said to me that the standard template library is differently implemented by every compiler, is this correct?

计算复杂度（时间和空间）如何变化？ （例如）是否使用链接列表而不是红黑树实现集合容器？

How can computational complexity (both in time and space) be observed if (for instance) the set container is implemented with a linked list rather than a red-black tree?

我错过了什么吗？

推荐答案

首先，您可能是指 C ++标准库，而不是 STL 。 STL是在C ++标准化之前编写的一个库，在很大程度上影响了C ++标准库。

First things first, you probably mean the C++ standard library, not STL. The STL was a library written before C++ was standardised that heavily influenced the C++ standard library.

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

Now, the C++ standard provides rules and definitions that an implementation should conform to. In particular, the standard library is described as various partial class definitions and function declarations and the properties that they should have. The implementation is free to implement the library in any way it chooses, as long as it meets exactly what the standard says. Here's what the standard says about a conforming implementation (§1.4):

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

For classes and class templates, the library Clauses specify partial definitions. Private members (Clause 11) are not specified, but each implementation shall supply them to complete the definitions according to the description in the library Clauses.

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

For functions, function templates, objects, and values, the library Clauses specify declarations. Implementations shall supply definitions consistent with the descriptions in the library Clauses.

例如，为了确保 std的复杂性：： list 的实现与双向链接列表的实现相同，其成员函数具有复杂性要求。例如，给 std :: list :: insert 函数提供以下要求（§23.3.5.4，增加了强调）：

For example, to ensure the complexity of a std::list implementation is equal to that of a double-linked list, its member functions are given complexity requirements. For example, the std::list::insert functions are given the following requirement (§23.3.5.4, emphasis added):

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

Insertion of a single element into a list takes constant time and exactly one call to a constructor of T.

这不一定意味着 std :: list 必须被实现为双向链接列表。但是，这是一个常见的选择。实现只能以满足要求的方式行事（或者出现表明已经满足要求； 假设规则）。

This doesn't necessarily mean that std::list must be implemented as a double-linked list. However, this is a common choice. An implementation must only act in such a way that the requirements are met (or that it appears that the requirements have been met; the as-if rule).

这篇关于STL-每个编译器实现方式是否有所不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！