可以使用迭代器维护插入顺序的数据结构

Question

这是一个非常普遍的问题，我会尽量清楚。假设我有一些对象集合，为简单起见，使它们成为整数。现在我想创建一个表示这些整数的类作为一些数据结构。在这堂课中，我想实施

• 排序函数，根据一些定义的排序逻辑对集合进行排序
• 迭代接口，Iterator按插入顺序遍历

我怎么能这样做，即使我以未排序的顺序添加整数，例如

someCollection.add(1);
someCollection.add(3);
someCollection.add(2);

然后打电话

Collections.sort(someSortingLogic);

在对集合进行排序之后，迭代器仍按插入顺序遍历。是否有我可以用于此目的的特定数据结构，或者是手动跟踪哪些元素以哪种顺序插入的情况，或者我想不到的其他内容？

非常感谢！

Answer 1

通常，要解决此类问题，请为这些值维护两个索引。也许其中一个索引包含实际值，也许两个索引都包含实际值，或者实际值可能存储在其他位置。

然后，当您想要遍历已排序的顺序时，可以使用排序的索引来指定值，并且当您需要插入顺序时，可以使用插入索引来指定值。

索引可以像包含值的数组一样简单。当然，您不能将两个不同的值存储到数组中的一个位置，因此一个简单的解决方案是将两个数组包装在Object中，这样调用Object的sort()方法就可以对一个数组进行排序，同时保持插入顺序数组不变。

Fancier数据结构利用更高级的技术，但它们基本上归结为维护两个订单，即插入顺序和排序顺序。

public class SomeCollection {
   public void add(int value) {
      insertArray = expandIfNeeded(insertArray);
      insertArray[insertIndex++] = value;
      sortArray = expandIfNeeded(sortArray);
      sortArray[sortIndex++] = value;
      sort(sortArray);
   }
   ...
}

Answer 2

我不确定你是否向我们展示了足够的代码来给你一个很好的答案，但是如果你有一个看起来像这样的类：

public class Hand implements Iterator<Card>
{
    private List<Card> cards = new ArrayList<>();

    // Returns iterator for natural ordering of cards
    @Override
    public Iterator<Card> iterator()
    {
        return cards.iterator();
    }

    // Rest of code omitted

然后你可以实现这样的sortedIterator(...)方法：

    // Returns iterator for sorted ordering by Comparator c
    public Iterator<Card> sortedIterator(Comparator<? super Card> c)
    {
        return cards.stream().sorted(c).iterator();
    }

如果您向我们展示更多代码，可能会有更好的解决方案。