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

ここで新しいデータ構造が必要になるとは思えません。あなたが本当に望んでいるのは、新しいallocatorであり、あなたが最善だと思うどんな構造でも使用できるように思えます。

C++03 では、これは比較的困難でしたが、C++1 では、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 に答える