在 Scala 中迭代排序集的反向？

Question

我有一个可变的 SortedSet，我可以通过执行 for (item <- nameOfMySortedSet) 来迭代它。然而，我希望能够做同样的事情，但与 nameOfMySortedSet 相反。我似乎没有看到此数据类型的 reverse() 选项？还有其他方法吗？

Answer 1

以下有效，但我不想为它辩护：

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

Answer 2

您可以尝试以相反的顺序构建一个新的 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)

或者您可以将其转换为列表或序列，然后运行相反：

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

Answer 3

一个解决方案，

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

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

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

注意：以上实现不是线程安全的。

在 Scala 中迭代排序集的反向？

Iterate over the reverse of a sorted set in Scala?

scala

treeset

sortedset