Boost logo

Boost :

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?


template <class T, class Allocator = std::allocator<T> >
class cdeque
        // 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& =
        template <class InputIterator>
                cdeque(InputIterator first, InputIterator last, const Allocator& a =
        cdeque(const cdeque<T,Allocator>& x);
        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>
operator==(const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);

template <class T, class Allocator>
operator!=(const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);

template <class T, class Allocator>
operator< (const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);

template <class T, class Allocator>
operator> (const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);

template <class T, class Allocator>
operator>=(const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);

template <class T, class Allocator>
operator<=(const cdeque<T,Allocator>& x, const cdeque<T,Allocator>& y);

template <class T, class Allocator>
swap(cdeque<T,Allocator>& x, cdeque<T,Allocator>& y);

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