質問: Java SEコアAPIに次の条件を満たすコンテナクラスは用意されているでしょうか。 (1)重複要素を許す (2)最大値/最小値の取得がO(1) (3)任意の要素の削除がO(log(n)) STLでは`multiset`がこれらの性質を満たしています。一方Javaでこのようなクラスを探してみたところ、近いものとして`PriorityQueue`と`TreeSet`が挙がりました。 しかし前者は削除に線形時間かかり、後者は重複要素を許さないため条件に合いませんでした。 `TreeSet`とタプルを使えば同じことを実現できると思いますが、先に挙げた性質を満たすクラスがあるかどうかを知りたいです。
回答: TreeMapを使えばどうですか?やりたいことに一番近いんじゃないかなと。 ``` TreeMap treeMap = new TreeMap<>(); // 要素の追加 Integer n = treeMap.get(i); if (n == null) { n = 0; } treeMap.put(i, n + 1); // 最大値 treeMap.lastKey(); // 最小値 treeMap.firstKey(); // 削除 Integer n = treeMap.get(i); if (n != null) { treeMap.put(i, n - 1); } // 存在確認 Integer n = treeMap.get(i); boolean hasValue = (n != null && n > 0); ``` オーダーの計算はあまり得意じゃないので雰囲気ですが、ソースを見る感じと木構造というのを考えると要素の操作はO(log(n))になりそうです。