URGENT: <algorithm> lower_bound() problem
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: URGENT: <algorithm> lower_bound() problem

  1. #1
    Join Date
    Mar 2003
    Location
    Orange County, CA
    Posts
    99

    Exclamation 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 02:12 AM.

  2. #2
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863
    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."

  3. #3
    Join Date
    Mar 2003
    Location
    Orange County, CA
    Posts
    99
    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.

  4. #4
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863
    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 Eventlhs, const Eventrhs) const
        {
            return *
    lhs.time < *rhs.time//or whatever accessor you have
        
    }
    }


    //and your code becomes
    eQueue.insert(lower_bound(eQueue.begin(), eQueue.end(), ePtrEventInTimeCompare()), 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."

  5. #5
    Join Date
    Mar 2003
    Location
    Orange County, CA
    Posts
    99
    Should I put that struct in the Simulation class or the Event class?

  6. #6
    Join Date
    Apr 1999
    Posts
    27,446
    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

  7. #7
    Join Date
    Mar 2003
    Location
    Orange County, CA
    Posts
    99
    Sorry, I didn't mean inside the class, just inside the file where the class resides.
    Thanks for the help. :D

  8. #8
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863
    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."

  9. #9
    Join Date
    Mar 2002
    Location
    NY, USA
    Posts
    12,097
    Snide comment that could possibley cause offense, removed by me!.
    Last edited by TheCPUWizard; April 7th, 2004 at 08:14 PM.
    TheCPUWizard is a registered trademark, all rights reserved. (If this post was helpful, please RATE it!)
    2008, 2009
    In theory, there is no difference between theory and paractice; 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

  10. #10
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863
    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."

  11. #11
    Join Date
    Mar 2003
    Location
    Orange County, CA
    Posts
    99
    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!

  12. #12
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863
    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."

  13. #13
    Join Date
    Mar 2003
    Location
    Orange County, CA
    Posts
    99
    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());
        }
    };

  14. #14
    Join Date
    Mar 2003
    Location
    Orange County, CA
    Posts
    99
    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! :-)

  15. #15
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863
    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."

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center