C++ベクトル

Question

考えるからアイテムの既知のサブセットを削除：実行するコードを記述するための最も効率的な/クリーンな方法は何

• struct Item { int id; ... };
• std::vector<Item> items;
• std::vector<int> idsToRemove;

削除（注文を保持している間）？ remove_ifを使用して

、これは次のようになります。

items.erase(std::remove_if(items.begin(), items.end(), 
    [&](const Item& i) { 
     return std::find(idsToRemove.begin(), idsToRemove.end(), i.id) 
      != idsToRemove.end(); 
    }), items.end()); 

もう一つの方法は、次のようになります。

for (auto id : idsToRemove) 
{ 
    items.erase(std::remove(items.begin(), items.end(), id), items.end()); 
    // or items.erase(std::find(items.begin(), items.end(), id)); 
    // provided that we know id always exists in items 
} 

どちらもこれらの特に素敵な感じ（と彼らの両方がO（N * M）に見えます）第二のものは最初のものよりもきれいに見えます。より良い方法がありますか？

（どちらのベクトルもソートされていないが、どちらもidsToRemoveは、itemsに表示されているのと同じ順序でIDのサブセットであり、両方の配列が小さいことがわかっている。あそこに適した何か。）

Answer 1

idsToRemoveでIDがitemsで、同じ順序であることが知られているので、あなたは現在の比較要素を追跡するためにitemsにイテレータのカップルを使用することができ、現在の宛先、およびidsToRemoveとitemsを歩き、両方の要素を比較し、保持したい要素を移動します。そのプロセスの最後に、itemsを新しい小さなサイズに変更します。

Answer 2

私はこれを（ゴールポストを動かすために）述べたような疑問に対する真の答えとは考えませんが、調査中に見つけたもので、将来の検索には役立つかもしれません。あなたはidsToRemoveが外部に渡されていますが、削除するかを決定するために、とにかくitemsを反復処理する必要がない場合は、その後、O（N）でこれを行うにはかなり良い方法があります場合は

：

#include <boost/range/algorithm_ext/erase.hpp> 

boost::range::remove_erase_if(items, [&](const Item& item) 
{ 
    // do whatever else you want to item 
    // return true to erase the item, or 
    return false; // to keep it 
}); 

これは内部的にはstd::remove_ifに基づいていますが、それははるかに整頓され、範囲ベースのものに似ています。

Answer 3

あなたの要素には一意のIDがあるとしますので、削除する要素をstd::vectorに保存する代わりに、std::unordered_setに保存してください。

この方法では、std::remove_if方法が本当にきれいです：

struct Item { 
    int id; 
}; 

// ... 
std::vector<Item> items; 
std::unordered_set<int> idsToRemove; 
items.erase(
    std::remove_if(std::begin(items), std::end(items), [&](Item const& it) { 
      return (idsToRemove.find(it.id) != std::end(idsToRemove)); 
     }), 
    std::end(items)); 

複雑（償却）Nは、ベクトルの要素数があるO(N)になります。