8

只是出于兴趣...

如果我要设计一个容器库，我肯定会从一个公共基类派生它们，该基类将具有（可能是抽象的）方法声明，如size()和insert()。

标准库容器是否有充分的理由不这样实现？

4

5 回答 5

13

在 C++ 中，继承用于运行时多态（阅读：运行时接口重用）。它带有在运行时通过 vtable 进行重定向的开销。

为了使多个容器类具有相同的接口（以便 API 是可预测的并且算法可以做出假设），不需要继承。只要给他们相同的方法，你就完成了。C++ 中的容器（和算法）是作为模板实现的，这意味着您可以获得编译时多态性。

这避免了任何运行时开销，并且符合 C++ 口号“只为您需要的东西付费”。

于 2012-07-13T09:39:40.260 回答
4

Java 集合（您可能已经想到）在 中实现了一堆常用方法，它们位于具体类中实现的和方法AbstractCollection之上。然后IIRC还有更多这样的方法等等。一些子类覆盖了大多数这些方法，一些子类可以只实现所需的抽象方法。某些方法真正在共享接口的大多数或所有集合中共同实现。例如，在我的痛苦经历中，给你一个不可修改的视图的是一个完整的 PITA。size()iterator()AbstractList

C++ 容器有一些所有容器共有的成员函数，几乎没有一个可以以相同的方式为所有容器实现[*]。在有可以使用迭代器（如find）执行的通用算法的情况下，它们是 中的自由函数<algorithm>，与继承可以查看的任何地方相去甚远。

还有所有序列、所有关联数组等共有的成员函数。但是对于每个这些概念，不同具体数据结构的实现之间并没有太多共同点。

所以最终归结为设计哲学的问题。Java 和 C++ 在容器方面都有一些代码重用。在 C++ 中，此代码重用来自<algorithm>. 在 Java 中，其中一些是通过继承来实现的。

主要的实际区别可能是，在 Java 中，您的函数可以在java.util.Collection不知道它是什么类型的集合的情况下接受 a。在 C++ 中，函数模板可以接受任何容器，但非模板函数不能。这影响了用户的编码风格，并且也受到了影响——Java 程序员比 C++ 程序员更有可能达到运行时多态性。

从实现者的角度来看，如果您正在编写 C++ 容器库，那么没有什么可以阻止您在 中的不同容器之间共享私有基类std，如果您认为这将有助于重用代码。

[*] 现在这在 C++11中size()得到保证，可能可以共同实现。在 C++03中只是“应该”是，并且有一些实现利用这一点来实现 in 的版本之一，而不是更新大小所需的版本。O(1)empty()size()O(1)std::listspliceO(1)O(n)

于 2012-07-13T11:16:24.803 回答
1

没有充分的理由引入这样的基类。谁会从中受益？它在哪里有用？

需要“通用”接口的算法使用迭代器。没有将元素插入不同容器的通用方法。事实上，你甚至不能在某些容器中插入元素。

于 2012-07-13T09:35:13.547 回答
1

如果您可以编写独立于您正在使用的容器的代码，那将是有意义的。但事实并非如此。推荐阅读Effective STL一书的“第 2 项：谨防容器无关代码的错觉”这一章。

于 2012-07-13T09:40:28.357 回答
1

从另一个角度来看：现在，如果您以通用方式使用它们，编译器就会拥有它可以拥有的所有信息，从而实现彻底的优化。感谢模板实现。

现在，例如，如果 list 和 vector 都实现了类似 push_backable 的抽象 OO 接口，并且您将在代码中使用抽象指针 (push_backable*)->push_back(...)，编译器将丢失大量信息并且因此有优化的机会。

这些是可能出现在内部循环中的典型操作，您确实希望对它们进行最大可能的优化。另请参阅 Frerich Raabe 的回答。

于 2012-07-13T09:44:20.410 回答