Proposed container: cdeque

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2001-01-10 19:36:53

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