Boost logo

Boost :

From: Greg Colvin (greg_at_[hidden])
Date: 2001-01-10 20:04:13


I have also found circular buffers to be very useful, and
surprisingly difficult to code correctly. So I like this
class, but hate the name.

----- Original Message -----
From: Howard Hinnant <hinnant_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Wednesday, January 10, 2001 5:36 PM
Subject: [boost] Proposed container: cdeque

> There have been a lot of proposals lately, which makes me hesitate to
> propose yet something else. But on the other hand, I've found this
> container very handy.
>
> cdeque is probably a terrible name (and the name is not important to me).
> I'm proposing a circular array. This class is a cross between
> std::vector and std::deque. It is implemented with continuous memory
> like vector, and also has reserve() and capacity() like vector. But at
> the same time, it has an amitorized constant push/pop_front(). It does
> this by mapping the iterator and operator[] to wrap the end of the
> internal array back around to the front. And thus the front() of the
> container does not necessarily coincide with the start of the internal
> contiguous array.
>
> Some might wonder why we just don't name this beast std::deque. The
> reason is that a std::deque requires that references and pointers into
> the container remain valid during a push_front() and push_back(). cdeque
> lacks this guarantee as it might need to reallocate its capacity (just as
> vector does).
>
> What advantage does cdeque have over std::deque? Simplicity.
>
> The overhead of cdeque can be as low as 4 words (vector overhead is
> typically only 3 words). The Metrowerks overhead for std::deque is 7
> words (for an empty deque). And that has been highly optimized from a
> previous value of 12 words. I'm not sure what the overhead for other
> implementations of std::deque is, but I doubt that it gets much below 7
> words. Is overhead important? You bet it is when you start talking
> about containers of containers.
>
> This simplicity also translates into smaller and faster code. If you
> need push_front and random access iteration, cdeque can often fit the
> bill better than std::deque. Indeed, cdeque is an excellent container
> for std::queue.
>
> It turns out that cdeque is also an ideal container for the "map" that
> std::deque holds internally. In fact this is why I was originally
> motivated to implement it in the Metrowerks lib. I think a circular
> array might better fit many applications than std::deque. It is not
> often that one requires outstanding pointers and references to remain
> valid during push_front/back. And when this is a requirement, often
> std::list is a better choice (iterators/pointers/references remain valid
> during any insert).
>
> Below is a synopsis of cdeque. The semantics for each method, except for
> what I've outlined above, can be taken from std::vector and std::deque.
>
> Comments and opinions?
>
> -Howard
>
> template <class T, class Allocator = std::allocator<T> >
> class cdeque
> {
> public:
> // types:
> typedef typename Allocator::reference reference;
> typedef typename Allocator::const_reference const_reference;
> // implementation defined iterator;
> // implementation defined const_iterator;
> typedef typename Allocator::size_type size_type;
> typedef typename Allocator::difference_type difference_type;
> typedef T value_type;
> typedef Allocator allocator_type;
> typedef typename Allocator::pointer pointer;
> typedef typename Allocator::const_pointer const_pointer;
> typedef std::reverse_iterator<iterator> reverse_iterator;
> typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
>
> // cdeque.cons_ construct/copy/destroy:
> explicit cdeque(const Allocator& = Allocator());
> explicit cdeque(size_type n);
> explicit cdeque(size_type n, const T& value, const Allocator& =
> Allocator());
> template <class InputIterator>
> cdeque(InputIterator first, InputIterator last, const Allocator& a =
> Allocator());
> cdeque(const cdeque<T,Allocator>& x);
> ~cdeque();
> cdeque<T,Allocator>& operator=(const cdeque<T,Allocator>& x);
> template <class InputIterator> void assign(InputIterator first,
> InputIterator last);
> void assign(size_type n, const T& u);
> allocator_type get_allocator() const;
> // iterators:
> iterator begin();
> const_iterator begin() const;
> iterator end();
> const_iterator end() const;
> reverse_iterator rbegin();
> const_reverse_iterator rbegin() const;
> reverse_iterator rend();
> const_reverse_iterator rend() const;
> // cdeque.capacity_ capacity:
> size_type size() const;
> size_type max_size() const;
> void resize(size_type sz);
> void resize(size_type sz, const T& value);
> size_type capacity() const;
> bool empty() const;
> void reserve(size_type n);
>
> // element access:
> reference operator[](size_type n);
> const_reference operator[](size_type n) const;
> const_reference at(size_type n) const;
> reference at(size_type n);
> reference front();
> const_reference front() const;
> reference back();
> const_reference back() const;
> // cdeque.modifiers_ modifiers:
> void push_front(const T& x);
> void push_back(const T& x);
> void pop_front();
> void pop_back();
> iterator insert(iterator position, const T& x);
> void insert(iterator position, size_type n, const T& x);
> template <class InputIterator>
> void insert(iterator position, InputIterator first, InputIterator last);
> iterator erase(iterator position);
> iterator erase(iterator first, iterator last);
> void swap(cdeque<T,Allocator>&);
> void clear();
> };
>
> template <class T, class Allocator>
> bool
> operator==(const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);
>
> template <class T, class Allocator>
> bool
> operator!=(const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);
>
> template <class T, class Allocator>
> bool
> operator< (const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);
>
> template <class T, class Allocator>
> bool
> operator> (const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);
>
> template <class T, class Allocator>
> bool
> operator>=(const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);
>
> template <class T, class Allocator>
> bool
> operator<=(const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);
>
> template <class T, class Allocator>
> void
> swap(cdeque<T,Allocator>& x, cdeque<T,Allocator>& y);
>
>
>


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk