0

今天学了Dynamic Array Stack，教授把模板代码上传到网上。如果您有兴趣查看http://ideone.com/oXe2t1 ，请点击此处的链接。但是代码中有一些我不明白的部分。

// I did not know how he comes up with the (3 * _size)
void pop() {
    assert(!is_empty());
    _size--;
    if (_capacity > (3 * _size))
        resize();
}

然后在 resize()

//how does he know that the max capacity will be equal to either (_size * 2)
// or DYNAMIC_ARRAYED_STACK_MIN_CAPACITY
void resize() {
    _capacity = max(_size * 2, DYNAMIC_ARRAYED_STACK_MIN_CAPACITY);
    unique_ptr<E[]> new_array(new E[_capacity]);
    for (int i = 0; i < _size; i++)
        new_array[i] = _elements[i];
    _elements.swap(new_array);
}
4

1 回答 1

2

我正在重新输入并重新发布我的答案，并查看了您在链接中发布的代码。

答案是，教授不知道设置这些值；他们正是他选择的。

只是为了确保我们知道我们的术语：_capacity是堆栈可以容纳多少，而 _size 是堆栈当前容纳多少。制作动态堆栈的目标是始终尽量减少浪费的内存量，并尽量减少内存的重新分配量。你用一种来换取另一种。

您的教授使用以下规则制作了这个堆栈：

  • 从容量 1 开始。（这是定义的DYNAMIC_ARRAYED_STACK_MIN_CAPACITY值。）
  • 如果容量曾经是大小的 3 倍或更高，请将其调整为大小的 2 倍。
  • 如果大小 = 容量，则将容量调整为大小的 2 倍。

你必须有一个最低容量。一些实现（如 Microsoft .NET 标准）实际上将最小值设置为大约 10，然后从那里调整大小。通过设置一个稍大的值，您可以避免为前几个条目调整数组的大小，但是在这种情况下（可能是为了让您可以看到逻辑是如何工作的），它被设置为 1。这意味着只要您按下一个元素，你必须调整大小。你必须有一个最大值DYNAMIC_ARRAYED_STACK_MIN_CAPACITY和 2 倍的大小，因为大小最初是 0。如果你没有最小值，你的容量也将是 0，这会导致错误。

使容量增加一倍也是任意的。如果您愿意，可以将其放大 100 倍。这意味着您将进行更少的调整大小 - 但您会浪费大量内存。2 可能是一个很好的数字来平衡调整大小与浪费。

触发缩小数组的阈值也是任意的。通过将其设置为 3 倍，这为弹出元素留下了很大的空间，而无需每次都调整大小。这有点浪费内存，但还不错。

当您使用这些概念时，您可以将数字设置为您需要的任何值。除了 MIN 设置为 1 之外，这些都是相当不错的标准数字。

希望这可以帮助。

于 2013-10-03T22:27:35.593 回答