数据结构按插入排序，可以获取子集的长度

Question

我正在寻找一种按插入排序的 Java 数据结构，它可以快速查找和删除特定元素并计算在该元素之后添加的元素数量。

LinkedHashSet 理论上满足了这一要求，但接口没有提供任何方法，例如创建从指定元素开始的迭代器。我总是必须遍历整个集合。

感谢您的任何建议。

编辑：好的，我（不是真的）LinkedHashSet的简单实现完全适用于我的，目前只有我的用例如下，以防万一有人感兴趣。这可以更改为包括实际迭代元素的可能性，而不仅仅是能够计算元素的数量。可能还需要一些重构...

public class DoublyLinkedHashSet<T> {
private final Map<T, Entry> map;
private Entry youngestEntry;
public DoublyLinkedHashSet() {
    this.map = new HashMap<T, Entry>();
}
public int size() {
    return map.size();
}
public boolean contains(final T element) {
    return map.containsKey(element);
}
public void add(final T element) {
    final Entry newEntry = new Entry();
    final Entry entryForElement = map.put(element, newEntry);
    boolean entryWasNotAlreadyInSet = entryForElement == null;
    if (entryWasNotAlreadyInSet) {
        newEntry.previousEntry = youngestEntry;
        if (youngestEntry != null) {
            youngestEntry.hasNext = true;
            youngestEntry.nextEntry = newEntry;
        }
    }
    youngestEntry = newEntry;
}
public void remove(final T element) {
    removeEntry(element);
}
public int removeAndGetAmountOfEntriesAfter(final T element) {
    Entry startEntry = removeEntry(element);
    if (startEntry == null) {
        return 0;
    }
    return countAllNextEntries(startEntry);
}
private int countAllNextEntries(final Entry startEntry) {
    int amount = 0;
    Entry currentEntry = startEntry;
    while (currentEntry.hasNext) {
        amount++;
        currentEntry = currentEntry.nextEntry;
    }
    return amount;
}
private Entry removeEntry(final T element) {
    final Entry removedEntry = map.remove(element);
    if (removedEntry == null) {
        return null;
    }
    if (hasPreviousAndNextEntry(removedEntry)) {
        final Entry previousEntry = removedEntry.previousEntry;
        final Entry nextEntry = removedEntry.previousEntry;
        connect(previousEntry, nextEntry);
    } else if (isEndOfList(removedEntry)) {
        final Entry previousEntry = removedEntry.previousEntry;
        resetEndTo(previousEntry);
    } else if (isHead(removedEntry)) {
        final Entry nextEntry = removedEntry.nextEntry;
        resetHeadTo(nextEntry);
    }
    return removedEntry;
}
private boolean hasPreviousAndNextEntry(final Entry entry) {
    return entry.hasPrevious && entry.hasNext;
}
private void connect(final Entry previousEntry, final Entry nextEntry) {
    previousEntry.nextEntry = nextEntry;
}
private boolean isHead(final Entry entry) {
    return !entry.hasPrevious && entry.hasNext;
}
private void resetHeadTo(final Entry entry) {
    entry.previousEntry = null;
    entry.hasPrevious = false;
}
private boolean isEndOfList(final Entry removedEntry) {
    return removedEntry.hasPrevious && !removedEntry.hasNext;
}
private void resetEndTo(final Entry entry) {
    entry.nextEntry = null;
    entry.hasNext = false;
    youngestEntry = entry;
}
private static final class Entry {
    private boolean hasNext;
    private boolean hasPrevious;
    private Entry nextEntry;
    private Entry previousEntry;
}
}

Answer 1

你应该能够使用 SortedSet。它提供了一个 tailSet 方法，该方法应该执行您需要的操作。

您可以按广告顺序对它们进行排序，方法是向对象添加序列号并对其进行排序。

Answer 2

我想你正在寻找一个ArrayList，或者有什么原因你不能使用它？

public int removeAndCount(Object o){
    int i = list.indexOf(o);
    list.remove(o);
    return list.size() - i;
}

Answer 3

有一个散列集合来保存你的对象，并在它们旁边维护一个列表（例如，这就是 LinkedHashMap 所做的，这对你来说太好了，但它隐藏了它的内部列表）。如果哈希集合的元素在列表中具有同一元素的索引，则可以跳转到给定索引处的列表，并轻松迭代其余部分。我认为您提到的所有操作都需要亚线性时间来使用此解决方案运行，除了不能更快（~n 元素的迭代总是需要 ~n 时间）

使用HashMap和LinkedList的示例解决方案：

find：HashMap.get(key)列表中保存索引，key是你的元素.log（n） 时间

remove： LinkedList.remove(HashMap.get(key)) ， HashMap.remove（key），你的元素消失了.log（n） 次

迭代：

for (i=HashMap.get(key); i<LinkedList.size(); i++){
     //etc
}

您可能还需要解开 LinkedList，因为 .get（index） 我敢打赌需要线性时间才能运行。