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
LVL 3
DimkovAsked:
Who is Participating?
 
jkrCommented:
The problem is 'list' (other containers like 'vector' and 'set' work fine with your code). The problem for 'list' is that you cannot just subtract iterators, you need to call 'std::distance()' instead.
0
 
jkrCommented:
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)
0
 
Infinity08Commented:
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.

0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

 
Infinity08Commented:
>> because it doesn't have an operator[]

Mmm, that was a misleading (incorrect statement). The fact that there's no operator[] in a list is another symptom, but not the cause of the "problem". The real problem is that a priority queue requires random access iterators for its container, which a list doesn't provide.
The fact that there's no operator[] is related to this lack of random access iterators, but is not the base reason ;)

The recommendation is still the same - use a vector instead of a list.

There's not even a good reason to use a list instead of a vector, because a priority_queue will only access the end of the container anyway (and swap elements for insertions in the middle).
0
 
DimkovAuthor Commented:
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
0
 
Infinity08Commented:
>> 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.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.