这是一个非常笼统的问题，我会尽力弄清楚。假设我有一些对象集合，为简单起见，使它们成为整数。现在，我想创建一个将这些整数表示为某种数据结构的类。在这个课上我想实现
排序功能，根据定义的排序逻辑对集合进行排序
可迭代的接口，迭代器按插入顺序遍历
即使我以未排序的顺序添加整数，我如何做到这一点，例如
someCollection.add(1);
someCollection.add(3);
someCollection.add(2);
然后打电话
Collections.sort(someSortingLogic);
在对集合进行排序之后，迭代器仍然按插入顺序遍历。我是否可以为此目的使用特定的数据结构，或者是手动跟踪按哪些顺序插入了哪些元素的情况，或者是我想到的其他情况？
非常感谢！
通常，要解决这样的问题，您需要为值维护两个索引。这些索引之一可能包含实际值，两个索引可能包含实际值，或者实际值存储在其他位置。
然后，当您要遍历排序顺序时，可以将排序索引用于值，而当需要插入顺序时，可以将插入索引用于值。
索引可以像包含值的数组一样简单。自然地，您不能将两个不同的值存储到数组的一个点中，因此一种简单的解决方案是将两个数组包装在一个Object中，这样调用Object的sort()方法将对一个数组进行排序，而插入顺序数组保持不变。
先进的数据结构利用了先进的技术，但它们基本上都归结为维护两个顺序，即插入顺序和排序顺序。
public class SomeCollection {
public void add(int value) {
insertArray = expandIfNeeded(insertArray);
insertArray[insertIndex++] = value;
sortArray = expandIfNeeded(sortArray);
sortArray[sortIndex++] = value;
sort(sortArray);
}
...
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句