数据结构，独特的元素和快速的添加和删除 [英] Data structure with unique elements and fast add and remove

问题描述

我需要具有以下属性的数据结构

I need a data structure with the following properties:

• 结构中的每个元素必须是唯一的。
• 添加：添加一个元素的数据结构，除非已经元素 存在。
• 在弹出：删除数据结构中的一个元素，并返回该元素 除去。这是不重要的其中一个元素被删除。

• Each element of the structure must be unique.
• Add: Adds one element to the data structure unless the element already exists.
• Pop: Removes one element from the data structure and returns the element removed. It's unimportant which element is removed.

所需的该结构没有其它操作。一个天真的执行情况，名单将几乎不需要O（1）必须检查一次POP和O（N）的时间加（因为整个列表以确保 唯一性）。我目前使用的是红黑树来实现这个数据结构的需要，但我想知道如果我可以使用的东西来实现几乎相同的性能那么复杂。

No other operations are required for this structure. A naive implementation with a list will require almost O(1) time for Pop and O(N) time for Add (since the entire list must be checked to ensure uniqueness). I am currently using a red-black tree to fulfill the needs of this data structure, but I am wondering if I can use something less complicated to achieve almost the same performance.

我preFER答案在C＃中，也包括Java，JavaScript和C ++

I prefer answers in C#, but Java, Javascript, and C++ are also acceptable.

我的问题是类似<一个href="http://stackoverflow.com/questions/5207741/data-structure-for-fast-insertion-deletion-with-sorting">this问题，但我有没有必要来查找或删除最大值或最小值（或任何特定类型的值），所以我希望会有改善这方面。如果任何结构的问题是适当的位置，但是，让我知道。

My question is similar to this question, however I have no need to lookup or remove the maximum or minimum value (or indeed any particular kind of value), so I was hoping there would be improvements in that respect. If any of the structures in that question are appropriate here, however, let me know.

那么，什么样的数据结构只允许独特的元素，支持快速添加和删除，并比红黑树？

So, what data structure allows only unique elements, supports fast add and remove, and is less complicated than a red-black tree?

推荐答案

那么内置的 的HashSet＆LT; T＆GT;

What about the built-in HashSet<T>?

它只包含独特的元素。 删除（POP）是O（1）和添加是O（1）除非内部数组必须调整。

It contains only unique elements. Remove (pop) is O(1) and Add is O(1) unless the internal array must be resized.

这篇关于数据结构，独特的元素和快速的添加和删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！