design question in c++ classes

[koren99]

Hi,

i'm a student and got an assignment, and was wandering what is the best way to design it, or simply put - what would a skilled programmer do?

here goes: (it's a bit long, so sorry in advance and thank you)

i have to create 2 containers as templates one of Queue and the other of Priority Queue (which is a queue with sorted items)

Oueue has these Methods:
Push - push into back of queue
Pop - remove item from top of queue
Front - inspect item in front
Back - inspect item in back

pQueue has these Methods:
Push - push into a sorted place in the queue (the item i'll be inserting will have operator< to comare)
Pop - remove item from top of queue
Front - inspect item in front

that's it...

notice that pQueue does not have a Back method and is not allowed to have one such as public, moreover no other public methods are allowed to exist for any client of these container classes.

hese is what i did:
i created a BaseQueue that stores the data in linked list with Elm *head, *tail and the methods:
Push - into the back of the Queue
Pop - the same thing in both containers
Front - the same thing in both containers

and inherited public from this one into pQueue and Queue.

the problem was that in order to get into the middle/end of this queue i'll have to throw out all items and put them in a temp queue and then return them back to the original queue when i'm done. --- This was a big problem with pQueue because i has to play with the entier Queue to search for the right position to insert the value, (pop out until i find the right place) and Back at queue not much simpler...

So.... is this a good way of doing this? (even though it has a very bad performence considering i'm poping and pushing back everything just to insert one item in pqeueu and running all the list to get to back in queue)

Any other suggestion or better way? i couldn't think of any...

Thanks in advance...
Koren. :-)

[weaknessforcats]

Your desing is OK but this class is not:

i created a BaseQueue that stores the data in linked list with Elm *head, *tail and the methods:
Push - into the back of the Queue
Pop - the same thing in both containers
Front - the same thing in both containers

If the BaseQueue is a linked list, then it should have linked list methods like:
1) add to end/front
2) remove from end/front/middle
3) insert at front/end/specificed position

You derive your stack from this BaseQueue and implement the Push as a call to BaseQueue::AddToEnd().

By keeping BaseQueue as a linked list your problems disappear.

And while you are at it, I would rename BaseQueue to something like LinkedList to better describe what it is.

[RRick]

Koren,

Your original design had QueueP (QP) using only the methods from Queue (Q) to perform its sorting. That means that QP can be derived from Q. You're right, this has issues, especially with storage.

Then you created a base class that would have just enough functionality to keep Q and QP happy if they inherit the base class publicly. That works, but there is another alternative. QP can inherit Q as protected. Then QP defines public methods for just the functionality it needs to reveal. Now there is no need for a base class. Also, this design decouples the underlying structure of Q from QP. Now Q can change and QP doesn't care. Also, Q's push method is a good candidate for a virtual method.

W4cats suggested a design with some class having enough functionality for both objects. This can be a base class or it can be the Queue class. The extra functionality will have to be protected by Q (and available to QP). W4cats suggested a link list but even vectors/arrays will work. Now QP can get the base structure quickly and can optimize its own push method. The down side is that Q and QP are tightly coupled. Any changes to Q's structure might change QP's behavior.

What's best depends on your application. What kind of time frame you are dealing with? Is it throwaway code? Does this scale well? These are all issues that affect the design.