C++ Guided Design Programming Challenge

Alright, this is not an attempt to compete with the contests that Prelude does a great job running, rather it complements those contests. The point of Prelude's contests is to compete with one another, this is a thread dedicated to cooperation and collaboration. It's on the C++ board as this will be a C++ only challenge.

Ground rules are simple, anyone can participate, but try not to duplicate effort -- please read other people's replies. As the whole point is to have participation of as many people as are interested, I also ask that people not give too many answers all at once -- give a few, and let others have a chance before you give more. Contributions should be posted to this thread. Feel free to discuss and critique solutions, but as always, keep criticism constructive.

Dunno how much interest people have in this kind of thing, but I think guided projects are a great learning tool (I did one last semester with a class I taught, and they liked it a lot). Hopefully people will think this is a worthwhile pursuit.

The focus of this project is to develop and use good programming techniques.

All that being said, the problem statement and the first design step are below. Once I think this step has been completed successfully, the next gets posted:

Problem Statement
-----------------------------------------------------------
A queue is a data structure which is similar to the line at your local grocery. Data enters the queue at the tail (the "back of the line") and leaves at the head. Once the head leaves the line, the person who was next becomes the new head of the line.

In this project, we will implement and test a Queue class. The data will be of arbitrary type, T, so we will use templates. This Queue class will also allow us to optionally specify a maximum capacity of the Queue, after which no new data may be queued at the tail until data is removed from the head.

Step #1 - Interface
-----------------------------------------------------------
The interface is the collection of methods exposed as public or protected, as well as friend or other helper functions (which are counted as part of the public interface).

List methods that we will need or want to include in our Queue class. Don't worry about how we will implement them, just give their signatures and a brief description (one to four lines describing what the function does). Also include relevant information about the method. For example, we will have a default constructor:

Queue();
// Creates an empty Queue object that has no capacity specified.
// Access : public member
// Parameters: None
// Returns: N/A

At this point, we're not even thinking about private data members or private methods, just the public and protected interfaces.

T& GetHead()
// Gets the object at the head of the queue
// Access : public member
// Parameters: None
// Returns: a reference(for efficiency) to the type of object(T) stored in the queue

Code:

---

template <class T>
struct queue {
~queue();
queue();
queue(const queue & replicate);
template <class Iter>
queue(const Iter & _begin, const Iter & _end);
queue & copy(const queue & replicate);
// fill with values from another type of container:
template <class Iter>
queue & copy(const Iter & _begin, const Iter & _end);
// returns a dynamically allocated copy:
queue * clone() const;
};

---

1)...also ask that people not give too many answers all at once

2) just give their signatures and a brief description (one to four lines describing what the function does). Also include relevant information about the method.

Sprechen Sie English Sebastiani?

void push_back(T);
//adds value T to the end of queue, if queue size not at max size,
//and increments private variable member itsSize by one;
//if size is already at max, then sends message to user of error
//and doesn't add current item to queue
//or
//automatically pops first item off queue (decreasing itsSize by 1)
//and then pushes current item on back of queue with or without
//notifying user
//how to handle a "full" queue is a matter of design preference I
//guess
//access: public

int size();
//returns the number of items in the queue;
//access: public

int itsSize;
//holds the current number of items in the queue
//access: private

push_back() might as well be push() since you can't add values to the head of the queue

void pop()
//takes the last value off of the queue
//decrements itsSize by one
//access: public

true, but putting the _back in there makes it explicit where you are pushing the value. Likewise, I would argue to use pop_front(), for better understanding----we'll be popping the "oldest" value put in the queue, not the "youngest". But it's just a matter of personal taste.

BTW, I would have pop() (or pop_front()) return type T, not void. That way if I want to ignore the return, I can, but if I want to use it, I can, too.

elad,

I agree with you about the descriptive nature of your function name. I guess the same thing could be said about the GetHead() function I suggested: you can only get objects from the head of the queue, so it could be named just Get().

Also, why not have push_back() return a reference to T?

Also, wouldn't push_back() only return an object if the queue was full? If the queue wasn't full you would have to return some kind of zeroed out object--maybe it's better if it returns void?

