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!

why not just use std::priority_queue?
In other words, the STL already has the container you need

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

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); 


---

Should I put that struct in the Simulation class or the Event class?

Quote:

---

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

Sorry, I didn't mean inside the class, just inside the file where the class resides.
Thanks for the help. :D

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.

Snide comment that could possibley cause offense, removed by me!.

:D

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! :confused:

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

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());
    }
};

---

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! :-)

Change
double getPriority();

to

double getPriority() const;

I am assumming of course that getPriority does in fact not
modify anything.

if it is just an accessor then you should inline it

__inline double getPriority() const {return priority;}

all in the header file

Thank you for all of the help!
I fixed the problem and finished the program. :D :cool: :D