asked on

priority_queue STL

I have the fallowing code:

#include "stdafx.h"
#include <map>
#include <list>
#include <queue>
#include <iterator>

struct M
{
      M(int g1,int c11,int c21,int p1, int q1)
      {
            g=g1;
            c1=c11;
            c2=c21;
            p=p1;
            q=q1;
      }
      int g; // funkcijata za sporedba
      int c1;//prvata cost funkcija bazirana na jazli
      int c2;//vtorata cost funkijca bazirana na vrski
      int p; //p,q poslednata torka na jazli koi se vneseni
      int q;
};

bool operator< (const M& M1, const M &M2)
{
      return M1.g > M2.g;
}
//Overload the > operator.
bool operator> (const M& M1, const M &M2)
{
      return M1.g < M2.g;
}
bool operator - (M& M1, M &M2)
{
      return M1.g - M2.g;
}

typedef priority_queue <M,list<M>,greater<list<M>::value_type>> match;

theMatch.push(M(0,0,0,1,1));

after compiling I have error:

Error      5      error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::list<_Ty>::_Iterator<_Secure_validation>'      c:\program files\microsoft visual studio 8\vc\include\algorithm      2042

and

Error      6      error C2676: binary '-' : 'std::list<_Ty>::_Iterator<_Secure_validation>' does not define this operator or a conversion to a type acceptable to the predefined operator      c:\program files\microsoft visual studio 8\vc\include\algorithm      2042

Can anyone shred light on why do I have it? I checked couple of sites and it seems to me the code is fine
I am using Visual studio 2005, and the project is win32 exe with mfc support

ASKER CERTIFIED SOLUTION

jkr

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

jkr

Actually, 'list' also works if you define the operator correctly - that is instead of

bool operator - (M& M1, M &M2)
{
return M1.g - M2.g;
}

use

int operator - (const M& M1, const M &M2)
{
return M1.g - M2.g;
}

Then it compiles ;o)

Infinity08

1) You should add :

using namespace std;

just after the includes, or alternatively, you have to properly add namespace qualifiers wherever necessary.

2) You need to add a space between the two > in your typedef :

typedef priority_queue <M,list<M>,greater<list<M>::value_type>> match;

should be :

typedef priority_queue <M,list<M>,greater<list<M>::value_type> > match;

3) You can't use a list with a priority queue, because it doesn't have an operator[]. Use a vector instead.

SOLUTION

Infinity08

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

Dimkov

ASKER

thanks to both of you for the help. I am keen on using list since I believe it is faster then using vectors, and I have couple of thousands of records I need to store.

But I will take your advice and make it with vectors

Infinity08

>> I am keen on using list since I believe it is faster then using vectors

No, a list won't be faster than a vector if you use it in a priority_queue. It will actually be quite a bit slower, plus it will use a lot more memory, not toe mention data locality that is worse than with vectors.

There's a reason that vectors are the default choice for priority_queues : for most situations, they are the best choice.