How about using front() or first() instead of GetHead(). That way, irrespective of the private access container the queue is based on (given the defined size the queue class could be based on an array/vector or a list) we would know that we were looking for the item at the front of the queue---head in the case of list, and index 0 in the case of an array/vector.

I guess we have to decide how to handle a call to push_back() when the queue is full to decide whether to return something other than void or not. I agree there seems to be benefit to returning something other than void in some conditions.

get_first(), push_last()?

I still don't understand how you want to implement push_last() with a return type, since if the queue isn't full there is nothing to return?

How about Append() for adding something to the stack?

append implies that the action takes place at the end.
I can't come up with an english word for doing the oppsite action on the first element, however. It would have to mean something like cut off and return the first element, pull all other elements one down. (Of course we'd just relink the elements and not decrement their position like in an array, but thats what you'd say to describe the process).

Quote:

---

Originally posted by elad
true, but putting the _back in there makes it explicit where you are pushing the value. Likewise, I would argue to use pop_front(), for better understanding----we'll be popping the "oldest" value put in the queue, not the "youngest". But it's just a matter of personal taste.

BTW, I would have pop() (or pop_front()) return type T, not void. That way if I want to ignore the return, I can, but if I want to use it, I can, too.

---

There is one possible pitfall in this approach, you sacrifice exception safety (which is why the STL never allows this). Because you are returning an object that is being removed from the queue, you must return by copy. And if this copy constructor fails, and throws, then the object is no longer retrievable -- it's gone from the queue but never made it back to the caller.

For this reason, the two effects of the traditional pop (to remove the next item and to return that item) are split into two methods, neither of which can fail. And if the client code uses copy constructor/assignment operator with the return from GetHead(), and this fails, the object was never removed from the queue so they can try again.

And there is a good point brought up -- how should we handle a full queue? My first thought was to throw an exception derived from std::logic_error, but I'd like to hear other ideas.

Code:

---

#include <deque>

---

Quote:

---

How about Append() for adding something to the stack?

---

Well that might make things confusing, because although you are adding to the "tail" the way things actually are is like this:

Code:

---

push-->tail-------------head-->pop

---

"push" makes it clear that you are pushing all the values foward, not just adding one to the end.

Quote:

---

Code:

---

#include <deque>

---

---

If you are going to waste our time with a useless post why not just:

Code:

---

#include <queue>

---

Quote:

---

Originally posted by JaWiB
"push" makes it clear that you are pushing all the values foward, not just adding one to the end.

---

Assuming you implement this like a linked list, you are not pushing anything forward. You change the last entries pointer from NULL to the address of the new element. Therefore you add something to the end.

Assuming you implement it as an array, you are not pushing anything forward. You increase the size of the array and copy the new data into the arrayindex of the previous size.
In contrary, you are pushing something when you remove an element from the ... what's it? a stack?... the stack because all array entries have to be moved one index down, second entry overwrites first index which gets dumped to result first, last index is freed. Ok, very slow thing to do.

So, I gathered all my limited knowledge. I mean, I could have misunderstood something, so don't take my post serious if it doesn't make any sense to you.

What I mean is that is how it acts...assume you push the number 1 into the stack and then the number 2:

Code:

---

-->2-->1------>

---

edit: I really don't know how a queue is implemented I'm just going with what I know of the STL queue...

Well, ... no.

Imagine a queue of 100 people. If a new person arrives, does that mean everybody moves up to the position of the guy/girl in front of him/herself? I don't think so. Instead that person makes the queue longer.

Pushing happens as soon as the happy first person in the queue receives all the hamburgers - and all that other stuff that makes people fat - and drives out of the MacDrive. The new number one in the queue pushes on to the place of the previous number one and everybody else does the same.

I got hungry.... aww..

Imagine a queue of 100 people. If a new person arrives, does that mean everybody moves up to the position of the guy/girl in front of him/herself? I don't think so. Instead that person makes the queue longer.

Good point.

From what Cat said, to retrieve the first object in the queue, it appears we should do something like this?

T& get_first();
//Gets a reference to the object at the front of the queue, but
//does nothing to the queue
//Access: public
//Parameters: none
//Returns: A reference to the first object thereby avoiding the object's
//copy constructor and preventing the operation from failing

