15

私は持っていvector<vector<int> > Yます。Y 内のサブベクトル (y と呼びます) を 1 つにマージしたいと思いvector<int>ます。しかし、私はそれらをソートしたくありません。つまり、出現順にマージします。おそらくSTLアルゴリズムを使用して、これを効率的に行うにはどうすればよいでしょうか? メソッドは、std::merge私が望まないソートによってマージされます。

編集:私が欲しいのは: {{1,6,5},{5,3-1,77},{0},...} return {1,6,5,5,3,-1, 77,0,...}

4

2 に答える 2

15 
template <typename T>
std::vector<T> flatten(const std::vector<std::vector<T>>& v) {
    std::size_t total_size = 0;
    for (const auto& sub : v)
        total_size += sub.size(); // I wish there was a transform_accumulate
    std::vector<T> result;
    result.reserve(total_size);
    for (const auto& sub : v)
        result.insert(result.end(), sub.begin(), sub.end());
    return result;
}

@not-sehe のソリューションと比較すると、これにはいくつかのパフォーマンス上の利点があります。

  • 結果の最終サイズを計算し、ストレージを事前に割り当てます。これは、再割り当てを繰り返す必要がないことを意味します。
  • 他のバージョンのように、単一要素の挿入の代わりに範囲挿入を使用します。これにより、コンテナはいくつかの最適化を適用できます。特に要素が自明にコピー可能な場合 (つまり、内部コンテナごとに 1 つの memcpy)。

欠点としては、ベクトルでのみ機能し、deque やリストでは機能しません。

于 2013-06-25T14:11:01.113 に答える