9

How can i hash (std::tr1::hash or boost::hash) a c++ pointer-to-member-function?

Example:

I have several bool (Class::*functionPointer)() (not static) that point to several diferent methods of the class Class and i need to hash those pointer-to-member-function.

How can i do that?

Also how can i compare (std::less) those member function pointers so i can store them in a std::set?

AllDayCpp
  • 253
  • 2
  • 8
  • 7
    There is not normally any reason to hash a pointer, as it points directly at the thing you want to access. Please provide some code that illustrates what you are asking about. –  Aug 25 '09 at 13:24
  • When would you say that one function pointer is 'less' than another? – Bojan Resnik Aug 25 '09 at 13:30
  • @bojan: If the only purpose of the comparison is to store them in a sorted list, any deterministic ordering will do. For example the binary value. – erikkallen Aug 25 '09 at 13:35
  • 2
    I have a class that has an member function pointer as an member variable. I need to store that class in a std::set and in a std::hash_set so it needs an hash and a std::less on that member function pointer. – AllDayCpp Aug 25 '09 at 13:35
  • 1
    Will you have instances of your class which are identical in every field except the member function pointer? If not, then you don't need to include it in the hash/comparison, which neatly avoids the problem. – Steve Jessop Aug 25 '09 at 14:40

3 Answers3

14

All C++ objects, including pointers to member functions, are represented in memory as an array of chars. So you could try:

bool (Class::*fn_ptr)() = &Class::whatever;
const char *ptrptr = static_cast<const char*>(static_cast<const void*>(&fn_ptr));

Now treat ptrptr as pointing to an array of (sizeof(bool (Class::*)())) bytes, and hash or compare those bytes. You can use unsigned char instead of char if you prefer.

This guarantees no false positives - in C++03, pointers to member functions are POD, which means among other things that they can be copied using memcpy. This implies that if have the same byte-for-byte values, then they are the same.

The problem is that the storage representation of member function pointers could include bits which do not participate in the value - so they will not necessarily be the same for different pointers to the same member function. Or the compiler might, for some obscure reason, have more than one way of pointing to the same function of the same class, which are not byte-wise equal. Either way you can get false negatives. You'll have to look into how member function pointers actually work on your implementation. It must implement operator== for member function pointers somehow, and if you can find out how then you can probably figure out an order and a hash function.

That's potentially hard: member function pointers are awkward, and the storage is likely to include different amounts of non-participating "slack space" according to what kind of function is pointed to (virtual, inherited). So you'll probably have to interact quite significantly with your compiler's implementation details. This article might help get you started: http://www.codeproject.com/KB/cpp/FastDelegate.aspx

A cleaner alternative might be to do a linear search through an array in order to "canonicalise" all your function pointers, then compare and hash based on the position of the "canonical" instance of that function pointer in your array. Depends what your performance requirements are. And even if there are requirements, does the class (and its derived classes) have so many functions that the linear search will take that long?

typedef bool (Class::*func)();
vector<func> canon;

size_t getIndexOf(func fn_ptr) {
    vector<func>::iterator it = find(canon.begin(), canon.end(), fn_ptr);
    if (it != canon.end()) return it - canon.begin();
    canon.push_back(func);
    return canon.size() - 1;
}
Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • Thanks the char* does the trick ! Only in my compiler i need a reinterpret_cast instead of static_cast. – AllDayCpp Aug 25 '09 at 14:57
  • 1
    Excellent treatment of some of the thornier issues, +1. It hadn't occurred to me that pmf1 == pmf2 does not necessarily imply bitwise identity. – j_random_hacker Aug 25 '09 at 14:58
  • A pointer to member function may contain padding, which would be ignored when comparing for equality, and may take on random values. Hashing any padding bytes will cause the hash function to fail. – James Kanze Oct 25 '12 at 10:18
  • @James: I discuss that, starting from "The problem is that the storage representation of member function pointers could include bits which do not participate in the value" – Steve Jessop Oct 25 '12 at 11:26
  • While the idea with the "canoicalised" index is certainly clever (thanks for that idea!), I'd like to add a WARNING: as far as I know, it is not possible to equality compare member pointers to virtual functions (e.g. functions in an interface / ABC). Since the same "offset" might actually resolve to different implementations, based on what actual instance you bind the member pointer do. Thus this approach breaks down in that case. – Ichthyo Jan 02 '15 at 09:42
  • @Steve your implementation (compiler) may be sloppy and allow such comparisons, but the standard is explicit. See §5.10 : "If either is a pointer to a virtual member function, the result is unspecified" – Ichthyo Jan 04 '15 at 19:58
  • see [C++14 draft](http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3797.pdf) Page 120f (that is at bottom of Page 134 in the linked PDF) – Ichthyo Jan 04 '15 at 20:04
  • Yeah, @Ichthyo is correct. Actually, even reading the bytes CAN have false positives if virtual functions are involved: you might get bit-to-bit identical member pointers for a virtual member function both in a base class and a class derived from it. I suggest also including type_index of pointer type in hash, seems to uniquely identify a member function as it bounds the value to a specific class (no false positives at least!). – hedayat Jan 10 '22 at 22:51
2

I could not cast the pointer (in Microsoft compiler 2010)as described in previous answer but this works for me:

static string fmptostr(int atype::*opt)
  {
      char buf[sizeof(opt)];
      memcpy(&buf,&opt,sizeof(opt));
      return string(buf,sizeof(opt));
  }

About bitwise identity of the pointer, it can be bitwise so it seems if appropriate compiler switches are used. At least this is true for Microsoft compiler E.g using #pragma pointers_to_members and a switch.../vmg

Aftershock
  • 5,205
  • 4
  • 51
  • 64
0

If your member function pointer is unique, which is true in most of cases for callback-based subscriptions, then you can use the tick with type_index, which uniqueness is guaranteed by uniqueness of type (i.e. Class::Method) in your program, and it is suitable to be stored in unordered_map, i.e.

struct MyEvent {

    using fn_t = std::function<void(MyEvent &)>;
    using map_t = std::unordered_map<std::type_index, fn_t>;


    template <typename Handler>
    void subscribe(Object& obj, Handler&& handler) {
        fn_t fn = [&, handler = std::move(handler)](MyEvent& event) {
            (obj.*handler)(event);
        }
        std::type_index index = typeid(Handler);
        subscribers.emplace(std::move(index), std::move(fn));
    }

    void fire() {
        for(auto& pair: subscribers) {
            auto& fn = pair.second;
            fn(*this);
        }
    }

    map_t subscribers;
}

And the subscription and fire event example:

MyEvent event;
MyObject obj = ...;
event.subscribe(obj, &MyObject::on_event );
...
event.fire();

So, example above gives you class/method uniqueness, and if you need object/method uniqueness, then you should have an struct, which provides combined hash, assuming that there is std::hash<MyObject> and there is already std::hash<std::type_index> for a member function pointer.

Ivan Baidakou
  • 713
  • 9
  • 14