0

可変量の要素を非常に効率的に追加できるコンテナが欲しいのですが、何かをトリガーできるので、最初から上書きを開始できます。これを使用すると、次のstd::listようになります。

while(whatever)
{
    for(int i = 0; i < randNumber; ++i)
        list.push_back( foo() );
    //now want to reset
    list.clear();
}

問題はlist.clear()線形時間ですが、実際には最初に戻ってそこから上書きを開始したいと思います...vector[index++] = foo()クリアを使用して置き換えてベクトルを試しましたindex = 0が、予測randNumberできないため、これは機能しません...何ができますか私はこれを達成するために代わりに使用しますか？

ところで、些細なデストラクタがあっても、ベクトルクリアは一定時間ではないようです。

struct rat
{
    rat(int* a, int* b) : a_(a), b_(b) {}

    int *a_;
    int *b_;
};

int main(int argc, char **argv)
{
    uint64_t start, end;

    int k = 0;
    vector<rat> v;
    for (int i = 0; i < 9000; ++i)
        v.push_back(rat(&k, &k));

    start = timer();
    v.clear();
    end = timer();

    cout << end - start << endl;
}
4

2 に答える 2

2

コード内でを置き換えるだけstd::listですstd::vector。push_back必要に応じてサイズをインクリメントclearし、コンテナからすべての要素を削除します。注：std::vector<>::clear()コンテナーのサイズには直線的な時間がかかりますが、操作は、とにかく実行する必要のある、格納されている要素の破棄です（重要なデストラクタがある場合）。些細なデストラクタを持つタイプの場合std::vector<>::clear()、定数時間演算として動作します。

于 2012-06-27T16:21:50.950 に答える
0

上界と下界はありrandNumberますか？もしそうなら、あなたはstd::vector::reserve()物事をスピードアップするために使用することができます。このように、O（1）で追加し、O（1）で削除する必要があります。

ノート！ベクトルに自明でないデストラクタを持つデータ型が含まれている場合、clearO（n）を取ります。ただし、デストラクタが自明である場合は、clearO（1）を取ります。

stl_constructor.hからのコメント：

/**
 * Destroy a range of objects.  If the value_type of the object has
 * a trivial destructor, the compiler should optimize all of this
 * away, otherwise the objects' destructors must be invoked.
 */
于 2012-06-27T16:09:54.433 に答える