关于DynamicArrayStack的基本问题

今天我学习了Dynamic Array Stack，教授在线上传模板代码。如果您有兴趣查看http://ideone.com/oXe2t1，请点击此链接。但是代码中有些部分我不明白。关于DynamicArrayStack的基本问题

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

来源

2013-10-03 Hoang Minh

这些数字很可能只是很好，但任意选择。你为什么不问他？ – GManNickG

我会的，但是因为他在课后发布了代码，所以直到下周才会看到他。这就是为什么我把它放在这里，并问你们这件事。 –

我重新输入和重新发布我的回答，说完看着你的链接发布的代码。

答案是，教授没有知道设置这些值;他们正是他所选择的。

只是为了确保我们知道我们的条款：_capacity是多少堆栈可以保持，而_size是多少堆栈目前持有。制作动态堆栈的目标是始终尽量减少浪费的内存量，并尽量减少内存重新分配的数量。你交易一个有利于另一个。

你的教授做这个堆栈的规则如下：（这是定义DYNAMIC_ARRAYED_STACK_MIN_CAPACITY值）

开始，其容量为1
如果容量是不断3倍的大小或更高，将其重新调整为2倍大小。
如果size =容量，则将容量调整为2x的大小。

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

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

触发收缩数组的阈值也是任意的。通过将其设置为3x，可以留出很多空间来弹出元素，而无需每次调整大小。这有点浪费记忆，但不是太糟糕。

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

希望这会有所帮助。

来源

2013-10-03 22:27:35

谢谢，这比我的教授在一个多小时的演讲中所说的更多，更清晰，更多的信息！ –

关于DynamicArrayStack的基本问题

回答

相关问题