时间戳

首页 > 解决方案 > 如何在 Kotlin 的迭代器实现中处理可为空的值？

kotlin - 如何在 Kotlin 的迭代器实现中处理可为空的值？

问题描述

所以我按照 Sedgewick 的 Algorithms book 并尝试将实现从 Java 转换为 Kotlin，当我尝试为Bag数据结构（本质上是一个单向链表）实现一个迭代器时，我陷入了可空性问题和线程Kotlin 的安全性。

书中的java实现是这样完成的：

public class Bag<Item> {
   private Node first;

   private class Node {
       Item item;
       Node next;
   }

   /* some methods */

   private class Iterator<Item> {
      private Node current = first;

      public boolean hasNext() { current != null; }

      public Item next() {
          if (!hasNext()) throw new NoSuchElementException();
          Item item = current.item;
          current = current.next;
          return item;
      }
   }
}

我试图像这样在 Kotlin 中实现：

class Bag<Item> : Iterable<Item> {
   private inner class Node(val item: Item, val next: Node?)

   private var first : Node? = null

   /* Some methods */

   override fun iterator() = object : Iterator<Item> {
      private var current : Bag<Item>.Node? = first

      override fun hasNext() : Boolean = current != null

      override fun next() : Item {
         if (current == null) throw NoSuchElementException()

         val item = current.item
         current = current.next
         return item
      }
   }
}

但我收到以下错误：

智能转换为 'Bag.Node' 是不可能的，因为 'current' 是一个可变属性，此时可能已更改

我知道这是由于检查变量是否为空和实际访问变量属性之间的竞争条件，因为该变量可能被其他线程设置为空。一段时间后，我进入了以下实现：

override fun iterator() = object : Iterator<Item> {
   private var current : Bag<Item>.Node? = first

   override fun hasNext() : Boolean = current != null

   override fun next() : Item {
      current?.let {
         val item = it.item
         current = it.next
         return item
      } ?: throw NoSuchElementException()
   }
}

编译器认为这很好。但我还是有些疑惑。这导致了我的问题：

1）分配current = it.next线程是安全的还是应该分配给隐式的it？

2) 是否有一种惯用的 Kotlin 方法来实现以空值结尾的不可空类型的迭代器？（意味着其中的所有值都是非空的，除了结束条件）

标签： kotlindata-structureslinked-list

解决方案

分配 current = it.next 线程是否安全

它不是线程安全的。

想象一个整数列表和两个线程A以及B谁想要使用迭代器实例I。

1 -> 2 -> 3 -> 4 -> 5            A: item=1, next=(2)
^                                A: item=1, next=(2)
I

两个线程都开始迭代。两道内current?.let。都读取当前项目 ( val item = it.item) 并得到item=1, next=(2)。然后，第一个线程A被冻结，第二个线程B将迭代器向前推进三个项目：

1 -> 2 -> 3 -> 4 -> 5            A: item=1, next=(2)
               ^                 B: item=4, next=(5)
               I

现在B进入let并阅读下一个item：item=4, next=(5)。请记住，A它仍在他的循环中，并且item是item=1, next=(2). 如果B现在被冻结并前进一行代码A（在下一次迭代中，它将被“扔回”到项目#2。不会发生任何不好的事情，程序也不会失败，但很可能这不是您需要的行为。current = it.nextcurrentBB

更重要的是：由于所描述的原因，迭代器并不是线程安全的，每个线程都应该有自己的独立线程。更改集合（插入/删除）的迭代器会变得更有趣，但这是另一个故事，因为它是关于集合的，而不是关于迭代器的。

我应该分配给隐式它吗？

您不能分配给它，因为它是一个函数参数并且它是按值传递的，因此不能更改。编译器将禁止分配，并显示“无法重新分配 Val”之类的消息

是否有一种惯用的 Kotlin 方法来实现以空值结尾的不可空类型的迭代器？

我会说：是的。您可能会使用密封类来指定不同类型的节点，例如：

sealed class Node<out T>;

object Empty : Node<Nothing>();

data class Full<T>(val item: T, val next: Node<T>) : Node<T>();

class Bag<T>(private val first: Node<T>) : Iterable<T> {
    override fun iterator(): Iterator<T> = object : Iterator<T> {
        private var current = first

        override fun hasNext() = current !is Empty

        override fun next() = when (val c = current) {
            Empty -> throw IllegalStateException()
            is Full -> {
                current = c.next
                c.item
            }
        }
    }
}

fun main() {
    val bag = Bag(Full(1, Full(2, Full(3, Empty))))

    bag.forEach(::println)
}

推荐阅读