STL - 每个编译器都以不同的方式实现它吗？

Question

有人告诉我,标准模板库是由每个编译器实现的,这是正确的吗？

如果(例如)使用链表而不是红黑树实现集合容器,如何计算复杂性(时间和空间)？

我错过了什么？

Answer 1

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

但是,他们都必须执行标准.并且该标准具有某些复杂性规范,它需要各种功能.A set 不能纯粹作为链表实现,仍然可以满足这些保证.因此,如果C++标准库实现set为链表,那么它违反了标准.这与执行if错误的C++编译器没有什么不同.

Answer 2

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

现在,C++标准提供了实现应该遵循的规则和定义.特别是,标准库被描述为各种部分类定义和函数声明以及它们应具有的属性.只要符合标准所说的内容,实现就可以以任何方式自由地实现库.以下是标准关于符合实施的内容(§1.4):

对于类和类模板,库子句指定部分定义.私人成员(第11条)未指定,但每个实施应提供他们根据图书馆条款中的描述完成定义.

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

例如,为了确保实现的复杂性std::list等于双链表的复杂性,其成员函数具有复杂性要求.例如,std::list::insert函数具有以下要求(第23.3.5.4节,增加了重点):

将单个元素插入到列表中需要恒定的时间,并且只需要调用一个T的构造函数.

这并不一定意味着std::list 必须实现为双链表.但是,这是一种常见的选择.实施必须仅以满足要求的方式行动(或者看起来满足要求; 假设规则).

Answer 3

实际标准的一个例子可能有助于澄清,并且unordered_*我认为是一个很好的标准,因为它是专门为了获得标准的哈希表而添加的.这句话来自草稿,但我希望最终版本大致相似:

23.5.4.4 unordered_map修饰符

template <class P>
pair<iterator, bool> insert(P&& obj);

1. 要求:value_type是可构造的std::forward<P>(obj).
2. 效果:插入obj转换为value_type当且仅当容器中没有元素且密钥等效于value_type(obj).
3. 返回:bool返回的pair对象的组件指示插入是否发生,迭代器组件指向具有等效键的元素的元素value_type(obj).
4. 复杂性:平均情况O(1),最差情况O(size()).
5. 备注:除非P可隐式转换为此签名,否则此签名不应参与重载决策value_type.

标准的其他部分实际上也要求它作为哈希表实现,但我认为重要的部分是它们制定了复杂性要求.