In the first part of this series [ Goodliffe ] we started to look at how to implement a template container class in the style of the C++ standard template library (STL). The example container we're working with is a circular buffer. We started off by writing a minimal circular buffer class, and through a number of exercises refined this basic class until we had a mostly STL-like container class.
We're still not quite there yet. By the end of this article we'll have covered all the necessary ground, and our container class can truly be used like any other STL container.
As in the previous article, the approach adopted here is to present a number of exercises for you to perform. This is more than a clumsy article-writing device. Experience shows that you only really learn something when you try to actually do it. You can read around a subject as much as you like; it's only when you pick up tools and start applying what you've read, when the metaphorical rubber hits the hypothetical road, that you really solidify your knowledge. These exercises are then a good opportunity to learn in a practical way. Put as much effort into them as you want to get out of the article.
So where are we?
So far we have a template container class with forward and reverse iterators. Unlike traditional circular buffer implementations we've provided operator[] for random access; this is largely to provide the iterator's implementation.
You can download an example copy of the code this far from http://cthree.org/pete/cbuf.html .
More constructors
Amongst the functions that we still need to implement for our circular_buffer class are a number of constructors. As an analogue, think about vector. It has a several useful constructors. So off we go…
Exercise #1
What operations does a C++ compiler automatically generate for a class? How do you prevent this from happening?
The compiler will automatically generate
-
a default constructor, which just calls the default constructors for the class' members and bases,
-
a default copy constructor, which performs a member-wise copy of all data members, and
-
a default comparison operator, which performs a bitwise comparison of two objects.
Sometimes these defaults are fine and do just what we want. Often when creating more adventurous classes (with dynamically created data members) they're not at all suitable and we have to provide our own, or just prevent the compiler from emitting its defaults.
If we provide our own versions, the defaults are suppressed. This is of particular note for constructors - any constructor you provide, no matter what signature it has [ 1 ] , will suppress the parameterless default constructor. If you want to have a parameterless constructor you will then have to provide it, even if it does exactly what the compiler generated version would.
If you don't want to supply the operations but the compiler generated versions are wrong, you can suppress them by declaring the functions, but not defining them. For this to make any sort of sense, you should declare the functions as private members of the class.
Constructor 1: Copy constructor
A copy constructor allows us to 'clone' objects. It allows us to write:
// for some existent circular_buffer<int> // called cbuf; circular_buffer<int> copy_of_cbuf1(cbuf); circular_buffer<int> copy_of_cbuf2 = buf;
Both of these copies are created using the copy constructor.
Exercise #2
What signature does the copy constructor have? Will the default version suffice for circular_buffer ? If not, write an appropriate copy constructor.
We're storing data in a dynamically created array, so the default copy constructor is not appropriate. Consider what would happen if we wrote:
{
circular_buffer<int> cbuf1(100);
circular_buffer<int> cbuf2(cbuf1);
}
The default copy constructor will copy the array pointer, array_ . Now both circular buffer objects use the same array, which is plainly nonsensical. Things get worse, though. At the end of the block scope cbuf2 will first be destroyed. The destructor calls delete [] array_ . It is now an ex-array. Next the cbuf1 destructor is called. It will attempt to delete the same array which is now pushing up the daisies, a plainly wrong operation; and one that is potentially disastrous.
Our replacement copy constructor can look something like the following:
circular_buffer(const circular_buffer &other)
: array_(new value_type[other.array_size_]),
array_size_(other.array_size_),
head_(other.head_),
tail_(other.tail_),
contents_size_(other.contents_size_)
{
std::copy(other.begin(),
other.end(), array_);
}
Did you hand-roll your own loop for the copy operation? It pays to use standard library facilities where you can. This implementation works most of the time, but there are some lurking problems that we'll come back to later.
Constructor 2: Iterator-based template constructor
The vector class has a nice constructor that takes two forward iterators defining a range, as the initial contents of the container. Although not strictly required, we can have some of that goodness, too.
Exercise #3
Implement a constructor with the following signature:
template <class InputIterator> circular_buffer(InputIterator from, InputIterator to);
Here we'll have to consider what initial size our buffer should take. We could make this value an extra parameter, but that makes the interface less flexible and more lumpy. We could require that the supplied iterators are random access iterators and make some decision based on the value of to-from. Again, this requirement makes the code less flexible. Or we can try some other scheme.
It is possible to implement this constructor if we provide another function, reserve that ensures we have a specified capacity. The vector class has this capability. Whilst it makes a bit more sense as a member function of vector (since by definition vectors can grow), we can make good use of it here.
template <class InputIterator>
circular_buffer(InputIterator from, InputIterator to)
: array_(new value_type[100]),
array_size_(100),
head_(0),
tail_(0),
contents_size_(0)
{
while (from != to) {
if (contents_size_ == array_size_) {
reserve(static_cast<size_type>(array_size_ * 1.5)); // (*)
}
push_back(*from);
++from;
}
}
The initial capacity value has been picked arbitrarily. I'll leave the implementation of reserve up to you. The choice of multiplication factor at the point marked (*) is interesting - there has been plenty of research into this. For most situations the value of 1.5 is practical, balancing the number of reallocations required with the amount of 'wasted space' in the buffer.
Assignment operator
This differs from the copy constructor considerably, although you might think it is doing the same job. That's because the constructor has to correctly create and initialise an entire object, whilst the assignment operator has to deal with an already created object; in our case memory has already been allocated.
Exercise #4
What signature does an assignment operator have? Write the assignment operator for circular_buffer .
How did you do it? Be careful about the capacity of the buffer parameter passed and the capacity of the buffer you're assigning to. There are two ways to implement this function. You'll probably have written something like the following:
circular_buffer &operator=(const circular_buffer &other) {
clear();
// Ensure we have enough space
if (other.contents_size_ > array_size_) {
reserve(other.array_size_ );
}
// Now copy the contents across
std::copy(other.begin(), other.end(), array_);
head_ = 0;
tail_ = other.size();
contents_size_ = other.size();
}
We'll see the 'other way' later. This little function has the same lurking problem as the copy constructor. Can you see what it is?
Use an allocator
The STL containers all take an additional template parameter, the allocator. This class type abstracts the real concerns of allocating, using, and releasing memory. The default library std::allocator is implemented in terms of new and delete , however other platforms may provide different views of memory, be it pooled memory, garbage collected memory, or whatever. By using an abstract allocator interface we can avoid worrying about this sort of implementation detail and also gain the benefits of these kinds of facilities for free. Even if it weren't required, it would be worth it.
So how do we need to modify circular_buffer ? First we add another template parameter with a default value. It goes at the end of the template parameter list:
typename Alloc = std::allocator<T>
This requires us to include the <memory> header file, which defines this default std::allocator template class. Now we modify our list of container class typedefs , thus:
typedef Alloc allocator_type; typedef typename Alloc::value_type value_type; typedef typename Alloc::pointer pointer; typedef typename Alloc::const_pointer const_pointer; typedef typename Alloc::reference reference; typedef typename Alloc::const_reference const_reference; typedef typename Alloc::size_type size_type; typedef typename Alloc::difference_type difference_type;
Note we've added the allocator_type and we also modified these other definitions, since the allocator now provides us with all the correct definitions. Next, to work like any other STL container we add a data member alloc_ of the allocator type and, for consistency, we also add a new member function, thus:
allocator_type get_allocator() const {
return alloc_;
}
That's the basic stuff out of the way. Next we need to make the constructors and destructor call the allocator functions for their memory management, rather than new and delete. Given that the allocator class has the following functions, try exercise #5.
template <class T>
class std::allocator {
public:
typedef T *pointer;
typedef size_t size_type;
pointer allocate(size_type n, /*hint parameter*/);
void deallocate(pointer p, size_type n)
/* ... */
};
Note that the 'hint' parameter can be ignored for our purposes, it defaults to zero and is usually unused. allocate returns space for n objects of type T . It doesn't initialise them. deallocate frees the memory resource, but doesn't destroy the objects.
Exercise #5
Alter the constructor, destructor, and reserve to use the alloc_ member.
That's not too onerous really. However, we're beginning to see a hint of the problem I alluded to in exercise #1 of the first article, and this is the solution. The allocator does not initialise any objects in the memory pool in the way that an array would. This is crucial. Why? Well, it doesn't matter too much for a container of ints . But think about a complicated class with a slow constructor. Creating an array of these objects is therefore a very slow operation; an array initialisation will call the default constructor to create an object at each array position. It's especially wasteful when you consider that you'll ignore the default construction, and use assignment to write the first value you care about to each array element anyway.
That's an awful lot of wasted array effort. It also introduces an unnecessary dependency on the value_type : it requires that there must be a default constructor in order to be able to allocate the array. Now using this 'allocator' approach we are no longer bound by this constraint, on top of not wasting effort constructing useless objects. Bonus!
However, we will need to construct and destruct each object by hand instead. This is the price we pay. Given that there are the std::allocator member functions below, answer exercise #6:
void construct(pointer p, const T &val)
{ new (p) T(val); }
void destroy(pointer p)
{ p->~T(); }
Note the use of placement new by the construct function.
Exercise #6
What further circular_buffer member functions need to be changed to use construct and destroy ?
push_back is the only function that needs to create new data elements [ 2 ] . Rather than using assignment in this function, we call construct . However, we don't need to do this when the buffer is full and we're throwing away the data at the end of the buffer by reusing the last buffer element. In this case we only have to assign to the element as before. pop_front removes elements from the container, as do clear and the destructor (are there any others in your implementation?). These therefore need to use destroy . Note that it will no longer be valid to use the std::copy algorithm as we did before - it won't take care of the object construction for us.
As a final allocator modification, we must now change max_size . The allocator class provides this function itself. This is logical enough since it knows how many objects could potentially be allocated using its memory model. We therefore make our max_size call the allocator's.
Whistle-stop Tour of Exception Safety
This is a subtle subject that has to be approached very carefully. We don't have the time or space to do so in this article. So here's the nuts and bolts.
To be maximally useful our container classes need to be "exception safe." No one's going to argue there. But what does exception safe actually mean? This has been a hot topic in the C++ community for some time, and only really recently has it been understood to a reasonable depth.
Exception safe code works correctly no matter what exceptions come its way, for some definition of 'correctly' (we'll define this below). There is an additional constraint to consider when writing code like ours: exception neutral code propagates all exceptions up to its caller; it doesn't assume the meaning of any thrown exception and won't consume it. This is important for our 'generic' container - the contained objects may generate all sorts of exceptions that we don't understand. The container user will (well, should) understand them and it's therefore up to them to deal with these errors, not us. That's what exceptions are good for, after all.
Now there are several different useful levels of exception 'safety'. They are described in terms of guarantees to the calling code.
These guarantees are:
Basic guarantee : If exceptions do occur in a function (resulting from an operation we perform, or a call on one of our contained objects) we will not leak resources. The container state will be consistent (i.e. it can still be used correctly) but we'll not necessarily leave in a known state. For example, say you have a container member function that adds 10 items to a container, and an exception propagates through the function. We will guarantee the container is still usable, but maybe no objects were inserted, maybe all ten were, or perhaps every other object was added. Container iterators may have been invalidated.
Strong guarantee : This is far more strict than the basic guarantee. Here we ensure that if an exception propagates through our member functions the program state will remain completely unchanged. The object hasn't been altered, no global variables changed, nothing. All container iterators will therefore still be valid. In our example above, we can assert that no objects will have been inserted into the container at all.
Nothrow guarantee : The final guarantee is the most restrictive. We guarantee that an operation can never ever throw an exception. If we are 'exception neutral' then this implies that the function cannot call any function that itself might throw.
Which of the guarantees you provide in your code is entirely up to you. The more restrictive the guarantee, the more widely (re)useable the code is. It turns out that in order to implement the strong guarantee in your member functions you will generally require a number of functions that provide the nothrow guarantee (for example, see the use of swap in this article). Most notably every destructor you write should always honour the nothrow guarantee. Always. Otherwise all exception handling bets are off.
Exception safety
If our class is not exception safe, it's of no real value in the Real World. See the sidebar for a brief description of what's involved in writing exception safe code. We don't have the space here to really describe the subject, but we'll take a look at what we need to do to make our code bullet proof. As it stands it is really not at all exception safe. In fact it's downright exception dangerous.
In truth, it's a bit late in the development to be considering exception safety. However, we really needed to have got this far to have illustrations of the issues involved.
We'd like to provide at least the basic exception safety guarantee in our member functions, and ideally we want to aim to provide the strong guarantee in every method. Let's quickly look at some of the reasons why our existing container is dangerous. We'll start at the beginning: some constructors, for example, are a cause of resource leaks.
Look at the copy constructor. The first thing it does is allocate memory in the initialiser list. If this fails then a std::bad_alloc exception is thrown and nothing leaks. This is fine behaviour, and a good reason to put dynamically allocated memory near the head of your list of variables (remember that data members are initialised in the order of the class definition, not the order you list them in the constructor's initialiser list). None of the other assignments might throw, so we're safe in the rest of this initialiser list.
However, on entering the constructor body, we loop around copying elements. Any of the value_type object constructors might throw an exception. Say we get half way through the copy loop and a constructor fails. The failure exception propagates through our constructor (so at least we're exception neutral here), and we leak the allocated memory. We've also created a number of contained objects that we didn't destroy - heaven help us if there are dangerous side effects from this behaviour.
Tightening up cases like this is not actually going to be impossible to do, since I've introduced facilities in a way that allows exception safety (for example, separating front and pop_front ). We'll just have to think carefully about each member function. One of the golden rules when writing exception safe code is that each function should have at most one side effect, otherwise an exception safe implementation is complicated. You can see then that writing exception safe code does have an impact on your public API design, you have to design it in from the start.
When people think about exception safety they imagine code strewn with try/catch blocks. In fact this is far from the truth. Our exception safe code will be practically free of these. The basic technique we follow is to perform all potentially dangerous activities 'off to one side' in a way that means they'll get tidied up neatly if anything fails. Once these dangerous activities are complete we can then make the changes live using operations that are known not to throw.
In order to do this we are going to need some operations that are known not to throw. We asserted in the sidebar that our destructor can't throw. Now enter swap .
Exercise #7
Implement a member function swap(const circular_buffer &) that is guaranteed not to throw.
It's not too nasty. Note that we don't bother to swap the allocator objects. They should be identical if the circular_buffer types are the same.
void swap(circular_buffer &other)
/* nothrow */
{
std::swap(array_, other.array_);
std::swap(array_size_, other.array_size_);
std::swap(head_, other.head_);
std::swap(tail_, other.tail_);
std::swap(contents_size_, other.contents_size_);
}
Although we're providing the nothrow guarantee note that we don't put an empty exception specification at the end of the function signature. We should try to avoid writing these when we can, they can add unnecessary overhead to the running code; they are more likely to make the compiler generate much worse code than anything better. We know the function won't throw; we don't need the compiler to check this for us too.
Exercise #8
Using this perform work off to the side then make it live idiom, go over each member function and modify it to become exception safe (as strictly as possible). Do you need any try/catch blocks at all? Look first at the simplest constructor, then the push_back and pop_front methods.
OK, that's a big task. Let's start with the basic constructor. It's actually already strongly exception safe. The only operation that might throw is the memory allocation. This is fine, the std::bad_alloc exception will propagate up and we won't leak at all. How must you alter the other constructors? I won't show you here, but note that you will actually need try/catch blocks in this case. Next, push_back :
void push_back(const value_type &item) {
size_type next = next_tail();
// no state change yet
if (contents_size_ == array_size) {
array_[next] = item; // (*)
increment_head();
}
else {
alloc_.construct(array_ + next, item); // (*)
}
increment_tail();
}
private:
size_type next_tail() {
return (tail_+1 == array_size_) ? 0 : tail_+1;
}
How is this different? Our interest is at the points marked (*). We move the constructions/assignments to positions above any other state manipulation. If an exception is thrown we haven't modified any other state. This is not quite a strong exception safety guarantee, though: our container is now as exception safe as the value_type 's constructor/assignment operators. This is best we can do.
As a final example, we'll consider the assignment operator. We use a neat idiom here to ensure that we are strongly exception safe:
circular_buffer &operator=(const self_type &other) {
circular_buffer tmp(other);
swap(tmp);
return *this;
}
Can you see how neat this is? We do all the work 'off to one side' by creating a temporary object that looks like other . If that fails (based on the fact the copy constructor is exception safe and won't leak) we will propagate the exception, but not have altered our own state and not leaked, so we are strongly exception safe. If it succeeds we 'make permanent' the change using two operations that are known not to fail: swap , and the destructor. We swap our current state with that of tmp so we now look as if we've been 'assigned to'. When tmp goes out of scope it is destroyed, taking with it our old state.
A lot of the other functions are adjusted in similar manners. We don't have space to describe them all here. See my reference code (in the Getting the code section below) for further examples.
The long and short of exception safety is: you can't reasonably bolt it on after writing the code. You have to factor it into the class' design from the start. Well written exception safe code shouldn't need tonnes of try/catch blocks. If it's not simple and clear to read then something's wrong. Generally you'll find that good 'exception safe' code is not just designed to be safe in the presence of potential exceptions at the expense of clarity and program efficiency - it will also be genuinely well designed and thought out code.
Miscellany
There are still a few loose ends we need to tie up, and then we're done.
Insertion behaviour policy
Currently push_back will always accept new data, even if the circular buffer is full. It does this by throwing away the oldest data members. Perhaps our users don't want this behaviour.
Exercise #9
Make this policy decision a template parameter. How much of the class needs to change?
It turns out that this is a simple change, and costs very little. Just add a new boolean template parameter (I called it the long winded always_accept_data_when_full and gave it a default value of true ). You want to put this parameter before the allocator definition to follow convention.
The only other change needed is minimal: You need to make the 'throw data away' operation in push_back conditional on the value of always_accept_data_when_full . If it's false we do nothing. Since this value is known at compile time, the if statement will be optimised away.
Perhaps you'd like the function to throw an exception if the buffer is full. That's another policy decision, and I'll leave it up to you to work out how to do it.
This should lead us to consider how you would use a circular buffer in the Real World. You will know the rate at which a producer adds data to the buffer, and the rate and frequency at which the consumer will work. Given this information you should be able to calculate a reasonable size for the circular buffer. Obviously throwing away data is really a last-ditch operation, and your use of the buffer should prevent it if at all possible, so use the buffer carefully!
A random access iterator
We wrote a bidirectional iterator in the previous article. It's not much work at all to make it a random access iterator, we just need to add the following operations: + - += -= , plus the following comparisons: < > >= <= . Some of these we'd already started on.
Exercise #10
Convert the circular_buffer_iterator into a random access iterator.
Don't forget to change the iterator_tag .
Comparison
It would be useful to be able to compare two circular_buffer classes.
Exercise #11
Implement operator== and operator!= . They only need to compare two circular_buffers of the same type. Should they be member functions or free functions?
There is no requirement for these functions to be members of the container class, so by conventional C++ wisdom they shouldn't be. If your implementation required access to the private members of the class then you introduced unnecessary coupling. There are two ways to implement the functions: the easy way and the hard way. If you hand coded a comparison loop then you did it the hard way. You can avoid a lot of the work by using std::equal .
template <typename A, bool B, typename C>
bool operator==(const circular_buffer<A, B, C> &a,
const circular_buffer<A, B, C> &b) {
return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
}
You can figure out operator!= from that. There's one more operator that the vector provides, which we can also provide:
Exercise #12
Implement operator< for the circular_buffer class.
Again, there's an easy way and a hard way. This time the easy way uses std::lexicographical_compare .
template <typename A, bool B, typename C>
bool operator<(const circular_buffer<A, B, C> &a,
const circular_buffer<A, B, C> &b) {
return std::lexicographical_compare(a.begin(),
a.end(),
b.begin(),
b.end());
}
Getting the code
Whilst I know you've been slavishly following the exercises I know that you'll want to see my reference implementation to see how close you came to it. Or perhaps you just want an STL style circular buffer class and can't be bothered to write your own.
My circular_buffer class library is available from http://cthree.org/pete/cbuf.html .
Conclusion
We've now created an entire template container class. It follows the STL style carefully. Not only does this mean that we now know how to write STL-like containers, it also means that anyone using this circular_buffer class can pick it up with a minimum of hassle. It behaves in a known way, can be accessed as most other STL containers, and it is immediately compatible with existing STL algorithms. Perhaps you've also gained a respect for the work that has been put into the standard C++ libraries.
Hopefully you've enjoyed these articles, and by stepping through the exercises you have now picked up some useful techniques that can be applied to other code you write. Let me know if it's been useful.
Exercise #13
Take a well deserved break.
References
[Goodliffe] Pete Goodliffe, "STL-style circular buffers by example," Overload 50, August 2002, ISSN: 1354-3172.
[ 1 ] Actually, modulo any tempate constructors.
[ 2 ] That is, if you implement the new constructors and assignment operator in terms of push_back, which is a very reasonable design.
