TreeMap 中的自定义排序

Question

以下是我一直在玩的例子：

  import collection.immutable.{TreeSet, TreeMap}
  val ts = TreeSet(9, 23, 1, 2)
  ts
  val tm = TreeMap(3 -> "c", 1 -> "a", 2 -> "b")
  tm
  // convert a map to a sorted map
  val m = Map("98" -> List(4, 12, 14), "001" -> List(22, 11))
  val t = TreeMap(m.toSeq: _*)
  t // sorted by key
  // sort an unsorted map
  m.toSeq.sortWith((x, y) => x._2(0) < y._2(0))

  // add a unsorted map into a sorted map
  val m1 = Map("07" -> List(3, 5, 1), "05" -> List(12, 5, 3))
  val t1: TreeMap[String, List[Int]] = t ++ m1
  t1 // "001" is the first key

我可以在 Map 上使用 sortWith 来获得自定义排序，如果我想使用与默认排序不同的 TreeMap 怎么办？

Answer 1

TreeMap 被定义为类似 Map 的类型，其键具有指定的顺序。该顺序由构造函数的隐式参数给出：

new TreeMap()(implicit ordering: Ordering[A]) // For TreeMap[A,B]

因此您可以通过显式提供自定义 Ordering[A]，在构建时为键设置替代顺序。

但是，class 不提供任何（直接）方法来根据值设置排序。据我所知，调用 .toSeq.sortWith 是你能做的最好的事情，除了编写你自己的集合类型之外。

Answer 2

您不能使用 Map 的值来定义地图的默认顺序。

TreeMap[A,B] 的构造函数接受一个隐含的 Ordering[A] 参数，所以你可以这样做：

// Will sort according to default Int ordering (ascending by numeric value)
scala> val tm = TreeMap(3 -> "c", 1 -> "a", 2 -> "b")
tm: scala.collection.immutable.TreeMap[Int,String] = Map(1 -> a, 2 -> b, 3 -> c)

// A wild implicit appears! (orders descending by numeric value)
scala> implicit val tmOrd = Ordering[Int].on((x:Int) => -x)
tmOrd: scala.math.Ordering[Int] = scala.math.Ordering$$anon@1d8e2eea

// Our implicit is implicitly (yeah) used by constructor
scala> val invTm = TreeMap(3 -> "c", 1 -> "a", 2 -> "b")
invTm: scala.collection.immutable.TreeMap[Int,String] = Map(3 -> c, 2 -> b, 1 -> a)

请注意，像这样限制隐式的范围更安全。如果可以，您应该构造一个（非隐式）对象并手动传递它，或者将隐式声明的范围与其存在可能影响其他代码的地方分开。

这背后的原因是 TreeMap 建立在树的顶部，树使用键的值来维护允许基于键的高效数据 reads/writes 的结构约束，这是 Map 的主要目的.对 Map 中的值进行排序毫无意义。

更新：订购逻辑的复杂性并不意味着什么。根据您的评论：

scala> object ComplexOrdering extends Ordering[Int] {
     |   def compare(a: Int, b: Int) = {
     |     if(a == 3) -1 else if(a == 2 * b) -1 else if(a == 3 * b) 0 else 1
     |   }
     | }
defined object ComplexOrdering

scala> val tm = TreeMap(3 -> "c", 1 -> "a", 2 -> "b")
tm: scala.collection.immutable.TreeMap[Int,String] = Map(1 -> a, 2 -> b, 3 -> c)

scala> val tm = TreeMap(3 -> "c", 1 -> "a", 2 -> "b")(ComplexOrdering)
tm: scala.collection.immutable.TreeMap[Int,String] = Map(3 -> c, 2 -> b, 1 -> a)

TreeMap 中的自定义排序

Custom ordering in TreeMap

scala

ordereddictionary