c++ - 关于 DynamicArrayStack 的基本问题

Question

今天学习了他们的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);
}

Answer 1

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

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

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

你的教授按照以下规则制作了这个堆栈:

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

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

使容量翻倍也是随意的。如果你愿意，你可以把它做成 100 倍的大小。这意味着您调整大小的次数会少得多——但您会浪费大量内存。 2 可能是平衡调整大小与浪费的一个很好的数字。

触发数组收缩的阈值也是任意的。通过将其设置为 3x，可以为弹出元素留出大量空间，而不必每次都调整大小。这有点浪费内存，但还算不错。

在使用这些概念时，您可以根据需要设置数字。除了 MIN 设置为 1 之外，这些都是非常好的标准数字。

希望这对您有所帮助。