jlanisdev
jlanisdev

Reputation: 65

std::map comparing pointers

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;
}

Upvotes: 2

Views: 2057

Answers (1)

Lily Ballard
Lily Ballard

Reputation: 185671

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.

Upvotes: 3

Related Questions