c++ - ベクトルを連結/マージする方法

Question

2つのベクトルと1つの整数を1つのベクトルにマージする方法を見つけようとしています。すなわち

return data.push_back(fn(data1), mid, fn(data2));

注意：これは再帰関数です。ベクターデータには、returnステートメントに到達する前に値が格納されています。データの値をreturnステートメントの値で更新する必要があります。

私はこれをどうやってやるのか全く分かりません。私は数時間探していましたが、何もうまくいかないようです！

どんなガイダンスでも大歓迎です。

Answer 1

std::vector::insert()イテレータ範囲を受け入れます：

std::vector<int> left(fn(data1));
std::vector<int> right(fn(data2));
data.insert(data.end(), left.begin(), left.end());
data.push_back(mid);
data.insert(data.end(), right.begin(), right.end());
return data;

std::copy()from<algorithm>およびstd::back_inserter()fromを使用することもできます<iterator>：

std::copy(left.begin(), left.end(), std::back_inserter(data));
data.push_back(mid);
std::copy(right.begin(), right.end(), std::back_inserter(data));

ただし、不透明な状態insert()で、入力範囲のサイズとreserve()適切なメモリ量を事前に知ることができます。これは、を繰り返し呼び出すだけです。どちらも線形時間で実行されますが、割り当てが少なくなる可能性があります。back_insert_iteratorpush_back()insert()

ベクトルの要素がコピーよりも移動の方が効率的である場合は、C ++11fromを使用して入力範囲を調整できstd::make_move_iterator()ます<iterator>。

data.insert(data.end(),
    std::make_move_iterator(left.begin()),
    std::make_move_iterator(left.end()));
data.push_back(mid);
data.insert(data.end(),
    std::make_move_iterator(right.begin()),
    std::make_move_iterator(right.end()));

私はこれが違いを生むとは思えませんがint。

Answer 2

std::back_inserterと一緒に使用しstd::copyます。例えば：

void foo(vector<int> lhs, vector<int>& rhs)
{
  vector<int> result;
  copy( lhs.begin(), lhs.end(), back_inserter(result));
  copy( rhs.begin(), rhs.end(), back_inserter(result));
  result push_back(42);
  return result;
}

Answer 3

3つのイテレータ引数をとるinsertmember関数を使用したいとします。