2

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;
}
jlanisdev
  • 65
  • 6
  • @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 Jan 22 '13 at 00:26

1 Answers1

3

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.

Lily Ballard
  • 182,031
  • 33
  • 381
  • 347
  • @jlanisdev: The same way `<` does, i.e. by comparing their integral values. – Lily Ballard Jan 22 '13 at 00:32
  • @jlanisdev: You could of course use `(a < b ? a : b)` if you want, but I find `min()` and `max()` to be clearer. – Lily Ballard Jan 22 '13 at 00:33
  • 1
    @KevinBallard: Comparing pointers with `<` is undefined behavior, use `std::less` 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);` – Mooing Duck Jan 22 '13 at 00:38
  • @MooingDuck: Funny, libc++ implements `std::less` using `<`, and doesn't seem to have any specializations at all (certainly not one for `T*`). – Lily Ballard Jan 22 '13 at 00:40
  • @MooingDuck: And no, this answer isn't overly complicated. I'm implementing `operator<()`, not `operator==()`. Your suggestion would, of course, be perfectly suitable for implementing `operator=()`, but ordering is harder than equality. – Lily Ballard Jan 22 '13 at 00:40
  • @KevinBallard: oh yeah, I don't know why I thought that would work. Point is using `<` on unrelated pointers is "unspecified". – Mooing Duck Jan 22 '13 at 00:41
  • @MooingDuck: Interesting, I had not run across that before. And yeah, it's unspecified, not undefined. – Lily Ballard Jan 22 '13 at 00:43
  • 1
    @jlanisdev: It's unspecified, which means it's implementation-defined, which means it's going to have consistent behavior, even if it's not necessarily what you'd expect. – Lily Ballard Jan 22 '13 at 00:44
  • @MooingDuck, `<` on unrelated pointers of the same type is unspecified, not undefined. However, I was just checking the standard w.r.t. a different question, and I don't see any constraint that says that if `a` and `b` are pointers of the same type whose targets are not part of the same object or array, then it must be the case that either `a < b` or `b < a`. That would be necessary for this stuff to work. – rici Jan 22 '13 at 00:44
  • 3
    @KevinBallard It's undefined 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. – Potatoswatter Jan 22 '13 at 00:44
  • @Potatoswatter: I'm actually looking in the standard right now to see if it says anything about converting a pointer to an integer. Interestingly, I'm not seeing that `reinterpret_cast<>` in libc++'s `std::less<>`. – Lily Ballard Jan 22 '13 at 00:45
  • 1
    @KevinBallard Probably because it's such an insignificant detail. It can only make a difference in non-uniform memory architectures, such as segmented 8086. – Potatoswatter Jan 22 '13 at 00:47
  • 2
    @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." – rici Jan 22 '13 at 00:48
  • 3
    @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). – GManNickG Jan 22 '13 at 00:48
  • @Potatoswatter: Well, magic is of course unspecified. It may cast to `intptr_t` (which *itself* relies on magic and may not necessarily do what you want) or just go ahead and use built-in `<` knowing how the compiler writers did it. – GManNickG Jan 22 '13 at 00:50
  • @kevinBallard: However, I think that `std::min` is defined in terms of `<`, not in terms of `std::less`. – rici Jan 22 '13 at 00:54
  • If each instance of Object had a unique identifier as part of the class, then I could compare that instead, which would probably be wiser and make all of this debate irrelevant. =) – jlanisdev Jan 22 '13 at 00:57
  • rici, GManNickG, Potatoswatter, you have some good points. I'm going to update my answer to use `std::less`, even though it's probably not going to make a difference in any architecture the OP is likely to use. – Lily Ballard Jan 22 '13 at 00:58
  • 1
    @KevinBallard: Well, you changed most, but left the last two. I'm confused as to why you did that. – Mooing Duck Jan 22 '13 at 01:02
  • 2
    @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`. You're right that in practice OP will never notice. – GManNickG Jan 22 '13 at 01:06
  • @GManNickG: So you can. I never noticed that. I'm going to edit my post again to use that, since I think it's nicer. – Lily Ballard Jan 22 '13 at 01:08
  • @KevinBallard: but you still need to fix `ourlow < theirlow` and `ourhigh < theirhigh` – rici Jan 22 '13 at 01:10
  • This discussion is growing too long and hard to follow. However it contains good information which should be integrated into the the question or an answer. Please do that and if needed, continue the discussion in the chat! – markus Jan 22 '13 at 01:15
  • @KevinBallard: Yeah, avoids repeating those values which is nice. I agree with markus, by the way, so I hope you don't mind the last edit I threw in to address Mooing's last comment. That'll be all from me! – GManNickG Jan 22 '13 at 01:19