Sign in to follow this  

(C++) finding the optimum STL container

This topic is 3373 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?[/quote]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.

Share this post


Link to post
Share on other sites
If you want to be able to access by index, this wont work as you will only be able to access the top item at any given time. Thats sort of the point behind queues, first in first out.

Now, i suppose you could do something like this:

typedef pair<Adult*, int> AdultPair; //or create a struct holding the data


vector<AdultPair> MyAdultVector;

This will allow you to access your data by index. Now to sort the data by priority, you should look into the STL sort algorithm, which allows you to provide your own sort algorithm.

http://www.cplusplus.com/reference/algorithm/sort.html

Hope this helps.
Cheers

Share this post


Link to post
Share on other sites
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<adult*,double> my_pair;
typedef std::make_pair<adult*,double> my_make_pair;
bool my_pair_less(my_pair const& lhs, my_pair const& rhs)
{
return lhs.second < rhs.second;
}
typedef std::priority_queue<my_pair,std::vector<my_pair>,my_pair_less> Container;


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

Container c;
c.push(my_make_pair(&Jimmy,2.0));
c.push(my_make_pair(&Billy,17.0);
c.push(my_make_pair(&Sammy,0.02);
c.push(my_make_pair(&Jill,20.4);

c.top().first->feed();//Jill is now fed
c.pop();
c.top().first->feed();//Billy is now fed
c.pop();
c.top().first->feed();//Jimmy is now fed





Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zouflain

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

I would say either std::map<time, adult*, std::greater> or std::vector<std::pair<time, adult*> > used with std::sort. The choice would depend on the dynamic nature of the data and the expected size (std::vector used with std::sort is generally better than std::map for reasonably small list sizes, say under 1000 items or so, if you rarely insert, change key values, or add to the list once it's initialized).

Share this post


Link to post
Share on other sites
Sorry that was untested code std::make_pair is a function, the following is tested.

#include <queue>
#include <vector>

struct adult{void feed(){}};
typedef std::pair<adult*,double> my_pair;

std::pair<adult*,double> my_make_pair(adult* t, double t1)
{
return std::make_pair<adult*,double>(t,t1);
}
struct my_pair_less
{
bool operator() (my_pair const& lhs, my_pair const& rhs)
{
return lhs.second < rhs.second;
}
};


int main(int /*argc*/, char ** /*argv*/ )
{

typedef std::priority_queue<my_pair,std::vector<my_pair>,my_pair_less> Container;

adult Jimmy;
adult Billy;
adult Sammy;
adult Jill;

Container c;
c.push(my_make_pair(&Jimmy,2.0));
c.push(my_make_pair(&Billy,17.0));
c.push(my_make_pair(&Sammy,0.02));
c.push(my_make_pair(&Jill,20.4));
c.top().first->feed();//Jill is now fed
c.pop();
c.top().first->feed();//Billy is now fed
c.pop();
c.top().first->feed();//Jimmy is now fed
}




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?

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
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. :)


Quite correct, I have no idea why I actually did that.

Share this post


Link to post
Share on other sites
Also, if you swapped the template parameters to std::pair around and of course the arguments as well, then you could let it use the built-in less-than operator from std::pair instead of having to write your own.

Share this post


Link to post
Share on other sites

This topic is 3373 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this