什么数据结构适合使用？

Question

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

• 存储tuple<Double,Integer,Integer>列表。仅按照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并保持其排序。使用二分查找可以快速查找。然而，插入和删除将涉及大量的内存复制，例如在列表前面插入会导致所有元素都要移动。

- Wei Shi

---

顺便提一下，在你写“相同的双精度值被认为是相同的”时要小心。 浮点数的相等概念是一个非常广泛的主题。 你可能需要编写一个自定义比较器来考虑误差范围。 - SyntaxT3rr0r

以上代码中的 j 是从哪里来的？ - 101100

你要搜索最小的 j<i，使得 list[j:i] 可以合并。 - Wei Shi

那么 j 在外部循环（在所示循环的外面）中是这样的：for(int j = 0; j < list.size(); j++)？ 另外，list[j:i] 是否使用类似Python的语法表示范围？它们什么时候可以合并？总体问题可能会导致我建议另一种结构。 - 101100

Answer 1

一个解决方案是使用已排序的映射到元组列表：

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

声明行有点丑，但它可以工作。我以前多次使用过映射到列表。好处是你可以从列表中删除项目，只要你的列表都很短，你就有更少的移动次数。要遍历整个结构，你需要创建自己的迭代器或者调整原始代码。

- 101100

Answer 2

如果您决定编写自己的Double比较器，有几件事情需要注意。

首先是浮点数相等性是一个非常棘手的领域。默认情况下，Java在不同虚拟机中运行代码时不能确保一致的浮点数计算，尽管可以使用strictfp关键字来实现。浮点数算术的这种不一致性可能会导致应用程序出现问题，特别是在运行在多个虚拟机之间通信的服务器和客户端通信等情况下。

第二个棘手的问题是比较器操作对象，这意味着您将使用Doubles而不是doubles进行操作。以下四个操作会导致Double取消装箱为double：<、<=、>和>=。以下两个操作不会导致取消装箱：==和!=。这两个运算符执行对象内存指针比较。总之，在执行比较之前，请手动取消装箱Doubles以将其转换为doubles；这将大大减少错误。

- Joshua Kaplan