在Scala中迭代排序集合的倒数

Question

我有一个可变的SortedSet，我可以通过做for (item <- nameOfMySortedSet)来迭代它。然而，我想做同样的事情，但是在nameOfMySortedSet的反面。我似乎没有看到这个数据类型的reverse()选项?还有别的办法吗?

Answer 1

您可以尝试构建一个顺序相反的新SortedSet:

scala> val mySet = collection.mutable.SortedSet("1", "2", "3")
mySet: scala.collection.mutable.SortedSet[String] = TreeSet(1, 2, 3)
scala> collection.mutable.SortedSet(mySet.toSeq:_*)(mySet.ordering.reverse)
res0: scala.collection.mutable.SortedSet[String] = TreeSet(3, 2, 1)

或者你可以把它转换成一个list或seq，然后反向运行:

scala> mySet.toSeq.reverse
res1: Seq[String] = ArrayBuffer(3, 2, 1)

Answer 2

一个解决方案，

val sSet = SortedSet(4,3,5)
sSet.foldLeft(List[Int]())((x,y)=>y::x)

如果您必须经常这样做，您可能不得不以相反的顺序保存Set。使用不同的Ordering

Answer 3

下面的操作是有效的，但我不想为它辩护:

  val s = collection.SortedSet(1,3,4)
  for (i <- s.to[List].reverse)
    println(i)

Answer 4

大多数情况下，我们只需要最后几个元素，这就是迭代器的作用。还有另一种方法，无需折叠所有元素或构造一个新的SortedSet实例。

我们可以有一个反向迭代器，每次调用next时，它都以log(n)的复杂度从上一次开始逐个选择每个元素。

下面是相同的优化实现。

object SortedSetExtras {
  implicit class ReverseIterator[A](val set: mutable.SortedSet[A]) extends AnyVal {
    def reverseIterator: Iterator[A] = new Iterator[A] {
      var upNext: Option[A] = None
      var upNextComputed: Boolean = false
      private def recompute(): Unit = {
        if (!upNextComputed) {
          upNext = upNext match {
            case Some(value) => set.until(value).lastOption
            case None => set.lastOption
          }
          upNextComputed = true
        }
      }
      override def hasNext: Boolean = if (upNextComputed) upNext.nonEmpty else {
        recompute()
        hasNext
      }
      override def next: A = {
        if (upNextComputed) {
          upNext.foreach(_ => upNextComputed = false)
          upNext.get
        } else {
          recompute()
          next()
        }
      }
    }
  }
}

实际使用,

import SortedSetExtras._
val ts = mutable.TreeSet[Int](1, 2, 3, 8, 9)
println(ts.reverseIterator.mkString(", ")) // 9, 8, 3, 2, 1