为什么大多数主流编程语言的标准库中都没有实现Disjoint Set（并查算法）？

Question

我找到了关于如何为 C++、Java、Kotlin、Python 等实现不相交集（并集查找算法实现）的文章。它的实现并不是特别困难，尽管存在一些出错的空间。令我惊讶的是，没有任何语言在其标准库中包含这种形式。

是否有一个原因？考虑到大多数标准库中已经存在多少种不同的数据结构，令我惊讶的是没有一个（我发现）包含这一点。是不是太晦涩难懂了？

Answer 1

这是一个合理的问题，除了“因为大多数人不需要它”之外，也许没有真正令人满意的答案。我可能使用过不相交集数据结构 10-20 次，但几乎只在竞争性编程的情况下使用过；大多数语言的标准库在设计时并没有考虑到竞争性程序员。编写一些标准算法（例如Kruskal 算法）也需要不相交集数据结构，但如果您自己实现 Kruskal 算法，那么您也可以自己实现不相交集数据结构。

现在，您可能直观地认为即使大多数程序员永远不会使用它，将它包含在标准库中也没有什么坏处。确实，语言开发人员首先花费很少的时间来编写它，但他们还必须对其进行广泛的测试，编写文档，响应有关它的错误报告或功能请求，等等。语言设计者还必须就标准库中提供的算法采取立场；有多种具有不同性能和并发特性的选项，因此需要进行一些研究来选择要实现的选项。

另一方面，如果某些利基数据结构不在标准库中，但对某些程序员来说足够重要，那么它很可能会出现在第三方库中。从语言设计者的角度来看，将其留给第三方库开发人员几乎没有什么坏处。