locked
Custom Hash & Comparer in unordered_map for reference classes

    Question

  • Hello,

    I'm using Win8 Consumer Preview and I want to build custom C++ component (e.g. WinMD).

    My problem is that I cannot override GetHashCode for my reference classes as well as Equals.

    The constructor of unordered_map accept hasher and comparer but the signature of both requires reference (e.g. &) but this is not possible with ^ types (or at least I did not managed to do it).

    Can someone show me how can I use custom hash function for managed C++ classes (e.g. public ref class MyType)?

    And if possible how can I override GetHashCode and Equals.

    Thanks,

    Hristo

    Monday, March 12, 2012 4:59 PM

Answers

  • Hi,

    I maintain the STL and collection.h.

    > 1. Should I define a function for Hash and Equals on unordered_map class?
    > (My guess was that there is probably such template for Platform::Object^ that calls GetHashCode and Equals)

    If you want to use X^ as the key type of an unordered associative container, you'll need to provide your own hashing and equality functors. The STL will not recognize X^ and definitely will not call GetHashCode() and Equals().

    > 2. Is it possible to override GetHashCode and Equals on custom ref classes (e.g. that inherit from Platform::Object);

    Someone else will have to answer this question.

    > 3. Is there class like Platform::Collections::Map which use std::unordered_map (instead of std::map)?

    Not in VC11. I may implement this in the future, if there is a compelling scenario with sufficient demand, but there are currently no plans for this.

    std::map is awesome. It is efficient, immune to pathological behavior (its operations are guaranteed O(log N), instead of worst case O(N)), and easy to use. It is much easier to provide a less-than functor than to provide hashing and equality functors - in particular, good hashes are tricky.

    > 4. How can I specify custom Hash function and custom comparer for C++ ref class to unordered_map and is this possible?

    If you're intent on using std::unordered_map, hashing functors can take their arguments by value. This is a bad idea if they're something like std::string, but for X^ it doesn't especially matter. So this works:

    C:\Temp>type meow.cpp
    #include <stddef.h>
    #include <algorithm>
    #include <functional>
    #include <iostream>
    #include <ostream>
    #include <unordered_map>
    #include <utility>
    #include <collection.h>
    using namespace std;
    namespace PC = Platform::Collections;
    namespace WFC = Windows::Foundation::Collections;

    struct Hash {
        // NOTE: Assumes iv != nullptr.
        size_t operator()(WFC::IVector<int>^ iv) const {
            size_t ret = 0;

            for (auto&& e : iv) {
                // TODO: This is a terrible way to mix hashes.
                ret += hash<int>()(e);
            }

            return ret;
        }
    };

    struct Equal {
        // NOTE: Assumes lhs != nullptr && rhs != nullptr.
        bool operator()(WFC::IVector<int>^ lhs, WFC::IVector<int>^ rhs) const {
            return lhs->Size == rhs->Size && equal(begin(lhs), end(lhs), begin(rhs));
        }
    };

    [Platform::STAThread] int main() {
      try {
        unordered_map<WFC::IVector<int>^, int, Hash, Equal> um;

        WFC::IVector<int>^ tens = ref new PC::Vector<int>;
        tens->Append(10);
        tens->Append(20);
        tens->Append(30);

        WFC::IVector<int>^ hundreds = ref new PC::Vector<int>;
        hundreds->Append(100);
        hundreds->Append(200);
        hundreds->Append(300);
        hundreds->Append(400);

        WFC::IVector<int>^ thousands = ref new PC::Vector<int>;
        thousands->Append(1000);
        thousands->Append(2000);
        thousands->Append(3000);
        thousands->Append(4000);
        thousands->Append(5000);

        WFC::IVector<int>^ meow = ref new PC::Vector<int>;
        meow->Append(10);
        meow->Append(20);
        meow->Append(30);
        meow->Append(-9999);
        meow->RemoveAtEnd();

        um[tens] = 60;
        um[hundreds] = 700;
        um[thousands] = 8000;
        um[meow] = 90;

        for (auto& p : um) {
            cout << "( ";

            for (auto&& e : p.first) {
                cout << e << " ";
            }

            cout << ") => " << p.second << endl;
        }

        cout << "DONE!" << endl;
      } catch (...) {
        cout << "UNCAUGHT EXCEPTION!" << endl;
      }
    }

    C:\Temp>cl /ZW /MDd /EHsc /nologo /W4 meow.cpp
    meow.cpp

    C:\Temp>meow
    ( 10 20 30 ) => 90
    ( 100 200 300 400 ) => 700
    ( 1000 2000 3000 4000 5000 ) => 8000
    DONE!

    (It is possible, though slightly tricky, to handle null hats - I simply haven't done so in this example. It is also possible to implement a better hash function.)

    Observe that I have implemented my hashing and equality predicates to care about the contents of my ref class (I have simply used WFC::IVector<int>^ because I am familiar with it; these techniques are applicable to any X^). In particular, um[meow] accesses the same value as um[tens] because meow's contents and tens's contents are identical, even though meow != tens (that simply compares the hats, and they are different objects).

    It is possible to take the hats by const reference. In the grammar, hats are like pointers, so you need to write the types "backwards", which you should be familiar with if you've ever worked with pointers-to-pointers. (Technically, it is "inside out", but that's only apparent when working with things like pointers-to-functions and references-to-arrays.) These lines will compile:

    size_t operator()(WFC::IVector<int>^ const& iv) const {
    bool operator()(WFC::IVector<int>^ const& lhs, WFC::IVector<int>^ const& rhs) const {

    I don't monitor this forum (someone else brought this to my attention), so if you have any further questions, feel free to E-mail me at stl@microsoft.com .

    Stephan T. Lavavej
    Visual C++ Libraries Developer

    Friday, March 16, 2012 2:33 AM

All replies

  • Hi Hristo,

    The WinRT C++ is not managed CLI/C++. It does not contain .NET host in WinRT project. Therefore, we cannot use .NET function directly in WinRT project.

    I suggest you to try the Collections namespace in WinRT instead of the collections in .NET
    http://msdn.microsoft.com/en-us/library/windows/apps/windows.foundation.collections

    You can try IMap(K,V)

    Best regards,
    Jesse


    Jesse Jiang [MSFT]
    MSDN Community Support | Feedback to us

    Tuesday, March 13, 2012 3:01 AM
  • Hi Jesse,

    I never mentioned .Net function in my post. I refer to managed C++ class for types declared as public ref class MyClass1.

    I'm using C++ unordered_map with ref class as Key and ref class as Value like this:

    std::unordered_map<Object^, Group^> groups;

    The problem comes when I try to override GetHashCode and Equals of my type (Group^).

    Here is a sample code:

    #pragma once
    
    namespace GetHashCode
    {
        public ref class WinRTComponent sealed
        {
        public:
            WinRTComponent();
    
            // Any of the following results in compile error:
    
            //virtual int GetHashCode() override;
            //int GetHashCode();
            //virtual int GetHashCode() override = Platform::Object::GetHashCode;
    
    
            //virtual bool Equals(Platform::Object^ other) override;
    
            // Compile without error:
            virtual bool Equals(WinRTComponent^ other) override;
        };
    }

    Now failing to override GetHashCode and Equals I tried to create custom Hash function like this:

    struct Group_Hash
    {
        size_t operator()(const Group^ &g) const
        {
            return std::hash<int>()(g->Hash);
        }
    };

    but this result in compile error: no instance of function "Grouping::Group::Hash::get" matches the argument list and object (the object has type qualifiers that prevent a match).

    So my questions are:

    1. Should I define a function for Hash and Equals on unordered_map class? (My guess was that there is probably such template for Platform::Object^ that calls GetHashCode and Equals)

    2. Is it possible to override GetHashCode and Equals on custom ref classes (e.g. that inherit from Platform::Object);

    3. Is there class like Platform::Collections::Map which use std::unordered_map (instead of std::map)?

    4. How can I specify custom Hash function and custom comparer for C++ ref class to unordered_map and is this possible?

    Thanks,

    Hristo

    Tuesday, March 13, 2012 8:10 AM
  • Hi,

    I maintain the STL and collection.h.

    > 1. Should I define a function for Hash and Equals on unordered_map class?
    > (My guess was that there is probably such template for Platform::Object^ that calls GetHashCode and Equals)

    If you want to use X^ as the key type of an unordered associative container, you'll need to provide your own hashing and equality functors. The STL will not recognize X^ and definitely will not call GetHashCode() and Equals().

    > 2. Is it possible to override GetHashCode and Equals on custom ref classes (e.g. that inherit from Platform::Object);

    Someone else will have to answer this question.

    > 3. Is there class like Platform::Collections::Map which use std::unordered_map (instead of std::map)?

    Not in VC11. I may implement this in the future, if there is a compelling scenario with sufficient demand, but there are currently no plans for this.

    std::map is awesome. It is efficient, immune to pathological behavior (its operations are guaranteed O(log N), instead of worst case O(N)), and easy to use. It is much easier to provide a less-than functor than to provide hashing and equality functors - in particular, good hashes are tricky.

    > 4. How can I specify custom Hash function and custom comparer for C++ ref class to unordered_map and is this possible?

    If you're intent on using std::unordered_map, hashing functors can take their arguments by value. This is a bad idea if they're something like std::string, but for X^ it doesn't especially matter. So this works:

    C:\Temp>type meow.cpp
    #include <stddef.h>
    #include <algorithm>
    #include <functional>
    #include <iostream>
    #include <ostream>
    #include <unordered_map>
    #include <utility>
    #include <collection.h>
    using namespace std;
    namespace PC = Platform::Collections;
    namespace WFC = Windows::Foundation::Collections;

    struct Hash {
        // NOTE: Assumes iv != nullptr.
        size_t operator()(WFC::IVector<int>^ iv) const {
            size_t ret = 0;

            for (auto&& e : iv) {
                // TODO: This is a terrible way to mix hashes.
                ret += hash<int>()(e);
            }

            return ret;
        }
    };

    struct Equal {
        // NOTE: Assumes lhs != nullptr && rhs != nullptr.
        bool operator()(WFC::IVector<int>^ lhs, WFC::IVector<int>^ rhs) const {
            return lhs->Size == rhs->Size && equal(begin(lhs), end(lhs), begin(rhs));
        }
    };

    [Platform::STAThread] int main() {
      try {
        unordered_map<WFC::IVector<int>^, int, Hash, Equal> um;

        WFC::IVector<int>^ tens = ref new PC::Vector<int>;
        tens->Append(10);
        tens->Append(20);
        tens->Append(30);

        WFC::IVector<int>^ hundreds = ref new PC::Vector<int>;
        hundreds->Append(100);
        hundreds->Append(200);
        hundreds->Append(300);
        hundreds->Append(400);

        WFC::IVector<int>^ thousands = ref new PC::Vector<int>;
        thousands->Append(1000);
        thousands->Append(2000);
        thousands->Append(3000);
        thousands->Append(4000);
        thousands->Append(5000);

        WFC::IVector<int>^ meow = ref new PC::Vector<int>;
        meow->Append(10);
        meow->Append(20);
        meow->Append(30);
        meow->Append(-9999);
        meow->RemoveAtEnd();

        um[tens] = 60;
        um[hundreds] = 700;
        um[thousands] = 8000;
        um[meow] = 90;

        for (auto& p : um) {
            cout << "( ";

            for (auto&& e : p.first) {
                cout << e << " ";
            }

            cout << ") => " << p.second << endl;
        }

        cout << "DONE!" << endl;
      } catch (...) {
        cout << "UNCAUGHT EXCEPTION!" << endl;
      }
    }

    C:\Temp>cl /ZW /MDd /EHsc /nologo /W4 meow.cpp
    meow.cpp

    C:\Temp>meow
    ( 10 20 30 ) => 90
    ( 100 200 300 400 ) => 700
    ( 1000 2000 3000 4000 5000 ) => 8000
    DONE!

    (It is possible, though slightly tricky, to handle null hats - I simply haven't done so in this example. It is also possible to implement a better hash function.)

    Observe that I have implemented my hashing and equality predicates to care about the contents of my ref class (I have simply used WFC::IVector<int>^ because I am familiar with it; these techniques are applicable to any X^). In particular, um[meow] accesses the same value as um[tens] because meow's contents and tens's contents are identical, even though meow != tens (that simply compares the hats, and they are different objects).

    It is possible to take the hats by const reference. In the grammar, hats are like pointers, so you need to write the types "backwards", which you should be familiar with if you've ever worked with pointers-to-pointers. (Technically, it is "inside out", but that's only apparent when working with things like pointers-to-functions and references-to-arrays.) These lines will compile:

    size_t operator()(WFC::IVector<int>^ const& iv) const {
    bool operator()(WFC::IVector<int>^ const& lhs, WFC::IVector<int>^ const& rhs) const {

    I don't monitor this forum (someone else brought this to my attention), so if you have any further questions, feel free to E-mail me at stl@microsoft.com .

    Stephan T. Lavavej
    Visual C++ Libraries Developer

    Friday, March 16, 2012 2:33 AM
  • I'm looking into question 2.

    I'll have an answer for you as soon as I get comment from the compiler team.

    -Steve

    Friday, March 16, 2012 9:43 PM
    Moderator
  • For GetHashCode, this is both a compiler issue and an Object Browser issue. The compiler error has been changed post-beta to be more descriptive of the actual problem. The actual problem is that GetHashCode is not virtual and cannot be overriden. The fact that the OB shows it as virtual, i've entered as a bug.

    -Steve

    Monday, March 19, 2012 8:15 PM
    Moderator