java - 使用什么数据结构

Question

我正在寻找具有以下属性的数据结构。

• 存储 tuple<Double,Integer,Integer> 的列表.订单仅在 double .具有相同 double 值的两个元组被认为是相同的。
• 支持重复。
• 需要能够按升序遍历。如果有重复，后面添加的顺序应该更高。
• 快速查找/插入
• 快速移除，注意移除总是遵循这个模式

方法包含移除:

for(int i=list.size()-1;i>=0;i--){// assume list is in ascending order
    if(list[j:i] can be merged){
        remove list[j:i-1];
        update list[i]'s two integers;
        i = j-1;
    }
}

我目前使用 ArrayList 并对其进行排序。使用二进制搜索可以快速查找。然而，插入和删除将涉及内存中的大量副本，例如在列表前面插入会移动所有元素。

Answer 1

一个解决方案是对元组列表进行排序映射:

SortedMap<Double,List<Tuple<Integer,Integer>>>

声明行有点难看，但它会起作用。我以前曾多次使用 map 来列出 list 。它的好处是你可以从列表中删除项目，只要你的列表很短，你的移动次数就会减少。要遍历整个结构，您需要创建自己的迭代器，或调整您的原始代码。