Boost logo

Boost :

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.


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

template <class T>
class alloc_once
    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;}

    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()
       typedef Metrowerks::cdeque<int, alloc_once<int> > CircularBuffer;
       CircularBuffer c;
       for (int i = 0; i < 10; ++i)
          if (i % 2)
    } catch (std::exception& e)
       std::cout << e.what() << '\n';
       return 1;
    std::cout << "done\n";

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