C ++中的STL集的基础数据结构是什么？ [英] What is the underlying data structure of a STL set in C++?

问题描述

我想知道如何在C ++中实现集合。如果我不使用STL提供的容器来实现我自己的集合容器，什么是最好的方式去执行这个任务？

我理解STL集是基于二叉搜索树的抽象数据结构。那么什么是底层的数据结构呢？数组？

此外，insert（）如何工作在一个集合？该集合如何检查元素中是否已经存在元素？

我在wikipedia上读到另一种实现集合的方法是使用哈希表。

解决方案

您可以通过首先定义一个 Node struct：

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

然后，您可以用另一个 Node * rootNode; >二叉搜索树有一个很好的例子，说明如何实现一个插入方法，所以我也建议检查它。

，它们通常不允许在集合中，因此您可以根据您的规范丢弃该输入，抛出异常等。

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?

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?

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?

解决方案

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

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

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.

这篇关于C ++中的STL集的基础数据结构是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！