使Multimap仅在Java中按键排序

I would like to have a c.g.c.c.Multimap that is sorted based on keys only. The values shouldn't be sorted. I've tried to build something with guava's TreeMultimap, but I can't use it because the value type doesn't implement Comparable.

我想要一个仅基于密钥排序的c.g.c.c.Multimap。不应对值进行排序。我试图用番石榴的TreeMultimap构建一些东西，但我不能使用它，因为值类型没有实现Comparable。

public class MyObject /* doesn't implement Comparable */ {
  private String name;
  private int score;
  // Getters/setters are implemented
  public static Function<MyObject,Integer> myObjectToScore {
    @Override public Integer apply (MyObject o) { return o.score; }
  }
  public static Multimap<Integer,MyObject> indexOnScore(Iterable<MyObject> i) {
    Multimap<Integer,MyObject> m = Multimaps.index(i, myObjectToScore());
    // Do the sort of the keys.
    return m;
  }
}

I've thought about getting a SortedSet of the keys, then iterating over each of these keys in the sorted set to fetch the various values, but I was hoping using an existing (yet undiscovered) feature in Guava rather than using this kind of hack.

我已经考虑过获取一个密钥的SortedSet，然后遍历排序集中的每个密钥以获取各种值，但我希望在Guava中使用现有的（但尚未发现的）功能而不是使用这种hack 。

Note: I won't make MyObject implement Comparable because it makes no sense with my actual object.

注意：我不会让MyObject实现Comparable，因为它对我的实际对象毫无意义。

---

Example of input/output:

输入/输出示例：

Set<MyObject> s = Sets.newHashSet(
  new MyObject("a", 2),
  new MyObject("b", 3),
  new MyObject("c", 1),
  new MyObject("d", 3),
  new MyObject("e", 1)
); // Assuming constructor MyObject(String name, int score)

for (Map.Entry<Integer, MyObject> e: MyObject.indexedOnScore(s).entries()) {
  System.out.printf("%d -> %s%n", e.getKey(), e.getValue().getName());
}

Prints:

打印：

1 -> c // or switched with line below
1 -> e
2 -> a
3 -> b // or switched with line below
3 -> d

7 个解决方案

#1

Multimaps.index returns an ImmutableListMultimap, so you wouldn't be able to sort it after creating it. You could, however, first create a sorted copy of your Iterable<MyObject> and feed that to Multimap.index... ImmutableListMultimap keeps things in the same order it was given them.

Multimaps.index返回一个ImmutableListMultimap，因此您无法在创建它之后对其进行排序。但是，您可以首先创建Iterable 的排序副本，并将其提供给Multimap.index ... ImmutableListMultimap保持事物的顺序与给定它们的顺序相同。

public static ImmutableMultimap<Integer, MyObject> indexOnScore(Iterable<MyObject> i) {
  List<MyObject> sorted = Ordering.natural().onResultOf(myObjectToScore())
      .sortedCopy(i);
  return Multimaps.index(sorted, myObjectToScore());
}

Another option might be to create a TreeMultimap and use Ordering.arbitrary() as the Comparator for the values.

另一种选择可能是创建一个TreeMultimap并使用Ordering.arbitrary（）作为值的比较器。

#2

MultimapBuilder was introduced in Guava 16:

MultimapBuilder在Guava 16中引入：

<K extends Comparable<? super K>, V> ListMultimap<K, V> multimap() {
    return MultimapBuilder.treeKeys().linkedListValues().build();
}

That keeps your keys sorted by their natural order (treeKeys() is also overloaded to accept a custom comparator), and the values associated with each key are maintained in a LinkedList (ArrayList and HashSet are among the other options).

这会使您的密钥按其自然顺序排序（treeKeys（）也会重载以接受自定义比较器），并且与每个密钥关联的值都保存在LinkedList中（ArrayList和HashSet是其他选项之一）。

#3

Though the OP's specific situation seems to have been answered using immutable multimap building functions, I needed a mutable version of what he was asking for. In case it helps anyone, here's the generic method I ended up creating:

虽然OP的具体情况似乎已经使用不可变的多图建筑功能得到了回答，但我需要一个他要求的可变版本。万一它可以帮助任何人，这里是我最终创建的通用方法：

static <K, V> Multimap<K, V> newTreeArrayListMultimap(
    final int expectedValuesPerKey)
{
    return Multimaps.newMultimap(new TreeMap<K, Collection<V>>(),
        new Supplier<Collection<V>>()
        {
            @Override
            public Collection<V> get()
            {
                return new ArrayList<V>(expectedValuesPerKey);
            }
        });
}

#4

Call Multimaps.newMultimap, which gives you the flexibility to create, for example, a Multimap backed by TreeMap whose values are ArrayLists.

调用Multimaps.newMultimap，它可以灵活地创建，例如，由TreeMap支持的Multimap，其值为ArrayLists。

#5

I'd like to point out that the alternative proposed solution, namely "to create a TreeMultimap and use Ordering.arbitrary() as the Comparator for the values", only works if MyObject doesn't override equals() or hashcode(). Ordering.arbitrary() is inconsistent with equals and uses object identity instead, which makes it not a good idea to use it in conjunction with a TreeSet.

我想指出另一个提出的解决方案，即“创建一个TreeMultimap并使用Ordering.arbitrary（）作为值的比较器”，只有在MyObject不重写equals（）或hashcode（）时才有效。 Ordering.arbitrary（）与equals不一致，而是使用对象标识，这使得将它与TreeSet结合使用并不是一个好主意。

#6

How about this:

这个怎么样：

    public static Multimap<Integer, MyObject> indexOnScore(Iterable<MyObject> i) {
        Multimap<Integer, MyObject> m = Multimaps.index(i, myObjectToScore());

        Multimap<Integer, MyObject> sortedKeys = Multimaps.newMultimap(
                Maps.<Integer, Collection<MyObject>>newTreeMap(),
                new Supplier<Collection<MyObject>>() {
                    @Override
                    public Collection<MyObject> get() {
                        return Lists.newArrayList(); // Or a Set if appropriate
                    }
                }
        );

        sortedKeys.putAll(m);

        return sortedKeys;
    }

There would be the overhead of creating two separate Multimaps in this case, though.

但是，在这种情况下，创建两个单独的Multimaps会产生开销。

#7

You can do it with TreeMultimap if you use Comparators.

如果使用Comparators，可以使用TreeMultimap执行此操作。

Create a Comparator for the key type and the value type (MyObject?). Then use create(Comparator keyComparator, Comparator valueComparator) to make the map.

为键类型和值类型（MyObject？）创建一个Comparator。然后使用create（Comparator keyComparator，Comparator valueComparator）来制作地图。

The benefit of using a Comparator over implementing Comparable is that you can make the Comparator specific to the situation that you want with the map and it doesn't effect your object in general. As long as your Comparator is consistent with equals it can do whatever you want.

使用Comparator而不是实现Comparable的好处是，您可以使Comparator特定于您想要的地图情况，并且它通常不会影响您的对象。只要你的比较器与equals一致，它就可以做你想做的任何事情。