3

2つの整数ベクトルがあるとします。

ここに画像の説明を入力してください

ここに画像の説明を入力してください

開始インデックスと2つのシーケンスの長さを引数として渡す2つのベクトル間で要素の範囲を交換できる関数を定義したいと思います。

例：ここに画像の説明を入力してくださいここでここに画像の説明を入力してください、およびここに画像の説明を入力してくださいはベクトルであり、引数として渡される数値は、シーケンスの開始インデックスと長さを表します。

この場合、私は出力として取得する必要があります

v1 = 1,2、13,14,15、5,6,7,8,9

v2 = 10,11,12、3,4、16,17,18

例として定義した関数のシグネチャは制約ではありません。より良い方法があると思われる場合は、それで問題ありません。

4

3 に答える 3

6

すべての通常のSTLアルゴリズムは、正確に実行したいことを満たしていないようです。

std::swap_rangesほぼそこにありますが、同じように長い範囲を交換する必要 std::rotateもありますが、1つの範囲の終点が2番目の範囲の始点と等しい必要があります。

// pseudo-splice on vector
v1.insert(v1.begin() + 2 + 2, v2.begin() + 3, v2.begin() + 3 + 3);
v2.erase(v2.begin() + 3, v2.begin() + 3 + 3);

// pseudo-splice on vector
v2.insert(v2.begin() + 3, v1.begin() + 2, v1.begin() + 2 + 2);
v1.erase(v1.begin() + 2, v1.begin() + 2 + 2);

もちろん、これを2つの範囲の任意のイテレータ境界をとる関数テンプレートに簡単に抽象化できます。

デビッドのコメントに基づいて編集し、不必要なサイズ変更を避けるためにいくつかの最適化を行うことができます

// compute smallest range here, in this case it's the v1 part
std::swap_ranges(v1.begin() + 2, v1.begin() + 2 + 2, v2.begin() + 3);

// now handle the remaining part of the longest range, in this case it's element v2 + 3 + 2
std::insert(v1.begin() + 2 + 2, v2.begin() + 3 + 2);
std::erase(v2.begin() + 3 + 2);

更新：それstd::list以来使用した方が簡単です（以下のコードを模倣するために/部分spliceを再配置しました）inserterase

v1.splice(v1.begin() + 2 + 2, v2, v2.begin() + 3, v2.begin() + 3 + 3);
v2.splice(v2.begin() + 3, v1, v1.begin() + 2, v1.begin() + 2 + 2);
于 2012-08-19T13:49:55.550 に答える
1

Length1！= Length2の場合、ベクトルを再割り当てする必要があるという事実以外に、これによって問題が発生することはないと思います。

 swap_elements(v1, start1, length1, v2, start2, length2){
      if(length1 != length2){
        //alloc mem for both of the arrays
        //copy the unmodified portions of the original arrays into the new arrays
      }

      //swap the elements
 }
于 2012-08-19T13:52:26.610 に答える
0

挿入と消去を適切に行うと、以下のコードよりも実行時間が遅くなります。これは、挿入と消去が呼び出されるたびに、ベクトルの他の要素をメモリ内で適宜移動し、新しいメモリブロックを割り当て、ベクトル要素を新しいメモリに移動する必要があるためです。必要に応じてブロックします。サイズ変更とメモリの問題を回避するために、最初に2つの新しいベクトルを作成することが望ましい場合があります。

swap_elements(vector<int> &v1, int s1, int l1, vector<int> &v2, int s2, int l2){
    vector<int> nv1(v1.begin(),v1.begin()+s1);
    vector<int> nv2(v2.begin(),v2.begin()+s2);
    for(int i=0;i<l2;i++)
      nv1.push_back(v2[s2+i]);
    for(int i=0;i<l1;i++)
      nv2.push_back(v1[s1+i]);
    for(int i=s1+l1+1;i<v1.size();i++)
      nv1.push_back(v1[i]);
    for(int i=s2+l2+1;i<v2.size();i++)
      nv2.push_back(v2[i]);
    v1.clear();
    v2.clear();
    v1=nv1;
    v2=nv2;
}
于 2012-08-19T13:53:49.183 に答える