有序数据结构，允许有效地去除重复的项目

必须是有序的数据结构（添加元素a, b and c到一个空的结构，会让他们是在位置0, 1 and 2）。
允许添加重复的项目。这是，我可以有一个列表a, b, c, a, b。
，可除去特定项目的所有ocurrences（如果我这样做delete(1)，它会删除结构1所有ocurrences）。如果我有元素a, b, c, d, c, e并删除元素c，我应该得到a, b, d, e。
我只需要通过两种方式访问元素。第一个是删除给定的事件（见上面的点），另一个是当我将这个结构中的数据转换为列表。

我真的不能挑选出最好的数据结构可以在这里。我首先想到了类似List的东西（问题是在移除项目时有O(n)操作），但也许我错过了一些东西？那么树木/堆什么呢？哈希表/地图？

我将不得不假设我会尽可能多地添加删除这个数据结构。

感谢

你没有真正提到你如何期待'阅读'访问。例如，你是否通过位置访问元素？这需要多快？在删除特定元素之后，这些职位会发生什么变化？另一个元素的位置是否相应改变？ – 2010-05-31 17:59:18

好点。看我的编辑。 – 2010-05-31 18:13:16

似乎戴夫的解决方案就是你正在寻找的东西。 – 2010-05-31 19:05:12

我想你可能必须写一个专用数据结构的副本的集合（取决于你的效率要求）。

东西像一个双向链接列表中有一个额外的nextEqualItemPtr在它和一个HashMap指向每个项目的第一个。

然后你就可以很快找到第一个“B”中删除，并遵守所有的nextEqualItemPtrs才能移除所有（双链接很容易保持完整列表）。开销正在使地图保持最新状态。新项目的nextEqualItemPtr列表可以指向由map.put（key）返回的节点.nextEqualItemPtr

我肯定会先使用一些简单的东西，并且只在插入这种东西时if/when太慢。

2010-05-31 17:26:06 DaveC

除了firstEqualItemPtr之外，HashMap还需要一个lastEqualItemPtr。插入一个新元素变成O（1）。 – 2010-05-31 17:57:18

+1。对这个问题的编辑使得这个解决方案更加完美，IMO。 – 2010-05-31 19:05:39

阿帕奇集合（homepage）的Bag接口可以满足您的需要。它有很多的实现，所以也许还会跟踪插入顺序（你的第一点）。

而且它具有：

这也是相当快相对于使用普通LinkedList或ArrayList，但我不知道有插入的元素的索引。

它被描述为

袋接口有一些每个对象

2010-05-31 17:24:12 Jack

回答