6

假设我正在编写一个简单的缓冲区类。该缓冲区将充当标准 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 足够大，push 和 pop 的成本可能会特别高。另一种解决方案是将前几个元素始终保留在堆栈上，并将溢出放在堆上。但这意味着 Buffer 无法“转换”为简单的数组。

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

4

2 回答 2

3
于 2012-09-09T08:01:33.343 回答
2

我不相信你在这里需要一个新的数据结构。在我看来，您真正想要的是一个新的分配器，可以与您认为最好的任何结构一起使用。

在 C++03 中，这会相对困难，但是 C++11 现在要求 STL 容器与有状态分配器一起工作，因此您可以完美地创建一个带有小堆栈的分配器供自己使用......并将其用作的一个论点std::vector<>。

示例（使用模板别名）

template <typename T, size_t N = 8>
using SmallVector = std::vector<T, SmallAllocator<T, N>>;

通过这种方式，您将受益于实现的所有稳健性和优化std::vector，并且您只需提供分配层，这似乎是最初的目标。

于 2012-09-09T12:51:05.370 回答