From: Howard Hinnant (hinnant_at_[hidden])
Date: 2001-01-11 13:28:22
This seems like a good proposal. But it also seems sufficiently
different from cdeque that I think it should be a different proposal.
Even with option 1 (silently grow), the semantics of the constructor that
takes a size_t are very different:
bounded_deque(size_t n); // n specifies initial (or permanent)
cdeque (size_t n); // n specifies initial size, initialized
In the applications that I have used cdeque to date, capping the max size
would be unacceptable. And at the same time, starting with a large
capacity would likely mean wasted storage.
It seems to me that an important characteristic of bounded_deque is
static sizing. Perhaps it would be appropriate to template on the max
capacity. Specializations could be made for small buffers that would be
very fast and efficient. The std::lib has an (almost) example of this:
bitset. And we have bitset's dynamically sized counterpart:
Lumping cdeque and bounded_deque into the same class I think might do a
disservice to both. There is a fair amount of logic in cdeque::insert
and cdeque::assign that deal with the case when capacity is about to be
exceeded. It would be a shame to have bounded_deque pay for this
unneeded code. And at the same time, it would seem a shame to give a
dynamically sized container like cdeque an interface that was not very
similar to the existing standard dynamically sized containers.
wb_at_[hidden] wrote on 1/11/2001 10:18 AM
>When I taught undergraduate computer science, we routinely exposed our
>sophomores (in the context of a data structures course, typically) to
>the notion of a "bounded" linear container. This encompassed stacks
>and queues as well as the more general deque, and was based on the
>observation that there are applications that can reliably predict a
>maximum-usage (typically, worst-case) scenario for such a structure and
>hence rarely, if ever, need to adjust memory usage during the
>Internally, such containers typically exhibited the "wraparound" or
>"circular" usage pattern described below.
>I have long believed that a family of bounded linear containers would
>be a useful complement to the unbounded linear containers now provided
>in the C++ library. Therefore, I strongly favor this proposal, and
>respectfully recommend that the name "bounded" be applied to identify
> bounded_deque<myType> myDeque( MAX_NEEDED );
> bounded_queue<myType> myQueue( MAX_NEEDED );
> bounded_stack<myType> myStack( MAX_NEEDED );
> // ...
> myQueue.reserve( NEW_BOUND ); // if needed
>I prefer "bounded" to either "circular" or "wraparound" because it
>describes the external behavior; the other terms better describe some
>implementation details, knowledge of which would not materially help an
>At issue, perhaps, are such containers' behavior at the bound (i.e.,
>when "full"). There appear to be several useful possibilities:
> 1) Let the containers (silently) grow beyond the stated bound as
> needed. This mimics the unbounded containers' behavior.
> 2) Throw an exception under the theory that the user has violated
> his own bounds specification and it is useful to be so notified.
> 3) Let the policy (e.g., (1) or (2) above) be specified by the user
> via a member function or template argument or ....
>My own preference is for policy (2). I have two primary reasons for
>this recommendation. First, I believe it leads to constant (not
>amortized constant) time complexity for all the insertion, deletion,
>and access functions, a most useful guarantee. Second, I believe this
>behavior will delineate most clearly, for potential users, the
>distinction between these containers and the corresponding standard
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk