Dart：条目前置后的 DoubleLinkedQueue 长度

Question

我正在通过 DoubleLinkedQueueElement.append/prepend 方法处理 DoubleLinkedQueue 中的条目。这导致新元素被插入到队列中，但无法更新长度，并且 toList() 方法导致抛出错误。

我知道队列只应该在 start/end 处添加元素，但看起来界面应该允许通过条目在中间添加元素。我发现很难相信这样一个 common/well 理解的数据结构在这一点上会有错误 - 那么我是否错误地使用了 DoubleLinkedQueues？我应该使用另一种数据结构吗？我希望将另一个可迭代对象的值合并到我自己排序的可迭代对象中 - SplayTreeSet 可能会在 n log n 时间内将我带到那里，但一个简单的合并应该让我在线性时间内到达那里...

意外行为的代码示例：

main() {
  var q = new DoubleLinkedQueue<int>.from([1]);
  q.firstEntry().prepend(0);
  print('length: ${q.length}');
  int i = 0;
  for (var qi in q){
    print('${i++}: $qi');
  }
}

输出：

length: 1
0: 0
1: 1

Answer 1

看起来长度 getter 只指向一个内部计数器。这样做是因为对于长列表，每次计算元素可能会花费很长时间。

仅当您使用直接操作列表的方法而不是使用元素的前置方法时，才会更新内部计数器。在您的示例中，您应该使用 q.addFirst(0); 来更新长度。 .prepend() 方法只是插入一个新元素并更改指针。这导致元素的正确遍历，但无论如何计数器都是错误的。

不幸的是，您似乎无法在列表中间插入元素，也无法使列表重新计算元素。您应该考虑在 www.dartbug.com.

创建一个错误

// 更新：

toList() 抛出错误，因为元素多于 length。

Dart：条目前置后的 DoubleLinkedQueue 长度

Dart: DoubleLinkedQueue length after entry prepend

queue

dart