0

ベクトルのマージ関数を実装しました。これは基本的に、ソートされたベクトルを 1 つのソートされたベクトルに結合します。(はい、マージソートアルゴリズム用です)。コードを高速化し、オーバーヘッドを回避しようとしていたため、ベクターで push_back メソッドを使用せず、代わりにオーバーヘッドの少ない配列構文を使用することにしました。しかし、何かがひどく間違っていて、これを行うと出力がめちゃくちゃになります。コードは次のとおりです。

while(size1<left.size() && size2 < right.size()) //left and right are the input vectors
{
             //it1 and it2 are iterators on the two sorted input vectors
    if(*it1 <= *it2)
    {

        final.push_back(*it1); //final is the final vector to output
        //final[count] = *it1; // this does not work for some reason
        it1++;
        size1++;
        //cout<<"count ="<<count<<" size1 ="<<size1<<endl;

    }
    else
    {
        final.push_back(*it2);
        //final[count] = left[size2];
        it2++;
        size2++;
    }
    count++;    
    //cout<<"count ="<<count<<" size1 ="<<size1<<"size2 = "<<size2<<endl;

}

2つの方法は機能的に同等であるべきだと私には思えます。

PS私はすでに最終ベクトル用のスペースを予約しているので、問題にはなりません。

4

2 に答える 2

4

を使用して新しいオブジェクトを追加することはできません。どちらも追加しません。またはのいずれかを使用する必要があります。vectoroperator[].reserve().resize().push_back()

また、オーバーヘッドをまったく回避していません。の呼び出しコストはoperator[]それよりもはるかに優れているわけではないpush_back()ため、コードを徹底的にプロファイルするまでは、push_back. 不必要な割り当てが行われないようにするために、引き続きreserve を使用できます。

ほとんどの場合、このような「最適化」はあまり役に立ちません。コードを高速化する場合は、最初にプロファイリングして、ホット パスを探します。

于 2013-03-10T08:26:48.250 に答える
3

の間には大きな違いがあります

vector[i] = item;

と

vector.push_back(item);

違い:

  • 最初のものはindex の要素を変更し、有効な indexiでなければなりません。iあれは、

    0 <= i < vector.size() は true でなければなりません

    が無効なインデックスである場合i、最初のインデックスは未定義の動作を呼び出します。つまり、何でも起こり得るということです。ただし、が無効なat()場合に例外をスローするを使用できます。i

    vector.at(i) = item; //throws exception if i is invalid

  • 2 番目のものは、ベクターの最後に要素を追加します。これは、ベクターのサイズが1増加することを意味します。

どちらも意味的には異なることを行うため、必要な方を選択してください。

于 2013-03-10T08:28:29.870 に答える