Re: [boost] Proposed container: cdeque

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) 
capacity
     cdeque       (size_t n);  // n specifies initial size, initialized 
with T()

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:  
vector<bool>.

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.

-Howard

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
>structure's lifetime.
>
>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
>them:
>
>	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
>average user.
>
>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
>(unbounded) versions.