priority_queue usually uses the greater<intpred icate function.
But as you know, we don't always use priority_queue< int>. Actually we
may need the "priority_queue <pair<int,int >, vector<pair<int ,int,
cmphp;" thing.
My question is how should I write the "cmp" function?
I tried this one:
bool cmp(pair<int,in t&x, pair<int,int&y) {
return x.second < y.second;
}
but it doesn't work while it usually makes sense for "sort" predicate.
Any comments? Thanks in advance. 8  4162 
On 2008-10-03 12:05:38 -0400, thomas <Fr*********@gm ail.comsaid:
priority_queue usually uses the greater<intpred icate function.
But as you know, we don't always use priority_queue< int>. Actually we
may need the "priority_queue <pair<int,int >, vector<pair<int ,int,
cmphp;" thing.
My question is how should I write the "cmp" function?
It depends on what you want it to do.
>
I tried this one:
bool cmp(pair<int,in t&x, pair<int,int&y) {
return x.second < y.second;
}
but it doesn't work while it usually makes sense for "sort" predicate.
It should work just fine, if you want your elements sorted by their
second field. If that's not what you want, then you need a different
comparison function.
--
Pete
Roundhouse Consulting, Ltd. ( www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
( www.petebecker.com/tr1book)
On 2008-10-03 12:41:16 -0400, Pete Becker <pe**@versatile coding.comsaid:
On 2008-10-03 12:05:38 -0400, thomas <Fr*********@gm ail.comsaid:
>priority_que ue usually uses the greater<intpred icate function.
But as you know, we don't always use priority_queue< int>. Actually we
may need the "priority_queue <pair<int,int >, vector<pair<int ,int,
cmphp;" thing.
My question is how should I write the "cmp" function?
It depends on what you want it to do.
>>
I tried this one:
bool cmp(pair<int,in t&x, pair<int,int&y) {
return x.second < y.second;
}
but it doesn't work while it usually makes sense for "sort" predicate.
It should work just fine, if you want your elements sorted by their
second field. If that's not what you want, then you need a different
comparison function.
However, it should probably take its arguments by const reference or by
value. But since you haven't posted real code, nor provided any details
about what "doesn't work" means, it's not possible to tell what, if
anything, is wrong.
--
Pete
Roundhouse Consulting, Ltd. ( www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
( www.petebecker.com/tr1book)
On Oct 4, 12:44*am, Pete Becker <p...@versatile coding.comwrote :
On 2008-10-03 12:41:16 -0400, Pete Becker <p...@versatile coding.comsaid:
On 2008-10-03 12:05:38 -0400, thomas <FreshTho...@gm ail.comsaid:
priority_queue usually uses the greater<intpred icate function.
But as you know, we don't always use priority_queue< int>. Actually we
may need the "priority_queue <pair<int,int >, vector<pair<int ,int,
cmphp;" thing.
My question is how should I write the "cmp" function?
It depends on what you want it to do.
I tried this one:
bool cmp(pair<int,in t&x, pair<int,int&y) {
* * return x.second < y.second;
}
but it doesn't work while it usually makes sense for "sort" predicate.
It should work just fine, if you want your elements sorted by their
second field. If that's not what you want, then you need a different
comparison function.
However, it should probably take its arguments by const reference or by
value. But since you haven't posted real code, nor provided any details
about what "doesn't work" means, it's not possible to tell what, if
anything, is wrong.
--
* Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)- Hide quoted text -
- Show quoted text -
-------code-----
#include<iostre am>
#include<vector >
#include<map>
#include<set>
#include<cstdli b>
#include<cmath>
#include<list>
#include<stack>
#include<queue>
using namespace std;
bool cmp(const pair<PII,int&x, const pair<PII,int&y) {
return x.second < y.second;
}
priority_queue< pair<PII, int>, vector<pair<PII ,int, cmp>
heap; //pair<pair<node I, node j>, weight>
int main(){
}
---------end---------
for simplicity, you can compile the code above.
I'm using vc8, and got the errors:
----------------------
------ Build started: Project: pku, Configuration: Debug Win32 ------
Compiling...
a.cpp
...\a.cpp(14) : error C2065: 'PII' : undeclared identifier
...\a.cpp(17) : error C3203: 'pair' : unspecialized class template
can't be used as a template argument for template parameter '_Ty',
expected a real type
...\a.cpp(17) : error C3203: 'pair' : unspecialized class template
can't be used as a template argument for template parameter '_Ty',
expected a real type
...\a.cpp(17) : error C2923: 'std::priority_ queue' : 'cmp' is not a
valid template type argument for parameter '_Pr'
..\a.cpp(14) : see declaration of 'cmp'
...\a.cpp(17) : error C2133: 'heap' : unknown size
...\a.cpp(17) : error C2512: 'std::priority_ queue' : no appropriate
default constructor available
------------------------
On Oct 4, 1:31*am, thomas <FreshTho...@gm ail.comwrote:
On Oct 4, 12:44*am, Pete Becker <p...@versatile coding.comwrote :
On 2008-10-03 12:41:16 -0400, Pete Becker <p...@versatile coding.comsaid:
On 2008-10-03 12:05:38 -0400, thomas <FreshTho...@gm ail.comsaid:
>priority_que ue usually uses the greater<intpred icate function.
>But as you know, we don't always use priority_queue< int>. Actually we
>may need the "priority_queue <pair<int,int >, vector<pair<int ,int,
>cmphp;" thing.
>My question is how should I write the "cmp" function?
It depends on what you want it to do.
>I tried this one:
>bool cmp(pair<int,in t&x, pair<int,int&y) {
>* * return x.second < y.second;
>}
>but it doesn't work while it usually makes sense for "sort" predicate.
It should work just fine, if you want your elements sorted by their
second field. If that's not what you want, then you need a different
comparison function.
However, it should probably take its arguments by const reference or by
value. But since you haven't posted real code, nor provided any details
about what "doesn't work" means, it's not possible to tell what, if
anything, is wrong.
--
* Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)-Hide quoted text -
- Show quoted text -
-------code-----
#include<iostre am>
#include<vector >
#include<map>
#include<set>
#include<cstdli b>
#include<cmath>
#include<list>
#include<stack>
#include<queue>
using namespace std;
bool cmp(const pair<PII,int&x, const pair<PII,int&y) {
* * * * return x.second < y.second;}
priority_queue< pair<PII, int>, vector<pair<PII ,int, cmp>
heap; * //pair<pair<node I, node j>, weight>
int main(){
}
---------end---------
for simplicity, you can compile the code above.
I'm using vc8, and got the errors:
----------------------
------ Build started: Project: pku, Configuration: Debug Win32 ------
Compiling...
a.cpp
..\a.cpp(14) : error C2065: 'PII' : undeclared identifier
..\a.cpp(17) : error C3203: 'pair' : unspecialized class template
can't be used as a template argument for template parameter '_Ty',
expected a real type
..\a.cpp(17) : error C3203: 'pair' : unspecialized class template
can't be used as a template argument for template parameter '_Ty',
expected a real type
..\a.cpp(17) : error C2923: 'std::priority_ queue' : 'cmp' is not a
valid template type argument for parameter '_Pr'
* * * * ..\a.cpp(14) : see declaration of 'cmp'
..\a.cpp(17) : error C2133: 'heap' : unknown size
..\a.cpp(17) : error C2512: 'std::priority_ queue' : no appropriate
default constructor available
------------------------- Hide quoted text -
- Show quoted text -
-------------code-----------
#include<iostre am>
#include<vector >
#include<map>
#include<set>
#include<cstdli b>
#include<cmath>
#include<list>
#include<stack>
#include<queue>
using namespace std;
#define PII pair<int,int>
bool cmp(const pair<PII,int&x, const pair<PII,int&y) {
return x.second < y.second;
}
priority_queue< pair<PII, int>, vector<pair<PII ,int, cmp>
heap; //pair<pair<node I, node j>, weight>
int main(){
}
---------------
this one in case you don't know what PII is.
On 2008-10-03 13:33:55 -0400, thomas <Fr*********@gm ail.comsaid:
On Oct 4, 1:31Â*am, thomas <FreshTho...@gm ail.comwrote:
>On Oct 4, 12:44Â*am, Pete Becker <p...@versatile coding.comwrote :
>>On 2008-10-03 12:41:16 -0400, Pete Becker <p...@versatile coding.comsa
id:
>>
>>>On 2008-10-03 12:05:38 -0400, thomas <FreshTho...@gm ail.comsaid:
>>>>priority_qu eue usually uses the greater<intpred icate function.
>>>>But as you know, we don't always use priority_queue< int>. Actually w
e
>>>>may need the "priority_queue <pair<int,int >, vector<pair<int ,int,
cmphp;" thing.
>>>>My question is how should I write the "cmp" function?
>>>It depends on what you want it to do.
>>>>I tried this one:
>>>>bool cmp(pair<int,in t&x, pair<int,int&y) {
Â* Â* return x.second < y.second;
}
>>>>but it doesn't work while it usually makes sense for "sort" predicat
e.
>>
>>>It should work just fine, if you want your elements sorted by their
second field. If that's not what you want, then you need a different
comparison function.
>>However, it should probably take its arguments by const reference or by
value. But since you haven't posted real code, nor provided any details
about what "doesn't work" means, it's not possible to tell what, if
anything, is wrong.
>>--
Â* Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)-Hide quoted text -
>>- Show quoted text -
-------code-----
#include<iostr eam>
#include<vecto r>
#include<map >
#include<set >
#include<cstdl ib>
#include<cmath >
#include<lis t>
#include<stack >
#include<queue >
using namespace std;
bool cmp(const pair<PII,int&x, const pair<PII,int&y) {
Â* Â* Â* Â* return x.second < y.second;}
priority_queue <pair<PII, int>, vector<pair<PII ,int, cmp>
heap; Â* //pair<pair<node I, node j>, weight>
int main(){
}
---------end---------
for simplicity, you can compile the code above.
I'm using vc8, and got the errors:
----------------------
------ Build started: Project: pku, Configuration: Debug Win32 ------
Compiling...
a.cpp
..\a.cpp(14) : error C2065: 'PII' : undeclared identifier
..\a.cpp(17) : error C3203: 'pair' : unspecialized class template
can't be used as a template argument for template parameter '_Ty',
expected a real type
..\a.cpp(17) : error C3203: 'pair' : unspecialized class template
can't be used as a template argument for template parameter '_Ty',
expected a real type
..\a.cpp(17) : error C2923: 'std::priority_ queue' : 'cmp' is not a
valid template type argument for parameter '_Pr'
Â* Â* Â* Â* ..\a.cpp(14) : see declaration of 'cmp'
..\a.cpp(17) : error C2133: 'heap' : unknown size
..\a.cpp(17) : error C2512: 'std::priority_ queue' : no appropriate
default constructor available
------------------------- Hide quoted text -
- Show quoted text -
-------------code-----------
#include<iostre am>
#include<vector >
#include<map>
#include<set>
#include<cstdli b>
#include<cmath>
#include<list>
#include<stack>
#include<queue>
using namespace std;
#define PII pair<int,int>
bool cmp(const pair<PII,int&x, const pair<PII,int&y) {
return x.second < y.second;
}
priority_queue< pair<PII, int>, vector<pair<PII ,int, cmp>
heap; //pair<pair<node I, node j>, weight>
int main(){
}
---------------
this one in case you don't know what PII is.
Presumably the result of compiling this code was different from the
result shown in the previous message.
--
Pete
Roundhouse Consulting, Ltd. ( www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
( www.petebecker.com/tr1book)
#include<iostre am>
#include<vector >
#include<map>
#include<set>
#include<cstdli b>
#include<cmath>
#include<list>
#include<stack>
#include<queue>
The headers required are queue, utility and vector.
using namespace std;
#define PII pair<int,int>
A typedef is preferable. Two of them would be useful.
typedef std::pair<int,i ntPII;
typedef std::pair<PII,i ntelement;
bool cmp(const pair<PII,int&x, const pair<PII,int&y) {
return x.second < y.second;
}
Comparisons can be done on second but first would be more akin to the
associative containers.
priority_queue< pair<PII, int>, vector<pair<PII ,int, cmp>
The third argument must be a type. It must be this: bool (*)(element
const &x, element const &y).
heap; //pair<pair<node I, node j>, weight>
A constructor that sets the comparison function must be invoked i.e.
heap(cmp)
A functor is easier to use than a function when you know how to use
them. I would rewrite the code to use a functor and to sort on first
instead of second.
Fraser.
On 3 Oct, 17:05, thomas <FreshTho...@gm ail.comwrote:
priority_queue usually uses the greater<intpred icate function.
But as you know, we don't always use priority_queue< int>. Actually we
may need the "priority_queue <pair<int,int >, vector<pair<int ,int,
cmphp;" thing.
My question is how should I write the "cmp" function?
I tried this one:
bool cmp(pair<int,in t&x, pair<int,int&y) {
* * return x.second < y.second;
}
but it doesn't work while it usually makes sense for "sort" predicate.
std::sort() accepts the predicate by value and deduces its type, so
both function pointers and function objects (with operator()) work.
std::priority_q ueue<>, on the other hand, does not deduce the template
types, so that you have to specify it explicitly. The type of your
predicate is a function pointer:
typedef priority_queue<
pair<int,int>
, vector<pair<int ,int
, bool(*)(pair<in t,int>&, pair<int,int>&) // <--- here
Q;
Constructors of the queue use a default-initialised value for the
predicate, which in your case is a NULL function pointer. Obviously,
you need to pass a pointer to you predicate function explicitly when
constructing the queue:
Q q(cmp);
It may be a bit easier to make your predicate a class, so that you
don't have to pass it into constructors:
struct cmp2
{
bool operator()(pair <int,intconst &, pair<int,intcon st&)
const;
};
typedef priority_queue<
pair<int,int>
, vector<pair<int ,int
, cmp2
Q2;
Q2 q2; // <--- default-initialised cmp2 works
Please also note, that when you use function pointers the calls
through a function pointer can not be inlined. With function objects
they can.
--
Max ra*@zedat.fu-berlin.de (Stefan Ram) kirjutas:
"Fraser Ross" <z@zzzzzz.comwr ites:
>>>>#include<st ack>
#include<qu eue>
The headers required are queue, utility and vector.
In a class, I explained that using certain names and
operators requires certain include directives.
Then I was asked if it would be possible to always
copy /all/ standard include directives to the start
of a program. I answered that no one does this, but
that it would be possible.
Is there a reason not to do so (except for a possible
increase in compilation time)?
Actually, a similar approach can be used for *reducing* compile times in
certain implementations (e.g. MSVC++). The idea is that you gather most
includes, including all needed standard includes, into a single header,
which is then marked to be precompiled. All cpp files include this header
first. As this header will be compiled only once it often means
significantly faster compile times for large projects.
As it might be quite hard to guess which standard includes any cpp might
need in an evolving project, I can imagine that it would be sometimes
practical to put *all* standard includes in the precompiled file, just in
case. Never done that myself, though.
hth
Paavo This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Dave |
last post by:
Hello all,
I'm pondering why the default underlying container for std::priority_queue<>
is std::vector<>. It would seem that inserts are liable to happen anywhere,
which would make std::list<> a superior alternative. Why factors am I not
considering here? Why in the general case would std::vector<> be best?
Thanks,
Dave
|
by: Tino |
last post by:
In using std::priority_queue, I'm concerned about the expense of
memory allocation and copying as the priority_queue grows large.
std::vector has reserve() to address this concern, though there
doesn't seem to be anything like this for priority_queue. Also, I
don't know anything about how priority_queue is implemented
(specifically, MSVC++ 6.0), so maybe I don't have anything to worry
about. Guidance, please?
Regards,
Ryan
|
by: Rich S. |
last post by:
Hi
In an earlier posting I was asking how to read thru millions of data records
keeping the top 2000 (where the top values are based upon a field in the
record) and niklasb suggested using a priority_queue like so
------------------- start old message ---------------------
A more efficient way than what you describe would be
to use priority_queue. Define the predicate in such
|
by: zl2k |
last post by:
hi, all
Here is what I want to do: to wrap my self defined class in a
shared_ptr and then insert it into the priority_queue. The
priority_queue should pump the least element of the self defined class
first. To make it simple, here is the toy code.
myClass.h
------------------------------------------
#ifndef MYCLASS_H
#define MYCLASS_H
|
by: Henning Hasemann |
last post by:
I'm using a stl-priority queue and want
- find out if a certain item is contained in the queue
- to be able iterate over all items without having to pop() them, order
does not matter.
I couldnt find methods for these which suprises me as both should be
easily solvable with access to the underlying vector.
Did I just miss these methods? Can I somehow access the vector to get .
begin() .end() and .find()?
| | |
by: J.M. |
last post by:
I would like to use a data structure (e.g. from the STL) that always allows
me to retrieve the largest element. (I want to push in elements, and remove
the largest, push in further elements, etc.) It seems a priority_queue from
the STL would work fine. However at some point, I am finished (even though
the queue is not empty) and want to throw away the rest of the elements. It
seems, I have to do this using:
while (!Q.empty()) Q.pop();
...
|
by: Eric Lilja |
last post by:
Hello, I have a the following priority_queue: priority_queue<pair<int,
string pq;
AFAICT, priority_queues doesn't support iterators. My question: is
there a way to print its contents without emptying it?
Right now I'm using the following code:
while (!pq.empty())
{
cout << setw(3) << pq.top().first << ": " << pq.top().second <<
|
by: Joe, G.I. |
last post by:
Can anyone help me w/ a priority_queue. I'm generating MyEvent classes
and I put them on a priority_queue, but I don't know how to get them in
priority. The priority is the event w/ the smallest timestamp.
// just a wrapper around priority_queue
pq = new MyPriorityQueue();
// I generate 10 events w/ a random timestamp
for (int i = 0; i < 10; i++) {
MyEvent *event = new MyEvent();
|
by: card |
last post by:
I was wondering if anyone has a definitive answer on whether the STL priority_queue is dynamic? What I mean by this is best illustrated by a simple example. Suppose I have a priority queue of class called Position with a comparator class called PositionCompare as follows:
priority_queue<Position, vector<Position>, PositionCompare> _pQ;
Now, I go along and keep inserting Position objects into _pQ. These Position objects are really...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| | |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |
