Set of pointer to member

Question

This doesn't work:

struct A {
    int x1;
    int x2;
};

int main() {
    int A::*p1 = &A::x1;

    set<int A::*> s;
    s.insert( p1 );  // compile error:  No operator<
    unordered_set<int A::*> us;
    us.insert( p1 ); // compile error:  No hash function 
}

I have to provide either a comparison function (for set) or a hash function (for unordered_set). The only way I figured out so far would involve checking the raw bytes underlying the member pointers:

struct XLess {
    bool operator()( int A::* a, int A::*b ){
        return memcmp( &a, &b, sizeof(a) ) < 0;
    }
};

set<int A::*, XLess> s; // now appears to work

Is this a reliable way to create a set? It depends on identical pointers being represented by identical bytes. Is there a better solution to this?

Assuming its member pointers you want, is `set` important, such that `vector` wouldn't cut it? — sp2danny, May 15 '14 at 10:50
@sp2danny Right, that would be one possible work-around. I will consider that if nothing better comes up. Thanks. — pentadecagon, May 15 '14 at 10:59

score 1 · Answer 1 · edited May 23 '17 at 12:13

You could expand std::less and std::hash operators, BTW this is perfectly allowed. Also inspired from this SO answer, I've created size_t getIndexOf(int A::* x) for the hashing and compare, See below:

#include <set>
#include <unordered_set>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct A {
  int x1;
  int x2;
};

typedef int (A::*x1);
vector<x1> canon;
size_t getIndexOf(int A::* x) {
  auto it = find(canon.begin(), canon.end(), x);
  if (it != canon.end()) return it - canon.begin();
  canon.push_back(x);
  return canon.size() - 1;
}

namespace std {
  template<> struct less<int A::*> {
    bool operator()(int A::* a, int A::*b){ return getIndexOf(a) < getIndexOf(b); }
  };

  template <> struct hash<int A::*>
  {
    size_t operator()(int A::* x) const
    {
      return  getIndexOf(x);
    }
  };
}

int main() {
  int A::*p1 = &A::x1;
  int A::*p2 = &A::x2;
  set<int A::*> s;
  s.insert(p1);
  s.insert(p2);

  for (auto e : s) std::cout << getIndexOf(e) << std::endl;

  unordered_set<int A::*> us;
  us.insert(p1);
  us.insert(p2);

  for (auto e : us) std::cout << getIndexOf(e) << std::endl;

  return 0;
}

This looks good. It's inefficient, but this was to be expected and I don't care, and it's not thread-safe, which can be fixed easily. Thanks. — pentadecagon, May 15 '14 at 12:02
This solution makes it redundant to use an associative container at all. You might as well just a vector of member pointers and perform a linear search in the first place. — François Andrieux, Jan 06 '22 at 15:45

score 1 · Answer 2 · answered May 15 '14 at 11:21

Formally, it isn't guaranteed. In practice, pointers to member data will most likely be just a simple integral type, and you should have no problems. For pointers to member functions, on the other hand: these are normally more or less complicated structures, and often will contain padding, whose content is undefined, so your technique wouldn't work.

I note too that in the first snippet, you have used std::unordered_set, not std::set. std::unordered_set doesn't use an ordering function, but rather an equivalence function (and == is defined for pointers to members) and a hash function. Of course, implementing the hash function has the same problems as implementing the ordering.

Having said this: why on earth would you want such a set. A pointer to member (e.g. int A::*) can only point to members of the given type (not to members of an array of the given type), and you can't possible write classes with thousands of members. The simplest solution might just be to use an std::vector<int A::*>, and linear search (std::find) to determine membership. It's likely to be faster than any of the std::set, unless you do have thousands of members.

Deduplicator · Answer 3 · 2014-05-15T11:02:48.113

0

Your XLess comparator relies on one assumption the standard does not guarantee:
That all bits of a member-pointer are significant and two member-pointers with a different bit-pattern point to different members.
Still, it should work on just about any implementation with a flat memory model, as long as they don't point to virtual functions: There are two ways to point to those: Use the vtable, or include the function address.

Also, AFAICT there is no better way because for that you would need to understand the member-pointer innards or have a comparison provided by the implementation.

edited May 15 '14 at 11:02

answered May 15 '14 at 10:56

Deduplicator

44,692
7
66
118

As long as the pointers aren't to member functions. A pointer to member function has to assume that the function it points to may or may not be virtual; one frequent way of doing this is to use the equivalent of `struct { void* ptrNonVirtual; int indexInVTable; }` (with a null pointer to indicate virtual), if pointers are larger than `int`, this may result in padding. – James Kanze May 15 '14 at 11:26

Set of pointer to member

3 Answers3

Linked