异常行为与使用自定义比较器的TreeSet()

huangapple go评论65阅读模式
英文:

Anomalous behaviour with TreeSet() with custom comparator

问题

我在下面的程序中所做的是,我创建了一个名为 "alls" 的 TreeSet,它使用自定义比较器来比较两个列表,如果它们相等,则返回 0,否则返回 1。但是,如果我将两个相同的列表添加到 TreeSet 中,那么 TreeSet 将接受这两个相同的列表。但实际上它不应该包含两个相同的列表,因为我已经定义了这样的比较器。

以下是您提供的代码:

List<Integer> a1 = new ArrayList<Integer>() {{add(1);add(2);add(3);add(4);}};
List<Integer> a2 = new ArrayList<Integer>() {{add(1);add(1);}};
List<Integer> a3 = new ArrayList<Integer>() {{add(2);add(1);}};
List<Integer> a4 = new ArrayList<Integer>() {{add(3);add(1);}};
List<Integer> a5 = new ArrayList<Integer>() {{add(4);add(1);}};
List<Integer> a6 = new ArrayList<Integer>() {{add(5);add(1);}};
        
Comparator b1 = (l1, l2) -> {if (l1.equals(l2)) return 0; else return 1;};
Collection<List<Integer>> alls = new TreeSet(b1);
alls.add(a1);
alls.add(a1);
alls.add(a1);
alls.add(a2);
alls.add(a3);
alls.add(a1);
alls.add(a4);
alls.add(a6);
alls.add(a5);
alls.add(a2);
alls.add(a1);

当我尝试打印我的 TreeSet(名称为 alls)时,以下输出显示出来:

1 2 3 4
1 1
2 1
1 2 3 4
3 1
5 1
4 1

您可以看到 [1 2 3 4] 被插入到我的 TreeSet(名为 alls)中两次,但它之后没有再被插入。

这是如何可能的呢?我认为 TreeSet 使用了我的自定义比较器,不应该允许重复项。而且如果它允许重复项,为什么相同的元素在我的程序中没有进一步被插入呢?

英文:

What I've done in the below program is, I've created a TreeSet named "alls" with a custom comparator which compares two list and if they are equal it returns 0 else returns 1. But if I add two same list into TreeSet then TreeSet accepts two same list into it. But it should not contain two same list cuz i've defined a comparator like that.

   List&lt;Integer&gt; a1 = new ArrayList&lt;Integer&gt;() {{add(1);add(2);add(3);add(4);}};
	List&lt;Integer&gt; a2 = new ArrayList&lt;Integer&gt;() {{add(1);add(1);}};
	List&lt;Integer&gt; a3 = new ArrayList&lt;Integer&gt;() {{add(2);add(1);}};
	List&lt;Integer&gt; a4 = new ArrayList&lt;Integer&gt;() {{add(3);add(1);}};
	List&lt;Integer&gt; a5 = new ArrayList&lt;Integer&gt;() {{add(4);add(1);}};
	List&lt;Integer&gt; a6 = new ArrayList&lt;Integer&gt;() {{add(5);add(1);}};
    
    Comparator b1 = (l1,l2)-&gt;{if(l1.equals(l2)) return 0; else return 1;};
    Collection&lt;List&lt;Integer&gt;&gt; alls = new TreeSet(b1);
    alls.add(a1);
    alls.add(a1);
    alls.add(a1);
    alls.add(a2);
    alls.add(a3);
    alls.add(a1);
    alls.add(a4);
    alls.add(a6);
    alls.add(a5);
    alls.add(a2);
    alls.add(a1);

When I try to Print my TreeSet(name alls) then the following output shows up:

1 2 3 4

1 1

2 1

1 2 3 4

3 1

5 1

4 1

You can see [1 2 3 4] is inserted into my TreeSet(whose name is alls) twice but it does not get inserted after.

How is this possible? I though TreeSet with my custom comparator doesn't allow duplicates. Also if it allows why not the same elements doesn't get inserted further in my program

答案1

得分: 3

你的比较器不起作用

Collection< List<Integer> > alls = new TreeSet(b1);
alls.add(a1);
alls.add(a2);
alls.add(a3);

你的实现使用了比较器对两个不同的列表进行排序,由于 return 1,所以你的树看起来像是:
> a1 <- a3 -> a2

现在让我们添加 a1:

Collection< List<Integer> > alls = new TreeSet(b1);
alls.add(a1);
alls.add(a2);
alls.add(a3);
alls.add(a1);

> a1 <- a3 ? a1 -> a2 结果 a1 更大
> a1 <- a3 -> a2 ? a1 结果 a1 更大
> a1 <- a3 -> a2 -> a1

你的树现在有了重复的 a1。
解决方案:使用评论中提到的正确的 Comparator

英文:

Your Comparator doesn't work

Collection&lt;List&lt;Integer&gt;&gt; alls = new TreeSet(b1);
alls.add(a1);
alls.add(a2);
alls.add(a3);

Your implementaton sorts two different list with the second always bigger due to return 1 so your Tree looks like :
> a1 <- a3 -> a2

Now let's add a1 :

Collection&lt;List&lt;Integer&gt;&gt; alls = new TreeSet(b1);
alls.add(a1);
alls.add(a2);
alls.add(a3);
alls.add(a1);

> a1 <- a3 ? a1 -> a2 RESULT a1 is bigger
> a1 <- a3 -> a2 ? a1 RESULT a1 is bigger
> a1 <- a3 -> a2 -> a1

Your tree has now duplicated a1.
SOLUTION : Use a correct Comparator mentionned in comments

答案2

得分: -1

请尝试以下代码:

Comparator<List<Integer>> b1 = (l1, l2) -> {
    if (l1.equals(l2)) {
        return 0;
    } else {
        if (l1.isEmpty())
            return 1;
        if (l2.isEmpty())
            return -1;

        int i = 0;
        while (l1.get(i).equals(l2.get(i))) i++;

        if (l1.get(i) > l2.get(i))
            return 1;
        else
            return -1;
    }
};

您的比较器没有处理一个列表"低于"另一个列表的情况。您的比较器只返回0和1。我认为TreeSet使用二进制搜索或任何更快的方法来查找对象并检查一个特定对象是否在集合中。像这样的方法需要明确定义一个对象是大于还是小于其他对象。如果TreeSet使用相等对象的原始比较方法在集合中进行比较,那么您的比较器将能够工作。在排序结构中,通常有更复杂和更好的方法来查找对象。

英文:

Try this:

        Comparator&lt;List&lt;Integer&gt;&gt; b1 = (l1, l2)-&gt;{

        if(l1.equals(l2)) {
            return 0;
        } else {
            if(l1.isEmpty())
                return 1;
            if(l2.isEmpty())
                return -1;

            int i = 0;
            while (l1.get(i).equals(l2.get(i))) i++;

            if(l1.get(i) &gt; l2.get(i))
                return 1;
            else
                return -1;
        }};

Your comparator doesn't handle the situation when one list "is lower" than the second. Your comparator returns only 0 and 1. I think that TreeSet uses binary search or any faster method to find an object and check if is a particular object is a set. Methods like that need to have clearly defined whether an object is greater or lower than others. If TreeSets use primitive comparing by equal object with each in the set your comparator would be working. In sorted structures are more complex and better methods to find an object.

huangapple
  • 本文由 发表于 2020年9月22日 21:54:29
  • 转载请务必保留本文链接:https://go.coder-hub.com/64011277.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定