C++ 中 STL 集的底层数据结构是什么?

2022-01-17 00:00:00 set c++

我想知道一个集合是如何在 C++ 中实现的.如果我在不使用 STL 提供的容器的情况下实现自己的 set 容器，那么完成这项任务的最佳方法是什么?

I would like to know how a set is implemented in C++. If I were to implement my own set container without using the STL provided container, what would be the best way to go about this task?

我了解 STL 集基于二叉搜索树的抽象数据结构.那么底层数据结构是什么?一个数组?

I understand STL sets are based on the abstract data structure of a binary search tree. So what is the underlying data structure? An array?

另外，insert() 如何对集合起作用?集合如何检查一个元素是否已经存在于其中?

Also, how does insert() work for a set? How does the set check whether an element already exists in it?

我在维基百科上读到，实现集合的另一种方法是使用哈希表.这将如何运作?

I read on wikipedia that another way to implement a set is with a hash table. How would this work?

推荐答案

你可以通过首先定义一个 Node 结构体来实现二叉搜索树:

You could implement a binary search tree by first defining a Node struct:

struct Node
{
  void *nodeData;
  Node *leftChild;
  Node *rightChild;
}

然后，您可以用另一个 Node *rootNode;

Then, you could define a root of the tree with another Node *rootNode;

二叉搜索树上的维基百科条目有一个很好的例子来说明如何实现插入方法，所以我也建议检查一下.

The Wikipedia entry on Binary Search Tree has a pretty good example of how to implement an insert method, so I would also recommend checking that out.

就重复而言，通常不允许在集合中使用它们，因此您可以丢弃该输入、抛出异常等，具体取决于您的规范.

In terms of duplicates, they are generally not allowed in sets, so you could either just discard that input, throw an exception, etc, depending on your specification.

相关文章