0

コンテナstd::vectorがあり、それぞれにx個のアイテムがあるサブ範囲に効率的に分割したいと思います。元のコンテナは必要ないため、アイテムを移動し、サブ範囲にコピーしないでください。

コピーを使用して分割を行うことができましたが、移動割り当てでそれを行う方法がわかりませんか？

    range.insert(range.end(), new_items.begin(), new_items.end());
    while(range.size() >= x)
    {
        sub_ranges.push_back(std::vector<int>(range.begin(), range.begin() + x));
        range = std::vector<int>(range.begin() + x, range.end());
    }

編集：

いくつかの進歩...まだ完全にはありません、そして少し醜い

    while(range.size() >= x)
    {
        std::vector<short> sub_range(x); // Unnecessary allocation?
        std::move(range.begin(), range.begin() + x, sub_range.begin());
        sub_ranges_.push_back(std::move(sub_range));

        std::move(range.begin() + x, range.end(), range.begin());
        range.resize(range.size() - x);
    }
4

2 に答える 2

3

View1つの質問：あなたはその概念について聞いたことがありますか。

アイデアは、実際にデータを移動する代わりに、データの認識を制限/変更する「ビュー」（プロキシパターン）を作成するだけであるということです。

たとえば、範囲の場合、非常に単純な実装は次のようになります。

template <typename Iterator>
struct Range
{
  Iterator mBegin, mEnd;
};

Boost.Rangeたくさんのものを備えたファットバージョンを提供しています。

この場合、多くの利点があります。その中で：

  • 単一vectorの、したがってより良いメモリの局所性
  • 分割は簡単で、データの移動/コピーは必要ありません

splitこの方法では、次のようになります。

typedef Range<std::vector<int>::iterator> range_type;

std::vector<range_type> split(std::vector<int> const& range, size_t x)
{
  std::vector<range_type> subRanges;
  for (std::vector<int>::iterator it = range.begin(), end = range.end();
       it != end; it += std::min(x, (size_t)std::distance(it,end)))
  {
    subRanges.push_back(range_type(it,end));
  }
  return subRanges;
}

もちろん、これはrangeオブジェクトを保持できる場合にのみ機能します。

元のアルゴリズムに関して：whileここではループの使用は偽物であり、必要以上に多くmoveのsを使用する必要があります。私が作成したforループは、この点ではるかに優れているはずです。

于 2010-11-10T08:09:41.870 に答える
1

を使用std::make_move_iteratorし<iterator>て、イテレータをにラップできますmove_iterator。このイテレータはstd::move、ベースイテレータの逆参照の結果であり、他の場所に移動できるようにします。

// assuming I understand your code, which I don't
range.insert(range.end(), new_items.begin(), new_items.end());
while(range.size() >= x)
{
    auto first = std::make_move_iterator(range.begin());
    auto last = std::make_move_iterator(range.begin() + x);

    sub_ranges.push_back(std::vector<int>(first, last));
    range = std::vector<int>(range.begin() + x, range.end());
}

編集：そしてあなたが見つけたように、との間にはマッピングがstd::move()ありmake_move_iteratorます：

std::move(first, last, out); // is the same as
std::copy(std::make_move_iterator(first), std::make_move_iterator(last), out);

だからあなたがよりきれいだと思うものはあなた次第です。（最初のもの、私にとって。）

于 2010-11-09T23:19:56.357 に答える