1

unordered_map複数の のをstructキーとして使用したいですstd::set< std::string >。

カスタム ハッシュ関数が必要であり、文字列をstd::hash適用できることがわかりました。ただし、unordered_map のこれらのセットのハッシュ関数の目的を満たすために何を返す必要があるかを判断できません。

カスタム ハッシュ関数はどのように返す必要がありますか?

4

2 に答える 2

1

の要件std::hashは次のとおりです: ( http://en.cppreference.com/w/cpp/utility/hash )

ハッシュ テンプレートは、ハッシュ関数を実装する関数オブジェクトを定義します。この関数オブジェクトのインスタンスは Hash を満たします。特に、次のようにoperator()を定義します。

  1. type の 1 つのパラメーターを受け入れますKey。
  2. size_tパラメータのハッシュ値を表す型の値を返します。
  3. 呼び出されたときに例外をスローしません。
  4. 2 つのパラメーターk1とk2が等しい場合、std::hash<Key>()(k1) == std::hash<Key>()(k2).
  5. 等しくない2 つの異なるパラメーターk1の場合、確率は非常に小さくなり、 に近づきます。k2std::hash<Key>()(k1) == std::hash<Key>()(k2)1.0 / std::numeric_limits<size_t>::max()

ハッシュ テンプレートはCopyConstructibleとDestructibleの両方です。

したがって、基本的に必要なのはstd::size_t、すべてのオブジェクトに対して一意でmyStructあり、同等と見なされるオブジェクトに対して同じ値を返す関数です。

編集: 以下は、ハッシュを生成するための最も堅牢な方法ではないかもしれませんが、それを行う方法の基本的な例として役立ちます。

これを行う 1 つの方法は、セパレーター シーケンスstd::hash<std::string>を使用して各std::setメンバーのすべての文字列を連結し、その後、結果のマージされたすべての文字列を 1 つに連結し、標準のハッシュ関数を使用してハッシュ値を返すことにより、標準の特殊化を使用することです。

myStructマージされた「スーパー」文字列は、メンバーが異なる場合はオブジェクトごとに一意になり、順序付けられたコンテナーのようにstd::setメンバーが異なる場合は同じになります。std::set

struct myStruct {
    std::set<std::string> s1;
    std::set<std::string> s2;
};

std::string mergeAllStrings(const myStruct& ms) {
    static const std::string SEPARATOR = "#¤%&"; // Some uncommon sequence.
    std::string super;
    for (const auto& s : ms.s1) {
        super += s + SEPARATOR; // Append separator.
    }
    for (const auto& s : ms.s2) {
        super += s + SEPARATOR; // Append separator.
    }
    return super;
}

int main() {
    myStruct ms1{{"apple", "pear", "orange"}, {"red", "green", "blue"}};
    myStruct ms2{{"pear", "apple", "orange"}, {"red", "green", "blue"}};
    myStruct ms3{{"apple", "banana", "orange"}, {"red", "green", "blue"}};

    std::cout << std::hash<std::string>()(mergeAllStrings(ms1)) << std::endl;
    std::cout << std::hash<std::string>()(mergeAllStrings(ms2)) << std::endl;
    std::cout << std::hash<std::string>()(mergeAllStrings(ms3)) << std::endl;
}

出力：

2681724430859750844 // Same
2681724430859750844 // Same
2942368903851914580 // Different

たとえば、次のようにハッシュ関数を作成できるようになりました。

struct MyHash {
    std::size_t operator()(const myStruct& ms) const {
        return std::hash<std::string>()(mergeAllStrings(ms));
    }
};

次のように使用しますstd::unordered_map。

std::unordered_map<myStruct, myValue, MyHash> m;

equal_toカスタムファンクターも提供する必要があることに注意してください。

于 2014-07-17T22:55:12.127 に答える