72

私が自分自身を書く前に、私は皆に尋ねます。

STL ベクトルとほとんど同じですが、スタック上の配列にデータを格納する C++ クラスを探しています。ある種の STL アロケーター クラスも機能しますが、静的に割り当てられたスレッドごとのヒープであっても、あらゆる種類のヒープを回避しようとしています (ただし、そのうちの 1 つが私の 2 番目の選択肢です)。スタックはより効率的です。

ベクトルを使用する現在のコードの代わりに、ほとんどドロップする必要があります。

私が自分で書こうとしていたことについては、次のようなことを考えていました。

char buffer[4096];
stack_vector<match_item> matches(buffer, sizeof(buffer));

または、クラスにバッファ領域が内部的に割り当てられている可能性があります。次に、次のようになります。

stack_vector<match_item, 256> matches;

スペースがなくなると std::bad_alloc がスローされると思っていましたが、それは決して起こらないはずです。

アップデート

Chromium の stack_container.h を使用するとうまくいきます!

私が自分でこのようにすることを考えていなかった理由は、STL コレクション コンストラクターへのアロケーター オブジェクト パラメーターを常に見落としていたからです。テンプレート パラメーターを使用して静的プールを実行したことは数回ありますが、オブジェクト パラメーターを実際に使用するコードを見たり書いたりしたことはありません。私は何か新しいことを学びました。とてもかっこいい！

コードは少し乱雑で、なんらかの理由で GCC によって、アロケーターをベクターのアロケーター パラメーターに構築するのではなく、実際の項目として宣言するように強制されました。それは次のようなものから始まりました：

typedef std::pair< const char *, const char * > comp_list_item;
typedef std::vector< comp_list_item > comp_list_type;

comp_list_type match_list;
match_list.reserve(32);

これに：

static const size_t comp_list_alloc_size = 128;
typedef std::pair< const char *, const char * > comp_list_item;
typedef StackAllocator< comp_list_item, comp_list_alloc_size > comp_list_alloc_type;
typedef std::vector< comp_list_item, comp_list_alloc_type > comp_list_type;

comp_list_alloc_type::Source match_list_buffer;
comp_list_alloc_type match_list_alloc( &match_list_buffer );
comp_list_type match_list( match_list_alloc );
match_list.reserve( comp_list_alloc_size );

そして、新しいものを宣言するたびに、それを繰り返さなければなりません。しかし、それは私が望んでいたように機能します。

stack_container.h に StackVector が定義されていることに気付き、それを使用してみました。ただし、ベクターから継承したり、同じメソッドを定義したりしないため、ドロップインの代替品ではありませんでした。ベクトルを使用してすべてのコードを書き直したくなかったので、あきらめました。

4

10 に答える 10

50

完全に新しいコンテナ クラスを作成する必要はありません。STL コンテナーに固執することはできますが、たとえば の 2 番目のパラメーターを変更してstd::vector、スタック バッファーから割り当てるカスタム アロケーターを指定します。クロムの作成者は、このためだけにアロケーターを作成しました。

https://chromium.googlesource.com/chromium/chromium/+/master/base/stack_container.h

バッファの大きさを指定する場所にバッファを割り当てることで機能します。コンテナを作成して を呼び出しますcontainer.reserve(buffer_size);。そのサイズをオーバーフローすると、アロケータは自動的にヒープから要素を取得します (これは から派生しているstd::allocatorため、その場合は標準のアロケータの機能を使用するだけです)。試したことはありませんが、Google からのようですので、試してみる価値はあると思います。

使い方はこんな感じです。

StackVector<int, 128> s;
s->push_back(42); // overloaded operator->
s->push_back(43);

// to get the real std::vector. 
StackVector<int, 128>::ContainerType & v = s.container();
std::cout << v[0] << " " << v[1] << std::endl;
于 2008-12-09T22:27:00.920 に答える
12

あなたが見たいかもしれないいくつかのオプション：

Matthew Wilson (Imperfect C++ の作者) による STLSoft にauto_bufferは、既定の配列をスタックに配置するテンプレート クラスがありますが、スタック割り当てよりも大きくなると、ヒープからメモリを取得します。私はこのクラスが好きです。コンテナのサイズが一般的にかなり低い制限に制限されることがわかっている場合は、ローカルのスタック割り当て配列の速度が得られます。ただし、より多くのメモリが必要なまれなケースでは、すべて正常に動作します。

http://www.stlsoft.org/doc-1.9/classstlsoft_1_1auto__buffer.html

私が自分で使用する実装は STLSoft のものではなく、STLSoft のものを多用した実装であることに注意してください。

