2

std::unordered_map<K,T>findを返すようなメソッドを提供しますstd::unordered_map<K,T>::iterator。私の知る限り、再ハッシュが発生しない限り、イテレータは有効なままです。

しかし、Linux リンク リストで行われる「ハック」と同様に、ラウンドトリップ::iterator-> T *->の保証された方法はないのではないかと私は疑っています。::iteratorイテレータはを介して逆参照可能である必要があるためだと思いますが->second、コンテナ内に耐久性のあるストレージタイプが必要な場所がわかりません。

それで、私は正しいですか？イテレータを保持する必要がありますか、またはメンバーのアドレスがT *ptr = &myiterator->secondであるイテレータ ポインタに後でバックキャストできますか?->secondptr

この質問は当然、他のコンテナのイテレータにも当てはまります。

4

2 に答える 2

2

最初の質問は単純です。一般に、要素へのポインターまたは値から反復子を取得する直接的な方法はありません。つまり、値から反復子を取得するには、通常、コンテナーを検索する必要があります。std::vector<T>連続している必要があるため、単純な計算を使用してポインターからイテレーターを取得できます (空でない必要がありますv)。

std::vector<T> v(...);
T* ptr = ...;
std::vector<T>::iterator it(v.begin() + (ptr - &v[0]));

関連する保証が複数の句に分散されているため、イテレータと値が安定しているかどうかを追跡することは完全に簡単ではありません。

  1. 23.2.1 [container.requirements.general] パラグラフ 11:

    別の方法で指定されていない限り (明示的に、または他の関数に関して関数を定義することによって)、コンテナー メンバー関数を呼び出したり、コンテナーをライブラリー関数への引数として渡したりしても、そのコンテナー内のオブジェクトの反復子を無効にしたり、その値を変更したりしてはなりません。 .

  2. 23.2.4 [associative.reqmts] 段落 9:

    insert メンバーと emplace メンバーは、イテレーターとコンテナーへの参照の有効性に影響を与えません。ererase メンバーは、イテレーターと消去された要素への参照のみを無効にします。

  3. 23.2.5 [unord.req] パラグラフ 9:

    ... 再ハッシュはイテレータを無効にし、要素間の順序を変更し、要素が表示されるバケットを変更しますが、要素へのポインタや参照を無効にしません。...

  4. 23.2.5 [unord.req] パラグラフ 14:

    insert メンバーと emplace メンバーは、コンテナー要素への参照の有効性に影響を与えませんが、コンテナーへのすべての反復子を無効にする可能性があります。...

  5. 23.2.5 [unord.req] パラグラフ 15:

    (N+n) < z * B の場合、insert メンバーと emplace メンバーは反復子の有効性に影響を与えません。ここで、N は挿入操作前のコンテナー内の要素の数、n は挿入された要素の数、B はコンテナのバケット数、z はコンテナの最大負荷係数です。

上記の節は、連想コンテナーのイテレーターの妥当性に関して重要な節でなければなりません。順序付けられていない連想コンテナのイテレータの有効性は、コンテナが再ハッシュされるかどうかに完全に依存します。再ハッシュを制御して、不意に発生するのを回避できるようです。

ただし、順序付けられていないコンテナーの全体的な考え方は、 を使用してオブジェクトを見つけるのが非常に効率的であるということですfind()。イテレータを要素に格納する必要は決してありません。それらを見つけることができるからです。もちろん、 astd::unordered_multimap<K, V>または aがある場合、std::unordered_multiset<V>どの同等の要素を見ているのかを知る必要があるかもしれません。

于 2013-08-25T12:16:54.903 に答える