void discard_first()
// Removes the first item from the queue and discards it
// Access : public member
// Parameters: None
// Returns: void

...how should we handle a full queue? My first thought was to throw an exception derived from std::logic_error, but I'd like to hear other ideas.

How about returning a bool from the append() function to signal success or failure? There could be a member variable int max that stores the optional max value, and there could be a member variable int count that keeps the count of how many objects are in the queue. Before append()'ing any object the function could check to see if count < max, if it is then append() can return true, and if isn't then append() can return false. Then the user can decide what to do if there isn't anymore room?

I agree. No sense in throwing an exception over a full queue. I would say that by default, the queue should allow an unlimited number of items unless a limit is set. So here are some additions:

Code:

---

template <class T>
struct queue {
~queue();
queue();
queue(const queue & replicate);
template <class Iter>
queue(const Iter & _begin, const Iter & _end);
queue & copy(const queue & replicate);
// fill with values from another type of container:
template <class Iter>
queue & copy(const Iter & _begin, const Iter & _end);
// returns a dynamically allocated copy:
queue * clone() const;
T & front() const;
T & back() const;
T & push(const T & value, bool then_pop = true);
void pop();
unsigned count() const;
bool empty() const;
// full() only returns true if max(unsigned) was set:
bool full() const;
// max returns zero if unlimited, otherwise...
unsigned max() const;
void max(unsigned set);
};

---

The instructions seem to imply a fixed length queue, but having that length set at runtime. I don't like this at all. If the length can be set at runtime then the only viable option on a "full" queue is to expand. If we want constant time push this can be done. If we shift to a fixed length compile time queue then we have something interesting (and distinct from stl) . In this case push/append can fail. There are two viable options here, throwing an exception cannot be ignored like a return code, and makes it very easy to prevent any loss of data. The other option is to victimize the oldest element. I think we should try to do both.

void push(const T &); // throws
void forced_push(const T &); // best effort

We have a similar problem with access on an empty queue. I tend to think throwing is the more appropriate action here. However, an inline return a reference, undefined on empty is very fast and easy. The stl tends to do this. Providing both is probably the best option.

T & oldest(); // undefined on empty
T & get_oldest(); // checks and throws

The instructions seem to imply a fixed length queue, but having that length set at runtime.

I disagree with that. I think the instructions say the opposite: the length is not fixed unless a maximum size is specified:

Quote:

---

This Queue class will also allow us to optionally specify a maximum capacity of the Queue, after which no new data may be queued at the tail until data is removed from the head.

---

I interpret that to mean the default will be: not fixed in size.

If the length can be set at runtime then the only viable option on a "full" queue is to expand.

I don't see how you draw that conclusion? Why must the queue expand? Why can't append() return false or throw an exception? At runtime the operator new could return a pointer to our queue object. That object could have pointers to type T(the type of the object to be queued) as data members. Why can't those pointers be used to link an infinite number of T objects together?

In fact, it seems to me that we wouldn't necessarily have to wait to use new to create the queue. At runtime, we could just read in the data member max_size for the queue object.

Quote:

---

Originally posted by 7stud

I interpret that to mean the default will be: not fixed in size.

---

I guess I could see that, it just seems like odd behavior to me. I read that as having a default, fixed size, or even that the size would be a paramiter to the constructor, just with a default value. It seems strange to start with a potentally infinate flexable object and then, optionally, to limit it.

Quote:

---

me:
If the length can be set at runtime then the only viable option on a "full" queue is to expand.
7stud:
I don't see how you draw that conclusion? Why must the queue expand? Why can't append() return false or throw an exception?

---

It's not so much that it must expand, it's just that it seems to me that the first resposibily of the container is to not loose data, and if we have already changed the size once at runtime then it's better to do so again than complain to the user.

Quote:

---

At runtime the operator new could return a pointer to our queue object. That object could have pointers to type T(the type of the object to be queued) as data members. Why can't those pointers be used to link an infinite number of T objects together?

---

I don't quite follow this, It should be quite trivial to have queues of queues or queues of pointers to queues and so forth. We haven't gotten into requrements for T, that will be a result of the implementation. I figure copy-constructable certainly, possibly assignable.

