为什么std :: set不只是称为std :: binary_tree？

Question

就数据结构而言，C ++中的std :: set不是真正的集合。std :: unordered_set是一个实数集，但std :: set是一个二叉搜索树，更具体地说是一棵红黑树。那么为什么将其称为std :: set？是否有一些特定功能可以将std :: set与二叉树区分开？谢谢。

Answer 1

为什么std :: set不只是称为std :: binary_tree？

因为

1. 树未描述如何使用该接口。集做。
2. std::set没有提供足够的操作以用作通用搜索树。它仅提供到搜索树的特定应用程序的接口：集的表示。
3. 从技术上讲，该标准没有指定std::set二进制搜索树。尽管红黑BST可能是唯一可以满足施加要求的数据结构std::set，并且已经考虑到该接口仔细地指定了该数据结构，但是内部数据结构的选择是实现细节。
4. 由于同样的原因std::unordered_set没有被调用std::hash_table。

std :: unordered_set是一个实数集，而std :: set是一个二进制搜索树

std::unordered_set或多或少不是“真实” std::set的。它们都是具有稍微不同的要求和保证的集合；一种设计为可使用树实现，另一种设计为可使用哈希表实现。

PS树和哈希表不是表示集合的唯一方法。可以实现大多数（但不是全部）功能的一种内部数据结构std::set是排序向量。特别是对于小集合，排序的向量可能比快得多std::set。