java 比较通用列表中的元素

Comparing elements in a generic list

提问by Matt R

I wrote a linked list implementation for my java class earlier this year. This is a generic class called LList. We now have to write out the merge sort algorithm for a lab. Instead of creating a new List implementation that takes Ints, I decided to just reuse the generic list I had created before.

今年早些时候，我为我的 java 类编写了一个链表实现。这是一个名为 LList 的通用类。我们现在必须写出实验室的归并排序算法。我没有创建一个接受 Int 的新 List 实现，而是决定重用我之前创建的通用列表。

The problem is how do I compare two generic objects? java wont let me do something like

问题是如何比较两个通用对象？java不会让我做类似的事情

if(first.headNode.data > second.headNode.data)

So, my question is, is their a way to implement some sort of comparison function that will work on any type of data? I tried the following:

所以，我的问题是，它们是否是一种实现某种比较函数的方法，该函数适用于任何类型的数据？我尝试了以下方法：

        String one, two;
        one = first.headNode.data.toString();
        two = second.headNode.data.toString();
        if(first.headNode.data.compareTo(second.headNode.data) < 0) {
            result.add(first.headNode.data);
            // remove head node. remove() takes care of list size.
            first.remove(1);
        } else {
            // If compareTo returns 0 or higher, second.headNode is lower or
            // equal to first.headNode. So it's safe to update the result
            // list
            result.add(second.headNode.data);
            second.remove(1);
        }

Which wont even work properly. I tested with the numbers 6 and 12, the above adds 12 to the result list.

这甚至无法正常工作。我用数字 6 和 12 进行了测试，上面将 12 添加到结果列表中。

Relevant stuff:

相关资料：

 private LList<T> mergeSort(LList<T> list) {
    LList<T> first = new LList();
    LList<T> second = new LList();
    if (list.length() == 1) {
        return list;
    }

    int middle = list.length() / 2;
    second.headNode = list.getNodeAt(middle + 1);
    second.length = list.length() - (middle);
    // Set first half to full list, then remove the "second" half.
    first.headNode = list.headNode;
    first.length = middle;
    first.getNodeAt(middle).next = null;

    // Get the splitted halves.
    first = mergeSort(first);
    second = mergeSort(second);
    return merge(first, second);
}

private LList<T> merge(LList<T> first, LList<T> second) {
    LList<T> result = new LList();

    while((first.length > 0) && (second.length > 0)) {
        // Ok, lets force toString to compare stuff since generics are a pain.
        String one, two;
        one = first.headNode.data.toString();
        two = second.headNode.data.toString();
        if(one.compareTo(two)) < 0) {
            result.add(first.headNode.data);
            // remove head node. remove() takes care of list size.
            first.remove(1);
        } else {
            // If compareTo returns 0 or higher, second.headNode is lower or
            // equal to first.headNode. So it's safe to update the result
            // list
            result.add(second.headNode.data);
            second.remove(1);
        }
    }
    return result;
}