Quote:

---

In fact, it seems to me that we wouldn't necessarily have to wait to use new to create the queue. At runtime, we could just read in the data member max_size for the queue object.

---

This is what seems silly to me, a logical implementation would be to have a real append operation that always (sans memory exaustion) works, a max_size variable along with a size, and a flag or sentinel value to tell if we should bother paying attention to the max_size variable. If the user is concerned about the size, the user should check it before appending. A compile time fixed size queue is usefull because it doesn't need to use the heap at all, and we give the compiler aditional freedoms to make things faster still.

It seems strange to start with a potentally infinate flexable object and then, optionally, to limit it.

I don't know anything about optimization, but it seems reasonable to me that if you allocate all the memory up front for a fixed size queue, it could be more efficient than allocating memory object by object.

It's not so much that it must expand, it's just that it seems to me that the first resposibily of the container is to not loose data..

Yes, I agree with that. But, if an append() fails, the calling function would still have either a pointer to the object or a reference to the object name wouldn't it? So, I'm not sure how data would be lost in the case of a failed append().

A compile time fixed size queue is usefull because it doesn't need to use the heap at all, and we give the compiler aditional freedoms to make things faster still.

That seems to contradict your first concern that it doesn't make sense to start with an infinite queue and then optionally limit its size. The motivation would be efficiency: it's more efficient to have a fixed queue.

Quote:

---

Originally posted by 7stud
I don't know anything about optimization, but it seems reasonable to me that if you allocate all the memory up front for a fixed size queue, it could be more efficient than allocating memory object by object.

---

I usually allocate memory in chunks. You just need one more if-check per append/push command and a realloc every chunksize elements. That would make an append/push look like....

Code:

---

increase [number of elements] by 1

if [size of queue] equals [number of elements] -1 then
  increase [size of queue] by [chunksize]
  re-allocate memory for [size of queue] [elements]

assign appended data to [element] at [number of elements] -1

---

I can't see any reason, not to increase the size of the queue, unless you don't want to use dynamic memory at all.
As soon as you use dynamic memory, you could as well set chunksize to what was previously the number of maximum elements and the code wouldn't be any slower - except for the case where you hit the maximum number of elements. But now instead of raising an exception (or throw as C++ler's seem to say), you would just realloc once. So it's only slower for the one single element that exceed the "maximum number of elements" which is called "chunksize" in this model.

Quote:

---

Originally posted by 7stud

I don't know anything about optimization, but it seems reasonable to me that if you allocate all the memory up front for a fixed size queue, it could be more efficient than allocating memory object by object.

[snip]
me:
A compile time fixed size queue is usefull because it doesn't need to use the heap at all, and we give the compiler aditional freedoms to make things faster still.

That seems to contradict your first concern that it doesn't make sense to start with an infinite queue and then optionally limit its size. The motivation would be efficiency: it's more efficient to have a fixed queue.

---

Consider std::vector and reserve. If you reserve enough space than push_back's will be efficent(not perform any new allocations, not move existing objects), but a push_back on a "full" vector is largely a non-event. To the users outside vector it was just an unusually slow operation (iterators are now invalidated). I suppose it's mildly usefull to force the user to manage these expantion events, it just seems like haveing an automatic transmition with a clutch thrown in, but leaving the tourque converter ineffecencys. With a compile time fixed length queue our space is allocated the easy way with

Code:

---

template<class T, int CAP>
...
    T data[CAP];
// or the hard, but cooler default ctor less
    union dummy_u
    {
        char data_store[ sizeof(T) * CAP ];
        int dummy_align;
    } dummy_ ;
// and make use of placement new.

---

There are some boost type traits that can make for a better alignment scheme, but this gives us effectively the effecencies of a static boring old fasioned array, with queue semantics and vector-like ease and safety.

I really like the idea of a collaborative program, but I think we're reinventing the wheel here. I suggest that we write a program and not just a class so that we create a program that might actually do something, not something useful mind you, but at least something. At this current point, it looks like we're going to end up with a header file that will likely never be as good as the STL and just sits there.

