[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

priority_queue STL

Posted on 2007-07-31
6
Medium Priority
?
722 Views
Last Modified: 2013-12-14
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
0
Comment
Question by:Dimkov
  • 3
  • 2
6 Comments
 
LVL 86

Accepted Solution

by:
jkr earned 1000 total points
ID: 19600646
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
 
LVL 86

Expert Comment

by:jkr
ID: 19600680
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 19600925
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 1000 total points
ID: 19601055
>> 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
 
LVL 3

Author Comment

by:Dimkov
ID: 19601296
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 19601992
>> 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

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn different types of Android Layout and some basics of an Android App.
When you discover the power of the R programming language, you are going to wonder how you ever lived without it! Learn why the language merits a place in your programming arsenal.
Progress
Loops Section Overview

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question