Re: [boost] Proposed container: cdeque

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2001-01-12 14:07:59

wb_at_[hidden] wrote on 1/12/2001 12:11 PM

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

Agreed.

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

I read this and understand what you are saying.  But your code examples 
are confusing me again.  Below you use the constructor to seemingly set 
the initial capacity and resize to seemingly grow the capacity.

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

But std::semantics have the constructor(size_t) set the size().  
capacity() is left unspecified, but is commonly set equal to size().  And 
resize(size_t), usually changes size(), and perhaps indirectly 
capacity().  If at capacity, and resize'ing up, myDeque.full() may well 
still be true after the resize.  I would better understand:

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

>Regarding container growth, I do see a discrepancy in views, but I
>firmly believe resolution is possible.  ... Thus, my view of
>bounded_deque<> does not encompass compile-time sizing.

Ok.

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

Good point.  It occurs to me that either bounded_deque or cdeque could be 
the wrapper:

template <class T, class Container = cdeque<T> >
class bounded
{
public:
        typedef typename Container::value_type            value_type;
        typedef typename Container::size_type             size_type;
        typedef          Container                        container_type;

        explicit bounded(size_type x, const value_type& t = T()) : c_(x, t) {}
        // ...

        void push_front(const value_type& x)
        {
                if (c_.size() == c_.capacity())
                        throw std::overflow_error("bounded capacity exceeded");
                c_.push_front(x);
        }
// ...
private:
        Container c_;
};

So I find myself contemplating if one way is better than the other.

Does a bounded_vector sound attractive?  bounded_string?

Unfortunately the bounded wrapper won't work with std::deque as there is 
no public interface to be able to anticipate the growth of another 
internal buffer.  But it would work with vector, string or cdeque. (with 
vector and string you just couldn't instantiate the push/pop_front() 
methods)

Having cdeque be the wrapper has some efficiency draw backs in the insert 
methods.  Consider:

     template <class T, class Allocator>
     typename cdeque<T, Allocator>::iterator
     cdeque<T, Allocator>::insert(iterator position, const T& x)
     {
         if (underlyingBoundedDeque.full())
            
underlyingBoundedDeque.reserve(2*underlyingBoundedDeque.capacity());
         return underlyingBoundedDeque.insert(position, x);
     }

vs:

    template <class T, class Allocator>
    typename bounded_deque <T, Allocator>::iterator
    bounded_deque<T, Allocator>::insert(iterator position, const T& x)
    {
        if ( underlyingcdeque.size() == underlyingcdeque.capacity() )
           throw std::overflow_error("bounded capacity exceeded");
        return underlyingcdeque.insert(position, x);
    }

Looking at cdeque<T>::insert, if capacity() is about to be exceeded, 
reserve is called which copies the existing elements to the new larger 
buffer.  And then those elements are scooted around in the new buffer to 
make room for the new element by underlyingBoundedDeque.insert.  If 
cdeque had a "native" insert, it would copy the old elements to the new 
buffer in the right place to avoid having to move them twice.

Ways to fix the efficiency problem:

     1.  Add more interface to bounded_deque such as 
insert_with_implicit_grow.
     2.  Put bounded_deque at the wrapper level.
     3.  Others?

Other problems (either way)?

-Howard