I acknowledge that this project is probably reinventing the wheel, given that the STL queue class is available, but as a learning excercize it is similar to writing your own list class from scratch or your own String class from scratch or your own bubble sort function etc. Those who feel comfortable writing their own STL class can act as proctors if they wish.

The phrase "optionally specify a maximum size" seems like the perfect out. Have the default behaviour be a memory dependent size, but allow the user to specify a maximum size if desired by using a parameter in a non-default constructor. If maximum size is desired a variable can be set to that size, otherwise it could be set to -1 by default, so it acts as a flag. An initial amount of memory can be allocated by the constructor and if additional memory is desired/required additional blocks of memory can be added. If a maximal amount of memory is indicated by the user, the program can notify the user when maximal memory has been acheived and the user can determine how much of the queue to empty and what to do with the information removed from the queue. No additional information would be added to the queue as long as memory was full.

The decision now would seem to be whether to build the queue on an array/vector, on a list, or on a dequeue (which in turn is built on an array/vector or list)? The array goes nicely with a defined amount of memory, either as the initial allocation from the default behaviour or as the maximal amount specified by the user. The drawback is the (potential) need to shift contents forward when popping the "oldest" item from the queue and the need to copy existing data in the queue to a new queue if the current queue needs to expand in size. The list seems like a viable alternative in that you can shift the front of the queue by just changing the designated pointer to the head of the list, without need for shifting data and you don't need to monitor size (except for RAM size limitations) UNLESS there is a maximal size restriction imposed by the user. Monkeying with pointers can always be challenge, and some may want to avoid doing so if possible. Using an existing list class (STL list class comes to mind), if allowable under the guidelines would minimize the need for extensive pointer/iterator usage, but not eliminate it. For that matter, pointer/iterator syntax is going to be needed for the array version sooner or later anyway, in all probability, so why not jump in?

To the list supplied by Sebastiani I would add:

//iterators/pointers to the beginning and end values of the queue
iterator begin();
iterator end();

and maybe:

//current capacity (potential number of items of type T) of queue
long capacity();

I would opt with using a list for the following reasons:

1) Easier to shift contents.

2) Iterators never invalidated unless the object was shifted out. That is, resizing a vector by definition invalidates iterators, not so with a list.

3) I have a fetish for linked lists. :D

So...who's going to start with the coding?

I'll start:

Code:

---

class CQueue
{
public:
    // other methods
    int      GetCount()                        { return count; }
    bool        IsEmpty();

private:
    // other vars
    int      count;
};

bool CQueue::IsEmpty()
{
        bool empty;

        if(count)
                empty = false;
        else
                empty = true;

        return empty;
}

---

As you can no doubt tell the count variable will be incremented per push and decremented per pop, for whatever reason the user might want to know how many objects are in the queue, so GetCount simply returns count, and IsEmpty() will return true if queue is empty (i.e. count is 0), count should be set to 0 in CQueue's constructor.

I took the easy ones, I hope that's what you're looking for.

Okay, good start, but an easier way to phrase it would be:

Code:

---

bool CQueue::IsEmpty()
{
 return count == 0;
}

---

How would you implement IsFull() then?

Well it depends how we're controlling the maximum, if it's just a variable then just return true if count == max, false otherwise.

Btw I didn't know you could return like that from IsEmpty(), that's cool.

Quote:

---

Originally posted by HybridM
Btw I didn't know you could return like that from IsEmpty(), that's cool.

---

return (count == 0); would probably be easier to read. Basically (count == 0) can either be true or false which will then be returned by return bool;

Code:

---

class CQueue
{
  public:
    CQueue()                        { count= 0; count_max= 0; };

    // other methods
    int                GetCount()        { return count; };
    bool        IsEmpty()        { return (count == 0); };
    bool        IsFull()        { return (count == count_max); };

  private:
    // other vars
    int        count;
    int        count_max;       
};

---

Maybe add a non default constructor for limited size?

Okay, so what is the underlying data structure going to be, then?

How would you implement Pop(), provided it was implemented:

1) on a list?

2) on an array?

Actually, I think we have not decided about this yet. Maybe it's Cat's turn to say something ;)

