I feel rather newbish for asking this, but I can't remember the right container for the following circumstance, and the specifications for them haven't helped. I have a pointer to an object and a priority (double) - I need to be able to access by location and to sort by priority. in other words:

for foo<bar
    container.push_back(priority[foo],pointer[foo]);
container.sort();//probably automatic, calling it is no problem though
for foo2<bar2
  container[bar2]->dofoobar();
container.clear();

I don't want to have to reinvent the wheel and come up with my own. This sounds like a priority queue, but the specifications aren't clear ("A serves purpose A, which is defined as A" doesn't help when I don't know what A is). I could just pop the first bar2 values and do whatever I need to with them if that was the case, but I can't figure out how to sort the darn things. I suppose the real question is, would this -

using namespace std;
priority_queue<foo*,vector<T>,double) bar;

- work for what I'm describing?

It's not exactly clear what you mean by 'location'... you mention pointers, but then your example code looks like you use indices...

What do you actually require? Do you need a queue, or just a sorted list? Are you popping elements off, or just iterating over them in order?

Assuming you're just after a priority queue (ie. insert random, extract in order) which you can iterate over (which the standard priority queue doesn't allow because it's absolutely stupid), then the standard library does not provide such a beast. I would be tempted to start with a deque, insert items in the correct position via lower_bound, and pop them from the relevant end.

Quote:Original post by Kylotan
It's not exactly clear what you mean by 'location'... you mention pointers, but then your example code looks like you use indices...

I meant location in the storage system, not memory.

What do you actually require? Do you need a queue, or just a sorted list? Are you popping elements off, or just iterating over them in order?A sorted, associative list. A type (lets say foo) should be stored in the descending order of a second (numeric) type. So say I had four adults but I can only feed three. I'd sort them by the number of days since they'd last eaten:

Jimmy = 2 days
Billy = 17 days
Sammy = 0.02 days
Jill = 20.4 days

and I'd feed them in the order of Jill then Billy then Jimmy.

In semi-code:
container<adult*,time> somecontainer;
somecontainer.push_back(&Jimmy,2.0);
somecontainer.push_back(&Billy,17.0);
somecontainer.push_back(&Sammy,0.02);
somecontainer.push_back(&Jill,20.4);

somecontainer.front->feed();//Jill is now fed
somecontainer.pop;
somecontainer.front->feed();//Billy is now fed
somecontainer.pop;
somecontainer.front->feed();//Jimmy is now fed

Quote:Assuming you're just after a priority queue (ie. insert random, extract in order) which you can iterate over (which the standard priority queue doesn't allow because it's absolutely stupid)

The values I was storing were (fairly) static and rarely update, so I thought it would be best if I didn't need to recalculate everything at every frame (ie, rebuilding the queue each time I want to read it).

Quote:I would be tempted to start with a deque, insert items in the correct position via lower_bound, and pop them from the relevant end.

I'm not too familiar with lower_bound. My data sorting is sorely lacking when it comes to C++, because I don't usually have to prioritize dynamically like this. It's usually maps and vectors with the occasional list.

Now that you have given more details then I think yes a priority queue can be used here, something like the following should do what you require.

typedef std::pair<double,lightsource*> lightpair;bool lightpair_compare(lightpair const& a,lightpair const& b){	return(a.first > b.first);}typedef std::priority_queue<lightpair,std::vector<lightpair>,lightpair_compare> lightlist;

VC8 is giving me an error
'std::priority_queue' : 'lightpair_compare' is not a valid template type argument for parameter '_Pr'

This is annoying (probably because it's 5:35 AM, I have class in far less than two hours, and I keep having to wade through 200+ warnings that have nothing to do with my code just to find this error.

warning C4005: '__reserved' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(702) : see previous definition of '__reserved'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(341) : warning C4005: '__checkReturn' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(703) : see previous definition of '__checkReturn'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(344) : warning C4005: '__typefix' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(704) : see previous definition of '__typefix'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(349) : warning C4005: '__override' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(705) : see previous definition of '__override'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(350) : warning C4005: '__fallthrough' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(714) : see previous definition of '__fallthrough'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(351) : warning C4005: '__callback' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(706) : see previous definition of '__callback'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(352) : warning C4005: '__in' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(499) : see previous definition of '__in'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(353) : warning C4005: '__out' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(508) : see previous definition of '__out'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(354) : warning C4005: '__inout' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(527) : see previous definition of '__inout'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(356) : warning C4005: '__out_ecount' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(509) : see previous definition of '__out_ecount'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(357) : warning C4005: '__in_ecount' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(500) : see previous definition of '__in_ecount'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(358) : warning C4005: '__inout_ecount' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(528) : see previous definition of '__inout_ecount'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(359) : warning C4005: '__out_bcount' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(510) : see previous definition of '__out_bcount'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(360) : warning C4005: '__in_bcount' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(501) : see previous definition of '__in_bcount'
c:\program files\microsoft visual studio 8\vc\include\specstrings.h(361) : warning C4005: '__inout_bcount' : macro redefinition
c:\program files\microsoft visual studio 8\vc\include\sal.h(529) : see previous definition of '__inout_bcount'

add nausium.

Sorry that was untested code std::make_pair is a function, the following is tested.

In actually writting the above code I notice something with yours

Quote:
Jimmy = 2 days
Billy = 17 days
Sammy = 0.02 days
Jill = 20.4 days

Here you are assigning the value to the instance is this correct or is the value stored separately to the instance and not changed?

Zouflain, you've still not fully specified the problem. Do you need to access random elements within the container without altering the container? Or do you only need to access elements one at a time as you remove them in order? There's actually no requirement in the second case that the elements be sorted, as such. You could just throw everything into any old list and do a scan to find the appropriate one to 'pop' when you need to, for example.

In the former case, you need a sorted random access structure like a vector or deque with sorted inserts (I would still recommend lower_bound() over sort()), and in the latter case it is exactly what a priority queue exists for (though I still wouldn't use std::priority_queue personally as it gives you few benefits).

Quote:Original post by dmail
Sorry that was untested code std::make_pair is a function, the following is tested.
*** Source Snippet Removed ***

You seem to have overlooked something. The whole reason std::make_pair exists is that the C++ compiler can infer the template types of parameters when a free function is called, but cannot when a class constructor is called. That is, 'X x; Y y; std::make_pair(x, y)' calls std::make_pair<X, Y>(x, y) with no extra effort required on the part of the programmer.

Thus, there is no need for my_make_pair(). Just use std::make_pair() directly. That's why it's there. :)

Quote:In actually writting the above code I notice something with yours

Quote:
Jimmy = 2 days
Billy = 17 days
Sammy = 0.02 days
Jill = 20.4 days

Here you are assigning the value to the instance is this correct or is the value stored separately to the instance and not changed?

I'm assuming that was pseudocode.