11

ノード ポインターの一部をハッシュすることで、特定のリンク リスト操作を高速化しようとしています。これは私が使用しているコードです:

unordered_set< typename list< int >::iterator > myhashset;

Visual Studio 2012 で、"エラー C2338: C++ 標準では、この型のハッシュが提供されていません" というメッセージが表示されます。これは、コンパイラが反復子をハッシュする方法を認識していないためです。したがって、次のようにリスト イテレータ用に独自のハッシュ関数を実装する必要があります。

struct X{int i,j,k;};

struct hash_X{
  size_t operator()(const X &x) const{
    return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
  }
};

(ウィキペディア参照)

イテレータのどのメンバーが一意性を保証するか (したがって、ハッシュしたいメンバー) を理解するのに苦労しています。もう 1 つの懸念は、それらのメンバーが非公開である可能性があることです。

頭に浮かぶ解決策の 1 つは、list::iterator を再実装することですが、これはハックのようで、維持するコードが増えます。

4

2 に答える 2

11

イテレータが参照する要素のアドレスを使用します。

struct list_iterator_hash {
    size_t operator()(const list<int>::iterator &i) const {
        return hash<int*>()(&*i);
    }
};

ただし、これは参照解除可能なイテレータに対してのみ機能し、end()orでは機能しませんlist<int>::iterator()。

于 2013-06-24T18:27:56.887 に答える