在堆栈和堆之间动态切换
假设我正在写一个简单的缓冲区类。 这个缓冲区将作为标准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只是浪费空间。 另外，如果缓冲区足够大，push和pop可能会特别昂贵。 另一种解决方案是将前几个元素始终放在堆栈上，并将堆溢出。 但是这意味着Buffer不能被转换成简单的数组。
有更好的解决方案吗？ 如果这是在std :: string中完成的，有人可以指出如何或提供一些资源吗？
我会建议你使用指针_data代替_heap ，这通常是指您的数据存储。 _heap == NULL会变成_data == _stack等等，但是在所有不会查看数据长度的情况下，您可以避免区分大小写。
您当前的草图不包含_capacity成员来跟踪当前分配的空间。 YOu需要实现“追加到它，重新分配，如果需要”的部分，除非你想重新分配每一个堆分配容器的长度变化。
您也可以考虑在您的数据放入堆栈时不释放堆空间。 否则，可能会有应用程序在该边界处添加和删除单个元素，每次都会导致分配。 因此，要么执行一些滞后操作，要么一旦分配完毕就不释放堆空间。 总的来说，我认为释放堆内存应该与缩小的堆内存一起使用。 这两种方法都可能会自动执行，以响应某个函数调用（如shrink_to_fit ，或者完全不执行，但在类似情况下执行一个操作时没有意义，而没有其他操作。
除此之外，我相信你的解决方案几乎是你所希望的。 也许为MinSize提供一个默认值。 如果MinSize很小，为了避免堆栈溢出，那么浪费这个空间不会有太大问题，是吗？
当然，最终这一切都取决于您的实际应用程序，因为此表单中大量未使用的堆栈分配可能会对堆栈内存的高速缓存产生不利影响。 考虑到默认分配器也可以非常聪明，您可能应该基准测试一下，对于给定的应用程序，您是否从这种优化中获得了什么。
我不相信你在这里需要一个新的数据结构。 在我看来，你真的想要的是一个新的分配器 ，用于你认为最好的任何结构。
在C ++ 03中，这会比较困难，但是C ++ 11现在要求STL容器使用有状态的分配器，所以你可以完美地创建一个分配器，它有一个小堆栈供自己使用......并将其用作std::vector<>一个参数。
示例（使用模板别名）
template <typename T, size_t N = 8>
using SmallVector = std::vector<T, SmallAllocator<T, N>>;
通过这种方式，您将受益于std::vector实现中的所有健壮性和优化，您只需提供分配层，这似乎是最初的目标。