Boost logo

Boost :

From: wb_at_[hidden]
Date: 2001-01-11 10:18:19


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.

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

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


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