java - 如何为 BitSet 类型的元素创建 SortedSet（例如 TreeSet）

Question

我有许多(power(2,k))BitSet 对象，我想将它们存储在SortedSet. 我使用代码：

Set <BitSet> S= new TreeSet<>();

但是，我收到此错误：java.lang.ClassCastException: java.util.BitSet cannot be cast to java.lang.Comparable

如何实现可比较的接口？或者有没有其他方法可以对这些类型的元素进行排序BitSet？

Answer 1

有两种使用TreeSet.

1. 让它包含实现的对象Comparable
2. 有一个自定义Comparator对象来比较您的TreeSet.

由于您想拥有您的contains并且TreeSet不实现，因此您需要给您一个 custom 。你如何实现它取决于你。BitSetBitSetComparableTreeSetComparatorComparator

SortedSet<BitSet> s = new TreeSet<BitSet>(new CustomBitSetComparator());
s.add(bitSet1);
s.add(bitSet2);
//etc ...

比较器可能看起来像这样

class CustomBitSetComparator implements Comparator<BitSet>{
    int compare(BitSet a, BitSet b) {
        if(a == b){
            return 0;
        } else if(a == null) {
            return -1;
        } else if(b == null) {
            return 1;
        } else if(a.equals(b)) {
            return 0;
        } else if(a.length() > b.length()) {
            return 1;
        } else if(b.lenght() > a.length()) {
            return -1;
        } else {
            for(int i = 0; i < a.length(); i++) {
               if(a.get(i) != b.get(i)) {
                   if(a.get(i)) {
                      return 1;
                   } else {
                      return -1;
                   }
                }
             }
             return 0;
         }
    }
}

Answer 2

我会将它们转换为 BigIntegers (O(N)) 并使用 TreeSet。否则，您将不得不为自己编写一个比较器，从本质上讲，它的运行速度会非常缓慢，正如您从其他答案中所看到的那样。我也会考虑使用 PriorityQueue 而不是 Set。

Answer 3

我不确定为什么要将 BitSet 放在 treeSet 中，而解决方法是创建一个实现Comparable接口的包装类。

Public class CustomComparableBitSet implements Comparable{
   private BitSet bs;

   public int compareTo(T o){
      //your comparison logic goes here.
   }
}

然后在客户端代码中，将CustomComparableBitSet 的实例添加到treeset中。