java - C++ 到 Java : searching a collection efficiently

Question

我的背景主要是 C++，现在我正在愤怒地编写一些 Java。我发现在 C++ 中使用 STL 的一些基本内容在 Java 中似乎比我认为的更麻烦。我的结论是，可能有一个更好的 Java 惯用语我还没有理解。这是一个使用伪代码的示例。

我有一些事物的集合，这些事物具有基于某些碰巧是字符串的成员变量的自然排序关系。

class Thing
{
   String key1;
   String key2;
}

在 C++ 中，我可能会定义一个排序运算符 <(Thing,Thing) 并将它们放在 std::set 中。例如

///
/// @brief
/// provide a total order for 'Things' using key1 and key2
///
bool operator<(const Thing& a, const Thing& b)
{
  if (a.key1 < b.key1) return true; 
  else if (a.key1 > b.key1) return false; 
  else return a.key2 < b.key2;
} 

然后我可以使用 set::find 在 O(log N) 时间内找到元素，以处理有事物的情况。使用 operator<() 的额外重载。我可以使用 std::lower_bound 或 std::equal_range 只搜索 key1 或同时搜索 key1 和 key2。例如:

struct Ordering
{
   /// A strict weak ordering not a total ordering
   bool operator()(const Thing& A,const std::string& key1) const;
}

const_iterator iter = std::lower_bound(someThings.begin(),
                                       someThings.end(),
                                       key1,
                                       Ordering());

为了不那么抽象，假设 key1 是名称，key2 是版本。我可以问一下我们是否有任何名为 Foobar 的软件，或者更具体地说，我们是否有 Foobar v1.0。

从表面上看，Java 中 std::set 最直接的等价物似乎是 TreeSet可以通过子类化 Comparator 接口(interface)来实现排序。然而，对于我所说的，看起来需要多个 map 才能在 Java 中执行此操作。在 C++ 中，如果我想更改值，只会费心使用像 std::map 这样的关联容器。在 C++ std::set 中，就像在 Java TreeSet 中一样，值是它自己的键。但是，在 C++ 中，我可以编写比较器，根据需要使用 key1 或 key2 将“Thing”与“std::string”进行比较，并在它们的 std::set 中找到特定的事物。在我看来，您必须使用 Map 在 Java 中执行此操作。否则(因为 Comparator 只有一个类型参数)你最终会像这样一团糟:

public static class Order implements Comparator<Object>
{
  @Override
  @Constant
  public int compare(Object a, Object b)
  {
     String aString;
     String bString;         
     if (a instanceof String)
     {
        aString = (String)a;
     }
     else if (a instanceof Thing)
     {
        aString = ((Field)a).getKey1();
     }
     else
     {
        throw new ClassCastException("String or Field object expected.");
     }
     if (b instanceof String)
     {
        bString = (String)b;
     }
     else if (b instanceof Thing)
     {
        bString = ((Field)b).getKey1();
     }
     else
     {
        throw new ClassCastException("String or Field object expected.");
     }
     return aString.compareTo(bString);
  }
};

但是，如果这样做，您可以(在 Thing 类中)写:

Set<Thing> things = new TreeSet<Thing>(new Order());

boolean hasFieldWithKey1(final String key1) 
{
   return this.fields.contains(key1);
}

使用 Java Set，您只能测试是否存在，而不能检索您正在搜索的对象。例如你做不到

Field getFieldWithKey1(final String key1) 
{
   return this.fields.floor(key1);
}

因为像 floor() 这样的方法只接受值类型的对象(即 Thing)

显而易见的解决方案是为每个键使用一个 Map。

Map<String,Thing> thingsByKey1 = new TreeMap<Thing>(new Order());

来自 C++ 背景，这似乎不必要地臃肿。当东西已经包含 key 时，为什么还要再次存储 key ？如果我有两把 key ，那就更糟了。我需要两张 map 。

Map<String,Thing> thingsByKey1 = new TreeMap<Thing>(new OrderByKey1());
Map<String,Thing> thingsByKey2 = new TreeMap<Thing>(new OrderByKey2());

我现在不仅要复制键，还要创建额外的不必要的树数据结构(或具有更好运行时性能的 HashMap)。对于上面的排序实现，这也可能是“完全错误的”，因为每个键本身仅形成部分顺序，而不是一组事物的总顺序。

我在此处看到有关使用线性搜索回答搜索的问题，这几乎总是最糟糕的选择。例如

Finding all objects that have a given property inside a collection

我注意到有一个 BinarySearch 版本接受 Comparator 对象作为参数，但返回元素的索引而不是元素本身。这意味着在使用它之后会不必要地调用 get()(假设集合支持它)。

那么 Java 在时间和空间上高效地执行此操作的方法是什么？

Answer 1

Java 的方法是，是的，使用 Map .

Coming from a C++ background this seems unnecessarily bloated. Why should I store the key again when thing already contains it?

这并没有您想象的那么多。您正在存储一个对 String 的额外引用，总成本为...4 字节。 (实际上，成本为零:TreeSet 实现占用的内存与 TreeMap 一样多。)

如果您想同时使用两个键进行搜索，您可以使用 Comparator<Thing>比较两个键，或使 Thing实现 Comparable<Thing> , 然后维护一个 TreeSet<Thing> .这比......令人不快的Comparator紧凑得多你在上面写了。如果要一键搜索，只需使用 Map<String, Thing> .如果您真的非常想同时使用两者进行搜索，那么请同时维护它们。 (实际上，我几乎从来不需要这样做……而且 JDK 集合框架的作者也不认为您需要经常这样做。)