Re: [boost] Proposed container: cdeque

From: wb_at_[hidden]
Date: 2001-01-12 12:11:36

Thank you (and other posters) for your gracious reception and
thoughtful consideration of my comments regarding bounded_deque<>,
etc.

I truly had not intended my remarks to be construed as a new proposal;
I believed, rather, that I was offering an endorsement of the cdeque
idea and attaching a suggestion.

I still believe, frankly, that our respective thoughts are not so
very widely separated.  The main distinctions appear to be in
    1) container initialization semantics, and
    2) container growth policy.

With respect to the former, I see no issue at all.  Initializing a
bounded_deque<T> with T() by default seems entirely appropriate and
certainly matches the std::deque<> semantics.  I did not intend to
suggest otherwise; a constructor with such signature as
    bounded_deque<T>::bounded_deque( size_t, T = T() )
seems just fine, for example, as does a similar resize() member.  As in
the case of std::vector<>, both resize() and reserve() functions can be
provided, thus giving users a choice.

Regarding container growth, I do see a discrepancy in views, but I
firmly believe resolution is possible.  It seems to me to be an issue
of implicit vs. explicit capacity extension, the latter being my
preference.  I'd like to try hard to reconcile these, because I believe
it is not a good idea to offer users a choice among three flavors of
deques.  It seems that we should be able to make do with two, one of
which has already been standardized.

A bounded_deque<>'s (internal) test for a full container, I believe,
can be as simple as the O(1) predicate
    front == next(rear)
where next() wraps around as in something like
    (1+rear) % (stored_capacity+1)
This of course depends upon other implementation choices, but such
relative simplicity seems desirable and attainable.  Encapsulating this
predicate yields the public member function full() that users can
employ, as in:

    bounded_deque<myT>  myDeque( INITIAL_N );
    //...
    if ( myDeque.full() )
      myDeque.resize( NEW_N );

Thus, my view of bounded_deque<> does not encompass compile-time
sizing.  (That would lead to such questions as whether it is meaningful
to compare a bounded_deque<10,int> with a bounded_deque<20,int>, and I
prefer to avoid those kinds of discussions.)  I simply don't want the
capacity to grow without my intervention.  That said, it seems that the
cdeque<> concept of wraparound usage with implicit growth can be
implemented as an adaptor/wrapper on bounded_deque<>.  For example, we
could have:

    template< class T >
    void  cdeque<T>::push_back( T const & t )  {

      if ( underlyingBoundedDeque.full() )
        underlyingBoundedDeque.resize( /*as desired*/ );

      underlyingBoundedDeque.push_back( t );

    }

A different wrapper/adaptor on bounded_deque<> might provide the LRU
semantics another poster has suggested, but I have not given this any
detailed thought at all.

Please understand that it is not my wish to be divisive.  I do believe,
however, that it is work making every attempt to avoid proliferation of
containers.

Thanks again.

        - WEB

Howard Hinnant <hinnant_at_[hidden]> wrote on Thu Jan 11 12:28:22 2001:

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