Boost logo

Boost :

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.


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


>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
        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");
// ...
        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()

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())
         return underlyingBoundedDeque.insert(position, x);


    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
     2. Put bounded_deque at the wrapper level.
     3. Others?

Other problems (either way)?


Boost list run by bdawes at, gregod at, cpdaniel at, john at