5

STL標準では、std :: deque、std :: listなどのコンテナで消去が発生すると、イテレータが無効になると定義されています。

私の質問は次のとおりです。std::dequeに含まれる整数のリストと、std :: dequeの要素の範囲を示すインデックスのペアを想定すると、すべての偶数要素を削除する正しい方法は何ですか？

これまでのところ、次のことがありますが、ここでの問題は、消去後に想定される終了が無効になることです。

#include <cstddef>
#include <deque>

int main()
{
   std::deque<int> deq;
   for (int i = 0; i < 100; deq.push_back(i++));

   // range, 11th to 51st element
   std::pair<std::size_t,std::size_t> r(10,50);

   std::deque<int>::iterator it = deq.begin() + r.first;
   std::deque<int>::iterator end = deq.begin() + r.second;

   while (it != end)
   {
      if (*it % 2 == 0)
      {
         it = deq.erase(it);
      }
      else
        ++it;
   }

   return 0;
}

std :: remove_ifがどのように実装されているかを調べると、非常にコストのかかるコピー/シフトダウンプロセスが進行しているようです。

  • すべてのコピー/シフトなしで上記を達成するためのより効率的な方法はありますか？

  • 一般に、要素を削除/消去することは、シーケンス内の次のn番目の値と交換するよりもコストがかかります（nはこれまでに削除/削除された要素の数です）

注：回答では、シーケンスサイズが非常に大きく、+ 1mil要素であり、平均して要素の1/3が消去可能であると想定する必要があります。

4

4 に答える 4

8

Erase-RemoveIdiomを使用します。リンクされているウィキペディアの記事には、あなたがしていること、つまり奇妙な要素を取り除くことさえ示されていると思います。

これを行うコピーremove_ifは、コンテナの中央から要素を削除した場合よりもコストがかかりません。それはさらに効率的かもしれません。

于 2010-12-03T03:56:43.323 に答える
5

呼び出す.erase()と、「非常にコストのかかるコピー/シフト ダウン プロセスが進行中です」という結果にもなります。コンテナの中央から要素を消去する場合、そのポイント以降の他のすべての要素は、使用可能なスペースに 1 つ下に移動する必要があります。複数の要素を消去すると、消去された要素ごとにそのコストが発生します。消去されていない要素の中には、複数のスポットを移動するものもありますが、すべてを一度に移動するのではなく、一度に 1 つのスポットを移動する必要があります。それは非常に非効率的です。

標準ライブラリのアルゴリズムは、この作業std::removeをstd::remove_if最適化します。彼らは巧妙なトリックを使用して、移動されたすべての要素が一度だけ移動されるようにします。これは、直感に反して、自分で行っていることよりもはるかに高速です。

擬似コードは次のようになります。

read_location <- beginning of range.
write_location <- beginning of range.
while read_location != end of range:
    if the element at read_location should be kept in the container:
        copy the element at the read_location to the write_location.
        increment the write_location.
    increment the read_location.

ご覧のとおり、元のシーケンスのすべての要素は 1 回だけと見なされ、保持する必要がある場合は、現在の write_location に 1 回だけコピーされます。write_location が read_location の前で実行されることはないため、再度参照されることはありません。

于 2010-12-03T05:26:43.410 に答える
2

deque は連続したメモリ コンテナー (ベクトルのように、おそらく実装を共有する) であるため、コンテナーの途中で要素を削除することは、必然的に、後続の要素をホールにコピーすることを意味します。削除するたびにすべてのオブジェクトを 1 つずつ移動するのではなく、1 回の反復を実行し、削除されない各オブジェクトを最終的な位置に直接コピーしていることを確認したいだけです。 remove_ifこの点で効率的で適切ですが、eraseループはそうではありません。大量の不要なコピーを行います。

FWIW - 代替案:

  • オブジェクトに「削除済み」状態を追加し、その場で削除済みとしてマークしますが、コンテナを操作するたびに自分で確認する必要があります
  • 前の要素と次の要素へのポインターを使用して実装されるリストを使用します。これにより、リスト要素を削除すると隣接するポイントが変更され、その要素がバイパスされます。ポインターのオーバーヘッド

何を選択するかは、特定の操作の性質、相対的な頻度、およびパフォーマンス要件によって異なります (たとえば、重要でない時間に行われる場合は、ゆっくりとした削除を許容できるかもしれませんが、可能な限り最速の反復が必要です。ニーズとさまざまなデータ構造の意味を理解していることを確認してください)。

于 2010-12-03T04:43:00.670 に答える
0

言及されていない代替手段の 1 つは、新しい を作成し、deque保持したい要素をコピーしswapて、古いdeque.

void filter(std::deque<int>& in, std::pair<std::size_t,std::size_t> range) {
    std::deque<int> out;
    std::deque<int>::const_iterator first = in.begin();
    std::deque<int>::const_iterator curr = first + range.first;
    std::deque<int>::const_iterator last = first + range.second;
    out.reserve(in.size() - (range.second-range.first));
    std::copy(first, curr, std::back_inserter(out));
    while (curr != last) {
        if (*curr & 1) {
            out.push_back(*curr);
        }
        ++curr;
    }
    std::copy(last, in.end(), std::back_inserter(out));
    in.swap(out);
}

コピーを作成するのに十分なメモリがあるかどうかはわかりませんが、通常は、大きなコレクションから要素をインライン消去するよりも、コピーを作成する方が速くて簡単です。それでもメモリのスラッシングが見られる場合は、呼び出して保持する要素の数を把握し、std::count_ifその数を予約します。このようにして、単一のメモリ割り当てが行われます。

于 2010-12-04T02:42:51.207 に答える