さらにstd :: set woes

Question

私はthis questionより早く尋ねました。私はstd :: setに興味を持っていますが、別の混乱するシナリオがあります。

すなわち、T = STD ::ベクトル及びT = STDのための次のコード法的、移植可能なC++で::設定：

template <typename T> 
void remove_elements(T& collection, int removal_value) 
{ 
    typename T::iterator new_end = 
     std::remove(collection.begin(), collection.end(), removal_value); 
    collection.erase(new_end, collection.end()); 
} 

SGI基準によれば、設定::イテレータと設定:: const_iteratorは同じなので、これが正当なものかどうかはわかりません。しかし、私はタイプに関係なく動作する必要がある操作を得る別の方法を見つけることができないようです。私はテンプレートの専門化に頼ることができますが、最初の場所に特化する必要はありません。

Answer 1

erase-removeイディオムは、シーケンスコンテナに対してのみ機能します。標準的な連想コンテナの場合、それはうまくいかず、解決策はそれほど簡単ではありません。

二つのアプローチ：

1. 使用remove_copy_if別の一時 の容器にすべて 値をコピーして、内容を一時的なものとは と元の容器の を交換します。 [関連するQにanswerを参照してください]
2. もう1つは、コンテナ要素を移動してイテレータをインクリメントするときに反復子をインクリメントするためにループします。

詳細については、このQを参照してください：remove_if equivalent for std::map

をまた、スコット・マイヤーズによる効果的なSTLからオプションを消去する間に、慎重に選択してください9.項目を参照してください。

Answer 2

std::remove()の要件の1つは、イテレータが可変イテレータであり、std::setのイテレータが変更可能でないためです。いいえ、std::setでは機能しません。

私は残念なことに、提案する良い選択肢がありません。あなたができることの1つは、おそらく、要素のオカレーターに対するイテレーターを見つけるためにstd::find()を使用し、イテレーター（std::vectorとstd::setの両方に存在する）で.erase()メソッドを使用してそれを消去することです。そのような要素がなくなるまでそれを続けてください。しかし、これはO（n）の代わりにO（n^2）という非常に非効率的であるかもしれません。

Answer 3

std::setの場合、「正しい」答えはremove_elementsです。 setは順序付けされ、重複を含まないので、removal_valueに等しい要素を削除することは、ベクトルまたは汎用シーケンスよりもはるかに簡単です。

template <typename T> 
void remove_elements(T& collection, const typename T::value_type& removal_value) 
{ 
    typename T::iterator new_end = 
     std::remove(collection.begin(), collection.end(), removal_value); 
    collection.erase(new_end, collection.end()); 
} 

template<typename T> 
void remove_elements(std::set<T>& collection, const T& removal_value) 
{ 
    collection.erase(removal_value); 
} 

私はこれらが今まであいまいであるかどうかについて、少し心配だけど、最も明白なユースケースでは、彼らがOKを動作するようです：あなたは本当にも、あなたができれば、すべてのための同じアルゴリズムを使用したくありません私のために。

std :: set以外のUnique Sorted Associative Containerがあると、これは苦労します。 std :: swapの領域に移動しています。ここで実装するすべてのクラスは、remove_elementsのオーバーロードを提供する必要があります。しかし、あなたが求めているクラスはsetだけなので、少なくとも今のところ、あなたが実際に使っている唯一の難しいケースだと思います。必要に応じて、特性を使用して、コンテナのプロパティに基づいてアルゴリズムの正しいバージョンを選択することができます。