Re: [boost] Proposed container: cdeque

From: Greg Colvin (greg_at_[hidden])
Date: 2001-01-11 11:53:33

From: <wb_at_[hidden]>
> When I taught undergraduate computer science, we routinely exposed our
> sophomores (in the context of a data structures course, typically) to
> the notion of a "bounded" linear container.  This encompassed stacks
> and queues as well as the more general deque, and was based on the
> observation that there are applications that can reliably predict a
> maximum-usage (typically, worst-case) scenario for such a structure and
> hence rarely, if ever, need to adjust memory usage during the
> structure's lifetime.
> 
> Internally, such containers typically exhibited the "wraparound" or
> "circular" usage pattern described below.
> 
> I have long believed that a family of bounded linear containers would
> be a useful complement to the unbounded linear containers now provided
> in the C++ library.  Therefore, I strongly favor this proposal, and
> respectfully recommend that the name "bounded" be applied to identify
> them:
> 
> bounded_deque<myType>  myDeque( MAX_NEEDED );
> bounded_queue<myType>  myQueue( MAX_NEEDED );
> bounded_stack<myType>  myStack( MAX_NEEDED );
>         // ...
> myQueue.reserve( NEW_BOUND );  // if needed
> 
> I prefer "bounded" to either "circular" or "wraparound" because it
> describes the external behavior; the other terms better describe some
> implementation details, knowledge of which would not materially help an
> average user.
> 
> At issue, perhaps, are such containers' behavior at the bound (i.e.,
> when "full").  There appear to be several useful possibilities:
> 
>   1)  Let the containers (silently) grow beyond the stated bound as
>       needed.  This mimics the unbounded containers' behavior.

This is what Howard's proposed container does, so it isn't unbounded.
But you are right that the "circularity" is an implementation detail.
For Howard's cdeque the "c" might as well stand for contiguous.

>   2)  Throw an exception under the theory that the user has violated
>       his own bounds specification and it is useful to be so notified.

And this would be an actually bounded container.

>   3)  Let the policy (e.g., (1) or (2) above) be specified by the user
>       via a member function or template argument or ....
> 
> My own preference is for policy (2).  I have two primary reasons for
> this recommendation.  First, I believe it leads to constant (not
> amortized constant) time complexity for all the insertion, deletion,
> and access functions, a most useful guarantee.  Second, I believe this
> behavior will delineate most clearly, for potential users, the
> distinction between these containers and the corresponding standard
> (unbounded) versions.
> 
> - WEB
> 
> 
> Howard Hinnant <hinnant_at_[hidden]> wrote on Wed Jan 10 18:36:53 2001:
> 
> | 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);
> 
> 
>