-
April 7th, 2004, 01:10 AM
#1
URGENT: <algorithm> lower_bound() problem
I am currently working on a simulation program that uses discrete event simulation. Basically, the program generates events (in this case, the arrival and departure of customers in a store). So the events are placed in a priority queue, ordered by the times that the events are to occur (i.e. an event that is supposed to occur at time 25 would have a higher priority than an event that is supposed to occur at time 30). To make this ordering easy, I decided to use the vector STL to implement the queue.
To insert things in the order I want, I use the <algorithm> function, lower_bound(line.begin(), line.end(), e), where line is the vector, and Event* e is inserted in the appropriate location, based on ascending event time order. I have used lower_bound() before, and for it to work, I had to overload the == and < operators for the object (in this case, Event). However, when I run my program with the debugger, the overloaded == and < are never accessed and, consequently, the events are not ordered. Here are the relevant sections of code...
In Simulation class...
Code:
void Simulation::schedule(Event *e) {
//Create an iterator for the vector queue
vector<Event *>::iterator pos;
//Determine the position to insert the event
pos = lower_bound(eQueue.begin(), eQueue.end(), e);
//Insert the event at the determined position
eQueue.insert(pos, e);
}
In Event class...
Code:
bool Event:operator==(const Event& rhs) const {
//Return true if the event times are equal, false otherwise
return (time == rhs.time);
}
bool Event:operator<(const Event& rhs) const {
//Return true if this event time is less than rhs event time,
// false otherwise
return (time < rhs.time);
}
Do you have any idea why the lower_bound() function isn't looking for those two operators? Can you think of a better way to do this? Any help will be greatly appreciated. Thank you in advance!
Last edited by waverdr9; April 7th, 2004 at 01:12 AM.
-
April 7th, 2004, 02:18 AM
#2
why not just use std::priority_queue?
In other words, the STL already has the container you need
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."
-
April 7th, 2004, 02:45 AM
#3
I am aware of the priority_queue STL, but the vector STL suits my purposes much better in my program as a whole. And like I said, I have used vector in conjunction with lower_bound() before. But for some reason it isn't working as I thought it would this time.
So if anyone has any ideas or suggestions regarding my problem, please let me know.
Thank you for the priority_queue suggestion though. I will use that as a last resort if I can't figure this problem out.
-
April 7th, 2004, 04:04 AM
#4
Your operators are not being called because you have a container
of pointers.
try doing this instead
PHP Code:
struct PtrEventInTimeCompare:public std::binary_function<const Event*, const Event*, bool>
{
bool operator()(const Event* lhs, const Event* rhs) const
{
return *lhs.time < *rhs.time; //or whatever accessor you have
}
}
//and your code becomes
eQueue.insert(lower_bound(eQueue.begin(), eQueue.end(), e, PtrEventInTimeCompare()), e);
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."
-
April 7th, 2004, 01:10 PM
#5
Should I put that struct in the Simulation class or the Event class?
-
April 7th, 2004, 01:17 PM
#6
Originally posted by waverdr9
Should I put that struct in the Simulation class or the Event class?
It shouldn't go into any class.
You should place the struct outside of any class, but put it into the source file where you have your Event class implemented.
Regards,
Paul McKenzie
-
April 7th, 2004, 02:33 PM
#7
Sorry, I didn't mean inside the class, just inside the file where the class resides.
Thanks for the help. :D
-
April 7th, 2004, 03:04 PM
#8
I will just give you some vocabulary associated with that solution
in case you want to do some searching. If this is old hat, then I
apologize
1. the struct used is called a functor or a function object.
2. I derived from std::binary_function to make sure this functor
was adaptable. i.e. I can use the funciton adapters with it.
(not1, not2, bind1st, bind2nd and any other custom adapters)
It costs you nothing and can make life easier for clients and you.
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."
-
April 7th, 2004, 03:22 PM
#9
Snide comment that could possibley cause offense, removed by me!.
Last edited by TheCPUWizard; April 7th, 2004 at 07:14 PM.
TheCPUWizard is a registered trademark, all rights reserved. (If this post was helpful, please RATE it!)
2008, 2009,2010
In theory, there is no difference between theory and practice; in practice there is.
* Join the fight, refuse to respond to posts that contain code outside of [code] ... [/code] tags. See here for instructions
* How NOT to post a question here
* Of course you read this carefully before you posted
* Need homework help? Read this first
-
April 7th, 2004, 03:27 PM
#10
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."
-
April 7th, 2004, 08:38 PM
#11
I tried using the struct above, and I get two errors regarding *lhs.time and *rhs.time:
error C2228: left of '.time' must have class/struct/union type
Also, when I tried using the code eQueue.insert(.... I get an error saying 'PtrEventInTimeCompare' : undeclared identifier
Please Help ASAP!
-
April 7th, 2004, 08:47 PM
#12
Where did you put the functor?
Put it just under the declaration of the Event class in the header
file.
class Event
{
};
...put it here
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."
-
April 7th, 2004, 09:07 PM
#13
That didn't work. But then I tried putting it in the Simulation class implementation file (the file that actually uses the event pointer compare) and now it works. However, I had to change the functor from this:
Code:
struct PtrEventInTimeCompare:public std::binary_function<const Event*, const Event*, bool>
{
bool operator()(const Event* lhs, const Event* rhs) const
{
return *lhs.time < *rhs.time; //or whatever accessor you have
}
}
to this:
Code:
struct EventPtrCompare {
bool operator()(const Event *lhs, const Event *rhs) const {
return (lhs->getTime() < rhs->getTime());
}
};
-
April 7th, 2004, 09:23 PM
#14
Hey wait...actually your idea works, but I still had to change your code to what I have above (only because of how my code is set up)
Thanks for the help!!!
But now I have one more question. I am trying to do the same thing with another part of my code, only this time I need to add customers to vector queues and order them by a priority number held by each customer in descending order. However, when I try the method that I used for ordering Event objects, it wont work. Here is the relevant code:
In the Store implementation file...
Code:
void Store::addToLine(int num, Customer *c) {
vector<Customer *>::iterator pos; //Vector iterator
//Make sure the line number is valid
if ((num >= 0) && (num < LINENUM)) {
//If the designated line is full
if (line[num].size() == LINEMAX) {
//Add a balker to the statistics
stats.addBalker();
//Schedule an immediate departure
schedule(new Departure(getSimTime(), num));
}
//Else add the customer to the designated line
else {
//Determine the position to insert the customer, based on their priority
pos = lower_bound(line[num].begin(), line[num].end(), c, CustomerPtrCompare());
//Else insert the customer at the determined position
line[num].insert(pos, c);
}
}
//Else, throw an error
else
cout << "\nError: invalid line number\n\n";
}
In the Customer header file...
Code:
#ifndef CUSTOMER_H
#define CUSTOMER_H
class Customer {
public:
//PURPOSE: Default Constructor
//PRECONDITION: None
//POSTCONDITION: Customer instance is initialized
Customer(int time = 0, int itemNum = 1);
//PURPOSE: Returns the arrival time of the customer
//PRECONDITION: None
//POSTCONDITION: The customer's arrival time is returned
int getArrivalTime();
//PURPOSE: Returns the customer's number of items
//PRECONDITION: None
//POSTCONDITION: The customer's number of items is returned
int getItems();
//PURPOSE: Returns the customer's priority
//PRECONDITION: None
//POSTCONDITION: The customer's priority is returned
double getPriority();
//PURPOSE: Overloaded == operator to compare customers' priority
//PRECONDITION: None
//POSTCONDITION: True is returned if customers have same priority,
// false otherwise
bool operator==(const Customer& rhs) const;
//PURPOSE: Overloaded > operator to compare customers' priority
//PRECONDITION: None
//POSTCONDITION: True is returned if customer's priority is greater than
// rhs customer's priority, false otherwise
bool operator>(const Customer& rhs) const;
private:
int arrivalTime; //Customer's time of arrival in seconds
int items; //Number of items customer intends to purchase
double priority; //Customer's priority based on (1/n) items
};
struct CustomerPtrCompare {
bool operator()(const Customer *lhs, const Customer *rhs) const {
return (lhs->getPriority() > rhs->getPriority());
}
};
#endif
When I compile the program, I get the following error associated with the line return (lhs->getPriority() > rhs->getPriority());
error C2662: 'getPriority' : cannot convert 'this' pointer from 'const class Customer' to 'class Customer &'
I am sure that the solution to this problem is easy, but how can I fix this error???
Thank you in advance to anyone who can help me. And a HUGE thank you to everyone who already has helped me! :-)
-
April 7th, 2004, 09:44 PM
#15
Change
double getPriority();
to
double getPriority() const;
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|