7

定義されていない C++03 でポインターを移植可能にハッシュすることは可能ですか?std::hash

ポインターを含むハッシュ可能オブジェクトが C++ で不可能であることは非常に奇妙に思えますが、それらを作成する方法は思いつきません。

私が考えることができる最も近い方法は実行していますがreinterpret_cast<uintptr_t>(ptr)、uintptr_tC++ 03で定義する必要はありません.値が定義されていても合法的に操作できるかどうかはわかりません...これは可能ですか?

4

2 に答える 2

10

いいえ、一般的に。実際、一般的に C++11 では .NET なしでは不可能std::hashです。

その理由は、値と値の表現の違いにあります。

値とその表現の違いを示すために使用される非常に一般的な例を思い出すかもしれません:ヌル ポインター値。多くの人が、この値の表現はすべてビット 0 であると誤って想定しています。これはいかなる方法でも保証されません。その値によってのみ動作が保証されます。

別の例として、次のことを考慮してください。

int i;
int* x = &i;
int* y = &i;

x == y;  // this is true; the two pointer values are equal

xただし、その下では、との値の表現y が異なる場合があります。

コンパイラをプレイしましょう。ポインターの値表現を実装します。(架空のアーキテクチャ上の理由から) ポインターが少なくとも 2 バイトである必要があるとしますが、値には 1 つしか使用されません。

先にジャンプして、次のようなものになる可能性があると言います。

struct __pointer_impl
{
    std::uint8_t byte1; // contains the address we're holding
    std::uint8_t byte2; // needed for architecture reasons, unused
    // (assume no padding; we are the compiler, after all)
};

さて、これが値の表現です。値のセマンティクスを実装しましょう。まず、平等:

bool operator==(const __pointer_impl& first, const __pointer_impl& second)
{
    return first.byte1 == second.byte1;
}

ポインターの値は実際には最初のバイトにしか含まれていないため (その表現には 2 バイトありますが)、比較する必要があるのはそれだけです。2 番目のバイトは、たとえ異なっていても関係ありません。

もちろん、address-of 演算子の実装が必要です。

__pointer_impl address_of(int& i)
{
    __pointer_impl result;

    result.byte1 = /* hypothetical architecture magic */;

    return result;
}

この特定の実装オーバーロードは、指定された のポインター値表現を取得しますint。2 番目のバイトは初期化されていないことに注意してください。それは問題ありません: valueにとっては重要ではありません。

ポイントを家に持ち帰るために必要なのは、これだけです。残りの実装が完了したふりをします。:)

それでは、最初の例である「コンパイラ化」をもう一度考えてみましょう。

int i;

/* int* x = &i; */
__pointer_impl x = __address_of(i);

/* int* y = &i; */
__pointer_impl y = __address_of(i);

x == y;  // this is true; the two pointer values are equal

架空のアーキテクチャの小さな例では、これはポインター値の標準で必要な保証を十分に提供します。ただし、 がx == y意味することは決して保証されないことに注意してくださいmemcmp(&x, &y, sizeof(__pointer_impl)) == 0。そうするための値の表現に関する要件はありません。

ここで、あなたの質問を考えてみましょう: ポインターをどのようにハッシュしますか? つまり、以下を実装したいと考えています。

template <typename T>
struct myhash;

template <typename T>
struct myhash<T*> :
    std::unary_function<T*, std::size_t>
{
    std::size_t operator()(T* const ptr) const
    {
        return /* ??? */;
    }
};

最も重要な要件は、 if x == y、 then myhash()(x) == myhash()(y). また、整数をハッシュする方法も既に知っています。私たちは何ができる？

私たちができる唯一のことは、どうにかしてポインターを整数に変換することです。C++11 では が得られるstd::uintptr_tので、これを実行できますよね?

return myhash<std::uintptr_t>()(reinterpret_cast<std::uintptr_t>(ptr));

意外かもしれませんが、これは正しくありません。理由を理解するために、それを実装していることをもう一度想像してください。

// okay because we assumed no padding:
typedef std::uint16_t __uintptr_t; // will be used for std::uintptr_t implementation

__uintptr_t __to_integer(const __pointer_impl& ptr)
{
    __uintptr_t result;
    std::memcpy(&result, &ptr, sizeof(__uintptr_t));

    return result;
}

__pointer_impl __from_integer(const __uintptr_t& ptrint)
{
    __pointer_impl result;
    std::memcpy(&result, &ptrint, sizeof(__pointer_impl));

    return result;
}

したがって、reinterpret_cast整数へのポインターの場合は を使用__to_integerし、戻って を使用します__from_integer。結果の整数は、ポインターの値表現のビットに応じた値を持つことに注意してください。つまり、2 つの等しいポインター値が異なる整数表現になる可能性があります...これは許可されています!

reinterpret_castの結果は完全に実装定義であるため、これが許可されます。反対の結果reinterpret_castが同じ結果を返すことが保証されているだけです。

したがって、最初の問題があります。この実装では、ポインター値が等しい場合、ハッシュが異なる結果になる可能性があります。

このアイデアはアウトです。おそらく、表現自体に到達して、バイトを一緒にハッシュすることができます。しかし、これは明らかに同じ問題で終わります。これは、あなたの質問に対するコメントが暗示しているものです。これらの厄介な未使用の表現ビットは常に邪魔になり、それらがどこにあるかを把握する方法がないため、無視できます。

立ち往生しています！それは不可能です。一般に。

実際には、特定の実装用にコンパイルします。これらの操作の結果は実装定義であるため、適切に使用するように注意すれば信頼できます。これはMats Petersson が言っていることです: 実装の保証を見つければ大丈夫です。

実際、使用するほとんどのコンシューマ プラットフォームは、このstd::uintptr_t試みを問題なく処理します。システムで使用できない場合、または別のアプローチが必要な場合は、ポインター内の個々のバイトのハッシュを組み合わせるだけです。これが機能するために必要なのは、未使用の表現ビットが常に同じ値を取ることだけです。実際、これは MSVC2012 が使用するアプローチです!

私たちの仮説的なポインタの実装が常にbyte2定数に初期化されていれば、そこでも機能します。しかし、実装がそうする必要はまったくありません。

これでいくつかのことが明確になることを願っています。

于 2013-01-05T08:02:56.770 に答える
5

あなたの質問への答えは、「どのようにポータブル」にしたいかによって異なります。多くのアーキテクチャには uintptr_t がありますが、DSP、Linux、Windows、AIX、古い Cray マシン、IBM 390 シリーズのマシンなどでコンパイルできるものが必要な場合は、構成オプションを定義する必要がある場合があります。そのアーキテクチャに存在しない場合は、独自の「uintptr_t」。

整数型へのポインターのキャストは問題ありません。投げ返してしまったら大変なことになるかもしれません。もちろん、多数のポインターがあり、32 ビット整数を使用して 64 ビット マシンにかなり大きなメモリ セクションを割り当てると、多数の衝突が発生する可能性があります。64 ビットの Windows には、32 ビットと同様の「long」がまだあることに注意してください。

于 2013-01-05T01:53:13.753 に答える