为什么std :: set不只是称为std :: binary_tree? [英] Why isn't std::set just called std::binary_tree?

问题描述

std :: set不是真正的集合. std :: unordered_set是一个实集，但std :: set是一个二进制搜索树，更具体地说是一棵红黑树.那么，为什么将其称为std :: set?是否有一些将std :: set与二叉树区分开的特定功能?谢谢.

std::set in C++ is not a real set in terms of data structures. std::unordered_set is a real set, but std::set is a binary search tree, more specifically a red-black tree. Why, then, is it called std::set? Is there some specific functionality that sets a std::set apart from a binary tree? Thanks.

推荐答案

为什么std :: set不仅仅称为std :: binary_tree?

Why isn't std::set just called std::binary_tree?

因为

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

1. Tree doesn't describe how the interface is used. Set does.
2. std::set does not provide sufficient operations to be used as a general purpose search tree. It only provides an interface to a particular application of a search tree: The representation of a set.
3. Technically the standard doesn't specify that std::set is a binary search tree; although red-black BST may be the only data structure that can achieve the requirements imposed on std::set, and the interface has carefully been specified with that data structure in mind, the choice of internal data structure is an implementation detail.
4. For same reason std::unordered_set isn't called std::hash_table.

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

std::unordered_set is a real set, but std::set is a binary search tree

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

std::unordered_set isn't any more or less "real" than std::set is. They are both sets with slightly different requirements and guarantees; One designed to be implementable using a tree, and another designed to be implementable using a hash table.

P.S.树和哈希表不是表示集合的唯一方法.可以实现大部分(但不是全部)std::set的一种内部数据结构是排序向量.特别是对于小集合，排序后的向量可能比std::set快得多.

P.S. Tree and a hash table are not the only ways to represent a set. One internal data structure that can implement most - but not all - of std::set is a sorted vector. Especially for small sets, a sorted vector can be much faster than std::set.

这篇关于为什么std :: set不只是称为std :: binary_tree?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！