C++到Java:有效地搜索集合

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在具有Thing的情况下在O(log N)时间内找到元素.使用运算符<()的其他重载.我可以使用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是name,key2是version.我可以问我们有没有任何名为Foobar的软件,或者更具体地说我们有Foobar v1.0.

从表面上看,Java中std :: set的最直接等价似乎是TreeSet.可以通过继承Comparator接口来实现排序.然而,就我所说的而言,看起来在Java中需要使用多个Maps.如果我想更改值,在C++中只会使用像std :: map这样的关联容器.在Java TreeSet中的C++ std :: set中,值是它自己的键.但是,在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);
  }
};

但是,如果你这样做,你可以(在课堂上)写:

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++背景,这似乎不必要地膨胀.当东西已经包含它时,为什么还要再次存储密钥呢？如果我有两把钥匙就更糟糕了.我需要两张地图.

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

我现在不仅复制密钥,还创建其他不必要的树数据结构(或具有更好运行时性能的HashMaps).对于上面的排序实现,这也可能是"完全错误的",因为每个键本身只形成一个部分顺序而不是一组事物的总顺序.

我已经看到有关搜索的问题在这里使用线性搜索回答,这几乎总是最糟糕的选择.例如

查找集合中具有给定属性的所有对象

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

那么在时间和空间上有效地实现这一目标的Java方法是什么？

Answer 1

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

从 C++ 背景来看，这似乎过于臃肿。当东西已经包含密钥时，为什么我要再次存储密钥？

这并不像你想象的那么大的开销。您正在存储对 的一个额外引用String，总成本为...4 个字节。（实际上，成本为零：TreeSet实现所占用的内存与 完全相同TreeMap。）

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