Re: [boost] Proposed container: cdeque

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