在堆栈和堆之间动态切换

Question

假设我正在编写一个简单的缓冲类.此缓冲区将充当标准C对象数组的简单包装器.它也应该是向后兼容的,可以使用简单数组作为输入的现有函数.

这里的目标是使这个缓冲区在速度和内存使用方面都很有效.由于堆栈分配总是比堆快,我想将堆栈上的所有内容分配到某个阈值,如果它变大,则在堆上重新分配.如何有效地完成这项工作？

我研究过,显然std :: string做了类似的事情.我只是不确定如何.我所拥有的最接近的解决方案是(伪代码,未编译):

template <typename T, int MinSize>
class Buffer
{
public:

    void Push(const T& t)
    {
        ++_size;

        if (_size > MinSize && _heap == NULL)
        {
            // allocate _heap and copy contents from stack
            // _stack is unused and wasted memory
        }
        else if (_heap != NULL)
        {
            // we already allocated _heap, append to it, re-allocate if needed
        }
        else
        {
            // still got room on stack, append to _stack
        }
    }

    void Pop()
    {
        --_size;

        if (_size <= MinSize && _heap != NULL)
        {
            // no need for _heap anymore
            // copy values to _stack, de-allocate _heap
        }
        else if (_heap != NULL)
        {
            // pop from heap
        }
        else
        {
            // pop from stack
        }
    }

private:

    T _stack[MinSize];
    T* _heap;
    int _size;
};

正如您所看到的,_stack当缓冲区超出时,就是浪费空间MinSize.此外,如果Buffer足够大,推送和弹出可能会特别昂贵.另一个解决方案是将前几个元素保持在堆栈上,并将溢出放在堆上.但这意味着缓冲区无法"转换"为简单数组.

有更好的解决方案吗？如果这是在std :: string中完成的,那么有人可以指出如何或提供一些资源吗？

Answer 1

我建议您使用指针_data而不是_heap，它始终引用您的数据存储。_heap == NULL会变成_data == _stack等等，但在不改变数据长度的所有情况下，您可以避免区分大小写。

\n\n

您当前的草图不包含用于_capacity跟踪当前分配的空间的成员。您将需要它来实现\xe2\x80\x9cappend ，如果需要，请重新分配 \xe2\x80\x9d部分，除非您想为堆分配容器的每个长度更改进行重新分配。

\n\n

您还可以考虑在数据装入堆栈时不释放堆空间。否则，应用程序可能会在该边界处添加和删除单个元素，从而每次都会导致分配。因此，要么实现一些滞后，要么在分配堆空间后根本不释放它。一般来说，我认为释放堆内存应该与收缩堆内存一起进行。您可能希望自动执行这两种操作，以响应某个函数调用（例如 ）shrink_to_fit，或者根本不执行，但在类似情况下只执行其中一项而不执行另一项没有什么意义。

\n\n

除此之外，我相信您的解决方案几乎就是您所希望的。也许为 提供默认值MinSize。如果MinSize很小，为了避免堆栈溢出，那么浪费该空间不会是一个大问题，不是吗？

\n\n

当然，最终这一切都取决于您的实际应用程序，因为这种形式的许多未使用的堆栈分配可能会对堆栈内存的缓存产生不利影响。考虑到默认分配器也可以非常智能，您可能应该针对给定的应用程序进行基准测试，以确定您是否真正从这种优化中获得任何收益。

\n