On a sidenote, my personal opinion is that push and pop are definetly the wrong names. This is not a stack where something can be pushed into and all previous elements will change their "position" in the stack (i.e. one rank up), where stuff get's pushed in and popped out at the same "side", this is a queue where data get's added to the end and taken from the beginning. (At least if I understood the excercise ;) )

Try to push somebody at the end of a reallife queue. Could be funny. For a second or two...

OK, feel free to use something else, but this is how I implemented Pop in my queue, I called it "Serve()" as it fits the queue theme better.

Code:

---

int CQueue::Serve(bool Remove)
{
        int Value;
        Node *Temp;

        if(!IsEmpty())
        {
                Value = Front->GetData();
                if(Remove)
                {
                        --count;
                        Temp = Front;
                        if(count)
                        {
                                Front = Front->Next;
                        }
                        delete Temp;
                }
        }
        else
                cout << "Unable to serve, queue is empty." << endl;

        return Value;
}

---

This may need some explanation, so here goes...
The Remove boolean is there so the user can choose whether they wish to peek at the front of the queue (not remove) or remove as well as get value.

A temporary Node is created so as to allow memory deallocation, value is assigned the data of the front node, so as to be returned, front is assigned to the node behind it, unless it is the last node in the queue. What used to be the front is then deleted through temp, and value is returned.

I think that's all

It would also be nice to have two (or more) different threads for this project: one for software engineers who just want to post the code and be done with everything, and one for those that want to learn something and maybe go at a slower pace.

On a sidenote, my personal opinion is that push and pop are definetly the wrong names.

Agreed.

Quote:

---

Originally posted by Cat
At this point, we're not even thinking about private data members or private methods, just the public and protected interfaces.

---

I'm enjoying following this process and seeing people's ideas on how to implement this queue. Just wondering, did everybody agree on an interface? Or maybe the interface cannot be agreed upon without making decisions about implementation.

I think a forum is a difficult medium to conduct something like this, someone should do a simple website where people can submit their ideas, perhaps cat (or someone else if cat doesn't have the time) could screen them and launch votes to decide which we go with. On the same page we could also keep an up to date version of the project so far.

It could be very cool, and could set cprogramming.com apart from the plethora of other boards. :D

Quote:

---

Originally posted by HybridM
It could be very cool, and could set cprogramming.com apart from the plethora of other boards. :D

---

You mean like defining new standards, reaching out for new worlds ...errr..? :D

The topic was "C++ Guided Design Programming Challenge" and I think we should stick to that. If Cat's project is successful, it can still be extended.

Quote:

---

You mean like defining new standards, reaching out for new worlds ...errr..?

---

Hmm..no.

What I meant was it would make the whole experience easier for everyone and overall more enjoyable. It was a suggestion for if this sort of thing becomes regular.

I think this is what we have so far:

Queue();
// Creates an empty Queue object that has no capacity specified.
// Access : public member
// Parameters: None
// Returns: N/A

Note that in the debate over whether the default size of the queue was intended to be unlimited or not, we overlooked the default constructor description:

"Creates an empty Queue object that has no capacity specified. "

I know grib and others argued against this, but the "client" has asked for that. Is this something in the real world where we would go back to the "client" and tell them the requirements they have imposed are not the best way to implement something and suggest they change the requirements, or are we to treat the requirements as set in stone? Since apparently we don't have any way to contact the client, I vote it's set in stone.
-------------------

bool append(T);
//adds value T to the end of queue, if queue size not at max size,
//and increments private variable member itsSize by one;
//if size is already at max, then returns false
//and doesn't add current item to queue

T& get_first();
//Gets a reference to the object at the front of the queue, but
//does nothing to the queue
//Access: public
//Parameters: none
//Returns: A reference to the first object thereby avoiding the object's
//copy constructor and preventing the operation from failing

void discard_first()
// Removes the first item from the queue and discards it
// Access : public member
// Parameters: None
// Returns: void

OR

void push(const T &); // throws
void forced_push(const T &); // best effort

T & oldest(); // undefined on empty
T & get_oldest(); // checks and throws
---------------------------

int size();
//returns the number of items in the queue;
//access: public

int itsSize;
//holds the current number of items in the queue
//access: private

//iterators/pointers to the beginning and end values of the queue
iterator begin();
iterator end();

and maybe:

//current capacity (potential number of items of type T) of queue
long capacity();
-------

1)We still need to decide if we want to throw exceptions when the queue is full. I don't really understand the argument for throwing exceptions. Is a full queue an exceptional event? If we decide it is, how will the exception be handled--what happens after the exception is thrown?

