C++ Guided Design Programming Challenge

**darksaidin** · 08-25-2003

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.

**JaWiB** · 08-25-2003

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

**darksaidin** · 08-25-2003

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

**7stud** · 08-25-2003

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?

**Sebastiani** · 08-26-2003

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

**grib** · 08-26-2003

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

**7stud** · 08-26-2003

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:

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.

**grib** · 08-26-2003

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.

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.

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.

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.

**7stud** · 08-27-2003

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.

**darksaidin** · 08-27-2003

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.

**grib** · 08-27-2003

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.

**joshdick** · 08-27-2003

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.

**elad** · 08-28-2003

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?

**elad** · 08-28-2003

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

**Sebastiani** · 08-28-2003

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.

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