c# - 有序数据结构，允许有效删除重复项

Question

我需要一个数据结构

• 必须有序(将元素 a、b 和 c 添加到空结构中，将使它们位于位置 0、1 和 2)。
• 允许添加重复项目。也就是说，我可以有一个包含 a, b, c, a, b 的列表。
• 允许删除给定项目的所有出现(如果我执行诸如 delete(1) 之类的操作，它将删除结构中 1 的所有出现)。如果我有元素 a, b, c, d, c, e 并删除元素 c，我应该得到 a, b, d, e >.
• 我只需要通过两种方式访问​​元素。第一个是删除给定的 ocorrence 时(参见上面的观点)，另一个是当我将此结构中的数据转换为列表时。

我真的无法在这里选出最好的数据结构。我一开始想到了像列表这样的东西(问题是删除项目时有一个 O(n) 操作)，但也许我错过了一些东西？树/堆呢？哈希表/映射？

我必须假设我会使用此数据结构进行添加和删除操作。

谢谢

Answer 1

我认为你可能必须编写一个专用的数据结构(取决于你的效率要求)。

类似于双向链表，其中有一个额外的 nextEqualItemPtr 和一个指向每个项目的第一个的 HashMap。

然后，您可以快速找到要删除的第一个“b”，并按照所有 nextEqualItemPtrs 将其全部删除(双链接，因此很容易保持列表完整)。开销确实使 map 保持最新。新item的nextEqualItemPtr列表只能指向map.put(key).nextEqualItemPtr返回的节点

我肯定会首先使用一些简单的东西，只有在速度太慢时才插入这种东西。