TreeSetの使い方

導入

こんにちは。けちょんです。
TreeSet使ってますか？
私は今日初めて見ました。
類似のHashSetやTreeMapは使ったことがあるんでないでしょうか。

TreeSetとは

重複を許さず、addするときにソートして保持してくれるクラスです。
競技プログラミングで役立ちそうな気がするクラスですね。

使ってみる

まず、TreeSetにaddするオブジェクトを作成

class Product {
    private int id;
    private String name;

    public Product() {
    }

    public Product(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

}

idとnameのフィールドと、コンストラクターと、アクセッサーを作成しました。

次に、インスタンスを追加

Set<Product> tree = new TreeSet<>();
tree.add(new Product(1, "kechong"));
tree.add(new Product(2, "me"));
tree.add(new Product(3, "you"));
for (Product product : tree) {
    System.out.print("id:" + product.getId() + ", ");
    System.out.print("name:" + product.getName());
    System.out.println();
}

はい、実行してみます。

Exception in thread "main" java.lang.ClassCastException: Product cannot be cast to java.base/java.lang.Comparable
    at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
    at java.base/java.util.TreeMap.put(TreeMap.java:536)
    at java.base/java.util.TreeSet.add(TreeSet.java:255)
    at Main.main(Main.java:26)

エラーが出ましたね。

どんなエラー？

ClassCastExceptionが投げられていますね。
ProductがComparableにキャストできないって怒られています。
発生場所は、TreeSetにaddしようとしたときです。

なぜキャストしようとしているか

キャストとかしないでいいのに、、、
と、思いますが、これはTreeSetには必要なんです。

TreeSetは順序という概念を持っています。
TreeSetにaddするときに、保持する位置を定めるために順序を決める必要があります。
Productクラスを自分で作成した時に、「Productオブジェクトを比較する方法」を定めなかったためにエラーが発生しています。

比較という概念を追加する

具体的には、Comparableインターフェースを実装します。

class Product implements Comparable<Product> {
    private int id;
    private String name;

    public Product() {
    }

    public Product(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    @Override
    public int compareTo(Product o) {
        return this.id - o.id;
    }

}

はい、implementsして、compareToメソッドをオーバーライドしました。

もう一回実行すると、、、

id:1, name:kechong
id:2, name:me
id:3, name:you

はい、良さそうですね！

ちなみに

今回はProductクラスでComparableインターフェースを実装しました。
が、TreeSetのインスタンス化時に、コンストラクターの引数に以下のように指定することでも同様の出力となります。

Set<Product> tree = new TreeSet<>(Comparator.comparing(Product::getId));

これはTreeSet側に比較方法を与えることで、順序を決定できるようにしています。

まとめ

TreeSetに自作オブジェクトを追加する場合は、以下のいずれかの作業が必要
・自作オブジェクトでComparableインターフェースを実装する
・TreeSetのコンストラクター引数に比較方法を指定する