stl priority_queue

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

stl priority_queue

Postby the mishanator » Sun Mar 27, 2011 2:16 am UTC

i have something like this:

Code: Select all

#include <iostream>
#include <queue>

class object {
public:
  object(int thing1): thing1(thing1) {}
  int get() {return thing1;}
  friend bool operator<(object &first, object &second) {
    return first.thing1 < second.thing1;
  }
  friend bool operator>(object &first, object &second) {
    return first.thing1 > second.thing1;
  }
private:
  int thing1;
};

int main(void) {
  std::priority_queue<object *> test_queue;
  test_queue.push(new object(1));
  test_queue.push(new object(1));
  test_queue.push(new object(2));
  test_queue.push(new object(1));
  test_queue.push(new object(1));
  std::cout << test_queue.top()->get() << std::endl;
  while (!test_queue.empty()) {
    delete test_queue.top();
    test_queue.pop();
  }
  return 0;
}


my understanding is that i should see a "2" in the console when i run this program. maybe i'm not too clear on what "object compare" is that is being used by std::priority_queue though.
how do i fix this?

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: stl priority_queue

Postby kmatzen » Sun Mar 27, 2011 5:21 am UTC

Isn't this going to compare the pointers rather than the objects they point to? You could provide a comparison class as the third template parameter of std::priority_queue which has a bool comp::operator()(object *, object *) that dereferences the two arguments and then returns the result of comparison.

In either case, bool operator>(object &, object &) is redundant since these ordered containers are only defined on types with strict weak orderings and you can derive all comparisons using less than and logical conjunction, disjunction, and negation.

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: stl priority_queue

Postby the mishanator » Sun Mar 27, 2011 5:30 am UTC

In either case, bool operator>(object &, object &) is redundant since these ordered containers are only defined on types with strict weak orderings and you can derive all comparisons using less than and logical conjunction, disjunction, and negation.


I'm sorry, I don't understand. (I'm a newbie programmer)

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: stl priority_queue

Postby kmatzen » Sun Mar 27, 2011 5:39 am UTC

the mishanator wrote:
In either case, bool operator>(object &, object &) is redundant since these ordered containers are only defined on types with strict weak orderings and you can derive all comparisons using less than and logical conjunction, disjunction, and negation.


I'm sorry, I don't understand. (I'm a newbie programmer)


I just meant that you only need bool operator<(object &, object &) and not bool operator>(object &, object &).

a < b
a > b is equivalent to b < a
a == b is equivalent to !(a < b) && !(b < a)
a != b is equivalent to (a < b) || (b < a)
a <= b is equivalent to !(b < a)
a >= b is equivalent to !(a < b)

But more importantly, I wanted to make sure that my first point made sense regarding the comparison class. Here's a reference with a section that talks about template parameters for std::priority_queue. http://cplusplus.com/reference/stl/priority_queue/

the mishanator
Posts: 209
Joined: Mon May 31, 2010 6:49 pm UTC

Re: stl priority_queue

Postby the mishanator » Sun Mar 27, 2011 5:43 am UTC

=) thank you so much, I got it working.


Return to “Coding”

Who is online

Users browsing this forum: Google [Bot] and 5 guests