Version 1.01 - 4/16/96
by Evelio Perez-Albuerne
The documentation is modeled after the documentation of STL classes in the book "C++ Programmer's Guide to the Standard Template Library" by Mark Nelson.
In addition to documenting the public interface of the container, I've included sections on implementation details. You could skip these completely and still use the container without trouble, but they may give you a better idea of the costs (both memory and time) associated with various operations.
New in this version: All sections contain at least a brief comment (those annoying [*] symbols are gone).
ring<T> is an STL-compatable container template. The ring<T> container has the logical structure of a deque with a fixed (but changable) maximum length. The following table compares the time required for various operations on a C array, existing STL containers and ring<T>. linear indicates that the time required for the operation is proportional to the number of items in the container.
| C array | vector<T> | deque<T> | list<T> | ring<T> | |
| Insert/erase at start | n/a | linear | constant | constant | constant |
| Insert/erase at end | n/a | constant | constant | constant | constant |
| Insert/erase in middle | n/a | linear | linear | constant | linear |
| Access first element | constant | constant | constant | constant | constant |
| Access last element | constant | constant | constant | constant | constant |
| Access middle element | constant | constant | constant | linear | constant |
| Overhead | none | low | medium | high | low |
A major difference between the other STL containers and ring<T> is that the ring<T> container does not expand automatically. Instead, when an element is added to a full ring<T>, another element is deleted. When an element is added to the back (using push_back) of a full container, the first element is deleted. When an element is added to the front (using push_front), the last element is deleted.
The code was written to work with the STL that comes with the
Borland C++ 5.0 compiler. This compiler supports namespaces but
not member templates. Define the RWSTD_NO_NAMESPACE
macro if your compiler does not have namespaces. This version
has no support for member templates, but I do plan on adding them.
Defining the RWSTD_NO_MEMBER_TEMPLATES macro will
supress member templates in that revision.
The actual implentation of the container borrows heavily
from vector<T> in the STL. As for STL containers, memory
allocation and construction of member objects are separated
by use of the construct function of the STL. The amount of
memory allocated to hold items is one greater than the
capacity of the container. If it were not, a full ring<T>
container would have begin() == end()
in violation of STL iterator behavior.
The key element (described more completely below) to making the container work is the definition of the iterators. You will see that many of the functions for the container seem to ignore the fact that it can wrap around. In fact, the iterators used within these functions are responsible for keeping track of that.
The ring<T> container has two nested classes which perform its iterator functions.
The iterator class implements a random access iterator (the most
powerful type of STL iterator) for the ring<T> container. In
addition to its constructor and destructor, it supports the following
operations:
reference operator*() const;
difference_type operator-(const iterator& x) const;
iterator& operator++(); (prefix)
iterator operator++(int); (postfix)
iterator& operator--(); (prefix)
iterator operator--(int); (postfix)
iterator& operator+=(difference_type n);
iterator& operator-=(difference_type n);
iterator operator+(difference_type rhs) const;
iterator operator-(difference_type rhs) const;
reference operator[](difference_type n);
bool operator==(const iterator& x) const;
bool operator<(const iterator& x) const;
The key functions in the implementation are:
difference_type operator-(const iterator& x)
const;
iterator& operator+=(difference_type n);
The definition of operator+ and operator-
in terms of
operator+= and operator-=
was suggested by Scott Meyers in Item 22 of "More Effective C++".
It let me put all the code that does real work
in operator+=
and make operator-=, operator+
and operator- one-liners.
The const_iterator class supports C++ const functions and is nearly identical to the iterator class except that:
Like STL containers, ring<T> uses standard
type definitions to
support a uniform interface. Some of these types (like iterator
and const_iterator) had to be custom-built, but others can be
reused from STL components:
typedef Allocator<T> ring_allocator;
typedef T value_type;
typedef ring_allocator::pointer pointer;
typedef ring_allocator::reference reference;
typedef ring_allocator::const_reference const_reference;
typedef ring_allocator::size_type size_type;
typedef ring_allocator::difference_type difference_type;
typedef reverse_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, reference,
difference_type> reverse_iterator;
One new type was created for use in the iterator classes:
typedef ring<T>* ring_pointer;
ring_allocator serves as an alias for the underlying allocator class. This makes the code for the rest of the ring<T> class easier to write.
value_type is a synonym for type T.
The definition of pointer is borrowed from the underlying allocator class. In most cases, It will be a T*.
Also borrowed from the underlying allocator class. It will usually be T&.
Identical to reference, except it refers to a const object.
size_type defines the size of largest number that can be passed to allocate raw storage. It varies depending on the programming environment (32-bit or 16-bit) and in 16-bit programs, on the memory model.
This type is defined by the underlying allocator to hold the difference between two pointers.
This template creates a new iterator (an is an example of an iterator adaptor). The reverse_iterator can be used to step though a container in reverse order. The constant version is used when reverse stepping with a const_iterator is desired.
This typedef was added to make some of the iterator code easier to read. ring_pointer is used as a synonym for ring<T>*.
pointer start_of_storage;
pointer end_of_storage;
iterator start;
iterator finish;
A private data member that points to the start of the raw storage block of (capacity() + 1) T objects. Has a value of 0 if no memory has been allocated.
A private data member that points to one past the end of the the raw storage block of (capacity() + 1) T objects.
A private data member that points to the first logical item in the ring container. That item may be anywhere in the raw storage area.
A private data member that points to the one past the last logical item in the ring container. That item may be anywhere in the raw storage area. Because (capacity() + 1) spaces are allocated in raw storage, this item will never point to a constructed T item, even in a full container.
ring();
ring(size_type n);
ring(const ring<T>& x);
ring(const_iterator first, const_iterator last);
~ring();
ring<T>& operator=(const ring<T>& x);
The default constructor creates a ring with no raw storage allocated and a size of 0. Since ring<T> does not automatically expand, the size can only be changed by a resize function call. It is an error to call any of the modifier functions (see below) except for swap or erase(begin(), end()) on this type of ring.
This constructor makes an empty ring<T> which can hold a maximum of n objects. If more objects are added when the container is full, objects already in the container will be deleted.
This copy constructor creates a ring<T> that has the same capacity as x. It also contains copies of all the members of x (using the copy constructor for object T). Note that the new ring will have the same amount of available space as the old ring.
This constructor creates a ring<T> which is exactly large enought to hold copies of the objects from first to one before last. Note that this means ring<T>s created with this constructor always start out full.
The destructor destroys all of the members and then deallocates the raw storage for the container.
The assignment operator works in a way very similar to the copy constructor. The objects held in the container before the assignment are deleted. The containers size is adjusted to match that of x.
These member functions return iterator types which allow the
user to step through and manipulate items in the container.
Most come in const and non-const versions to allow for use with
const and non-const ring<T> containers.
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;
This function returns an iterator that points to the first object in the container. If it has the value 0, then no storage has been allocated for use in the container. If it has a value equal to end() (see below), then storage has been allocated but the container does not contain any items. In either of these cases, the iterator should not be dereferenced.
This function returns an iterator that can be tested against
to see if the end of the container has been reached. It returns
the value 0 if no storage has been allocated. Equality with
this iterator means that the entire container has been traversed.
Because both this function and begin() return 0 if no storage
has been allocated, begin() == end() is true
in this case as well, allowing the usual end of traversal
comparison.
These functions return reverse iterators.
A reverse_iterator<T> allows for reverse traversal of a
container with a minimum of effort. Instead of:
for (ring<T>::iterator i = r.begin(); i != r.end(); ++i)
the construct is
for (ring<T>::reverse_iterator ri = r.rbegin();
ri != rend(); ++ri)
Returns an iterator which indicates end of traversal for a reverse iterator.
size_type size() const;
size_type max_size() const;
size_type capacity() const;
bool empty() const;
bool full() const;
size_type ring_size() const; // protected
void resize(size_type n)
With the exception of resize, these member functions report on the state of the container.
Returns the number of items currently in the container.
This is a function defined by the allocator that reports on the maximum number of elements that could fit into the largest possible ring<T>. This function does not take into account real limitations on memory.
This gives the current capacity of the ring<T>. Since ring<T> does not expand automatically, this is an actual limit on the number of items that can be stored in the container. If you try to insert elements when the container is full, some of the existing elements will be deleted.
Returns true if the ring<T> has no members, false otherwise.
Since ring<T> does not automatically expand, it can become full. This function returns true if the container is full, false if more elements can be added without deleting any of the current members.
This protected function is added to simplify programming of other functions. It returns the raw storage allocated in the ring<T>. Except for zero-size rings, ring_size is always one greater than capacity.
This function changes the size of the ring<T> to exactly n. It can be used to make the ring<T> larger or smaller. If the new capacity of the container is equal or greater than the number of items in the container, all items are still present. If the new size is smaller than the number of items formerly in the container, the first n items are retained, and the rest are deleted. Calling this function invalidates any iterators for the container, unless n is equal to the current size.
These functions provide access to the contents
of the container.
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
These functions provide random access to the contents of the container. Like the operator[] for C arrays, they do not check that the supplied index is in range.
These functions return a reference and a const_reference to the first item in the container.
These functions return a reference and a const_reference to the last item in the container.
These functions can add or remove items from the container.
Because of this, they may change the location of data inside
the container. When these functions are called, existing iterators
may become invalid. It is an error to call any of these functions
(except for swap or erase(begin(), end()) on a zero-size ring.
void push_back(const T& x);
void push_front(const T& x);
void swap(ring<T>& x);
iterator insert_forward(iterator position, const T& x);
iterator insert_backward(iterator position, const T& x);
void insert_forward(iterator position, const_iterator first,
const_iterator last);
void insert_backward(iterator position, const_iterator first,
const_iterator last);
void insert_forward(iterator position, size_type n, const T& x);
void insert_backward(iterator position, size_type n, const T& x);
void pop_back();
void pop_front();
void erase(iterator position);
void erase(iterator first, iterator last);
This function adds an item to the end of the container. If the container is full, the first item in the container is deleted.
This function will destroy the last item in the container. No attempt is made to check if the container contains at least one item. If this function is called on an empty ring<T> the results are undefined.
This function adds an item to the start of the container. If the container is full, the last item in the container is deleted.
This function will destroy the first item in the container. No attempt is made to check if the container contains at least one item. If this function is called on an empty ring<T> the results are undefined.
This function exchanges the contents of two ring<T> containers. It invalidates all iterators for both containers.
These functions insert items into the middle of the container.
The first version inserts a single item just before the item
pointed to by the iterator position. The second version inserts
a range of items just before the item pointed to by position while
the third version inserts n copies of an item in the same place.
If the size after insertion exceeds the capacity of the ring<T>,
these functions will first delete items from the back of the
container (the items after the insert point are pushed
forward). Once all items after the insertion point
are deleted, items will be deleted from the front of the container.
Finally, if the number of elements inserted exceeds the capacity
of the container, all existing members will be deleted and the
first capacity() items from the insertion range
will be copied to ring<T>.
These functions insert items into the middle of the container.
The first version inserts a single item just before the item
pointed to by the iterator position. The second version inserts
a range of items just before the item pointed to by position while
the third version inserts n copies of an item in the same place.
If the size after insertion exceeds the capacity of the ring<T>,
these functions will first delete items from the front of the
container (the items before the insert point are pushed
backward). Once all items before the insertion point
are deleted, items will be deleted from the back of the container.
Finally, if the number of elements inserted exceeds the capacity
of the container, all existing members will be deleted and the
first capacity() items from the insertion range
will be copied to ring<T>.
The first function deletes a single item and the second a range of items in the ring<T>. When items are deleted, the remaining items are moved up to fill in the gap created. These function take linear time (based on the size of the container) to execute.
These functions compare the contents of two ring<T>
containers.
bool operator==(const ring<T>& x, const ring<T>& y);
bool operator<(const ring<T>& x, const ring<T>& y);
This function tests whether two ring<T> are equal. First the capacities and sizes are compared. If either differ between the two containers, the function returns false. Then an item-by-item comparision is performed on the members of each container. If all are equal, the function returns true, otherwise it returns false.
This function performs a lexicographical comparison between the members of the two containers using the STL algorithm lexicographical_compare().
Back up to C++ page.
Back up to the Computer page.
[Home] [Comp] [SF] [Med/Bio] [Other Sci] [Personal]
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation. I make no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.
