Operator overloading on priority_queue of object pointers

Question

class MyInteger
{
public:
    MyInteger() { }
    MyInteger(int val) { value = val }

    int value;

    bool operator<(const MyInteger* target) const
    {
        return value < target->value;
    }

Above is an example MyInteger class with the < operator overloaded. I am using a priority_queue of MyInteger*but it doesn't seem to recognize the overloaded operator, which results in the elements never being ordered.

std::priority_queue<MyInteger*> myInts;

MyInteger integer1 = MyInteger(1);
MyInteger integer5 = MyInteger(5);
MyInteger integer3 = MyInteger(3);

myInts.push(&integer1);
myInts.push(&integer5);
myInts.push(&integer3);

// result is same order they went in

Is it possible to use operator overloading for object pointers? Does it mean I will have to create my own functor to be used instead?

You can't overload operators for pointers, since all pointers are considered builtin types. — StoryTeller - Unslander Monica, Nov 24 '16 at 21:15
And the operator you defined takes `MyInteger` object as the left-hand parameter, not `MyInteger*`, BTW. — Yehezkel B., Nov 24 '16 at 21:18
Why not creating a `std::priority_queue` instead of `std::priority_queue`? — jpo38, Nov 24 '16 at 21:21
@jpo38, the object may need to live in a particular data structure. The priority_queue is then just used to get a sorted view of them, and non-owning pointers will be the way to go. — StoryTeller - Unslander Monica, Nov 24 '16 at 21:23
sookie, what problem are you actually trying to solve? Why do you think you need a priority queue of pointers? — StoryTeller - Unslander Monica, Nov 24 '16 at 21:25
@Story Teller I'm doing an implementation of A*. I've got a `TileMap` which stores the tile array and some basic interface functionality. I then have a `PathGenerator` which uses a `priority_queue` for the 'open list' to sort its elements based on movement cost. — sookie, Nov 25 '16 at 10:54

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

As mentioned by Olaf Dietsche, as you store pointers, the objet adresses are used for sorting, so in most case, order in the container will be equal to order of creation.

You'd better store objects in the container. Then it's comparison operator will be used for ordering:

class MyInteger
{
public:
    MyInteger() { }
    MyInteger(int val) { value = val }
    MyInteger( const MyInteger& val ) : value( val.value ) {}

    int value;

    bool operator<(const MyInteger& target) const
    {
        return value < target.value;
    }

};

...

std::priority_queue<MyInteger> myInts;

MyInteger integer1 = MyInteger(1);
MyInteger integer5 = MyInteger(5);
MyInteger integer3 = MyInteger(3);

myInts.push(integer1);
myInts.push(integer5);
myInts.push(integer3);

Then objects will be ordered correctly (using operator<).

It is even safer in case integer1, integer2 or integer3 gets destroyed before myInts (as this one stores copies).

If you really need to save pointers, then you 'ill have to pass a custom comparator to the container. See declaring a priority_queue in c++ with a custom comparator.

This should work:

class CompareMyIntegerPtr
{
public:
    bool operator() (MyInteger* left, MyInteger* right)
    {
        return left->value < right->value;
    }
};

...

std::priority_queue<MyInteger*, std::vector<MyInteger*>, CompareMyIntegerPtr> myInts;

score 0 · Answer 2 · answered Nov 24 '16 at 21:19

The order has nothing to do with insertion order, but with the addresses in memory.

This is because the comparison operator is applied to the addresses of the elements, e.g.

&integer1 < &integer5 < &integer3

The comparison operator of MyInteger is not considered here.

Operator overloading on priority_queue of object pointers

2 Answers2