3)Do we need a non-default constructor i.e. where a maximum size can be specified?

2)Do we need a non-default destructor?

Also, it might be helpful to reread the initial problem statement from time to time. This is some of what Cat had to say:

Quote:

---

...the problem statement and the first design step are below. Once I think this step has been completed successfully, the next gets posted.

...List methods that we will need or want to include in our Queue class. Don't worry about how we will implement them, just give their signatures and a brief description (one to four lines describing what the function does). Also include relevant information about the method.

---

I think it's safe to assume since Cat hasn't posted anything, we are not done with the first design step, and it's premature to start posting code.

Good work, 7Stud. Some additional thoughts, too:

1) By default, the queue should have no maximum size. Allow this to be reversable, such that a user can set a limit, unset it, set it, ad infinitum.

2) Exceptions are for more serious errors than full/empty queues.
For these cases, either let the user crash, as happens with normal user errors (ie: out-of-bounds accesses, etc) OR simply have the ADT exhibit 'no-op' behaviour (ie: nothing happens at all).

Let's say the user tries to get_front(), but the queue is empty.
To implement the first sort of behaviour (crash 'n burn), just return a temporary object. Otherwise, the queue has a member of type T called 'dummy' that get's returned when that happens, and no harm is done.


>> Do we need a non-default destructor?

Absolutely, how else can we guarantee proper cleanup?

I'm down with the limitable infinite queue now. I was working on a static_queue, where the storage would be a compile-time constant array, but getting it to be faster than deque is going to be more work than I expected, and insuring proper alignment for placement new (without resorting to boost) is more awkward than I want to deal with right now. If you're interested in where I was going with this have a look at boost's optional class, very clever way to get the space for an object and delay constructing it until absolutely necessary.

As to the general issue of throwing, I look at this as a question of how bad would ignoring the issue be? The standard streams have all sorts of things that they want to tell you, no-one pays any attention to them. How many threads have we seen where the problem is that the file was never opened in the first place(it was in another directory etc..)? You shouldn't rely on exceptions as the normal way of discovering that a queue is full, but it might be a good way to encourage users to check first. It does add a lot of bloat, not just for the throw, but often checking the same thing twice, once before the call and in the method just before you do anything. I can also sympathize with the view that if you wanted this sort of safety you would be using Ada.

I've confused the matter enough, here's my candidate for a final interface.

Code:

---

template<class T>
class queue {
public:
    typedef T value_type;    // comes in handy
    typedef size_t size_type; // future-proofing, clarity
 
    queue();          // infinite
    queue(size_type); // limited

    bool limited() const;    // true iff limit exists.
    void unlimit();          // removes any limit.
    void limit(size_type);  // sets new maximum number of elements
    size_type limit() const; // maximum number of elements if limited,
                            // numeric_limits<size_type>.max() if unlimited
    size_type size() const;  // number of elements in queue
    bool empty() const;      // size() == 0
    bool full() const;      // limited() && size() == limit()

    bool append(const T &); // no-ops & returns false if full.
    void discard();        // removes oldest element.
    T & oldest();          // access oldest element, undefined if empty
};

---

I've gone with limit, as opposed to capacity, as capacity already has semantics in the stl, and our behavior is different. front also has semantics in stl, that matches our behavior here, but if we want to use front it should probably be just front (not get_front) to match the stl and discard_front should also probably be pop_front for the same reasons. However, we can't use push_back because we are very different from the stl here, so append is the logical choice. Once append is used it makes sense to define our own words for access and removal.

There is one more outstanding issue. What should happen if we limit a queue to have fewer elements than it already has? I think that we should probably remove the most recently added elements until we are under the new limit, the users can remove the oldest themselves.

good summary 7Stud, even if I did pick a lot of nits, I just like arguing these things.