c++ - 在栈和堆之间动态切换

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;
};

如您所见，当缓冲区增长超过 MinSize 时，_stack 只是浪费空间。此外，如果 Buffer 足够大，push 和 pop 的成本可能会特别高。另一种解决方案是将前几个元素始终放在堆栈上，并将溢出放在堆上。但这意味着 Buffer 无法“转换”为简单数组。

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

Answer 1

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

您当前的草图不包含 _capacity 成员来跟踪当前分配的空间。您将需要它来实现“附加到它，如果需要则重新分配”部分，除非您想要为堆分配容器的每个长度变化重新分配。

您也可以考虑在数据适合堆栈时不释放堆空间。否则，可能会有应用程序在该边界处添加和删除单个元素，每次都会导致分配。所以要么实现一些hysteresis或者在分配堆空间后根本不释放堆空间。一般来说，我会说释放堆内存应该与缩小堆内存一起使用。您可能希望自动执行这两项操作，以响应某个函数调用，例如 shrink_to_fit。 ，或者根本不做，但是在类似情况下只做一个而不做另一个没有什么意义。

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

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