From: AlisdairM - BTInternet (AlisdairM_at_[hidden])
Date: 2000-10-30 18:16:55
I am looking to implement what I am calling a 'fixed-length' queue. If
there is something similar to what I describe below in the public domain,
please let me know. I haven't found it, but wouldn't pretend to know the
places to check for an exhaustive search.
Likewise, I am new to boost (warning, many newbie etiquete errors to
correct!) so not sure of the correct way to go about canvassing
interest/opinion. I'm sure you will put me straight :¬ )
The proposed class is for a fixed-length queue, such that pushing new values
when the queue is 'full' automatically pops the oldest value. A typical use
would be in some data-monitoring application that wants to keep a 10-minute
buffer of data. New data is always added without the need to 'house-clean'
the old. Another use might be scrolling around a zoomed range in a
scrollable window, where the queue 'length' corresponds the size of the
The container is easily implemented by using a standard array, and
maintaining an internal iterator for the current position. The internal
data would be accessed via iterators in the familiar STL fashion. begin/end
point to the same element, but end has an internal 'wrapped' flag to
indicate it has iterated past the end of the array and started again.
The most efficient implementation would have a statically sized array, where
the array size is an integer paramater of the template. A more dynamic
variation to allow run-time sizing of the array would be better based on
std::vector, with similar implementation details.
I have a simple implementation of the array-based version working to play
around with, and am still playing around with some design decisions that cut
to the heart of its expected behaviour, which is why I am canvasing for
opinions now. It is still a way out from being ready for submission!
I suspect this would better fit in as a part of a larger existing part of
the boost library (but which?) and have a few simple questions to resolve
(before getting to the hard ones!)
i/ Is the name 'queue' approriate, as the whole idea is to allow iteration
of the whole interval, whereas a queue traditionally has a front and a back,
but no knowledge of what lies between.
ii/ Should the iterators point to an absolute place in the array, so that
after a push() they still point to the same element (unless it is
overwritten) or point to the same 'offset' so that taking a copy of
(begin()+3) will always point to the 3rd element back from the front of the
queue. The former feels more conventional, but the latter seems very
useful. Should I implement two kinds of iterator, or is this even more
Finally, where do I go next with this? :¬ )
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk