消去要素

Question

次のループは、いくつかの述語predを満たすstd::unordered_mapから要素を消去する細かな方法であることを示唆しているStackOverflowの上のいくつかの答えがあります。

std::unordered_map<...> m; 
auto it = m.begin(); 
while (it != m.end()) 
{ 
    if (pred(*it)) 
     it = m.erase(it); 
    else 
     ++it; 
} 

私が特に興味C++ 11（C++ 14とは対照的に）、及び以下の不吉note on cppreference.com上記ループは未定義の動作に依存し、すべての後にC++ 11で動作しないことを示唆している：

ための消去されない要素は保存されます（thi SはC++ 14以降（）コンテナを反復しながら、個々の要素を消去することが可能となる）

も参照してくださいTitle 2356. Stability of erasure in unordered associative containersページ754のWorking Draft N3797項目14に要求された文言の変更（追加のフレーズから始まるが含まれています"、相対的な順序を維持する..."）。

この文言はN3797に関連しています。

修正[unord.req]、示されるように、P14：

-14-インサートと据え付けるメンバーは、コンテナ要素への参照の有効性に影響を与えてはならないが、 コンテナにすべてのイテレータを無効にすることができます。消去メンバーは、イテレーターと、消去されたエレメントへの参照を無効にし、消去されないエレメントの相対的な順序を に保持する。

私のcppreference.comからの注釈の解釈が正しい場合、上記のループはC++ 11の未定義の動作に依存しますが、C++ 11でこの問題を解決する最も効率的な方法は何ですか？

Answer 1

常にSTL-アルゴリズムを最初

を参照してくださいこの1つは望んでいたことのようです： http://www.cplusplus.com/reference/algorithm/remove_if/

概要について： http://www.cplusplus.com/reference/algorithm/

EDIT cppreferenceはで同様の例がありますサイトの下部。 これはC++ 11コンパイラで動作します。

Answer 2

さて、あなたは、常にこの操作を行うことができます。

std::unordered_map<...> m; 
std::vector<key_type> needs_removing; 
for(auto&& pair : m) 
{ 
    if (pred(pair)) 
     needs_removing.push_back(pair.first); 
} 
for(auto&& key : needs_removing) 
    m.erase(key); 

それは遅くなりますが、複雑さは同じです。

Answer 3

C++ 11に準拠するには、残念ながらこれに対処する方法が少し限られています。unordered_map上

1. 反復などのように削除するには、キーのリストを構築する：あなたのオプションは、基本的に煮詰める

   //std::unordered_map<...> mymap; 
   std::vector<decltype(mymap)::key_type> vec; 
   for (auto&& i : mymap) 
       if (/*compare i*/) 
        vec.emplace_back(i.first); 
   for (auto&& key : vec) 
       mymap.erase(key); 
   

2. 反復をオブジェクトの上に、我々は削除する何かを見つけた場合、リセット - 小さなデータセットの場合にのみこれをお勧めします。 gotoを感じるあなたのものは無条件に悪いです、このオプションは間違いなく間違いです。

   //std::unordered_map<...> mymap; 
   reset: 
   for (auto&& i : mymap) 
       if (/*compare i*/) { 
        mymap.erase(i.first); 
        goto reset; 
       } 
   

3. 多少そこオプションとして、あなたもちょうど新しいunordered_mapを作成し、維持したい要素を移動することができます。これは間違いなく、保持するよりも削除する必要がある場合には良い選択です。

   //std::unordered_map<...> mymap; 
   decltype(mymap) newmap; 
   for (auto&& i : mymap) 
       if (/*i is an element we want*/) 
        newmap.emplace(std::move(i)); 
   mymap.swap(newmap);