「The Lazy Programmer」はalloca()、ストレージに使用するコンテナの実装について投稿しました。私はこのテクニックのファンではありませんが、それがあなたの望むものかどうかはあなた自身で決めてください:

http://tlzprgmr.wordpress.com/2008/04/02/c-how-to-create-variable-length-arrays-on-the-stack/

次にboost::array、最初の 2 つの動的なサイズ変更動作はありvectorませんが、組み込み配列で取得する反復子としてポインターを使用するだけでなく、より多くのインターフェイスを提供します (つまりbegin()、end()、size()、 などを取得します)。

http://www.boost.org/doc/libs/1_37_0/doc/html/boost/array.html

于 2008-12-10T01:18:56.987 に答える
6

速度が重要な場合は、実行時間を確認します

  • 4 ns int[10]、スタック上の固定サイズ
  • 40ns<vector>
  • 1300ns<stlsoft/containers/pod_vector.hpp>

以下の 1 つのばかげたテスト -- 1 つのプラットフォームで 2 回のプッシュ、v[0] v[1]、2 回のポップ、mac ppc、gcc-4.2 -O3 のみ。(Apple が stl を最適化したかどうかはわかりません。)

自分で偽造していないタイミングを受け入れないでください。そしてもちろん、すべての使用パターンは異なります。それにもかかわらず、2 を超える要因には驚かされます。

(mems、メモリアクセスがランタイムの支配的な要因である場合、さまざまな実装で余分な mems は何ですか?)

#include <stlsoft/containers/pod_vector.hpp>
#include <stdio.h>
using namespace std;

int main( int argc, char* argv[] )
{
        // times for 2 push, v[0] v[1], 2 pop, mac g4 ppc gcc-4.2 -O3 --
    // Vecint10 v;  // stack int[10]: 4 ns
    vector<int> v;  // 40 ns
    // stlsoft::pod_vector<int> v;  // 1300 ns
    // stlsoft::pod_vector<int, std::allocator<int>, 64> v;

    int n = (argv[1] ? atoi( argv[1] ) : 10) * 1000000;
    int sum = 0;

    while( --n >= 0 ){
        v.push_back( n );
        v.push_back( n );
        sum += v[0] + v[1];
        v.pop_back();
        v.pop_back();
    }
    printf( "sum: %d\n", sum );

}
于 2009-07-29T11:20:15.903 に答える
5

std::vector に独自のアロケーターを使用して、例のようにスタックベースのストレージのチャンクを割り当てることができます。アロケータ クラスは、テンプレートの 2 番目の部分です。

編集: 私はこれを試したことはありません。さらにドキュメントを見ると、独自のアロケーターを作成できないと思います。私はまだそれを調べています。

于 2008-12-09T22:18:30.813 に答える
3

tr1::array はあなたの説明と部分的に一致します。push___back() などはありませんが、出発点として検討する価値があるかもしれません。それをラップし、「バック」にインデックスを追加して push_back() などをサポートすることは、かなり簡単なはずです。

于 2008-12-09T22:39:40.613 に答える
2

特にスタックに入れたいのはなぜですか？alloca() の実装がある場合は、malloc() の代わりにそれを使用してクラス アロケータを構築できますが、静的に割り当てられた配列を使用するという考えはさらに優れています。ほとんどのアーキテクチャで同じくらい高速であり、そうではありません。あなたのリスクスタックの破損が台無しになります。

于 2008-12-09T22:25:10.660 に答える
2

Qtを使用している場合があります。QVarLengthArray次に、 （docs ）に行きたいと思うかもしれません。基本的に と の間に位置std::vectorしstd::array、一定量を静的に割り当て、必要に応じてヒープ割り当てに戻ります。

私がそれを使っていたなら、私はブーストバージョンを好むだろう.

于 2014-05-13T20:00:24.230 に答える
1

ブーストはこれを持っています。small_vectorと呼ばれる

small_vector は、含まれる要素が少ない場合に最適化された、ベクターのようなコンテナーです。いくつかの事前割り当て済み要素がインプレースで含まれているため、実際の要素数がその事前割り当て済みしきい値を下回っている場合に、動的ストレージ割り当ての使用を回避できます。small_vector は、LLVM の SmallVector コンテナーに触発されています。static_vector とは異なり、small_vector の容量は、最初に事前に割り当てられた容量を超えて拡大する可能性があります。

small_vector は、事前に割り当てられた要素数から独立した型である small_vector_base に変換できるため、その N 引数でテンプレート化する必要のないクライアント コードが可能になります。small_vector はすべての vector のメンバー関数を継承するため、配置、ステートフル アロケータなどのすべての標準機能をサポートします。

于 2016-04-21T08:50:48.023 に答える