私は tr1::unordered_map を試していて、要素を効率的に削除する方法の問題に遭遇しました。「erase」メソッドは、キーまたはイテレータによる削除を提供します。前者はおそらく暗黙の検索操作を伴うため、後者の方が効率的であると思います。一方、インターネットで調査したところ、insert() メソッドを呼び出した後にイテレータが無効になる可能性があることがわかりました。
私は典型的な実世界の状況に興味があります.ハッシュテーブルに入れられたオブジェクトには、その寿命の間にinsert()の呼び出しが発生するのに十分な長さの寿命があります. したがって、そのような状況では、キーによる削除が残された唯一の選択肢であると結論付けてよいでしょうか? オブジェクトをより効率的に削除する方法はありますか? この質問は、削除が頻繁に発生するアプリケーションでのみ重要であることを十分に認識しています。これが私の現在のプロジェクトに当てはまるかどうかはまだわかりませんが、すでに多くのコードが存在する場合よりも、プロジェクトを設計しているときにこれらの問題について学びたいと思います.
順序付けられていないコンテナーの要点は、ルックアップ時間を可能な限り高速にすることです。キーごとに要素を消去するのにかかる時間を心配することは、時期尚早の最適化の典型的な例のように聞こえます。
他の理由でイテレータを保持しているため、それが非常に重要な場合、C++0x はstd::unordered_map23.2.5/11 で (FDIS からの引用) について述べています。
(N+n) < z * B の場合、insert メンバーと emplace メンバーは反復子の有効性に影響を与えません。ここで、N は挿入操作前のコンテナー内の要素の数、n は挿入された要素の数、B はコンテナー内の要素の数です。コンテナのバケット数、z はコンテナの最大負荷係数です。
仕様に同じ保証があるかどうかは確認していませんがtr1、予想される実装に基づいてかなり論理的です。
この保証を使用できる場合は、イテレータをある程度まで保護できます。ただし、Mark が言うように、ルックアップはunordered_map高速である必要があります。イテレータではなくキーを保持することは、 にイテレータではなくインデックスを保持することよりも悪いですvectorが、同等のものよりはましですmap。
はい、insert()すべてのイテレータを無効にすることができます。したがって、（暗黙の）ルックアップを回避する方法はないと思います。良いニュースは、後者が安い可能性が高いということです。