Re: [boost] cyclic buffer

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2002-10-01 13:14:26

On Tuesday, October 1, 2002, at 01:11  PM, Thomas Wenisch wrote:

> I am also interested in a cyclic container or cyclic buffer. In
> particular, I have use for a container with deque-like interface which 
> has
> fixed capacity, but for which insertion at the head or the tail does
> not invalidate any iterators into the container (ie a circular
> buffer).  Is this what you are describing?

Fwiw, Metrowerks has a container similar to this.  The capacity is not 
fixed, but grows like vector (and has a reserve and capacity like 
vector).  But otherwise it looks like a deque, except for invalidating 
pointers during a realloc.

You could turn it in to a fixed capacity circular buffer with an 
allocator that would only allocate once.

-Howard

#include <cstddef>
#include <new>
#include <limits>
#include <memory>

template <class T>
class alloc_once
{
public:
    typedef std::size_t    size_type;
    typedef std::ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U> struct rebind { typedef alloc_once<U> other; };

    explicit alloc_once() throw() : allocated_(false) {}
    alloc_once(const alloc_once& a) throw() : allocated_(a.allocated_) {}
    template <class U>
       alloc_once(const alloc_once<U>& a) throw() : 
allocated_(a.allocated_) {}
    ~alloc_once() throw() {}
    pointer address(reference x) const {return &x;}
    const_pointer address(const_reference x) const {return &x;}
    pointer   allocate(size_type n, const void* = 0);
    void deallocate(pointer p, size_type)
       {::operator delete((void*)p);}
    size_type max_size() const throw()
       {return std::numeric_limits<size_type>::max() / sizeof(T);}
    void construct(pointer p, const T& val) {::new((void*)p) T(val);}
    void destroy(pointer p) {p->~T();}
    friend bool operator == (const alloc_once&, const alloc_once&) 
{return true;}
    friend bool operator != (const alloc_once&, const alloc_once&) 
{return false;}

private:
    bool allocated_;
};

template <class T>
typename alloc_once<T>::pointer
alloc_once<T>::allocate(size_type n, const void*)
{
    if (allocated_)
       throw std::bad_alloc();
    allocated_ = true;
    return static_cast<pointer>(::operator new(n * sizeof(T)));
}

#include <cdeque>
#include <iostream>

int main()
{
    try
    {
       typedef Metrowerks::cdeque<int,  alloc_once<int> > CircularBuffer;
       CircularBuffer c;
       c.reserve(10);
       for (int i = 0; i < 10; ++i)
          if (i % 2)
             c.push_front(i);
          else
             c.push_back(i);
    } catch (std::exception& e)
    {
       std::cout << e.what() << '\n';
       return 1;
    }
    std::cout << "done\n";
}