std::map comparing pointers

Question

How would I implement the comparison operator in the example below so that ObjectPair( &a, &b ) is equal to ObjectPair( &b, &a )? In addition, how would I implement this using stdext::hash_map instead of std::map?

struct ObjectPair { public: ObjectPair( Object* objA, Object* objB ) { A = objA; B = objB; } bool operator<( const ObjectPair& pair ) const { // ??? } Object* A; Object* B; }; int main() { std::map< ObjectPair, int > pairMap; Object a; Object b; pairMap[ ObjectPair(&a, &b) ] = 1; pairMap[ ObjectPair(&b, &a) ]++; /// should output 2 std::cout<< pairMap[ ObjectPair( &a, &b ) ] << std::endl; return 0; }

@Jake223: No you shouldn't. std::map::operator[] returns a reference to the value. If it didn't, then this code wouldn't even compile. — Lily Ballard
– Lily Ballard, Commented Jan 22, 2013 at 0:26

Lily Ballard · Accepted Answer · 2013-01-22 01:37:42Z

Your fundamental problem is you need to implement operator< such that it doesn't distinguish between a and b, and yet returns consistent results for all nonequal objects.

The simplest thing to do is probably to sort the pointers and then compare them. Something like

bool operator<(const ObjectPair& pair) const { // Technically < is unspecified on most object pointers // but std::less<T> is guaranteed to have a total ordering std::less<Object*> comp; Object *ourlow = std::min(a, b, comp); Object *ourhigh = std::max(a, b, comp); Object *theirlow = std::min(pair->a, pair->b, comp); Object *theirhigh = std::max(pair->a, pair->b, comp); if (comp(ourlow, theirlow)) return true; if (comp(theirlow, ourlow)) return false; return comp(ourhigh, theirhigh); } return false; }

This is assuming, of course, that Object is not sortable, and therefore we only care about the pointer value being the same. If Object itself has an ordering, then you should probably call Object::operator<() instead of just using < on the pointer, i.e. if (*ourlow < *theirlow)

In order to make this work in a std::unordered_map (which is a C++11 thing that I'm assuming stdext::hash_map is the equivalent of) then you'll need to implement operator== as well as specialize std::hash<> for your object. For your specialization you may just want to hash the two pointers and combine the values (using something like bitwise-xor).

The gist of the really long comment thread attached to this question has to do with what the C++ standard says about comparisons on pointers. Namely, that comparing two object pointers of the same type that are not members of the same object/array invokes unspecified behavior. In general, this isn't going to matter on any architecture with a single unified memory system (i.e. any architecture you're likely to use), but it's still nice to be standards-compliant. To that end, the comparisons have all been changed to use std::less<Object*>, because the C++ standard guarantees that std::less<T> has a total ordering.

@KevinBallard: Comparing pointers with < is undefined behavior, use std::less<T*> to get well-defined behavior. (Also, isn't this answer overly complicated?) Why not return (a==rhs.a&&b==rhs.b) || (a==rhs.b&&b==rhs.a);
@KevinBallard It's <s>undefined</s> unspecified if the pointers don't point to the same allocation block of memory. The "magic" which std::less does is a reinterpret_cast to std::intptr_t. Anyway, +1 from me.
@KevinBallard: 20.8.5(14) "For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not."
@KevinBallard: std::less gets to use standard-library-writer magic, which includes going ahead and knowing undefined behavior's behavior. That is, even though we mere peasants cannot make such assumptions, if the compiler and library writers want to they can (i.e., ensure the platforms they run on do the Right Thing).
@KevinBallard: Note you can still use std::max (and kin) and pass in comp as a third parameter. Shame that two-parameter std::max uses built-in < instead of delegating to the three-parameter overload with std::less<T>. You're right that in practice OP will never notice.

Collectives™ on Stack Overflow

std::map comparing pointers

1 Answer 1

24 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

24 Comments

Linked

Related