priority_queue STL

Posted on 2007-07-31
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)
      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;


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      


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
Question by:Dimkov
    LVL 86

    Accepted Solution

    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.
    LVL 86

    Expert Comment

    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;      


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

    Then it compiles ;o)
    LVL 53

    Expert Comment

    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.

    LVL 53

    Assisted Solution

    >> 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).
    LVL 3

    Author Comment

    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
    LVL 53

    Expert Comment

    >> 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.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Suggested Solutions

    How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from ( Go to that link and select download selenium in the right hand columnThat will then direct you to their downlo…
    Does the idea of dealing with bits scare or confuse you? Does it seem like a waste of time in an age where we all have terabytes of storage? If so, you're missing out on one of the core tools in every professional programmer's toolbox. Learn how to …
    The viewer will learn how to use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…
    The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

    779 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

    Need Help in Real-Time?

    Connect with top rated Experts

    9 Experts available now in Live!

    Get 1:1 Help Now