NOTE: entire LList class can be found [here](http://rapidshare.com/files/219112739/LList.java.htmlMD5: BDA8217D0756CC171032FDBDE1539478)

注意：整个 LList 类可以在这里找到（http://rapidshare.com/files/219112739/LList.java.htmlMD5：BDA8217D0756CC171032FDBDE1539478）

回答by newacct

Note that Comparable is also a generic type, parameterized by what type it is comparable to. The most general, type-safe way to declare your mergeSort function above is:

请注意 Comparable 也是一个泛型类型，由它可比较的类型参数化。声明上面的 mergeSort 函数的最通用、类型安全的方法是：

private <T extends Comparable<? super T>> LList<T> mergeSort(LList<T> list) { }

This enforces that the type T's compareTo method can accept an argument of type T. (In theory, a type could implement Comparable, but not be comparable to itself, like SomeClass implements Comparable<CompletelyDifferentClass>, so it is important to have the requirement on the type parameter of Comparable. In practice, however, any well-designed Comparable class should be comparable to at least itself.)

这强制类型 T 的 compareTo 方法可以接受类型 T 的参数。（理论上，类型可以实现 Comparable，但不能与自身进行比较，例如SomeClass implements Comparable<CompletelyDifferentClass>，因此对 Comparable 的类型参数有要求很重要。然而，在实践中，任何设计良好的 Comparable 类至少应该与它本身具有可比性。）

We require that <T extends Comparable<? super T>>instead of just <T extends Comparable<T>>because it is okay if a type T's compareTomethod accepts a more general type than T, because it would still be able to accept an argument of type T. This is important because, if you have a class A, which implements Comparable<A>; and then you have a subclass B which extends A, B cannot implement Comparable<B>, because B already implements Comparable<A>, inherited from A, and a class cannot implement an interface twice. So if we required <T extends Comparable<T>>above, B would not satisfy it, and we would not be able to sort LList<B>objects.

我们要求这样做<T extends Comparable<? super T>>而不是仅仅<T extends Comparable<T>>因为如果类型 T 的compareTo方法接受比 T 更通用的类型就可以了，因为它仍然能够接受类型 T 的参数。这很重要，因为如果你有一个类 A，它实施Comparable<A>; 然后你有一个扩展 A 的子类 B，B 不能实现Comparable<B>，因为 B 已经实现了Comparable<A>，从 A 继承，一个类不能实现一个接口两次。所以如果我们<T extends Comparable<T>>上面要求，B 不会满足它，我们将无法对LList<B>对象进行排序。

回答by flicken

Look into the Comparatorand Comparableinterfaces.

查看Comparator和Comparable接口。

Your sort method should take Comparatoror you should specify < T extends Comparable > so that the Comparable interface can be used.

您的排序方法应该采用Comparator或者您应该指定 < T extends Comparable > 以便可以使用 Comparable 接口。

public void sort(Comparable<T> comparator) {
    sort(SortType.MERGE, comparator);
}
....
private LList<T> merge(LList<T> first, LList<T> second) {
    ...
        if(comparator.compare(first.headNode.data, second.headNode.data) < 0) {
    ...
}

回答by Brandon Yarbrough

Well, as you've discovered, you've got a problem. All you know about the objects in your list are that they are instances of Object or one of its subclasses. You can't really sort Objects. You now have a few options:

好吧，正如您所发现的，您遇到了问题。关于列表中的对象，您所知道的只是它们是 Object 或其子类之一的实例。你不能真正对对象进行排序。您现在有几个选择：

One option you have is to sort across something completely meaningless, like the hashCode for the object. You can in fact implement a perfectly valid mergesort using the hashCode, but it'd be largely pointless, since the hash code doesn't actually mean anything and there's no particular reason to sort by it except to learn about sorting.

您拥有的一种选择是对完全无意义的东西进行排序，例如对象的 hashCode。实际上，您可以使用 hashCode 实现完全有效的归并排序，但这在很大程度上毫无意义，因为散列代码实际上并不意味着什么，除了了解排序之外，没有特别的理由对其进行排序。

Here's a much better way to go: change the rules of your generic list. Right now, everything in your list must be some sort of anything. Why not change that so that it can be some sort of anything that implements the Comparableinterface? That way, you don't need to know anything about the objects other than how to compare them. This is largely how Java itself solves this problem. (I recommend reading up on its Collections stuff).

这是一个更好的方法：更改通用列表的规则。现在，您列表中的所有内容都必须是某种类型的任何内容。为什么不改变它，以便它可以是某种实现Comparable接口的东西？这样，除了如何比较它们之外，您不需要了解有关对象的任何信息。这在很大程度上是 Java 本身解决这个问题的方式。（我建议阅读它的 Collections 内容）。

Just change your object from LList<T>to LList<T extends Comparable<T>>and you're good to go!

只需将您的对象从 更改LList<T>为LList<T extends Comparable<T>>，您就可以开始了！

回答by Saint Domino

Something that worked for me in a C# framework that I made. Makes a comparer object for a typed object, and uses reflection to determine value of the property that the list is sorting on. Tweak as needed :

在我制作的 C# 框架中对我有用的东西。为类型化对象创建一个比较器对象，并使用反射来确定列表排序所依据的属性的值。根据需要调整：

using System;
using System.Collections.Generic;
using System.ComponentModel;

namespace BOCL
{
  /// <summary>
  /// Provides a comparer for collections of BOCL objects so they can be compared on any property
  /// </summary>
  /// <typeparam name="T">The type of BOCL object to compare</typeparam>
  public class BusinessBaseComparer<T> : IComparer<T> where T : BusinessBase<T>, new()
  {
    #region Constructors

    /// <summary>
    /// Provides a default constructor for the comparer
    /// </summary>
    protected BusinessBaseComparer()
    {
      //An instance of the business base comparer must be declared with at least one argument to be of any use
    }

    /// <summary>
    /// Build this comparer sorting on a particular property ascending
    /// </summary>
    /// <param name="property">The property on which the sort should be applied</param>
    public BusinessBaseComparer(PropertyDescriptor property)
    {
      m_SortProperty = property;
    }

    /// <summary>
    /// Build this comparer sorting on a particular property
    /// </summary>
    /// <param name="property">The property on which the sort should be applied</param>
    /// <param name="direction">The direction to which the sort should be applied</param>
    public BusinessBaseComparer(PropertyDescriptor property, ListSortDirection direction)
    {
      m_SortProperty = property;
      m_SortDirection = direction;
    }

    #endregion

    #region SortProperty

    private PropertyDescriptor m_SortProperty = null;

    /// <summary>
    /// The property on which the type is to be sorted. If the property is not found, the objects are deemed equal
    /// </summary>
    protected PropertyDescriptor SortProperty
    {
      get { return m_SortProperty; }
    }

    #endregion

    #region SortDirection

    private ListSortDirection m_SortDirection = ListSortDirection.Ascending;

    /// <summary>
    /// The direction in which the type is to be sorted
    /// </summary>
    protected ListSortDirection SortDirection
    {
      get { return m_SortDirection; }
    }

    #endregion

    #region IComparer<T> Members

    /// <summary>
    /// Performs comparison between to BOCL objects
    /// </summary>
    /// <param name="x">The first object to compare</param>
    /// <param name="y">The second object to compare</param>
    /// <returns>The result of the comparison</returns>
    public int Compare(T x, T y)
    {
      if (SortProperty == null)
        return 0; //we didn't find the property we were supposed to sort on

      //set up to get the value of the objects we are comparing against
      IComparable xValue = null;
      IComparable yValue = null;

      try
      {
        //now get the value for the x object and value for the y object
        //as something we can compare against
        xValue = (IComparable)SortProperty.GetValue(x);
        yValue = (IComparable)SortProperty.GetValue(y);

        //if either property came back null
        if (xValue == null || yValue == null)
          return 0; //treat them as the same
      }
      catch (InvalidCastException)
      {
        return 0; //ran into a proplem trying to convert the object into something we could compare against
      }


      if (SortDirection == ListSortDirection.Ascending)
        return xValue.CompareTo(yValue);
      else
        return yValue.CompareTo(xValue);
    }

    #endregion
  }
}

回答by Kip

You should make use of the Comparableinterface.

您应该使用Comparable接口。

Comparable one = (Comparable)first.headNode.data;
Comparable two = (Comparable)second.headNode.data;

if(one.compareTo(two) < 0)
{
  ...
}
else
{
  ...
}

Please note: this is pretty sloppy. I'm not checking anywhere that headNode.data is actually a Comparable object. We should really throw an exception if that is the case.

请注意：这很草率。我没有检查 headNode.data 实际上是 Comparable 对象的任何地方。如果是这种情况，我们真的应该抛出异常。